迭代器和back_insert_iterator有什么区别？

Question

如果随机访问迭代器可以用于相对于它们指向的元素的任意偏移位置访问元素（类似于指针），为什么不能在通用算法中使用它们，例如std::copy()，而要使用back_insert_iterator？它们之间有什么区别？

- Algo

---

它们可以在像std :: copy这样的算法中使用。您应该澄清您的问题。 - juanchopanza

Answer 1

std::back_insert_iterator是一种特定类型的输出迭代器，支持push_back操作。当你使用operator=写入它时，它会将值推送到基础容器中，因此在这个意义上，它充当了具有push_back成员函数的容器的适配器。

以下是一个易于理解的例子：

std::vector<int> v;

std::back_insert_iterator<std::vector<int>>  it(v);

*it = 10; // it is equivalent to v.push_back(10);
 it = 99; // it is ALSO equivalent to v.push_back(99);

for (auto const & i : v)
    std::cout << i << " " ; //10 99

它的输出结果是：

10 99

在线演示。

通常在迭代器 it 上的操作 ++ 和 * 没有影响。

但你很少直接使用它们（我直到现在也从未直接使用过它们）。你与算法一起使用它们，例如 std::copy，在这种情况下，你还会使用 std::back_inserter 函数，该函数返回类型为 std::back_insert_iterator 的对象。

//assuming dest is a container which supports push_back!
std::copy(src.begin(), src.end(), std::back_inserter(dest));

您可能也会喜欢以下（适配器）迭代器：

• std::front_insert_iterator 支持 push_front 操作
• std::insert_iterator 支持 insert 操作。

所以根据容器的不同，您可以选择使用适配器迭代器。

请注意，它们都是输出迭代器。

为什么不能在像std::copy()这样的通用算法中使用它们，而是要使用back_insert_iterator呢？

当然，您可以将随机访问迭代器（或任何输出迭代器）作为第三个参数在像std::copy这样的算法中使用，但这假定迭代器引用到现有范围——对于您传递的值，*it 和 ++it 都是定义良好的。您将它们传递给函数以覆盖范围内现有元素，而std::back_insert_iterator则向容器添加新元素。

希望这有所帮助。

- Nawaz

Answer 2

实际上，您完全可以在std::copy中使用常规迭代器。

int main() {
    std::vector<int> vec{1, 2, 3, 4};

    std::list<int> list{vec.size()};

    std::copy(vec.begin(), vec.end(), list.begin());

    // list = 1, 2, 3, 4
}

然而，正如您可能已经注意到的那样，这意味着：

- 首先创建`len(source range)`个默认元素 - 然后逐个将元素从源范围复制到目标范围中

这是相当低效的，需要元素可以被默认构造然后赋值。

相反，`back_insert_iterator`是一个“假”迭代器，它作为常规容器上的适配器操作。如果您查看其接口，您会发现它根本不像常规迭代器一样运行，并且每当您尝试推入项时，它只是在嵌入的底层容器引用上调用`push_back`。

int main() {
    std::list<int> list;

    std::back_insert_iterator<std::list<int>> bii(list);

    bii = 1;
    bii = 2;
    bii = 3;
    bii = 4;

    // list = 1, 2, 3, 4

    // note: decltype(*bii) == bii&, so deferencing bii serves no purpose;
    // similarly, ++bi does nothing either; both operations are just defined
    // to mimick a regular operator interface so it can be used in regular
    // algorithms over iterators.
}

因此，这两种方法都是有效的，但具有不同的行为：

- 常规迭代器允许您覆盖现有范围。 - back_insert_iterator 允许您将内容添加到现有容器中。

语义不同，根据手头任务选择合适的方法。

- Matthieu M.

Answer 3

常规迭代器对于它们所使用的容器除了它所持有的数据类型之外一无所知。为了向容器中添加元素，比如说一个 vector，我们需要知道该 vector 中元素的数量。

- A.B.

Answer 4

它们可以这样做，但这样做可能不安全。

我建议阅读来自赫尔辛基大学的优秀迭代器介绍。

如果您有一个容器的迭代器（前向、双向和随机访问都可以），并将其用作STL算法上下文中的输出迭代器，则输出将写入容器中，但迭代器永远不会与容器的end()进行比较。如果所有写入的元素都适合，则这是可以的，但如果不适合，则输出迭代器将到达end()，并对其进行解引用以写入下一个元素将导致未定义行为。

像back_insert_iterator之类的东西专门设计用于用作输出迭代器，并且不会以这种方式导致UB，因为它们始终可以插入更多元素。

- Simon Richter

Answer 5

一般的迭代器不会改变序列的大小或结构。特别是随机访问迭代器只是访问特定位置的元素。

std::back_insert_iterator<Cont> 是一个模板，它模拟了一个具体的输出迭代器，每写入一个元素就会更改它所引用的序列：它为每个写入的元素调用 cont.push_back()。由于迭代器不读取正在修改的序列，因此添加元素非常方便。

- Dietmar Kühl