c++ - 简单高效的C++容器，具有map和list容器的特点

Question

我正在寻找一个将享受 map 容器和列表容器优势的 C++ 容器。

ma​​p 我想维护的容器优势:

• O(log(n)) 访问
• 运算符[] 易用性
• 自然稀疏

列出我想维护的容器优势:

• 在项目之间有顺序
• 能够轻松地遍历列表更新:通过基于键或值的排序

一个简单的示例应用程序是保存特定有效日期的列表(工作日期、假期、其他一些重要日期集......)，一旦给定特定日期，您可以立即找到它“ map 样式”并且然后找到下一个有效日期“列表样式”。

Answer 1

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 提供您所要求的一切。