ChatGPT解决这个技术问题 Extra ChatGPT

C++,复制集到向量

我需要将 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

问题出在哪里?

还有assign()功能:output.assign(input.begin(), input.end());
你的向量是空的。尽管正如人们在下面指出的那样,有很多方法可以解决这个问题。
@Gene:assign() 想要提前保留必要的存储量。它将使用输入迭代器来确定需要多少,除非迭代器是严格的 InputIterator,在这种情况下,它将跳过保留并导致在每个 push_back() 上重新分配。在频谱的另一端,BiderectionalIterators 将允许它只减去 end - begin。然而,std::set 的迭代器都不是(它们是 ForwardIterator),这很不幸:在这种情况下,assign() 只会遍历整个集合以确定其大小——在大型集合上性能不佳。

M
Marlon

您需要使用 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()); 

嗨詹姆斯,而不是你的 std::copy 行(你的答案中的第一个代码块),我不能只做 output.insert(output.end(), input.begin(), input.end()); 吗?
或者只使用 cbegin 和 cend 版本:output.insert(output.cend(), input.cbegin(), input.cend()); 你怎么看?谢谢。
我应该 output.reserve(input.size());由我自己还是我可以希望一些编译器为我做这件事?
@jimifiki,没有希望我害怕。
您的第一个向量初始化不正确。您创建一个由 input,size() 个空条目组成的数组,然后在此之后追加附加内容。我认为您的意思是使用 std::vector<double> output; output.reserve(input.size()); std::copy(...);
M
Marlon

只需使用带有迭代器的向量的构造函数:

std::set<T> s;

//...

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

假设您只想要 v 中 s 的内容,并且在将数据复制到 v 之前,v 中没有任何内容。


T
Tim Sylvester

这是使用 vector::assign 的另一种选择:

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

这行得通,但正如@SergeyShevchenko 在 q. 评论的那样,这可能需要在向量增长时反复重新分配向量,同时遍历集合。
F
Fred Foo

您没有在矢量对象中保留足够的空间来保存集合的内容。

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

这不值得-1。特别是,这允许向量只进行一次分配(因为它无法确定 O(1) 中集合迭代器的距离),并且,如果没有为向量定义在构造时将每个元素归零,这可能值得让副本归结为 memcpy。如果实现发现vector的ctor中的循环可以被删除,后者仍然是值得的。当然,前者也可以通过储备来实现。
我给了你一个-1,但这是我的想法。做一个小的编辑,这样我就可以撤消我的投票,我会给你一个+1:这实际上是一个非常干净的解决方案,因为失败优先属性。
我只是发现如果我自己编辑答案,我可以投赞成票。这样做,给了你一个+1的失败优先内存分配。对不起!
此外,非常重要的是,不仅需要“保留” 足够的空间,而且还要初始化(默认构造)这些实例槽。因此,仅调用 output.reserve(input.size()) 是不够的。
d
dshvets1

我认为最有效的方法是预先分配然后放置元素:

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;
}

这样,我们只会为每个元素调用复制构造函数,而不是先调用默认构造函数,然后再为上面列出的其他解决方案复制赋值运算符。更多说明如下。

可以使用 back_inserter,但它会在向量上调用 push_back() (https://en.cppreference.com/w/cpp/iterator/back_insert_iterator)。 emplace_back() 更有效,因为它避免了在使用 push_back() 时创建临时文件。这对于普通构造的类型不是问题,但对于非普通构造的类型(例如std::string)会产生性能影响。我们需要避免使用 size 参数构造一个向量,这会导致所有元素都默认构造(什么都不做)。例如,与使用 std::copy() 的解决方案一样。最后,vector::assign() 方法或采用迭代器范围的构造函数不是好的选择,因为它们会在集合迭代器上调用 std::distance() (以了解元素的数量)。这将导致对所有集合元素进行不必要的额外迭代,因为集合是二叉搜索树数据结构,并且它不实现随机访问迭代器。

希望有帮助。


请添加对权威的引用为什么这很快以及为什么不需要使用 back_inserter
在答案中添加了更多说明。
M
Marlon

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())); 

这在向量第一次重新分配时失败:来自 output.begin() 的迭代器失效。
M
Mostafa Wael
set<T> s;
// some code
vector<T> v;
v.assign(s.begin(), s.end());

a
ashish_nandan

COPY 函数将一个迭代器返回到目标范围的末尾(它指向复制的最后一个元素之后的元素)。

反向插入迭代器是一种特殊类型的输出迭代器,旨在允许通常覆盖元素(例如复制)的算法在容器末尾自动插入新元素。

设置操作系统;向量向量;

复制(os.begin(),os.end(),back_inserter(vec));