为什么在C++中插入向量是有效的

  • 本文关键字:向量 有效 插入 C++ c++
  • 更新时间 :
  • 英文 :


来源https://learn.microsoft.com/en-us/cpp/cpp/value-types-modern-cpp?view=vs-2019年,我们有:

#include <set>
#include <vector>
#include <string>
using namespace std;
//...
set<widget> LoadHugeData() {
set<widget> ret;
// ... load data from disk and populate ret
return ret;
}
//...
widgets = LoadHugeData();   // efficient, no deep copy
vector<string> v = IfIHadAMillionStrings();
v.insert( begin(v)+v.size()/2, "scott" );   // efficient, no deep copy-shuffle
v.insert( begin(v)+v.size()/2, "Andrei" );  // (just 1M ptr/len assignments)
//...
HugeMatrix operator+(const HugeMatrix& , const HugeMatrix& );
HugeMatrix operator+(const HugeMatrix& ,       HugeMatrix&&);
HugeMatrix operator+(      HugeMatrix&&, const HugeMatrix& );
HugeMatrix operator+(      HugeMatrix&&,       HugeMatrix&&);
//...
hm5 = hm1+hm2+hm3+hm4+hm5;   // efficient, no extra copies

我想我可以看到集合是如何高效的,集合将其数据存储在堆上,所以我假设返回集合会创建集合的副本,其中底层数组中的每个指针都指向与我们要复制的集合相同的内存位置。我想你可以通过使用std::move来更快地实现这一点,它甚至不必使用指向相同内存位置的新指针,而是使用相同的指针。

如果C++中的向量是连续存储的,我看不出插入到向量中是如何有效的。如果它们被连续存储,我认为你肯定必须做一个";复制混洗";。我错过了什么?

我假设返回集合会创建集合的副本,其中底层数组中的每个指针。。。

你的假设是错误的。CCD_ 1不具有";底层阵列";。它通常被实现为一个平衡的搜索树。

其中底层数组中的每个指针都指向与我们要从中复制的集合相同的内存位置。

集合的副本不引用原始集合的数据。这将是一个深度复制;每个元素都被复制到新的集合中。

然而,在本例中,您返回了一个局部变量,因此它将被移动而不是复制。移动是一个浅层副本,生成的对象确实会引用其他对象最初拥有的数据。

然而,可能发生的情况是,编译器进行优化,并使其成为本地声明的集合,从而实际创建在函数外部使用的集合。正因为如此;魔术";,练习中只有一套,不需要复制也不需要移动。

我想你可以通过使用std::move 来更快地实现这一点

实际上,return std::move(local)几乎从未比return local快过。Latter无论如何都会调用move构造函数,但也允许前面提到的优化。std::move阻止了这种优化。

如果C++中的向量被连续存储,我看不出插入到向量中是如何有效的。

"效率";是主观的,在很大程度上取决于上下文。

当然,基于节点的数据结构,如列表和集合,对于插入有非常好的最坏情况——O(1(渐近复杂度与向量的O(N(。但这通常与你的项目无关。通常更相关的是数据结构与CPU缓存的配合程度。简而言之,数组与缓存配合得很好,而链接节点则不然。

注意,向量是用一个聪明的算法实现的,该算法允许将N个元素插入向量的后面,以具有O(N(渐近复杂度,这与链接节点结构相同。

因此,当你知道向量将有多少个元素,并且可以按顺序插入元素时,你可以简单地在最初保留足够的空间,然后就不需要洗牌了。

如果它们被连续存储,我认为你肯定必须做一个"复制混洗";。我错过了什么?

它确实需要进行洗牌。但它比复制混洗更有效,因为它是移动混洗,移动std::string是有效的。

由于拷贝省略或返回值优化,LoadHugeData的第一个赋值是有效的,set实际上从未被复制。

vector中间的插入确实需要移动一些或全部现有项。这样做更有效率,因为移动语义不需要进行任何新的分配或复制——新项将简单地接管旧项的内部,包括指向实际字符串缓冲区的指针。不需要深度复制。

我认为注释意味着字符串被移动,而不是深度复制。它仍然是一个关于向量中字符串数量的线性时间运算,但它不会复制字符串中的所有字符(可能除了SSO(。这就是";只有1M ptr/len分配";方法我想你可以考虑一下";高效的";与复制每个字符相比。

最新更新