STL关联式容器中包含容器是否影响性能？

Question

在我的情况下，我有一个std :: map<std :: string，std :: vector<cCustomClass>>，但同样的问题也适用于std :: set。这些向量可能会变得非常大（超过100000个元素），所以如果我向地图添加更多元素，我会担心向量是否被重新分配或复制。

核心问题是：地图是否在某个时候复制大型向量，如果是，它的成本是否与std :: vector :: capacity()成比例？

如果两者的答案都是肯定的，我的选择是什么？我的第一个解决方案将是使用std :: map<std :: string，std :: vector<cCustomClass> * >和（智能指针），但我想知道是否必要。

我使用C ++ 03。如果答案取决于标准，我将感激任何关于它的评论。

- Fabian

---

向映射（或集合）中插入新元素或移除元素不会使迭代器无效，表明内容不会被移动或复制。但并非绝对保证。 - Some programmer dude

不，map 不会随意复制元素。您能展示一些执行不必要的复制的代码吗？ - Baum mit Augen

你能具体一些吗？“相当大”是多大？你想用地图做什么？ - 463035818_is_not_a_number

我认为只有当你将一个已经填充好的大向量插入到映射中时，才会出现性能问题，因为自C++11以来，只有移动插入(move-insert)可用。因此，在插入这样一个大向量时，整个向量将被复制到映射中。但这只会影响您正在插入的一个映射项，现有的映射项不会被复制。 - zett42

Answer 1

地图是否会在某个时刻复制大向量

不会。 map，set和其他关联容器是基于节点的。每个条目都独立分配节点，通过指针连接，并且在容器增长、缩小、重新平衡等情况下不需要被复制或重新分配。

您可以通过各种容器上的迭代器失效要求来保证这一点。请比较。

• std::map::insert

  不会使任何迭代器或引用失效。

  如果迭代器没有失效，那么它们指向的元素必须在内存中保持其位置，因此插入到映射中不能要求复制或移动任何现有元素。

• std::vector::insert

  如果新的 size() 大于 capacity()，则所有迭代器和引用都将失效。否则，仅插入点之前的迭代器和引用保持有效。past-the-end 迭代器也将失效。

  如果迭代器被失效，该元素可能已经移动，从而复制或移动了该值。特别是对于向量，插入后的元素必须被移动/复制以腾出空间给新元素。

  如果向量需要重新分配才能增长，则必须移动/复制所有元素到新分配的区域。

值得注意的是，尽管这对于使用map没有真正影响，但现代编译器会在可能的情况下移动元素。例如，您的大向量将被移动，这比复制它要便宜得多 - 如果您可以升级到C++11或更高版本的话。

- Useless