使用 copy 和 back_inserter 将向量附加到自身时出现错误的结果 [英] Wrong results when appending vector to itself using copy and back_inserter

问题描述

灵感来自 这个问题，询问如何将向量附加到自身，我的第一个想法是以下(是的，我意识到 insert 现在是一个更好的选择):

Inspired by this question, asking how to append a vector to itself, my first thought was the following (and yes, I realize insert is a better option now):

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

int main() {
    std::vector<int> vec {1, 2, 3};
    std::copy (std::begin (vec), std::end (vec), std::back_inserter (vec));

    for (const auto &v : vec)
        std::cout << v << ' ';
}

但是，这会打印:

1 2 3 1 * 3

每次运行程序时，* 都是不同的数字.只有 2 被替换的事实很奇特，如果真的有对此的解释，我很想听听.继续，如果我附加到不同的向量(原始的副本)，它会正确输出.如果我在 copy 之前添加以下行，它也会正确输出:

The * is a different number every time the program is run. The fact that it's only the 2 being replaced is peculiar, and if there actually is an explanation for that, I'd be interested to hear it. Continuing, if I append to a different vector (a copy of the original), it outputs correctly. It also outputs correctly if I add the following line before the copy one:

vec.reserve (2 * vec.size());

我的印象是 std::back_inserter 是一种将元素添加到容器末尾的安全方法，尽管事先没有保留内存.如果我的理解是正确的，那复制行有什么问题?

I was under the impression std::back_inserter was a safe way to add elements onto the end of a container, despite not reserving memory beforehand. If my understanding is correct, what's wrong with the copying line?

我认为这与编译器无关，但我使用的是 GCC 4.7.1.

I assume it's nothing to do with the compiler, but I'm using GCC 4.7.1.

推荐答案

std::back_inserter 创建一个将元素插入容器的插入迭代器.每次取消引用此迭代器时，它都会在容器上调用 push_back 以将新元素附加到容器中.

std::back_inserter creates an inserting iterator that inserts elements into a container. Each time this iterator is dereferenced, it calls push_back on the container to append a new element to the container.

对于 std::vector 容器，调用 push_back 其中 v.size() == v.capacity() 将导致重新分配:创建一个新数组来存储向量的内容，将其当前内容复制到新数组中，并销毁旧数组.此时向量中的任何迭代器都无效，这意味着它们不能再被使用.

For a std::vector container, a call to push_back where v.size() == v.capacity() will result in a reallocation: a new array is created to store the contents of the vector, its current contents are copied into the new array, and the old array is destroyed. Any iterators into the vector at this time are invalidated, meaning they can no longer be used.

在您的程序中，这包括由 begin(vec) 和 end(vec) 定义的输入范围，copy 算法就是从该范围复制.算法会继续使用这些迭代器，即使它们已失效，因此您的程序会表现出未定义的行为.

In your program, this includes the input range defined by begin(vec) and end(vec) from which the copy algorithm is copying. The algorithm continues to use these iterators, even though they are invalidated, thus your program exhibits undefined behavior.

即使你的容器有足够的容量，它的行为仍然是不确定的:规范指出，在插入时，如果没有发生重新分配，插入点之前的所有迭代器和引用仍然有效"(C++11 §23.3.6.5/1).

Even if your container had sufficient capacity, its behavior would still be undefined: the specification states that, upon insertion, "if no reallocation happens, all the iterators and references before the insertion point remain valid" (C++11 §23.3.6.5/1).

对push_back的调用相当于在末尾插入，所以你传入std的结束迭代器(std::end(vec))::copy 在单次调用 push_back 后失效.如果输入范围不为空，则程序因此表现出未定义的行为.

The call to push_back is equivalent to insertion at the end, so the end iterator (std::end(vec)) that you passed into std::copy is invalidated after a single call to push_back. If the input range is nonempty, the program therefore exhibits undefined behavior.

请注意，如果您使用 std::deque<int> 或 std::list<int>，您的程序的行为将是明确定义的，因为在添加元素时，这些容器都不会使迭代器失效.

Note that the behavior of your program would be well-defined if you used a std::deque<int> or a std::list<int>, because neither of those containers invalidates iterators when elements are appended.

这篇关于使用 copy 和 back_inserter 将向量附加到自身时出现错误的结果的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！