Что произойдет, если я использую vector :: begin() вместо std :: back_inserter (vector) для вывода set_intersection?

Question

Я использую высоко сжатый и интуитивный синтаксис 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() составлен под clang.

Что гарантируется в соответствии со стандартом? Если это скомпилируется, что может произойти - то есть, когда итератор, возвращенный на c.begin(), в конечном итоге увеличивается до конца вектора, и делается попытка получить доступ к указанному элементу, что должно/может произойти? Может ли соответствующая реализация молча расширить вектор в этом случае, так что begin() на самом деле является добавлением OutputIterator, например back_inserter?

Я прошу об этом в основном, чтобы понять, как стандарт работает с итераторами: что происходит, поэтому я могу перейти за рамки копирования и вставки в STL.

Answer 1

Важное требованием для итератора вывода является то, что это будет действительным и записи состояния для диапазона
[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 не пусто.

Может соответствующая реализация беззвучно продлить вектор в этом случае, так что начать() в действительности является добавление OutputIterator как back_inserter есть?

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

Answer 2

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

Итак, вас не интересует, проходящий мимо конца диапазона, так как push_back автоматически расширяет контейнер. Однако это не относится к вставке с использованием begin().

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

Answer 3

Он компилируется отлично, потому что вы возвращаете действительный итератор из функции begin, но если вектор пуст, вы вернете итератор end, а затем продолжите оттуда.

Он будет работать только если вектор уже содержит, по меньшей мере столько же элементов, как вы пытаетесь добавить, и тогда это будет на самом деле перезаписать эти элементы и не добавлять новые.

И добавление элементов - это то, что делает итератор back_inserter, он возвращает итератор, который в основном делает push_back на векторе.