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

问：

我正在使用 .std::list

元素按“插入顺序”显示到列表中，而不是根据元素的值显示。

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

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

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

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

C++ 列表容器 C++17 标准

谢谢，这就是我想做的，但我突然想到，这种需求对于存在现成的标准容器来说已经足够普遍了。我会接受你的回答，因为我认为它回答了我的问题：什么是/一种“标准”的方式。然后，我将在提供封装和单点访问的类中实现这种同步簿记。谢谢！

0赞 mrchance 10/27/2020 #2

目前答案的部分和非常原始的（原型）实现 https://stackoverflow.com/a/64539693/11608725（由 Paul Sanders 撰写）：

 #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

除其他外，此原型缺少用于实现自定义容器的迭代器方法，有关此内容的信息，请参阅：如何实现 STL 样式的迭代器并避免常见的陷阱？

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

如果这种容器开箱即用，那真的会很整洁。以及其他基于更基础的容器建模/派生的容器，但增加了反映特定使用情况的特定性能优势。如果有人知道任何提供这种专用容器的图书馆，请告诉;-）

有些事情必须改变。如果该元素不存在，您将创建一个映射条目，并返回默认构造的 .支持插入重复项，但地图不支持。插入两个并删除一个，然后您将得到一个包含一个条目的列表，而地图是空的。如果 you 和 element 并更改值，则不会在地图中进行相应的更改。我在这里做了一些调整，但如果你改变列表中一个条目的值，它就会被破坏。find()list<T>::iteratorlistfind

1赞 mrchance 10/27/2020

@TedLyngmo 谢谢！我会让“例子”保持原样，但任何想要修改它的人当然都比福康多。我还认为我不会自己制作一个完整的容器，因为我没有信心能够使它完全健壮 + 完整 + 通用 + 快速。我将寻找其他人的解决方案和/或一些专有/专业级（但免费）的容器。感谢！

0赞 mrchance 10/27/2020

@TedLyngmo顺便说一句，你的 godbolt.org/z/6xfbq7 很整洁！！也许您离成为专业发布级“index_list”容器的实现者不远了？轻推轻推，我鼓励你;-）谢谢！

1赞 Ted Lyngmo 10/27/2020

:-)谢谢，但我想如果我需要具有这些功能的容器，我会依靠 boost。

1赞 mrchance 10/27/2020

@TedLyngmo是的，当然，Ive 在 stackoverflow.com/a/39510606/11608725 上面添加了这个 stackoverflow 答案，以给出如何使用 Boost MultiIndex 的实际示例

0赞 mrchance 10/27/2020 #3

非常简短且易于理解的指南（基于单个示例），介绍如何使用 Boost MultiIndex 实现具有所需功能的容器 https://stackoverflow.com/a/39510606/11608725

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

上一个：如何遍历嵌套向量？

下一个：C++ - std：：list.erase（）不删除元素

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

C++ list with fast find

评论

评论

评论