Чтобы понять смысл происходящего, необходимо запомнить следующее: Алгоритм remove «по настоящему» ничего не удаляет, потому что не может. На всякий случай повторю: …потому что не может!
Алгоритм
remove
не знает, из какого контейнера он должен удалять элементы, а без этого он не может вызвать функцию «настоящего» удаления.
Итак, теперь вы знаете, чего алгоритм
remove
сделать не может и по каким причинам. Остается понять, что же он все-таки делает.
В общих чертах
remove
перемещает элементы в заданном интервале до тех пор, пока все «оставшиеся»
элементы не окажутся в начале интервала (с сохранением их относительного порядка). Алгоритм возвращает итератор, указывающий на позицию за последним «оставшимся» элементом. Таким образом, возвращаемое значение можно интерпретировать как новый «логический конец» интервала.
Вопросительными знаками отмечены значения элементов, «концептуально» удаленных из
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
возвращает итератор для нового логического конца массива, задача решается прямолинейно: