具有快速查找功能的 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 中，是否有 standard/common 或最佳实践方法来实现具有列表的所有属性以及快速 find 的容器（以及, 例如 remove)?或者，这样的容器类型是否已经存在？也许是 C++20？

Edit/Nb: 列表中元素的顺序是相关的，因此不能直接使用std::map。

Answer 1

由于 std::list 的迭代器在插入和删除过程中仍然有效（当然，您删除的元素除外），您可以维护类型为 std::map <my_key, my_list_iterator> 的二级数组数据结构（或 std::unordered_map如果那个更合适）。

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

Answer 2

当前答案的部分和非常原始（原型）实现（保罗·桑德斯）：

 #include <unordered_map>
 #include <list>
 #include <iterator>
 #include <iostream>

 using std::unordered_map;
 using std::list;
 using std::make_pair;
 using std::begin;
 using std::end;
 using std::prev;
 using std::cout;

 template <typename T>
 struct fastlist {
    list<T> l;
    unordered_map<T, typename list<T>::iterator> m;
     
    void push_front(T e) {
        l.push_front(e);
        m.insert(make_pair(e, begin(l)));
    }

    void push_back(T e) {
        l.push_back(e);
        m.insert(make_pair(e, prev(end(l))));
    }

    auto find(T e) {
        return m[e];
    }

    void remove(T e) {
        auto it = m[e];
        m.erase(*it);
        l.erase(it);
    }
};

int main() {          // Giving it a spin
    fastlist<int> f;

    f.push_back(3);
    f.push_back(4);
    f.push_back(5);
    f.push_front(2);
    f.push_front(1);
    f.remove(3);
    f.remove(5);
    f.remove(1); 
    f.push_back(200); 
    f.push_front(-100);
    cout << *f.find(4);
}

演示：https://godbolt.org/z/jdnvdM

除此之外，此原型缺少实现自定义容器的迭代器方法，相关信息请参见：How to implement an STL-style iterator and avoid common pitfalls?。

（编辑：Ted Lyngmo 在下面的评论中提供了一个更好的版本：https://godbolt.org/z/6xfbq7）。

这种容器要是能提供out-of-the盒子就好了。以及从更基本的容器建模 on/derived 的其他容器，但增加了反映特定使用情况的特定性能优势。如果有人知道任何提供这种专用容器的库，请告诉;-)

Answer 3

关于如何使用 Boost MultiIndex 实现具有所需功能的容器的非常简短且易于理解的指南（基于单个示例）

对我来说，hands-on比formal-styledhttps://www.boost.org/doc/libs/release/libs/multi_index/doc/tutorial/basics.html#list_fast_lookup更容易理解，它涵盖了所有可能的用途（尽管也使用示例）。

具有快速查找功能的 C++ 列表

C++ list with fast find

c++

containers

list

std

c++17