C++ 如何确保 std::map 是有序的？

How to ensure that a std::map is ordered?

提问by danijar

Using a std::map<int, ...>how can I ensure at inserting time that iterating over it will take place in ascending order of the integer key?

使用 astd::map<int, ...>如何确保在插入时迭代它将按整数键的升序进行？

回答by juanchopanza

You don't have to do anything. The map will be in ascending order according to the values of the key.

你不必做任何事情。地图将根据键的值按升序排列。

Internally, the map performs a comparison between keys to order its elements. By default, it uses std::less<KEY>, which is equivalent to bool operator<(int, int)for integers. For user defined types, you have to options:

在内部，映射执行键之间的比较以对其元素进行排序。默认情况下，它使用std::less<KEY>，相当于bool operator<(int, int)整数。对于用户定义的类型，您必须选择：

1. Implement a bool operator<(const MyType&, const MyType&)implementing a strict weak ordering comparison between your user defined types. Use this if your type has a natural ordering

2. Provide a binary functor that implements strict weak ordering, which you can pass as the 3rd template parameter to the map. Use this if your type does not have a natural ordering, or if you want to build the map with an ordering different to that used by std::less<Key>via the bool operator<(...)from point 1.

1. 实现一个bool operator<(const MyType&, const MyType&)实现你的用户自定义类型之间的严格弱顺序比较。如果您的类型具有自然排序，请使用此选项

2. 提供一个实现严格弱排序的二元函子，您可以将其作为第三个模板参数传递给地图。如果您的类型没有自然排序，或者您想使用与std::less<Key>通过bool operator<(...)起始点 1使用的排序不同的排序来构建地图，请使用此选项。

What typically happens behind the scenes is that the map is implemented as a self-balancing binary tree, and the strict weak ordering is used to place new elements in the map, and to determine whether two elements are equal. As an aside, the same logic applies to std::set, where the key and value are one and the same.

通常在幕后发生的是，映射被实现为自平衡二叉树，并且使用严格弱排序在映射中放置新元素，并确定两个元素是否相等。顺便说一句，相同的逻辑适用于std::set，其中键和值相同。

回答by Nawaz

std::mapdoes that itself. You don't have to do anything.

std::map这样做本身。你不必做任何事情。

By default it sorts the keys in the increasing order. If you want it to do sorting in decreasing order, then pass std::greater<T>as thirdtemplate argument to std::map.

默认情况下，它按递增顺序对键进行排序。如果您希望它按降序进行排序，则将std::greater<T>作为第三个模板参数传递给std::map.

std::map<int, X>  m1;                    //sorts key in increasing order
std::map<int, X, std::greater<int>>  m2; //sorts key in decreasing order
std::map<int, X, std::less<int>> m3;     //sorts key in increasing order

The defaultargument for thirdtemplate parameteris std::less<T>, so above m1and m3are same types!

在默认的参数第三个模板参数的std::less<T>，所以上面的m1和m3相同类型！

Demo:

演示：

#include <iostream>
#include <map>
#include <string>

int main()
{
    std::cout << "\nkeys are in increasing order: \n";
    std::map<int, std::string> m1;
    m1[5] = "first insertion but higher key";
    m1[1] = "second insertion but lower key";
    for(auto const & item : m1) 
       std::cout << "{" << item.first  <<"," << item.second << "}\n";

    std::cout << "\nkeys are in decreasing order: \n";   
    std::map<int, std::string, std::greater<int> > m2;
    m2[1] = "first insertion but lower key";
    m2[2] = "second insertion but higher key";
    for(auto const & item : m2) 
       std::cout << "{" << item.first  <<"," << item.second << "}\n";
}

Output:

输出：

keys are in increasing order: 
{1,second insertion but lower key}
{5,first insertion but higher key}

keys are in decreasing order: 
{2,second insertion but higher key}
{1,first insertion but lower key}

Notice that in both cases the items are ordered as specified by the third template argument of std::map. The output doesn't depend on the order of insertion, rather the order of the keys!

请注意，在这两种情况下，项目都按照 的第三个模板参数指定的顺序进行排序std::map。输出不取决于插入的顺序，而是键的顺序！

Live demo

现场演示

There is also std::unordered_mapwhich doesn't sort elements.

还有std::unordered_mapwhich 不排序元素。

回答by none

mapis usually implemented as a binary search tree, therefore iterators would give you sorted keys already.

map通常实现为二叉搜索树，因此迭代器已经给你排序的键。

If you don't care about the order you may use unordered_map(from c++11 or boost) which would give you some speed in trade of the order.

如果您不关心您可以使用的订单unordered_map（来自 c++11 或 boost），这会给您一些订单交易速度。