集合必须为std :: map有多大才能超出已排序的std :: vector>？集合必须为std :: map <k,v>超出排序的std :: vector <std :: pair <k,v>>？有多大？
我有一个系统，我需要几千个关联容器，并且std::map似乎在CPU缓存方面带来了很多开销。我听说过，对于小型收藏std :: vector可以更快 - 但我想知道那条线是在哪里....
编辑：我一次谈论5个项目或更少一个给定的结构。我最关心的是执行时间，而不是存储空间。我知道像这样的问题本质上是平台特定的，但我正在寻找一个“经验法则”来使用。
Billy3
这不是一个真正的大小问题，而是用法问题。
当使用模式是读取数据，然后在数据中进行查找时，排序后的向量工作正常。
当使用模式涉及修改数据（添加或删除项目）和对数据执行查询的或多或少的任意混合时，映射运行良好。
原因很简单：地图在单独查找时具有更高的开销（由于使用链接节点而不是单块存储）。但是，保持顺序的插入或删除仅具有O（lg N）的复杂性。在矢量中维护顺序的插入或删除具有O（N）的复杂性。
当然，还有各种混合结构可以帮助您考虑。例如，即使在动态更新数据时，您通常会从大量数据开始，并一次对其进行相对少量的更改。在这种情况下，您可以将数据加载到内存中，并将其添加到已排序的向量中，并将添加的对象（少数）添加到单独的向量中。由于第二个向量通常很小，因此您不必费心去整理它。如果/如果它变得太大，则对其进行分类并将其与主数据集合并。
编辑2 :(回应编辑问题）。如果你谈论的是5件或更少，你最好忽略全部以上。只需保留数据未排序，并进行线性搜索。对于这个小的集合，线性搜索和二分搜索几乎没有区别。对于线性搜索，您希望平均扫描一半项目，进行〜2.5次比较。对于二元搜索，你在谈论日志 N，这（如果我的数学是在这个时间的早晨）工作到〜2。3 - 关心或注意的差别太小（实际上，二进制搜索具有足够的开销，它可能会很容易地结束较慢）。
这个。如果你的容器中只有五件物品，那么无论你想要什么都不会有所作为。 – Puppy 2010-06-05 14:07:11
如果说“outspace”你的意思是消耗更多的空间（又称内存），那么它很有可能是矢量总是会更有效（标的实施是一个连续存储器阵列没有行吟诗人的数据，其中map是一棵树，所以每个数据意味着使用更多的空间）。然而，这取决于向量为未来的插入预留多少空间。
当它是关于时间（而不是空间）时，向量也总是更有效（做二分搜索）。但它会是extreamly不利于添加新元素（或删除它们）。
所以：没有简单的答案！查找复杂性，考虑你将要做的用途。 http://www.cplusplus.com/reference/stl/
编辑：看到你在谈论5个项目或更少：
排序涉及交换的物品。当插入std :: map时，只会涉及指针交换。矢量或地图是否会更快取决于交换两个元素的速度。
我建议您配置您的应用程序来弄明白。
如果你想要一个简单的和一般的规则，那么你的运气了 - 你需要至少考虑以下因素：
时间
内存
过去容器和元件的一定大小，分配和树指针的开销将变得未使用的存储器的成本在矢量的末端抵销 - 但到目前为止，找出这种情况是否发生以及何时发生的最简单方法是通过测量。
它是在百万分之一的项目。甚至还有......
我更想在这里内存使用和内存访问。数十万人以下，随心所欲，不会有明显的差异。现在的CPU真的很快，而且瓶颈是内存延迟。
但是，即使上百万的项目，如果你的地图<>已通过插入随机顺序的元素已经建立。当你想遍历你的地图时（按排序顺序），你最终会随机在内存中跳转，导致CPU停止内存的使用，导致性能下降。
另一方面，如果你的数以百万计的项目是载体，穿越它是真快，走的是CPU内存的优势访问预测。
至于其他已经写的，它取决于您的使用。
编辑：如果只包含5个项目，我会更多地质疑如何组织您的数千个关联容器，而不是容器本身。
每个容器都与一个文件关联。它包含与该文件相关联的数据块，例如MD5哈希。地图查找再次保存该文件的MD5的计算。此应用程序遍历目录树，以查找文件系统上的“有趣”项目。因此，每个文件一次只需要5个项目，一个用于属性，一个用于MD5，另一个用于....等等。但是由于有数千个文件，容器的性能变得很重要。 – 2010-06-04 16:08:18
这正是我的意思。不要担心容器，因为它只有几个小尺寸的项目，使用矢量来简化和预测行为（而不是映射行为和性能取决于各个项目是否分配在连续的内存位置中）。确实有所作为！）。多关注你的容器容器。 – 2010-06-04 16:30:33
我的容器容器并不重要，因为几乎没有文件在任何时候都在内存中 - 一个是具体的。 （除非需要对事物进行排序，在这种情况下，我使用的是一个deque）容器的原因是有大约35种类型的信息我想要与一个文件关联，但为这些文件中的每一个在与文件关联的类中导致该类A做得太多而且B太大。我预计一次可以使用5个，但它完全有可能更多。 – 2010-06-04 17:59:14
正如您指出的，std::map的主要问题是缓存问题。
排序的向量是一个众所周知的方法：Loki::AssocVector。
对于非常小的数据集，AssocVector应该仅仅因为缓存局部性而在插入过程中涉及拷贝，因此应该压碎映射。 AssocVector也将超出地图的只读使用。二进制搜索在那里效率更高（更少指针）。
对于所有其他用途，你需要的个人资料...
然而，有你不妨考虑一个混合的选择：使用地图的Allocator参数限制存储区里的项目被分配，从而最小化局部性参考问题（高速缓存未命中的根源）。
你也可以考虑一个范式转变：你需要排序的项目还是快速查找？
在C++中，用于快速查找的唯一STL兼容容器已经在Sorted Associative Containers方面实施多年。然而，即将到来的C++ 0x提供了期待已久的unordered_map，它可能无法执行上述所有解决方案！
无序映射在我的实现中不可用，因为A.它需要散列算法和B.它的内存开销太高。至于分配器，STL的大多数通用实现已经为标准关联容器做了这个。我怀疑你或我会写什么比Dinkumware或SGI的执行更好。 – 2010-06-04 19:14:52
@Billy：VS2005（Dinkumware）的std :: map的分配器只是简单地为map的每个节点使用new-> malloc。这对地方参考问题有什么好处？ – 2010-11-16 07:15:26
@Martin：如果你碰巧在使用2版本的VC++之前，然后继续编写自己的分配器;）（虽然我不知道为什么你要评论一个6个月大的问题......） – 2010-11-18 01:18:35
这个问题太模糊了。在什么平台上？对于什么工作量？集装箱有多大？什么是k和v？你将如何修改和访问集合？你会经常访问任意（随机）键的值吗？ – 2010-06-04 15:01:53
我不确定我是否理解这个问题？ “空白”是什么意思？要有更大的记忆？更快的搜索？你能重新解释一下这个问题吗？ 谢谢。 – utnapistim 2010-06-04 15:02:45
@utnapistim：我编辑了这个问题。我更有意义吗？ – 2010-06-04 15:30:43