在 STL 中选择具有尽可能快插入和查找的数据结构 [重复]-解网

问：

这个问题在这里已经有答案了：

用于检索集合中第 k 个最小/最大项目的数据结构（在 STL 或 Boost 中）？（1 个答案）

10天前关闭。

我正在寻找一种在 STL 中存储整数的数据结构。

我必须支持的主要操作是插入和删除，查找前 20 个元素，以及查找任何 k 的第 k 个最大元素。

我知道使用集合，我可以在对数 N 时间内实现插入和删除，在 O（1）时间内实现前 20 名，在 O（k）时间内实现前 k。

有没有办法选择一种可能更有能力找到前 k 个条目的数据结构？例如，选择 k = N/2---中位数---使用集合需要 O（N）时间，但理想情况下，我们可以有更好的东西。

C++ 数据结构 STL

评论

0赞 273K 11/12/2023

我正在寻找一种数据结构你是说容器吗？

0赞 Drew Brady 11/12/2023

是的，这就是我的意思。

1赞 Pepijn Kramer 11/12/2023

你可以从探索这个开始：en.cppreference.com/w/cpp/container。我认为了解 C++ 提供的内容比我们指出潜在的匹配更有用。只有您最了解您的要求。另请查看 en.cppreference.com/w/cpp/algorithm 可能存在有用的部分排序算法

1赞 ph3rin 11/12/2023

理论上可以支持在对数时间中查找 -th 元素，但这不会被 API 公开。使用自定义数据结构会更好。std::setk

0赞 ph3rin 11/12/2023

也许这个答案会有所帮助：用于检索集合中 k 个最小/最大项的数据结构（在 STL 或 Boost 中）？。不过，这仅支持 K 的固定值。

答：

0赞 Suhana Shaik 11/12/2023 #1

哈希表在 o（1）时间内进行插入、删除和搜索。所以这个

评论

0赞 BoP 11/12/2023

除了 O（1）的意思不是“快”，而是“总是需要大约相同的时间”。

0赞 Soundararajan 11/12/2023

learn.microsoft.com/en-us/cpp/standard-library/hash-map-class看起来hash_map不再可用，根据 MSDN，建议使用 unordered_map。learn.microsoft.com/en-us/cpp/standard-library/......

上一个：使用 unordered_set/unordered_multiset 的迭代器失效

下一个：为什么我可以将<unordered_map>与引用一起使用，但不能将<stack>与它们一起使用？