如何确保订购std :: map？

Question

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

Answer 1

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

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

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

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

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

Answer 2

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

在默认的参数第三个模板参数是std::less<T>,那么上面的m1和m3相同类型!

演示:

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

输出:

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}

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

现场演示

还有std::unordered_map哪些不对元素进行排序.