Является ли vector:: insert разрешено резервировать только один раз и избежать дополнительных проверок емкости?

vector::insert(dst_iterator, src_begin, src_end) (вставить диапазон) можно оптимизировать для итераторов с произвольным доступом, чтобы сначала зарезервировать требуемую емкость src_end - src_begin, а затем выполнить копию.

Основной вопрос У меня есть: позволяет ли Стандарт также vector::insert избегать проверки емкости для каждого скопированного элемента? (I.e. не используя push_back или аналогичный для каждого элемента, который нужно вставить)

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

Что может пойти не так: я могу представить себе итератор с побочными эффектами при разыменовании:

Примечание. Стандарт гарантирует, что итераторы, переданные в insert, будут разыменованы ровно один раз (см. конец вопроса).

#include <vector>
#include <iterator>
#include <iostream>

template < typename T >
struct evil_iterator : std::iterator < std::random_access_iterator_tag, T >
{
    using base = std::iterator < std::random_access_iterator_tag, T >;

    std::vector<T>* evil_feedback;
    typename std::vector<T>::iterator innocent_iterator;

    evil_iterator( std::vector<T>* c,
                   typename std::vector<T>::iterator i )
        : evil_feedback{c}
        , innocent_iterator{i}
    {}

    void do_evil()
    {
        std::cout << "trying to do evil; ";
        std::cout << "cap: " << evil_feedback->capacity() << ", ";
        std::cout << "size: " << evil_feedback->size() << ", ";

        // better not invalidate the iterators of `*evil_feedback`
        // passed to the `insert` call (see example below)
        if( evil_feedback->capacity() > evil_feedback->size() )
        {
            evil_feedback->push_back( T{} );
            // capacity() might be == size() now
            std::cout << "successful >:]" << std::endl;
        }else
        {
            std::cout << "failed >:[" << std::endl;
        }
    }

    T& operator*()
    {
        do_evil();  // <----------------------------------------
        return *innocent_iterator;
    }


    // non-evil iterator member functions-----------------------

    evil_iterator& operator++()
    {
        ++innocent_iterator;
        return *this;
    }
    evil_iterator& operator++(int)
    {
        evil_iterator temp(*this);
        ++(*this);
        return temp;
    }


    evil_iterator& operator+=(typename base::difference_type p)
    {
        innocent_iterator += p;
        return *this;
    }
    evil_iterator& operator-=(typename base::difference_type p)
    {
        innocent_iterator -= p;
        return *this;
    }

    evil_iterator& operator=(evil_iterator const& other)
    {
        evil_feedback = other.evil_feedback;
        innocent_iterator = other.innocent_iterator;
        return *this;
    }

    evil_iterator operator+(typename base::difference_type p)
    {
        evil_iterator temp(*this);
        temp += p;
        return temp;
    }
    evil_iterator operator-(typename base::difference_type p)
    {
        evil_iterator temp(*this);
        temp -= p;
        return temp;
    }

    typename base::difference_type operator-(evil_iterator const& p)
    {
        return this->innocent_iterator - p.innocent_iterator;
    }

    bool operator!=(evil_iterator const& other) const
    {  return innocent_iterator != other.innocent_iterator;  }
};

Пример:

int main()
{
    std::vector<int> src = {3, 4, 5, 6};
    std::vector<int> dst = {1, 2};

    evil_iterator<int> beg = {&dst, src.begin()};
    evil_iterator<int> end = {&dst, src.end()};

    // explicit call to reserve, see below
    dst.reserve( dst.size() + src.size() );
    // using dst.end()-1, which stays valid during `push_back`,
    //   thanks to Ben Voigt pointing this out
    dst.insert(dst.end()-1, beg, end);  // <--------------- doing evil?

    std::copy(dst.begin(), dst.end(), 
              std::ostream_iterator<int>{std::cout, ", "});
}

Вопросы:

Можно ли оптимизировать vector::insert, чтобы избежать проверки емкости для каждого вставленного элемента?
Является ли evil_iterator допустимым итератором?
Если это так, это evil_iterator зло, т.е. может ли это привести к UB/несоблюдению поведения, если insert оптимизирован, как описано выше?

~~Возможно, мой do_evil не является достаточно злым.. не имеет проблем с clang++ 3.2 (используя libstdС++):~~

