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

Question

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

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

我正在考虑使用 std::map，这是一个不错的选择吗？如果是，我需要什么时间来检索最低的 N 个元素？ O(n*logn)?

Answer 1

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

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