Удаление необработанных указателей из std::vector
У меня есть следующий шаблон:
- У меня есть
std::vector, содержащий необработанные указатели на объекты (я знаю, что необработанные указатели - это "зло", но это устаревшее программное обеспечение, которое необходимо поддерживать). - Теперь для каждого элемента в векторе мне нужно сделать тест, и если тест положительный, сделайте что-нибудь с указателем, удалите его, а затем удалите из вектора:
Псевдокод:
for each pointer in vector
{
if (SomeTest(pointer))
{
DoSomething(pointer)
delete pointer
remove pointer from vector
}
}
Я не могу придумать хороший чистый код для этого.
Эта ссылка предлагает разные подходы, но все они кажутся мне более или менее громоздкими.
Громоздкое решение, которое я использую сейчас:
for(auto & p : v)
{
if (SomeTest(p))
{
DoSomething(p);
delete p;
p = nullptr;
}
}
v.erase(std::remove(v.begin(), v.end(), nullptr), v.end());
Единственная проблема, о которой я могу думать, - это сделать итератор недействительным и испортить ваш цикл, который не будет иметь ничего общего с указателем. Возможно, вы могли бы опубликовать минимальный воспроизводимый пример. (рассмотрите std::remove_if ?)
Что конкретно не так с erase_if?
@user463035818 user463035818 Излишне говорить, что deleteing необработанные указатели имеет смысл только в крайнем случае владения необработанными указателями. Утверждение в вопросе явно не приписывает владение указателям, поэтому вы технически правы, чтобы придираться.
@MaxLanghof, если вектор отвечает за них delete, то я бы сказал, что вектор ими владеет. Во всяком случае, я специально имел в виду «я знаю, что необработанные указатели — это зло», и я немного придирчив, когда что-то получает атрибут «зло». Слишком легко это может привести к непониманию
@MaxLanghof в моем случае вектор является, владеющий указателями.
Обновление @NathanOliver для использования правильной механики было бы довольно долгим, но да, это определенно было бы лучшим решением. Я могу использовать С++17.
@Jabberwocky Это была моя точка зрения. Вы не написали это черным по белому рядом с частью «злые указатели», поэтому технически придирка этого парня оправдана, но я хотел указать, что очевидно, что их придирка здесь не применима.
Ответы 7
Как часто ответ: знай свои <algorithm> (и это хорошее напоминание самому себе) ;)
std::partition - это то, что вам нужно: std::partition(begin, end, p) "перемещает" элементы диапазона [begin, end), не надо которых удовлетворяет предикату p в конце диапазона; затем вы можете рассматривать их как партию.
auto const to_be_removed = std::partition(begin(v), end(v), [](auto p){ /* predicate */ });
std::for_each(to_be_removed, end(v), [](auto p) {
/* crunch */
delete p;
});
v.erase(to_be_removed, end(v));
Полная программа
#include <iostream>
#include <algorithm>
#include <vector>
int main()
{
std::vector v = { new int{0}, new int{1}, new int{2} };
// let's delete all even values
auto const to_be_removed = std::partition(begin(v), end(v), [](auto p){ return *p % 2 != 0; });
std::for_each(to_be_removed, end(v), [](auto p) {
std::cout << "Deleting value " << *p << "...\n";
delete p;
});
v.erase(to_be_removed, end(v));
}
Чтобы пойти дальше
У этой реализации есть два основных недостатка: порядок из вектора нестабилен (1), его можно было бы преобразовать в повторно используемую функцию (2).
- (1) решается
std::stable_partition. - (2) не так сложно:
template<class InputIt, class UnaryPredicate, class UnaryDeleter>
InputIt delete_if (InputIt begin, InputIt end, UnaryPredicate p, UnaryDeleter d)
{
auto const to_be_removed = std::stable_partition(begin, end, std::not_fn(p));
std::for_each(to_be_removed, end, [d](auto p) { d(p) ; delete p; });
return to_be_removed;
}
template<class Container, class UnaryPredicate, class UnaryDeleter>
auto delete_if (Container& c, UnaryPredicate p, UnaryDeleter d)
{
using std::begin, std::end;
return c.erase(delete_if (begin(c), end(c), p, d), end(c));
}
использование:
delete_if (v, SomeTest, DoSomething);
Кроме того, delete p должен обрабатываться UnaryDeleter, иначе его можно использовать только для динамических указателей.
Я не согласен с этим пунктом; я полагаю, что мы решаем конкретную проблему OP: «для каждого элемента в векторе мне нужно сделать тест, и если тест положительный, сделайте что-нибудь с [необработанным] указателем, удалите его, а затем удалите из вектора». У них нет причин не помещать оператор delete в функцию delete_if.
Предположим, у вас есть вектор указателя int. Вот мое решение:
vector<int*> vpi;
for (vector<int*>::iterator it = vpi.begin(); it != vpi.end(); )
{
if (SomeTest(*it))
{
DoSomething(*it)
int* old = *it;
it = vpi.erase(it);
delete old;
} else
{
it++;
}
}
не уверен, но, насколько я понял, это код, который OP хотел бы избежать написания.
@LocTran Я обычно делаю it = vector.erase(it) .. не так хорошо, как твой старый, новый :)
Зачем использовать old? DoSomething(*it) delete *it; it = vpi.erase(it); делает то же самое.
@NathanOliver приятно знать, что кто-то еще делает то же самое
если вы удалите *it, исходный указатель потеряется или нет (не определено). Лучший способ сохранить старый указатель
Это решение O (N ^ 2) (подумайте об элементах, которые нужно переместить, когда вы стираете в середине). Вместо этого используйте std::partition, а затем один erase.
@LocTran Что ты имеешь в виду под исходный указатель потеряет или нет (не определено)? Если вы уберете элемент из вектора сразу после того, как проблем не возникнет. Наличие old не делает операцию безопаснее. Это только загромождает код.
Не сильно отличается от того, что вы делаете. Что это дает в миксе? Многопоточность не безопаснее, и это единственная причина, по которой у вас может быть это временно.
@rustyx, я не думаю, что это решение O (N ^ 2). Оно включено). Почему О(N^2)? могли бы вы объяснить?
Рассмотрим вектор из 1000 элементов, из которых нужно удалить первые 100. Сколько раз оставшийся элемент нужно будет переместить внутри вектора (около 95000).
@rustyx хорошо знать std::partition. впервые вижу эту функцию
Некоторый подход, который я бы использовал:
for (auto i = vector.begin(); i != vector.end(); ++i) {
if (SomeTest(*i)) {
DoSomething(*i);
delete *i;
*i = nullptr;
}
}
vector.erase(std::remove(vector.begin(), vector.end(), nullptr), vector.end());
Это более или менее то, что я делаю сейчас
@UmNyobe Что плохого в использовании nullptr в качестве магического значения?
@Galik, возможно, вектор действительно содержит nullptr, и, возможно, SomeTest возвращает false для nullptr.
Самое простое решение — начиная со статьи по ссылке — взять функцию erase_if.
template <typename Container, typename Pred>
void erase_if (Container &c, Pred p)
{
c.erase(std::remove_if (std::begin(c), std::end(c), p), std::end(c));
}
и просто позвоните с
erase_if (v, [](T *pointer)
{
if (SomeTest(pointer))
{
DoSomething(pointer);
delete pointer;
return true; //remove pointer from vector
}
return false;
});
Очевидно, вы можете разделить свой предикат на две части, если хотите отделить часть SomeTest/DoSomething от части delete:
template <typename Container, typename Pred>
void delete_if (Container &c, Pred p)
{
auto e = std::remove_if (std::begin(c), std::end(c),
[&p](Container::value_type *pointer)
{
if (p(pointer)) {
delete pointer;
return true;
}
return false;
});
c.erase(e, std::end(c));
}
Поскольку вы не сказали Зачем, что вам не нравится erase_if, который вы сами связали, я не могу предположить, имеет ли он ту же проблему.
С этим подходом есть проблема: std::erase_if (...) эквивалентен v.erase(std::remove_if (...)), в котором явно указывает соответствует предикату не должен изменять элемент.
@You Технически это не изменяет элемент, но я думаю, смысл в том, что p должен быть идемпотентным (вызываемым много раз без вреда), и это, конечно, не так в этом случае, поскольку следующий вызов удаленного указателя, вероятно, будет иметь УБ.
Честная оценка. (Я полагаю, что точная формулировка такова: «[предикат] не должен применять какую-либо неконстантную функцию через разыменованный итератор», чего deleteing технически не делает, я думаю, поскольку это нормально для delete как постоянный указатель.)
@ArneVogel Стандарт гарантирует, что предикат будет вызываться только один раз для каждого элемента.
Я предполагаю, что вы выводите это из (алг.удалить/5) - ИМО, это все еще немного технический вопрос. Если бы я делал обзор кода, я бы предложил переключиться на partition/stable_partition или написать осмысленный комментарий, почему это правильно.
Вы можете использовать std::remove_if. Я не уверен, почему в статье, на которую вы ссылаетесь, используется std::remove_ifдо, удаляющий указатели, потому что это не сработает. Вы должны Удалить указатели до удалить:
std::vector<int*> v;
v.erase(std::remove_if (std::begin(v), std::end(v), [](int* p){
// do your test and do not remove on failure
if (!SomeTest(p))
return false; // keep this one
DoSomething(p);
// Now we remove but be sure to delete here, before the
// element is moved (and therefore invalidated)
delete p;
return true; // signal for removal
}), std::end(v));
Примечания: Почему это безопасно.
Удаление указателя изменяет не сам указатель, а объект, на который он указывает. Это означает, что при таком подходе никакие элементы не изменяются.
Стандарт C++17 28.6.8 5 гарантирует, что предикат будет вызываться только один раз для каждого элемента.
Отвечая на ваш комментарий, да: это хорошая идея для этого конкретного случая. (+1)
При следующем подходе сначала вы разделяете элементы, которые нужно удалить, затем удаляете, а затем корректируете вектор.
auto badIt = std::stable_partition(std::beging(v), std::end(v), SomeTestInverse);
std::for_each(badIt, std::end(v), [](auto e){ DoSomething(e); delete e;});
v.erase(badIt,std::end(v));
Предоставленный предикат должен быть истинным, чтобы элемент оставался, чтобы работать, поскольку элементы, не соответствующие предикату, находятся в последнем диапазоне.
Будь проще. ЯГНИ. Нет причин решать более общую и сложную версию проблемы, если она вам понадобится (подсказка: вам не понадобится) или искать непонятные методы STL (ну, если вы не желание).
size_t target = 0;
for (size_t idx = 0; idx < v.size(); idx++) {
if (should_delete(v[idx]))
delete v[idx];
else
v[target++] = v[idx];
}
v.resize(target);
<algorithm> не является связкой "непонятные методы STL". Изучите их, используйте их. Они создают легко читаемый, простой в обслуживании и легко оптимизируемый код.
Конечно, «простота» — это в глазах смотрящего, но я видел слишком много кода с несколькими уровнями шаблонного наследования, который можно было бы написать с помощью простого цикла for или оператора switch, только если бы программист сопротивлялся желанию обобщить все до максимума. Если кому-то std::for_each с лямбдами покажется проще, чем for, то это на их вкус: но сомневаюсь, что будет быстрее.
...Легко ли нет в глазах смотрящего? Я рад, что вы согласны с тем, что петля for объективно лучше! :P Шутки в сторону, цикл forбыл - идиома C++, поскольку он назывался "C с классами", и в отличие от строк в стиле C, он никуда не денется. Сам Страуструп предостерег от «попыток писать на C++, как если бы это были $(другие языки)» в своем «Языке программирования C++» (2-е изд.): я не уверен, изменил ли он свою позицию позже, но C++ не совсем функциональный язык. , и пытаясь написать C++ так, как будто это легко может привести к слишком сложному беспорядку.
Вероятно, нет никакого вреда в замене одного цикла for на for_each, но глупо утверждать, что последний объективно лучше только потому, что он новый. В C++ нет недостатка в функциях, которые кричат: «То, что вы используете может здесь, не обязательно означает, что это хорошая идея».
for_each часто является плохой заменой старой доброй петли for, с этим я полностью согласен. я говорю обо всех остальных 103 алгоритмах.
извините, придирка: необработанные указатели на объекты, принадлежащие кому-то другому, довольно безвредны. Только обладание необработанными указателями является злом