c++ - std::map 获取最低 n 个元素的时间

Question

std::map正如我在文档中阅读的那样，应该使用二叉搜索树来实现，并且它也会对它们进行排序。

我需要快速插入并快速检索元素。我还需要不时获取第一个最低的 N 个元素。

我在考虑使用 a std::map，这是一个不错的选择吗？如果是，我需要多长时间才能检索到最低的 N 个元素？O(n*logn)？

Answer 1

您可以使用迭代器快速读取最低的 N 个元素。从begin()到第 N-1 个元素将花费 O(n) 时间（获取下一个元素是 a 的摊销常数时间std::map）。

std::vector但是，我要注意的是，根据您的确切要求，使用带有二分查找方法的排序来实现听起来像您正在执行的操作实际上通常更快，这可能值得研究。

Answer 2

C++ 标准要求所有必需的迭代器操作（包括迭代器增量）均摊销常数时间。因此，获取容器中的前 N ​​个项目必须花费分摊O(N)时间。

Answer 3

鉴于您需要检索和 n 最小，我会说std::map是合理的选择。但是根据确切的访问模式std::vector进行排序也可能是一个不错的选择。

我不确定您所说的检索是什么意思。读取k个元素的时间是 O( k ) （假设您使用迭代器按顺序执行），删除它们的时间是 O( k log n ) （n是元素的总数；即使您使用迭代器按顺序执行）。

Answer 4

我对这两个问题都说是。