C++ 中是否有排序集合？
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/6498098/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
Are there any Sorted Collections in C++?
提问by Jim
In Smalltalk, you can create a sortedCollection, which is to say that you can add an element and it would insert it into the correct location.
在 Smalltalk 中，您可以创建一个 sortedCollection，也就是说您可以添加一个元素并将其插入到正确的位置。
Is there anything like this in C++? Or even better is there anything like a sortedQueue, such that when you add an element, it would sort it into a queue like structure that you can just pop the first element off of?
在 C++ 中有这样的东西吗？或者更好的是有没有像 sortedQueue 这样的东西，这样当你添加一个元素时，它会将它排序到一个类似队列的结构中，你可以从中弹出第一个元素？
I looked into set, this is what I need in terms of sorting, but it is an unordered collection. I am looking for a small run time as possible.
我查看了集合，这是我在排序方面所需要的，但它是一个无序的集合。我正在寻找尽可能小的运行时间。
回答by Peter Alexander
There are four sorted containers in the C++ standard library:
C++标准库中有四种排序容器：
std::set- A sorted sequence of unique values.std::map- A sorted sequence of unique key/value pairs.std::multiset- A sorted sequence of values (possible repeats).std::multimap- A sorted sequence of key/value pairs (possible repeats).
std::set- 唯一值的排序序列。std::map- 唯一键/值对的排序序列。std::multiset- 排序的值序列（可能重复）。std::multimap- 键/值对的排序序列（可能重复）。
If you just want a sorted queue, then what you are looking for is std::priority_queue, which is a container adaptorrather than a stand-alone container.
如果你只是想要一个排序的队列，那么你要找的是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;
}
If you want to store your own types in a priority_queuethen you need to define operator<for your class.
如果你想在 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;
};
Creating a priority_queueof Persons would then give you a queue with the oldest people at the front.
创建一个priority_queueof Persons 会给你一个队列，最老的人在前面。
回答by Aasmund Eldhuset
You seem to be looking for the std::priority_queue, which is located in the <queue>header file. With push(), you can insert an element into the priority queue; with top(), you will get the currently largest element in the queue (or the smallest one, depending on how you implement operator<); and with pop(), you will remove the largest/smallest element.
您似乎正在寻找std::priority_queue位于<queue>头文件中的 。使用push()，您可以将元素插入优先级队列；有top()，你会得到在队列中的最大的当前元素（或最小的一个，这取决于你如何实现operator<）; 并使用pop()，您将删除最大/最小的元素。
As far as I know, it's implemented with a heap, which makes the time complexity of each push and pop operation O(lg n). Simply looking at the top element is done in O(1).
据我所知，它是用堆实现的，这使得每次推送和弹出操作的时间复杂度为O(lg n)。简单地查看顶部元素是在O(1) 中完成的。
回答by littleadv
std::mapfor sorted container
用于排序容器的std::map
std::queuefor queue.
队列的 std::queue。
std::priority_queuefor sorted queue
std::priority_queue用于排序队列
回答by Alan Stokes
std::setis an ordered collection; iterating over it will give you the elements in order (either as defined by the <operator or a custom predicate). Finding and removing the first element are O(1).
std::set是有序集合；迭代它会按顺序为您提供元素（由<运算符或自定义谓词定义）。查找和删除第一个元素是 O(1)。
Alternatively you could use std::priority_queue, which is basically a heap and allows efficient insert and least item removal.
或者，您可以使用std::priority_queue，它基本上是一个堆，允许有效插入和最少删除项目。
In fact it's harder to find unordered (hashed) containers - they weren't part of the original standard, although they were widely available in non-standard form.
事实上，很难找到无序（散列）容器——它们不是原始标准的一部分，尽管它们以非标准形式广泛可用。
Of course you may find that simply holding your items in a sorted vector is faster, even if it is theoretically slower, if the number of items is not significantly large.
当然，您可能会发现简单地将您的项目保存在排序向量中会更快，即使理论上它更慢，如果项目的数量不是很大。
