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。