考虑到在主内存中搜索时缓存和数据局部性的积极影响，我倾向于使用 std::vector<>与 std::pair<> -喜欢键值项并对两者执行线性搜索，如果我知道键值项的总量永远不会“太大”而不会严重影响性能。
最近我遇到了很多情况，我事先知道我将有大量键值项，因此选择了 std::map<>从头开始。
我想知道在上述情况下，您是如何决定使用合适的容器的。
你会吗
- 总是使用
std::vector<>(或类似)？ - 总是使用
std::map<>(或类似)？ - 对项目计数范围内的哪一个比另一个更可取有直觉吗？
- 完全不同的东西？
谢谢!
最佳答案
我很少将 std::vector 与线性搜索一起使用(除非与二进制搜索结合使用，如下所述)。我想对于足够小的数据量会更好，但是对于那么少的数据，任何东西都不太可能提供巨大的优势。
根据使用模式，在 std::vector 上进行二分搜索是有意义的。当您需要在使用过程中定期更新数据时，std::map 非常适用。然而，在相当多的情况下，您加载了一些数据，然后使用了这些数据——但在您加载数据之后，它大多保持静态(即，即使有变化，也非常小)。
在这种情况下，将数据加载到 vector 中、在必要时对其进行排序，然后对数据进行二进制搜索(例如 std::lower_bound 、 std::equal_range )非常有意义。这几乎提供了两全其美的优势——低复杂度的二进制搜索和来自高引用位置的良好缓存使用(即， vector 是连续的，而不是 std::map 的链接结构) .缺点当然是插入和删除很慢——但这是我第一次使用你的原始想法——将新插入的数据单独存储，直到达到某个限制，然后才将其与其余数据一起排序数据，因此单个搜索包括对数据主体的二分搜索，然后是对(少量)新插入数据的线性搜索。
关于c++ - 何时为键值数据选择 std::vector 而不是 std::map？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/2722442/