我正在寻找一个 C++ 容器，它将同时享受地图容器和列表容器的优点。
我想要保持的 map 容器优势：
- O(log(n)) 访问
- 运算符[] 易用性
- 稀疏性
list 我想要保持的容器优势：
- 拥有项目之间的顺序
- 能够轻松地遍历列表更新：通过基于键或值的排序顺序
一个简单的示例应用程序是保存某些有效日期的列表（营业日期，假期，一些其他重要日期的集合...），一旦给出特定日期，您可以立即找到它“地图样式”，然后找到下一个有效日期“列表样式”。
I'm looking for a C++ container that will enjoy both map container and list container benefits.
map container advantages I would like to maintain:
- O(log(n)) access
- operator[] ease of use
- sparse nature
list container advantages I would like to maintain:
- having an order between the items
- being able to traverse the list easily UPDATE: by a sorting order based on the key or value
A simple example application would be to hold a list of certain valid dates (business dates, holidays, some other set of important dates...), once given a specific date, you could find it immediately "map style" and then find the next valid date "list style".
发布评论
评论（8）
std::map已经是一个排序容器，您可以在其中按顺序迭代所包含的项目。但它只提供 O(log(n)) 访问。std::tr1::unordered_map（或 C++0x 中的std::unordered_map）具有 O(1) 访问权限，但未排序。您真的需要 O(1) 访问权限吗？您必须使用大型数据集并进行多次查找，以防止 O(log(n)) 不够快。
如果 O(log(n)) 就足够了，std::map 可以提供您所要求的一切。
std::mapis already a sorted container where you can iterate over the contained items in order. It only provides O(log(n)) access, though.std::tr1::unordered_map(orstd::unordered_mapin C++0x) has O(1) access but is unsorted.Do you really need O(1) access? You have to use large datasets and do many lookups for O(log(n)) not being fast enough.
If O(log(n)) is enough,
std::mapprovides everything you are asking for.如果不考虑稀疏性，可以看看 Boost 多索引库。对于稀疏性质，您可以查看 Boost Flyweight 库，但我想你必须自己加入这两种方法。请注意，您的要求通常是矛盾的并且难以实现。例如，O(1) 和项目之间的顺序很难有效维护。
If you don't consider the sparse nature, you can take a look at the Boost Multi-Index library. For the sparse nature, you can take a look at the Boost Flyweight library, but I guess you'll have to join both approaches by yourself. Note that your requirements are often contradictory and hard to achieve. For instance, O(1) and order between the items is difficult to maintain efficiently.
映射通常以树的形式实现，因此具有对数查找时间，而不是 O(1)，但听起来您想要一个排序的关联容器。哈希映射有 O(1) 最好情况，O(N) 最坏情况，所以也许这就是你的意思，但它们没有排序，而且我认为它们还不是标准库的一部分。
在 C++ 标准库中，
map、set、multimap和multiset是排序关联容器，但是您有放弃 O(1) 查找要求。Maps are generally implemented as trees and thus have logarithmic look up time, not O(1), but it sounds like you want a sorted associative container. Hash maps have O(1) best case, O(N) worst case, so perhaps that is what you mean, but they are not sorted, and I don't think they are part of the standard library yet.
In the C++ standard library,
map,set,multimap, andmultisetare sorted associative containers, but you have to give up the O(1) look up requirement.根据 Stroustrup 的说法，映射的
[]运算符的复杂度为 O(log(n))。如果你用列表尝试这样的事情，这比你得到的 O(n) 要好得多，但它绝对不是 O(1) 。为您提供[]运算符的唯一容器是向量。除此之外，您已经可以使用地图完成所有清单上的事情。迭代器对它们工作得很好。所以如果我是你，我会坚持使用地图。
According to Stroustrup, the
[]operator for maps is O(log(n)). That is much better than the O(n) you'd get if you were to try such a thing with a list, but it is definitely not O(1). The only container that gives you that for the[]operator is vector.That aside, you can already do all your listy stuff with maps. Iterators work fine on them. So if I were you, I'd stick with map.
地图已经做到了这两点。它们是排序的，因此您从 begin() 开始并遍历，直到到达 end()。当然，您可以从任何映射迭代器开始；您可能会发现 map 的 find、lower_bound 和相关方法很有帮助。
Maps already do both. They are sorted, so you start at begin() and traverse until you hit end(). You can, of course, start at any map iterator; you may find map's find, lower_bound, and related methods helpful.
您可以将数据存储在列表中，并拥有列表迭代器的映射，使您能够找到实际的列表元素本身。这种东西是我经常用于 LRU 容器的东西，我想要一个列表，因为我需要将访问的元素移动到末尾以使其成为最近访问的元素。您可以使用 splice 函数来执行此操作，并且自 2003 年标准以来，只要将迭代器保留在同一列表中，它就不会使迭代器无效。
You can store data in a list and have a map to iterators of your list enabling you to find the actual list element itself. This kind of thing is something I often use for LRU containers, where I want a list because I need to move the accessed element to the end to make it the most recently accessed. You can use the splice function to do this, and since the 2003 standard it does not invalidate the iterator as long as you keep it in the same list.
这个怎么样：所有日期都存储在
std::list中，但您可以使用辅助结构stdext::hash_map 来查找它::迭代器> 。一旦有了列表的迭代器，访问下一个元素就很简单了。在您的 STL 实现中，它可能是std::tr1::unordered_map而不是stdext::hash_map，并且有boost::unordered_map作为出色地。How about this one: all dates are stored in
std::list<Date>, but you look it up with helper structurestdext::hash_map<Date, std::list<Date>::iterator>. Once you have iterator for the list access to the next element is simple. In your STL implementation it could bestd::tr1::unordered_mapinstead ofstdext::hash_map, and there isboost::unordered_mapas well.您永远找不到一个既满足
O(log n)访问权限又满足有序性质的容器。原因是，如果容器是有序的，那么它本质上必须支持任意顺序。这就是有序性质的含义：您可以准确决定任何元素的位置。因此，要找到任何元素，您必须猜测它在哪里。它可以在任何地方，因为您可以将它放置在任何地方！请注意，有序序列与排序序列不同。排序性质意味着任何两个元素之间都存在一种特定的排序关系。有序性意味着元素之间可能存在多个排序关系。
You will never find a container that satisfies both
O(log n)access and an ordered nature. The reason is that if a container is ordered then inherently it must support an arbitrary order. That's what an ordered nature means: you get to decide exactly where any element is positioned. So to find any element you have to guess where it is. It can be anywhere, because you can place it anywhere!Note that an ordered sequence is not the same as a sorted sequence. A sorted nature means there is one particular ordering relation between any two elements. An ordered nature means there may be more than one ordering relation among the elements.