在 STL 中，哪个是更好的 Map 或 Vector。假设我有一组需要删除的记录，那么我应该更喜欢什么 - std::map 或 std::vector。为什么？
问问题
73 次
2 回答
2
如果您没有键值对之类的东西并且只有您拥有的值，您可能应该考虑使用 Set 而不是 Map。我假设这是因为您在谈论使用矢量
于 2012-10-20T08:35:12.733 回答
0
如果您需要以不可预知的顺序添加和删除许多记录，则映射或集合可能会执行得更好。这是因为删除一个条目只需要与映射或集合的大小成正比的对数时间，而从向量中删除一个条目所花费的时间与向量的大小成正比。unordered_map / unordered_set 可能会更好——删除记录的成本通常是恒定的。
背景：
- vector 是一个数组，因此如果删除单个元素，则所有其他元素都需要向左移动一个。
- map 和 set 是红黑树（http://en.wikipedia.org/wiki/Red-black_tree）
- unordered_map 和 unordered_set 是哈希表（http://en.wikipedia.org/wiki/Hash_table）
于 2012-10-20T08:27:37.307 回答