如何确保 std::map 有序？

Question

如何确保 std::map 有序？

c++stl

16

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

- danijar

2

除非您已按排序顺序插入，否则您插入的顺序将丢失。如果这是您的问题，那么是这样的。 - GManNickG

2

可能是Is the order of iterating through std::map known (and guaranteed by the standard)?的重复问题。 - Ciro Santilli OurBigBook.com

3个回答

20

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，它不会对元素进行排序。

- Nawaz

小优化，也是clang-tidy现代化检查的一部分：您应该透明地定义它们 ;) std::map<int, X, std::greater<>> - jaques-sam

2

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

如果您不关心顺序，可以使用unordered_map（来自c++11或boost），这将在交换顺序的同时提供一定的速度优势。

- none

1

不一定要实现成树形结构。它只需要有序，并满足一定的复杂度限制。搜索树可以做到这一点，其他各种数据结构也可以。 - Mike Seymour

这仍然意味着元素是否按键排序可能取决于实现模式，但这是错误的；按键排序是一个要求，不仅是（最常见的）实现细节。 - underscore_d

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- juanchopanza · Accepted Answer

您不需要做任何事情。根据键的值，该映射将按升序排列。

内部，该映射对键进行比较以对其元素排序。默认情况下，它使用std :: less<KEY>，对于整数等同于bool operator <(int，int)。对于用户定义的类型，您有两个选项：

实现bool operator <(const MyType&，const MyType&)，用于实现严格弱序比较用户定义的类型之间的比较。如果您的类型具有自然排序，则使用此选项
提供一个二进制函数对象，实现严格弱序，您可以将其作为第三个模板参数传递给映射。如果您的类型没有自然顺序，或者如果要使用与由std :: less<Key>使用的顺序不同的顺序构建映射，则使用此选项通过从第1点的bool operator<(...)来实现。

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