Std:: удалить с помощью vector:: erase и undefined поведение

Во всем Интернете я вижу, что люди используют удалить/удалить идиому для векторов С++, например:

#include <vector> // the general-purpose vector container
#include <iostream>
#include <algorithm> // remove and remove_if
int main()
{
  // initialises a vector that holds the numbers from 0-9.
  std::vector<int> v = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 };

  // removes all elements with the value 5
  v.erase( std::remove( v.begin(), v.end(), 5 ), v.end() );

  return 0;
}

То есть, если я хочу удалить все элементы, соответствующие некоторым критериям (например, число 5 из вектора int s), я использую std::remove или std::remove_if в сочетании с vector.erase следующим образом:

vector.erase( std::remove( vector.begin(), vector.end(), <some_value>), vector.end());

Это хорошо работает в целом; std::remove (и remove_if) скопирует (или использует семантику перемещения в С++ 11) элементы, которые должны быть удалены до конца вектора, поэтому вектор из нашего предыдущего примера теперь будет выглядеть так:

{0, 1, 2, 3, 4, 6, 7, 8, 9, 5};

С элементом 5 полужирным шрифтом, потому что он был перенесен в конец.

Теперь std::remove вернет ему итератор, который мы затем используем в erase, чтобы очистить элементы. Ницца.

Но как насчет следующего примера?

int main()
{
  // initialises an empty vector.
  std::vector<int> v = {};

  // removes all elements with the value 5
  v.erase( std::remove( v.begin(), v.end(), 5 ), v.end() );

  return 0;
}

Кажется, что это работает как ожидалось (не стирая ничего, а не segfaulting и т.д.) на всех платформах, на которых я запускаю его, но я знаю, что только потому, что что-то работает, это не значит, что это не поведение undefined.

Быстрое reference для vector.erase говорит об этом (основное внимание):

iterator erase (const_iterator first, const_iterator last);

first, last являются

Итераторы, определяющие диапазон внутри вектора]: [first,last). то есть диапазон включает в себя все элементы между first и last, , включая элемент, указанный первым, но не тот, на который указывает last.  Типы участников iterator и const_iterator являются типами итераторов произвольного доступа, которые указывают на элементы.

Итак, поведение vector.erase(vector.end(),vector.end()) undefined?

Вот что говорится в быстрой ссылке о безопасности исключений:

Если удаленные элементы содержат последний элемент в контейнере, никаких исключений не выбрасывается (гарантия отсутствия броска).  В противном случае контейнер, как гарантируется, должен быть закончен в действительном состоянии (основная гарантия).  Недопустимый position или range вызывает поведение undefined.

Итак, ответ, по крайней мере, мне кажется "ДА", и qaru.site/info/210702/..., похоже, его поддерживает.

Следовательно, является ли распространенная идиома неправильной?

Предполагая, что это поведение undefined, любой вызов remove мог бы вернуть итератор в vector.end(), который должен быть проверен перед вызовом vector.erase, и вызов remove на пустой вектор, кажется, возвращает vector.end: (IDEOne для кода ниже)

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

int main() {
   vector<int> myInts;
   auto anIter = std::remove(myInts.begin(),myInts.end(),5);
   if (anIter == myInts.end())
      std::cout << "iterator = myInts.end()";
}

Наконец, мой вопрос:

Должен ли быть фактический идентификатор удаления/стирания?

auto endOfRangeIterator = std::remove(vector.begin(), vector.end(), <value>);
if (endOfRangeIterator != vector.end())
   vector.erase(endOfRangeIterator, vector.end())

Ответы

Ответ 1

24.2.1/7. Большинство алгоритмических шаблонов библиотеки, которые работают с структурами данных, имеют интерфейсы, которые используют диапазоны. Диапазон - это пара итераторов, которые обозначают начало и конец вычисления. Диапазон [i,i) - пустой диапазон; в общем случае диапазон [i,j) относится к элементам в структуре данных, начиная с элемента указана на i и до, но не включая элемент, на который указывает на j.

Акцент на мой.

Кроме того, описание erase, которое вы цитируете, не является нормативным текстом в стандарте. Стандарт должен сказать это (Таблица 100):

a.erase(q1,q2)

Эффекты: стирает элементы в диапазоне [q1, q2).

Это не требует, чтобы q1 был разыменован. Если [q1, q2] - пустой диапазон (в 24.2.1/7), то никакие элементы не находятся в диапазоне, и поэтому ни один из них не стирается.

Ответ 2

Итак, поведение vector.erase(vector.end(), vector.end()) undefined?

Нет. Из-за утверждения рядом с тем, которое вы создали:

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

Итак, vector.erase(vector.end(),vector.end()) не пытается удалить vector.end(), потому что на него указывает параметр last.

Конечно, это определение неоднозначно, и эти утверждения можно интерпретировать как противоречивые. Указанная формулировка не используется стандартом.

Ответ 3

Я думаю, что более важным в вашем цитировании является:

Итераторы, определяющие диапазон внутри вектора], которые необходимо удалить: [первый Последний). то есть диапазон включает в себя все элементы между первыми и последний, включая элемент, указанный первым , но не тот указана последним. Типы итераторов типов и const_iterator являются случайными доступ к типам итераторов, которые указывают на элементы.

Как мы нашли в комментариях, эта цитата из cpluspluc.com неверна. Это не будет нарушать правила в случае ( v.end, v.end), но будет неправильным в случае

#include <vector>

int main()
{
    std::vector<int> v = { 1, 2, 3 };

    v.erase( v.begin(), v.begin());
}

поскольку утверждение, противоречащее себе с

диапазон включает (...), включая элемент, на который указывает v.begin() , но не тот, на который указывает v.begin().

не может быть допустимым оператором.

С++ Стандарт n3337 в § 23.2.2 Требования к контейнерам последовательностей В таблице 100 указано, что

a.erase(q1,q2) возвращает iterator. Обратите внимание:

Требуется: для вектора и дека Т должен быть MoveAssignable. Последствия: Стирает элементы в диапазоне [q1, q2).

И вот что он говорит о диапазоне [i,j) в § 24.2.1/7 Требования к итератору

Большинство алгоритмических шаблонов библиотеки, которые работают с данными структуры имеют интерфейсы, которые используют диапазоны. Диапазон - это пара итераторы, которые обозначают начало и конец вычисления. диапазон [i, i) - пустой диапазон; в общем случае диапазон [i, j) относится к в структуре данных, начиная с элемента, на который указывает я и до , но не включая элемент, на который указывает j. Диапазон [i, j) справедливо тогда и только тогда, когда j достижимо из i. Результат применение функций в библиотеке к недопустимым диапазонам undefined.

Таким образом, чтобы ответить на ваши вопросы

Но как насчет следующего примера?

cplusplus.com ошибочен в этом случае

Итак, поведение vector.erase(vector.end(), vector.end()) undefined?

Нет, не срабатывает поведение undefined.

Следовательно, является ли распространенная идиома неправильной?

Нет, это правильно.

Должен ли быть фактический идентификатор удаления/стирания?

Нет необходимости в этом, хотя это тоже хорошо.