c++ - 哪个STL容器？

Question

我需要一个容器(不一定是 STL 容器)，它可以让我轻松地执行以下操作:

• 在任意位置插入和移除元素
• 通过索引访问元素
• 以任意顺序遍历元素

我使用了 std::list，但它不允许我在任何位置插入(它允许，但为此我必须遍历所有元素，然后在该位置插入我想要，这很慢，因为列表可能很大)。那么您能推荐任何有效的解决方案吗？

Answer 1

我不太清楚“以任何顺序迭代元素”是什么意思 - 这是否意味着您不关心顺序，只要您可以迭代，或者您希望能够使用任意定义的标准进行迭代？这些是非常不同的条件!

假设您的意思是迭代顺序无关紧要，那么您会想到几种可能的容器:

std::map [通常是红黑树]

• 插入、删除和访问都是 O(log(n))
• 迭代按索引排序

hash_map 或 std::tr1::unordered_map [哈希表]

• 插入、删除和访问都是(大约)O(1)
• 迭代是“随机的”