向量拷贝构造函数C++：它必须是线性时间吗？

Question

我有一个包含STL map类型对象的向量，并且我做了vector.push_back(some map)。

不幸的是，这调用了map copy构造函数，并且浪费了大量时间。我知道我可以通过保留一个指向映射的(智能)指针向量来解决这个问题--但这让我想知道--我读到STL无论如何都会将它的数据保存在堆上而不是堆栈上-那么为什么复制ctor不是通过简单地复制指针来O(1) time呢？

Answer 1

如果在将副本推回向量后不再需要原始贴图，请编写：

some_vector.push_back(std::move(some_map));

如果您还没有C++11编译器，请添加一个空映射，然后将其与原始映射进行交换：

some_vector.resize(some_vector.size() + 1);
some_vector.back().swap(some_map);

Answer 2

直接回答您的问题:要做到这一点，必须从某种写入时复制机制开始--当您将某些内容放入向量中时，它必须是原始数据的副本(或者至少要像原始数据一样)。例如，如果我将一个地图推送到我的向量上，然后从原始地图中删除一个项目，该项目应该仍然存在于推送到向量上的地图的副本中。

然后，它必须跟踪所有指针，并确保指针对象(在本例中为map )保持有效，直到所有这些指针自身被销毁。当然，这样做是可能的。例如，相当多的语言在很大程度上出于这个原因提供了垃圾收集。其中大多数改变了事物的语义，所以当(例如)创建一个映射的向量时，将一个映射放入向量中具有引用语义--即，当您修改原始映射时，这将更改您放入其他集合中的任何“副本”。

正如您所观察到的，如果您真的想要，您可以在C++中执行上述任何/所有操作。它现在没有这样做的原因是，大多数C++标准库都是围绕值语义而不是引用语义构建的。两者都不是(无论如何)完全有效和合理的方法--一些语言采用一种，另一些语言采用另一种。两者都可以很好地工作，但是值语义恰好是在C++中做出的选择。

Answer 3

如果要复制指针，请创建指向map的指针的vector。你可以做到的。

std::vector<std::map<A,B>* > x;

它不会自动执行此操作，因为它不知道您希望由谁来管理内存。当vector超出作用域时，是否应该销毁map的对象。如果原始map仍在作用域中，该怎么办？