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

Я пытался написать общий, на месте, 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 что делает возможным такое использование?

Источник

2 ответа

Решение

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

Именно так.

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

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

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

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

Источник

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

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

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

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

Источник
Другие вопросы по тегам