Изменить 2: добавлен вызов reserve. Теперь я делаю зло:)

пытается сделать зло; колпачок: 6, размер: 2, успешный > :]
пытаясь сделать зло; колпачок: 6, размер: 3, успешный > :]
пытаясь сделать зло; колпачок: 6, размер: 4, успешный > :]
пытаясь сделать зло; колпачок: 6, размер: 9, не удалось > : [
1, 3, 4, 5, 6, 0, 0, 135097, 2,

Изменить: почему я думаю, что оптимизация может нарушить это:

Рассмотрим dst.size() == dst.capacity() == 2 в начале.
Для вызова insert требуется новая емкость 6.
Оптимизация увеличивает емкость до точности 6, а затем начинает вставлять элементы путем копирования из итераторов src (beg, end).
Это копирование выполняется в цикле, где не происходит проверки емкости. (Это оптимизация.)
В процессе копирования в вектор добавляются дополнительные элементы (без признания итераторов), в do_evil. Теперь емкость недостаточна для хранения остальных элементов, которые нужно скопировать.

Возможно, вам пришлось использовать reserve в явном виде для принудительного обновления наблюдаемого capacity перед использованием do_evil. В настоящее время insert может зарезервировать некоторую емкость, но изменить то, что возвращает capacity (т.е. Наблюдаемая емкость) только после завершения копирования.

То, что я нашел в Стандарте, похоже, позволяет оптимизировать insert:

[sequence.reqmts]/3

a.insert(p,i,j) [...]

Требуется: T должен быть EmplaceConstructible в X из * i.

Для вектора, если итератор не удовлетворяет требованиям прямого итератора (24.2.5), T также должен быть MoveInsertable в X и MoveAssignable. Каждый итератор в диапазоне [i, j) должен быть разыменован ровно один раз.

pre: я и j не являются итераторами в a. Вставляет копии элементов в [i, j) до p

[vector.modifiers] на insert

1 Примечания: вызывает перераспределение, если новый размер больше старой. Если перераспределение не происходит, все итераторы и ссылки до точки вставки остаются в силе. Если исключение выбрано иначе, чем конструктор копирования, переместите конструктор, оператор присваивания или оператор присваивания перемещения T или любую операцию InputIterator, никаких эффектов нет. Если исключение вызывается конструктором перемещения не-CopyInsertable T, эффекты не заданы.

2 Сложность: сложность линейна по числу вставленных элементов плюс расстояние до конца вектора.

Ответы

Ответ 1

Глядя снова, я думаю, что это правило (раздел 17.6.4.9) является более четким запретом на то, что вы пытались сделать:

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

Если аргумент функции имеет недопустимое значение (например, значение вне домена функции или указатель недействителен для его предполагаемого использования), поведение undefined.

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

Кроме того, push_back() гарантирует, что (23.3.7.5):

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

Ваш position передан insert, который равен dst.end(), который был оценен перед вызовом insert, не находится перед точкой вставки первого вызова evil_feedback->push_back(), поэтому он не остается в силе (факт что вы тщательно избегаете перераспределения здесь, не спасает вас, так как вы только встретили половину этого условия). Это означает, что аргумент, который вы передали std::vector::insert, функция, определенная в стандартной библиотеке С++, недействительна в течение продолжительности этого вызова, вы приземляетесь прямо в области поведения undefined.

Предыдущий ответ:

Я думаю, что вы нарушили это предварительное условие, которое вы указали:

pre: i и j не являются итераторами в a.

Ответ 2

(Примечание: это скорее комментарий, я использую ответ, чтобы разрешить форматирование и более длительный контент. Маркировка CW, потому что комментарии не должны получать rep)

Я считаю, что это правильный алгоритм, который позволяет избежать сложности O (NM), если входные итераторы являются случайным доступом:

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

Ответ 3

Вот мои взгляды:

Да; de-referencing может иметь побочные эффекты для вашего вектора (пример), который может привести к поведению undefined в некоторых случаях, но это не должно быть в случае со стандартными итераторами.
Нет; Итераторы предназначены для обобщения указателей - поскольку у указателей de-referencing не могут быть побочные эффекты (не удается найти ссылку), то то же самое должно быть в случае итераторов [iterator.requirements.general]. Учитывая эту интерпретацию, "оптимизация вставки" (1) действительна.