Что произойдет, если я буду использовать vector :: begin () вместо std :: back_inserter (vector) для вывода set_intersection?
Я использовал очень лаконичный и интуитивно понятный синтаксис C ++ для нахождения пересечения двух отсортированных vectorи положить результат в третьем vector:
vector<bar> a,b,c;
//...
std::set_intersection(a.begin(),a.end(),b.begin(),b.end(),
std::back_inserter(c));
Это должно установить c до пересечения (a,b), предполагая a а также b отсортированы.
Но что, если я просто использую c.begin() (Я думал, что видел пример где-то из этого, именно поэтому я и сделал):
std::set_intersection(a.begin(),a.end(),b.begin(),b.end(),
c.begin());
set_intersection ожидает OutputIterator на этот параметр. Я считаю, что стандарт требует только c.begin() вернуть forward iterator, который я полагаю, может быть или не быть OutputIterator,
Во всяком случае, код с c.begin() составлено под лязг.
Что гарантированно произойдет по стандарту? Если это скомпилируется, то, что может произойти, то есть когда итератор возвращается c.begin() в конечном итоге увеличивается после конца вектора, и делается попытка получить доступ к указанному элементу, что должно / может произойти? Может ли соответствующая реализация молча расширить вектор в этом случае, чтобы begin() на самом деле является добавлением OutputIterator лайк back_inserter является?
Я спрашиваю это главным образом, чтобы понять, как стандарт работает с итераторами: что на самом деле происходит, поэтому я могу выйти за рамки копирования и вставки при использовании STL.
Решение
Важным требованием для выходного итератора является то, что он должен быть допустимым и доступным для записи для диапазона [out, out+размер продукции),
Переходя c.begin() приведет к тому, что значения перезаписаны который работает только если контейнер c содержит достаточно элементов для перезаписи. Представь это c.begin() возвращает указатель на массив размером 0 — тогда вы увидите проблему при записи *out++ = 7;,
back_inserter добавляет каждое присвоенное значение vector (с помощью push_back) и предоставляет краткий способ заставить STL-алгоритмы расширять диапазон — он перегружает операторы, которые используются для итераторов соответствующим образом.
таким образом
std::set_intersection(a.begin(),a.end(),b.begin(),b.end(),
c.begin());
вызывает неопределенное поведение один раз set_intersection записывает что-то в свой выходной итератор, то есть когда устанавливается пересечение a а также b не пусто
Может ли соответствующая реализация молча расширить вектор в этом случае, так что begin () на самом деле является добавлением
OutputIteratorлайкback_inserterявляется?
Конечно. Это неопределенное поведение. (Это юмористический подход к тому, чтобы сказать вам, что вам даже не следует использовать его, независимо от того, какое влияние это оказывает на любую реализацию.)
Другие решения
back_inserter вставляет элемент в диапазон, вызывая push_back (вот почему вы не можете использовать back_inserter с диапазоном, который не обеспечивает push_back операция).
Так, тебя не волнует пройдя конец диапазона как push_back автоматически расширяет контейнер. Тем не менее, это не так с использованием вставки begin(),
Если вы используете begin()то вы должны убедиться, что диапазон назначения достаточно большой держать все элементы. Невыполнение этого требования приведет к немедленному переносу вашего кода в область неопределенного поведения.
Он хорошо компилируется, потому что вы получаете верный итератор из begin функция, но если вектор пуст, то вы получите обратно end итератор, а затем продолжить оттуда.
Это будет работать только если целевой вектор уже содержит по крайней мере столько элементов, сколько вы пытаетесь добавить, то он фактически перезапишет эти элементы и не добавит новые.
А добавление элементов — это то, что back_inserter итератор делает, он возвращает итератор, который в основном делает push_back на векторе.