Эффективное использование STL

Мейерс Скотт

cout << v.size; // Все равно выводится 10!

Чтобы понять смысл происходящего, необходимо запомнить следующее: Алгоритм remove «по настоящему» ничего не удаляет, потому что не может. На всякий случай повторю: …потому что не может!

Алгоритм

remove

не знает, из какого контейнера он должен удалять элементы, а без этого он не может вызвать функцию «настоящего» удаления.

Итак, теперь вы знаете, чего алгоритм

remove

сделать не может и по каким причинам. Остается понять, что же он все-таки делает.

В общих чертах

remove

перемещает элементы в заданном интервале до тех пор, пока все «оставшиеся»

элементы не окажутся в начале интервала (с сохранением их относительного порядка). Алгоритм возвращает итератор, указывающий на позицию за последним «оставшимся» элементом. Таким образом, возвращаемое значение можно интерпретировать как новый «логический конец» интервала.

В рассмотренном выше примере вектор

v

перед вызовом

remove

выглядел следующим образом:

Предположим, возвращаемое значение

remove

сохраняется в новом итераторе с именем

newEnd

:

vector<int>::iterator newEnd(remove(v.begin, v.end, 99));

После вызова вектор

v

принимает следующий вид:

Вопросительными знаками отмечены значения элементов, «концептуально» удаленных из

v

, но продолжающих благополучно существовать.

Раз «оставшиеся» элементы v находятся между

v.begin

и

newEnd

, было бы логично предположить, что «удаленные» элементы будут находиться между

newEnd

и

v.end

. Но это не так! Присутствие «удаленных» элементов в v вообще не гарантировано. Алгоритм

remove

не изменяет порядок элементов в интервале так, чтобы «удаленные» элементы сгруппировались в конце — он перемещает «остающиеся» элементы в начало. Хотя в Стандарте такое требование отсутствует, элементы за новым логическим концом интервала обычно сохраняют свои старые значения. Во всех известных мне реализациях после вызова

remove

вектор

v

выглядит так:

Как видите, два значения «99», ранее существовавших в

v

, исчезли, а одно осталось. В общем случае после вызова

remove

элементы, удаленные из интервала, могут остаться в нем, а могут исчезнуть. Многие программисты находят это странным, но почему? Вы просите

remove

убрать некоторые элементы, алгоритм выполняет вашу просьбу. Вы же не просили разместить удаленные значения в особом месте для последующего использования… Так в чем проблема? (Чтобы предотвратить потерю значений, вместо remove лучше воспользоваться алгоритмом

partition

, описанным в совете 31.)

На первый взгляд поведение remove выглядит довольно странно, но оно является прямым следствием принципа работы алгоритма. Во внутренней реализации

remove

перебирает содержимое интервала и перезаписывает «удаляемые» значения «сохраняемыми». Перезапись реализуется посредством присваивания.

Алгоритм

remove

можно рассматривать как разновидность уплотнения, при этом удаляемые значения играют роль «пустот», заполняемых в процессе уплотнения. Опишем, что происходит с вектором v из нашего примера.

1. Алгоритм

remove

анализирует

v[0]

, видит, что данный элемент не должен удаляться, и перемещается к

v[1]

. То же самое происходит с элементами

v[1]

и

v[2]

.

2. Алгоритм

определяет, что элемент

v[3]

подлежит удалению, запоминает этот факт и переходит к

v[4]

. Фактически

v[3]

рассматривается как «дыра», подлежащая заполнению.

3. Значение

v[4]

необходимо сохранить, поэтому алгоритм присваивает

v[4]

элементу

v[3]

, запоминает, что

v[4]

подлежит перезаписи, и переходит к

v[5]

. Если продолжить аналогию с уплотнением, элемент

v[3]

«заполняется» значением

v[4]

, а на месте

v[4]

образуется новая «дыра».

4. Элемент

v[5]

исключается, поэтому алгоритм игнорирует его и переходит к

v[6]

. При этом он продолжает помнить, что на месте

v[4]

остается «дыра», которую нужно заполнить.

5. Элемент

v[6]

сохраняется, поэтому алгоритм присваивает

v[6]

элементу

v[4]

, вспоминает, что следующая «дыра» находится на месте

v[5]

, и переходит к

v[7]

.

6. Аналогичным образом анализируются элементы

v[7]

,

v[8]

и

v[9]

. Значение

v[7]

присваивается элементу

v[5]

, а значение

v[8]

присваивается элементу

v[6]

. Элемент

v[9]

игнорируется, поскольку находящееся в нем значение подлежит удалению.

7. Алгоритм возвращает итератор для элемента, следующего за последним «оставшимся». В данном примере это элемент

v[7]

.

Перемещения элементов в векторе

v

выглядят следующим образом:

Как объясняется в совете 33, факт перезаписи некоторых удаляемых значений имеет важные последствия в том случае, если эти значения являются указателями. Но в контексте данного совета достаточно понимать, что

remove

не удаляет элементы из контейнера, поскольку в принципе не может этого сделать. Элементы могут удаляться лишь функциями контейнера, отсюда следует и главное правило настоящего совета: чтобы удалить элементы из контейнера, вызовите

erase

после

remove

.

Элементы, подлежащие фактическому удалению, определить нетрудно — это все элементы исходного интервала, начиная с нового «логического конца» интервала и завершая его «физическим» концом. Чтобы уничтожить все эти элементы, достаточно вызвать интервальную форму

erase

(см. совет 5) и передать ей эти два итератора. Поскольку сам алгоритм

remove

возвращает итератор для нового логического конца массива, задача решается прямолинейно:

vector<int> v; //См. ранее

…

v.erase(remove(v.begin, v.end, 99), v.end); // Фактическое удаление

// элементов со значением 99

cout << v.size; // Теперь выводится 7

Передача в первом аргументе интервальной формы

erase

возвращаемого значения

remove

используется так часто, что рассматривается как стандартная конструкция.

Remove

и

erase

настолько тесно связаны, что они были объединены в функцию

remove

контейнера

list

. Это единственная функция STL с именем

remove

, которая производит фактическое удаление элементов из контейнера: