C++中有排序集合吗？

Question

在Smalltalk中，你可以创建一个sortedCollection，这意味着你可以添加一个元素，并将其插入到正确的位置。

C++中是否有类似的东西？甚至更好的是，是否有类似于sortedQueue的东西，当你添加一个元素时，它会将其排序到一个队列结构中，你只需要弹出第一个元素就可以了？

我研究了set，这符合我的排序需求，但它是一个无序集合。我正在寻找尽可能小的运行时间。

- Jim

---

我查了一下 set，在排序方面正是我所需要的，但它是一个无序集合。什么？set 是有序的，而 unordered_set 才是无序的。 - ildjarn

你错了，std::set 是有序的。 - Nikolai Fetissov

set 是有序的，默认使用 std::less，因此通过循环遍历 myset.begin() 到 myset.end() 将按升序遍历元素。 - Node

@ildjarn和@Fetissov，我想我可能误读了。谢谢你们的澄清。 - Jim

Answer 1

在C++标准库中有四个排序容器：

std::set - 一组唯一值的排序序列。
std::map - 一组唯一键/值对的排序序列。
std::multiset - 一组可能重复的值的排序序列。
std::multimap - 一组可能重复的键/值对的排序序列。

如果您只需要一个排序队列，那么您要找的是std::priority_queue，它是一个容器适配器而不是一个独立的容器。

#include <queue>

int main()
{
    std::priority_queue<int> q;
    q.push(2);
    q.push(3);
    q.push(1);
    assert(q.top() == 3); q.pop();
    assert(q.top() == 2); q.pop();
    assert(q.top() == 1); q.pop();
    return 0;
}

如果你想在一个priority_queue中存储自定义类型，那么你需要为你的类定义operator<。

class Person
{
public:
    Person(int age) : m_age(age) {}

    bool operator<(const Person& other) const
    {
        return m_age < other.m_age;
    }

private:
    int m_age;
};

创建一个以Person为元素类型的priority_queue，会得到一个队列，其中最年长的人位于队列最前面。

- Peter Alexander

Answer 2

STL容器选择流程图（来源于这个问题）：

注意：本人翻译仅供参考，如需精准翻译请联系专业翻译人员。

- Igor

---

即使看了这个图表，我也无法确定在我的问题中使用哪一个最好http://stackoverflow.com/questions/9329011/mfc-dictionary-collection-with-key-unicity-and-ordering-by-position - sergiol

好的图表！但是链接已经失效了。无论如何，这里有更新的 C++11 版本：https://dev59.com/TXRB5IYBdhLWcg3w6LV2#22671607。 - MaMazav

Answer 3

您似乎在寻找位于<queue>头文件中的 std::priority_queue，它与IT技术有关。使用push()可以将元素插入到优先队列中；使用top()可以获取当前优先队列中最大的元素（或最小的元素，这取决于您如何实现operator<）；使用pop()可以删除最大/最小的元素。

据我所知，它是用堆来实现的，使每个push和pop操作的时间复杂度为 O(lg n)。查看顶部元素是在 O(1) 的时间内完成的。

- Aasmund Eldhuset

Answer 4

std::map 是用于排序容器的。

std::queue 是用于队列的。

std::priority_queue 是用于排序队列的。

- littleadv

---

嗯，我不认为map是我要找的。我可能会直接使用set，但是没有将它们合并成一个ADT的东西吗？ - Jim

@Jim - 你需要什么？如你所描述的sortedQueue是std::priority_queue。我提到了map，因为你要求一个通用的排序容器（至少这是我从你对sortedCollection的讨论中理解的）。 - littleadv

我认为优先队列正是我所需要的，谢谢。我想当时我发表评论时它还不存在。 - Jim

std::set是一种排序容器。而map则是一种键值对容器，其中数据是通过一个单独的键进行排序的。 - Martin York

Answer 5

std::set 是一个有序的集合；迭代它会按顺序返回元素（按照 < 运算符或自定义谓词定义的顺序）。查找和删除第一个元素的时间复杂度为 O(1)。

或者，您可以使用 std::priority_queue，它基本上是一个堆，允许高效插入和删除最小项。

实际上，要找到无序（哈希）容器更难一些 - 它们不是原始标准的一部分，尽管它们在非标准形式中广泛可用。

当然，如果项目数量不是非常大，则可能会发现仅将项目保存在排序向量中速度更快，即使理论上较慢。

- Alan Stokes