[C++] STL, vector

[The Nameless One]

Привет)
Удаление элемента из середины вектора - это правильно, можно так делать?

К примеру, в цикле просматриваются все элементы вектора, при выполнении определенного условия, текущий элементы удаляется:

Код:

vector <just> v;
vector <just>::iterator it=v.begin();
while(it!=v.end())
{ 
   it->foo();
   if(it->a) it=v.erase(it);
   else it++;
}

Добавление элементов происходит вне цикла.

Так нормально поступать? Или будет постоянное перераспределение памяти?
Нужно достичь как можно меньшей нагрузки на процессор.

Заранее благодарен за ответы.

[Антон (LogRus)]

перераспределения не будет, но вот копирование больших кусков данных будет
т.е. когда ты удаляешь элемент все элементы после него будут смещены на 1 элемент влево.

кроме того, erase вызывает инвалидацию итераторов, как следствие цикл надо запускать сначала
посмотри в сторону алгоритма remove_if
не забываем, что remove_if не удаляет хвост контейнера поэтому
делаем такд

Код:

bool check_just(just & j)
{
  j.foo();
  return j.a;
}

v.erase(std::remove_if(v.begin(), v.end(), check_just), v.end());

[The Nameless One]

Спасибо, посмотрю.

Насчёт инвалидации итераторов после erase, а разве erase() не возвращает итератор, следующий за удалённым? Именно потому делал it=v.erase(it), а не просто v.erase(it) ?

[Вад]

Насчёт инвалидации итераторов после erase, а разве erase() не возвращает итератор, следующий за удалённым?

И это будет единственный валидный итератор, указывающий на элементы, следующие за удалённым. То есть, в общем случае уже нельзя полагаться на любые другие ранее полученные итераторы для данного вектора, поскольку сдвиг данных приводит к тому, что они могут указывать совсем не туда, куда должны бы.

Что касается цикла - не совсем согласен с LogRus: поскольку полученный итератор будет корректным, можно продолжать удаление с него. Только потери производительности будут существенными, поскольку каждое удаление одного элемента будет приводить к перемещению в среднем size/2 элементов ближе к началу буфера. То есть, сложность получается в худшем случае квадратичная.

[Вад]

Кстати, remove_if поступает более хитро и за счёт этого экономит время: он не удаляет элементы по одному, а просто копирует вектор сам в себя, пропуская элементы, которые должны быть удалены. В результате, сложность алгоритма линейная по копированию, а в конце вектора оказываются не удалённые элементы, а те, которые там были до копирования в себя.

[The Nameless One]

А если перед удалением менять местами последний и удаляемый, а после этого удалять?

Если текущий элемент не последний, то
temp=v.back();
v.back()=it;
it=temp;
v.erase(v.back());

Как-то так можно делать? Насчёт back() не уверенн, вроде она возращает ссылку на последний элемент.


P.S. Думаю, можно адреса менять местами, а не сами объекты -  *v.back()=*it;

[Вад]

А зачем так усложнять, если erase-remove_if хорошо справляется с задачей?

Тем более, что v.back() = *it - лишнее, ведь ты следующим действием удаляешь его. И ещё: back возвращает не итератор, а прямую ссылку, поэтому присваивать её итератору не получится.

Если же очень не хочется писать предикат для remove_if, то, по крайней мере, можно же взять и посмотреть, как сама remove_if работает

The behavior of this function template is equivalent to:

Код:

template < class ForwardIterator, class Predicate >
  ForwardIterator remove_if ( ForwardIterator first, ForwardIterator last,
                              Predicate pred )
{
  ForwardIterator result = first;
  for ( ; first != last; ++first)
    if (!pred(*first)) *result++ = *first;
  return result;
}

[The Nameless One]

Думаю, что копирование целого вектора (кроме удаляемого) каждый раз при удалении - больно долго для моего случая.

Я решил, что будет быстрее ставить удаляемый элемент в конец вектора и только после этого его удалять, чтобы не было сдвигов влево и чтобы не было лишних копирований - поменять местами два элемента всегда быстрее, чем копировать вектор при удалении элемента методом remove_if - разве я не прав?
Вся для скорости.

[Джон]

Если тебе так важна скорость - сделай свой список, хранящий указатели на объекты и нужными ф-ми. Быстрей не бывает. А работы на полчаса.

В крайнем случае храни в векторе не сами объекты, а указатели на них. В этом случае объём премещаемых, копируемых и тд данных сократится до максимум N*размер указателя, где N - число элементов в векторе.

[Алексей++]

The Nameless One,  так всё равно же придётся по кольцу элементы двигать

[Джон]

зы Да даже просто добавь к своему типу just два поля:

just *m_pPrev;
just *m_pNext;

И уже можно делать список.

[Вад]

Алексей1153++, не придётся. Если не задаваться целью сохранять в векторе порядок при удалении.
The Nameless One, если очень хочется, и порядок в векторе не заботит - то да, так будет быстрее всего: поменять удаляемый элемент местами с последним и затем удалить последний элемент.

Только нельзя делать vec.erase(vec.back()), придётся делать resize или явно получать итератор на последний элемент (vec.end() -1)

[The Nameless One]

Всем большое спасибо!
Да, порядок векторе не важен. В том числе поэтому и не хотелось связываться с предикатами.

[Антон (LogRus)]

The Nameless One, а зачем вектор кстати?
почему не дек или лист?

[The Nameless One]

До list я ещё не дошёл просто

[Джон]

The Nameless One, тебе бы лучше со своих списков начать. С теории. Полезней будет и для понимания STL.

[The Nameless One]

Джон, спасибо, так и сделаю))

[Джон]

Кстати, посмотри на форуме. Мы уже как-то раз кому-то помогали на тему списков, очередей и стеков.