C++ STL 中是否有已排序的容器？
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/15582504/
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
Is there a sorted container in the STL?
提问by Igor
Is there a sorted container in the STL?
STL 中是否有已排序的容器？
What I mean is following: I have an std::vector<Foo>, where Foois a custom made class. I also have a comparator of some sort which will compare the fields of the class Foo.
我的意思是：我有一个std::vector<Foo>，哪里Foo是一个定制的类。我还有一个比较器可以比较类的字段Foo。
Now, somewhere in my code I am doing:
现在，在我的代码中我正在做的某处：
std::sort( myvec.begin(), myvec.end(), comparator );
which will sort the vector according to the rules I defined in the comparator.
这将根据我在比较器中定义的规则对向量进行排序。
Now I want to insert an element of class Foointo that vector. If I could, I would like to just write:
现在我想将 class 的一个元素插入Foo到该向量中。如果可以，我只想写：
mysortedvector.push_back( Foo() );
and what would happen is that the vector will put this new element according to the comparator to its place.
并且会发生的是，向量将根据比较器将这个新元素放置到它的位置。
Instead, right now I have to write:
相反，现在我必须写：
myvec.push_back( Foo() );
std::sort( myvec.begin(), myvec.end(), comparator );
which is just a waste of time, since the vector is already sorted and all I need is to place the new element appropriately.
这只是浪费时间，因为向量已经排序，我需要的只是适当地放置新元素。
Now, because of the nature of my program, I can't use std::map<>as I don't have a key/value pairs, just a simple vector.
现在，由于我的程序的性质，我不能使用，std::map<>因为我没有键/值对，只有一个简单的向量。
If I use stl::list, I again need to call sort after every insertion.
如果我使用stl::list，我再次需要在每次插入后调用 sort 。
回答by Jason
Yes, std::set, std::multiset, std::map, and std::multimapare all sorted using std::lessas the default comparison operation. The underlying data-structure used is typically a balanced binary search tree such as a red-black tree. So if you add an element to these data-structures and then iterate over the contained elements, the output will be in sorted order. The complexity of adding N elements to the data-structure will be O(N log N), or the same as sorting a vector of N elements using any common O(log N) complexity sort.
Yes, std::set, std::multiset, std::map, 和std::multimap都std::less作为默认比较操作进行排序。使用的底层数据结构通常是平衡二叉搜索树，例如红黑树。因此，如果您向这些数据结构添加一个元素，然后迭代包含的元素，输出将按排序顺序。向数据结构添加 N 个元素的复杂度将是 O(N log N)，或者与使用任何常见的 O(log N) 复杂度排序对 N 个元素的向量进行排序相同。
In your specific scenario, since you don't have key/value pairs, std::setor std::multisetis probably your best bet.
在您的特定场景中，因为您没有键/值对，std::set或者std::multiset可能是您最好的选择。
回答by honk
I'd like to expand on Jason's answer. I agree to Jason, that either std::setor std::multisetis the best choice for your specific scenario. I'd like to provide an example in order to help you to further narrow down the choice.
我想扩展杰森的回答。我同意杰森，std::set或者std::multiset是您特定场景的最佳选择。我想提供一个示例，以帮助您进一步缩小选择范围。
Let's assume that you have the following class Foo:
让我们假设您有以下课程Foo：
class Foo {
public:
Foo(int v1, int v2) : val1(v1), val2(v2) {};
bool operator<(const Foo &foo) const { return val2 < foo.val2; }
int val1;
int val2;
};
Here, Foooverloads the <operator. This way, you don't need to specify an explicit comparator function. As a result, you can simply use a std::multisetinstead of a std::vectorin the following way. You just have to replace push_back()by insert():
在这里，Foo重载<运算符。这样，您无需指定显式比较器函数。因此，您可以通过以下方式简单地使用 astd::multiset代替 a std::vector。你只需要替换push_back()为insert()：
int main()
{
std::multiset<Foo> ms;
ms.insert(Foo(1, 6));
ms.insert(Foo(2, 5));
ms.insert(Foo(3, 4));
ms.insert(Foo(1, 4));
for (auto const &foo : ms)
std::cout << foo.val1 << " " << foo.val2 << std::endl;
return 0;
}
Output:
输出：
3 4
2 4
1 5
1 6
3 4
2 4
1 5
1 6
As you can see, the container is sorted by the member val2of the class Foo, based on the <operator. However, if you use std::setinstead of a std::multiset, then you will get a different output:
如您所见，容器按val2类的成员排序Foo，基于<运算符。但是，如果您使用std::set而不是 a std::multiset，那么您将获得不同的输出：
int main()
{
std::set<Foo> s;
s.insert(Foo(1, 6));
s.insert(Foo(1, 5));
s.insert(Foo(3, 4));
s.insert(Foo(2, 4));
for (auto const &foo : s)
std::cout << foo.val1 << " " << foo.val2 << std::endl;
return 0;
}
Output:
输出：
3 4
1 5
1 6
3 4
1 5
1 6
Here, the second Fooobject where val2is 4 is missing, because a std::setonly allows for unique entries. Whether entries are unique is decided based on the provided <operator. In this example, the <operator compares the val2members to each other. Therefore, two Fooobjects are equal, if their val2members have the same value.
在这里，缺少 4的第二个Foo对象val2，因为 astd::set只允许唯一条目。条目是否唯一取决于提供的<运算符。在此示例中，<操作员将val2成员相互比较。因此，Foo如果两个对象的val2成员具有相同的值，则它们是相等的。
So, your choice depends on whether or not you want to store Fooobjects that may be equal based on the <operator.
因此，您的选择取决于您是否要存储Foo基于<运算符可能相等的对象。
回答by Anil Gupta
C++ do have sorted container e.g std::set and std::map
C++ 确实有排序容器，例如 std::set 和 std::map
int main()
{
//ordered set
set<int> s;
s.insert(5);
s.insert(1);
s.insert(6);
s.insert(3);
s.insert(7);
s.insert(2);
cout << "Elements of set in sorted order: ";
for (auto it : s)
cout << it << " ";
return 0;
}
Output: Elements of set in sorted order: 1 2 3 5 6 7
输出：按排序顺序排列的集合元素：1 2 3 5 6 7
int main()
{
// Ordered map
std::map<int, int> order;
// Mapping values to keys
order[5] = 10;
order[3] = 5;
order[20] = 100;
order[1] = 1;
// Iterating the map and printing ordered values
for (auto i = order.begin(); i != order.end(); i++) {
std::cout << i->first << " : " << i->second << '\n';
}
Output:
1 : 1
输出：
1：1
3 : 5
3 : 5
5 : 10
5 : 10
20 : 100
20 : 100
