C++中是否有任何Sorted Collections？

Question

在Smalltalk中,您可以创建一个sortedCollection,也就是说您可以添加一个元素,然后将其插入到正确的位置.

在C++中有这样的东西吗？或者甚至更好的是有类似sortedQueue的东西,这样当你添加一个元素时,它会将它排序成一个类似于结构的队列,你可以直接弹出第一个元素？

我查看了set,​​这是我在排序方面所需要的,但它是一个无序的集合.我正在寻找一个小的运行时间.

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;
}

如果您想将自己的类型存储在a中,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;
};

创建priority_queue的Person则s会给你在前面的最古老的一队人.

Answer 2

STL容器选择流程图(来自这个问题):

Answer 3

您好像正在寻找std::priority_queue位于<queue>头文件中的.使用push(),您可以将元素插入优先级队列; 使用top(),您将获得队列中当前最大的元素(或者最小的元素,具体取决于您的实现方式operator<); 并且pop(),您将删除最大/最小元素.

据我所知,它是用堆实现的,这使得每个推送和弹出操作的时间复杂度为O(lg n).只需查看顶部元素即可在O(1)中完成.

Answer 4

std :: map用于已排序的容器

std :: queue for queue.

排序队列的std :: priority_queue