C++ 列表与快速查找

Question

我正在与一个std::list.

元素按“插入顺序”出现在列表中，而不是根据元素的值。

当std::find()-ing 一个元素时，必须搜索整个列表。

为了加快从 O(n) 到 O(log(n)) 的“查找”速度，我可以自己实现一个哈希映射来存储元素std::list位置，或者我可以使用 boost 多索引，https://www.boost .org/doc/libs/release/libs/multi_index/doc/tutorial/basics.html#list_fast_lookup。

问题：如今，使用 C++17，是否有一种标准/通用或最佳实践方法来实现具有列表所有属性以及快速find（例如 remove）的容器？或者说，这样的容器类型是否已经存在？也许是 C++20？

编辑/注意：列表中元素的顺序是相关的，因此不能直接使用 std::map 。

Answer 1

由于 a 的迭代器std::list在插入和删除时仍然有效（当然，删除的元素除外），因此您可以维护类型的辅助数组数据结构std::map <my_key, my_list_iterator>（或者std::unordered_map如果更合适的话，可以维护 a ）。

然后，每当您添加或删除列表条目时，请对您的列表条目执行相同的操作std::map / unordered_map，然后就完成了。当然，您可以以 O(log(n)) （或 O(1)）复杂度进行搜索。