Jon*_*han 2 c++ containers linked-list map
我正在寻找一个既能享受地图容器又能享受列表容器优势的C++容器.
我希望维护地图容器的优点:
列出我想维护的容器优势:
一个简单的示例应用程序是保存某些有效日期(业务日期,假日,其他一些重要日期......)的列表,一旦给定特定日期,您可以立即找到它"地图样式",然后找到下一个有效日期"列表样式".
std::map已经是一个已排序的容器,您可以按顺序迭代所包含的项目.但它只提供O(log(n))访问.
std::tr1::unordered_map(或std::unordered_map在C++ 0x中)具有O(1)访问权限但未排序.
你真的需要O(1)访问吗？您必须使用大型数据集并对O(log(n))进行多次查找,但速度不够快.
如果O(log(n))足够,则std::map提供您要求的所有内容.
如果您不考虑稀疏性,可以查看Boost Multi-Index库.对于稀疏性质,你可以看看Boost Flyweight库,但我想你必须自己加入这两种方法.请注意,您的要求通常是矛盾的,很难实现.例如,O(1)和项目之间的顺序难以有效维护.