Гарантирует ли std::vector:: reserve, что реализация не приведет к аннулированию итераторов в этом случае?

Вот функция, которая предназначена для:

a) принять вектор int

b) для каждого int во входном векторе добавьте инверсию этого int

предпосылки: none

постусловия: возвращаемый векторный размер() - это быстрая 2 * размер входного вектора.

Обратите внимание, что вектор изменен на месте.

Вопрос:

Является ли эта функция строго определенным поведением vis-a-vis аннулирование итератора во время преобразования?

Бонус:

Есть ли лучший/более сжатый/надежный способ его написать?

код:

std::vector<int> append_negatives(std::vector<int> v)
{
    v.reserve(v.size() * 2);
    std::transform(begin(v), end(v), 
                   back_inserter(v), 
                   [](auto&& x) { return -x; });
    return v;
}

Ответ 1

Если вы не превысите предопределенную емкость, перераспределение не должно происходить, и никакие ссылки или итераторы, ссылающиеся на векторные элементы, не должны быть признаны недействительными. Однако, поскольку итератор, возвращаемый end(), не ссылается на какие-либо элементы вектора, он все равно может стать недействительным.

23.3.11.3 векторная емкость [vector.capacity]

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

...

23.3.11.5 векторные модификаторы [vector.modifier]

... Если перераспределение не происходит, все итераторы и ссылки до точки вставки остаются в силе.

Ответ 2

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

Бонус:

Есть ли лучший/более сжатый/надежный способ его написать?

часть вопроса.

Честно говоря, я полностью обойду проблему с передовой технологией петель for. KISS!

std::vector<int> append_negatives(std::vector<int> v) {
    size_t sz = v.size();
    v.resize(sz*2);
    for(size_t i = 0; i < sz; ++i) v[i+sz] = -v[i];
    return v;
}

Не все должно быть запутано в глубоком плаще алгоритмов STL. Это является более коротким, ИМО более читаемым и позволяет избежать головных болей за недействительность итераторов.

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

Помните, что преимущество скорости/отсутствие недействительной головной боли можно получить даже с помощью transform benemoth:

std::vector<int> append_negatives(std::vector<int> v) {
    size_t sz = v.size();
    v.resize(sz * 2);
    auto beg = begin(v);
    std::transform(beg, beg + sz, beg + sz, 
                   [](int x) { return -x; });
    return v;
}

но я не вижу никакого преимущества такого избыточного подробного кода в простом цикле for, если только вам не платят количество "классных" возможностей С++, которые вам удается сжать в вашем коде.

@MikeMB запрашивает типы, которые являются дорогостоящими для построения по умолчанию; в этом случае явный push_back штраф:

std::vector<int> append_negatives(std::vector<int> v) {
    size_t sz = v.size();
    v.reserve(sz*2); // optional
    for(size_t i = 0; i < sz; ++i) v.push_back(-v[i]);
    return v;
}

Вы также можете использовать цикл, основанный на диапазоне, если значение transform в исходном сообщении было действительным:

std::vector<int> append_negatives(std::vector<int> v) {
    v.reserve(v.size()*2);
    for(int &x: v) v.push_back(x);
    return v;
}

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