C++，将set复制到vector

Question

我需要将std::set复制到std::vector中：

std::set <double> input;
input.insert(5);
input.insert(6);

std::vector <double> output;
std::copy(input.begin(), input.end(), output.begin()); //Error: Vector iterator not dereferencable

问题出在哪里？

- CrocodileDundee

---

还有一个assign()函数：output.assign(input.begin(), input.end());它的作用是将input容器中的元素赋值给output容器。 - Gene Bushuyev

你的向量是空的。然而，正如下面的人们所指出的那样，有许多方法可以解决这个问题。 - AJG85

@Gene：assign()函数希望提前保留所需的存储空间。它将使用输入迭代器来确定需要多少空间，除非迭代器严格为InputIterator，在这种情况下，它将跳过保留并导致每次push_back()都重新分配内存。在相反的极端，BiderectionalIterators允许它只需减去end-begin即可。然而，std::set的迭代器既不是这两者（它们是ForwardIterator），这很不幸：在这种情况下，assign()将遍历整个集合以确定其大小——对于大型集合来说性能很差。 - Sergey Shevchenko

Answer 1

你需要使用 back_inserter。

std::copy(input.begin(), input.end(), std::back_inserter(output));

std::copy不会向你插入的容器中添加元素：它不能这样做；它只有一个指向容器的迭代器。因此，如果你直接将输出迭代器传递给std::copy，你必须确保它指向的范围至少足够大以容纳输入范围。

std::back_inserter创建了一个输出迭代器，对于每个元素都调用容器的push_back函数，因此每个元素都被插入到容器中。

或者，你可以在std::vector中创建足够数量的元素来容纳被复制的范围：

std::vector<double> output(input.size());
std::copy(input.begin(), input.end(), output.begin());

或者，您可以使用 std::vector 的范围构造函数：

std::vector<double> output(input.begin(), input.end()); 

- James McNellis

---

嗨，詹姆斯，除了你在答案中的第一个代码块里的std::copy行（the first code block in your answer），我可以用output.insert(output.end(), input.begin(), input.end());来代替吗？ - user2015453

或者只使用cbegin和cend版本：output.insert(output.cend(), input.cbegin(), input.cend()); 你觉得怎么样？谢谢。 - user2015453

我应该自己输出.reserve(input.size());还是可以指望一些编译器为我完成它？ - jimifiki

@jimifiki，恐怕没有希望了。 - Alexis Wilke

你的第一个向量初始化是不正确的。你创建了一个由 input,size() 个空条目组成的数组，然后在此之后添加附加项。我认为你想使用 std::vector<double> output; output.reserve(input.size()); std::copy(...);。 - Alexis Wilke

Answer 2

只需使用接受迭代器的向量构造函数：

std::set<T> s;

//...

std::vector v( s.begin(), s.end() );

假设你只想获取v中s的内容，并且在将数据复制到v之前，v中没有任何其他数据。

- Jacob

Answer 3

这里有另一种使用 vector::assign 的替代方案：

theVector.assign(theSet.begin(), theSet.end());

- TeddyC

---

这个可以工作，但是正如@SergeyShevchenko在问题中评论的那样，当迭代集合时，这可能需要重复重新分配向量，因为它增长了。 - Sz.

Answer 4

您的向量对象中没有预留足够的空间来容纳您集合的内容。

std::vector<double> output(input.size());
std::copy(input.begin(), input.end(), output.begin());

- Marlon

---

这不应该被评为-1。特别是，这允许向量只进行一次分配（因为它无法在O（1）中确定集合迭代器的距离），如果没有定义向量在构造时将每个元素归零，那么允许复制简化为memcpy可能是值得的。如果实现发现可以删除向量的ctor中的循环，则后者仍然可能是有价值的。当然，前者也可以通过reserve实现。 - Fred Nurk

我给你投了一个负一票，但那只是我的疏忽。做个小修改以便我可以撤销我的投票，我就会给你一个加一票：实际上，这是一个非常干净的解决方案，因为它具有优先失败的属性。 - Fred Foo

我刚刚才意识到，如果我自己编辑答案，我就可以点赞。我已经这样做了，为你的“失败优先内存分配”点了一个+1。抱歉！ - Fred Foo

同样重要的是，不仅需要“保留”足够的空间，还需要初始化（默认构造）这些实例槽。因此，仅调用 output.reserve(input.size()) 是不够的。 - Sz.

Answer 5

我认为最有效的方法是预分配并插入元素：

template <typename T>
std::vector<T> VectorFromSet(const std::set<T>& from)
{
    std::vector<T> to;
    to.reserve(from.size());

    for (auto const& value : from)
        to.emplace_back(value);

    return to;
}

这样我们只需要为每个元素调用复制构造函数，而不是先调用默认构造函数，然后再调用其他解决方案中的复制赋值运算符。以下更多澄清。

1. 可以使用 back_inserter 但它会在 vector 上调用 push_back() (https://en.cppreference.com/w/cpp/iterator/back_insert_iterator)。emplace_back() 更有效率，因为它避免了在使用 push_back() 时创建临时对象。对于平凡构造类型来说这不是问题，但对于非平凡构造类型（例如 std::string）则会影响性能。

2. 我们需要避免使用带有大小参数的构造函数创建 vector，因为这会导致所有元素都被默认构造（没必要）。例如像使用 std::copy() 的解决方案。

3. 最后，vector::assign() 方法或使用迭代器范围的构造函数不是好的选择，因为它们将在 set 迭代器上调用 std::distance() 来知道元素数量。这将导致额外的迭代通过所有 set 元素，因为 set 是二叉搜索树数据结构并且没有实现随机访问迭代器。

希望这有所帮助。

- dshvets1

---

请添加一个权威参考，说明为什么这很快，以及类似于为什么不需要使用 back_inserter 的解释。 - Tarick Welling

在答案中添加了更多的澄清。 - dshvets1

Answer 6

set<T> s;
// some code
vector<T> v;
v.assign(s.begin(), s.end());

- Mostafa Wael

Answer 7

std::copy 无法用于向空容器中插入元素。为了实现这一点，您需要使用 insert_iterator，如下所示：

std::set<double> input;
input.insert(5);
input.insert(6);

std::vector<double> output;
std::copy(input.begin(), input.end(), inserter(output, output.begin())); 

- Bradley Swain

---

当向量重新分配内存时，第一次调用将失败：output.begin()返回的迭代器会失效。 - Fred Nurk

Answer 8

COPY函数返回一个指向目标范围末尾的迭代器（指向最后一个被复制元素之后的位置）。

back-insert迭代器是一种特殊类型的输出迭代器，旨在允许通常会覆盖元素（如copy）的算法自动将新元素插入到容器的末尾。

set os; vector vec;

copy(os.begin(), os.end(), back_inserter(vec));

- ashish_nandan