std :: insert_iterator и аннулирование итератора

Question

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

#include <vector>
#include <list>
#include <algorithm>
#include <iostream>

template<typename ForwardIterator, typename InserterFunc>
void intersperse(ForwardIterator begin, ForwardIterator end, InserterFunc ins, 
                 // we cannot use rvalue references here, 
                 // maybe taking by value and letting users feed in std::ref would be smarter
                 const ForwardIterator::value_type& elem) {
  if(begin == end) return;
  while(++begin != end) {
    // bugfix would be something like:
    // begin = (ins(begin) = elem); // insert_iterator is convertible to a normal iterator
    // or
    // begin = (ins(begin) = elem).iterator(); // get the iterator to the last inserted element

    // begin now points to the inserted element and we need to
    // increment the iterator once again, which is safe
    // ++begin;
    ins(begin) = elem;
  }
}

int main()
{
  typedef std::list<int> container;
  // as expected tumbles, falls over and goes up in flames with:
  // typedef std::vector<int> container;
  typedef container::iterator iterator;
  container v{1,2,3,4};

  intersperse(v.begin(), v.end(), 
              [&v](iterator it) { return std::inserter(v, it); },
              23);
  for(auto x : v)
    std::cout << x << std::endl;
  return 0;
}

Пример работает только для контейнеров, которые не делают их недействительными итераторы на вставке. Должен ли я просто избавиться от итераторов и принять контейнер в качестве аргумента или я что-то упустил insert_iterator, что делает возможным такое использование?

Answer 1

Пример работает только для контейнеров, которые не делают недействительными свои итераторы при вставке.

Точно.

Должен ли я просто избавиться от итераторовпринять контейнер в качестве аргумента

Это была бы одна возможность.Другим было бы не сделать алгоритм на месте (т. Е. Выводить в другой контейнер / выходной итератор).

Я что-то упускаю из-за insert_iterator, который делает возможным такое использование?

Нет.insert_iterator предназначен для многократных вставок в одно место контейнера, например.по алгоритму преобразования.

Answer 2

Проблемы с вашей реализацией абсолютно не связаны со свойствами insert_iterator. Все виды итераторов вставки в стандартной библиотеке C ++ гарантированно остаются действительными, даже если вы выполняете вставку в контейнер, который потенциально делает недействительными итераторы при вставке. Это, конечно, верно, только если все вставки выполняются только через итератор вставки.

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

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

Между тем, по какой-то причине вы делаете это полностью назад. Кажется, вы заботитесь об обновлении итератора вставки (который совершенно не нужен), при этом полностью игнорируя begin и end.