C++ STL: map的按key和按value排序 C++

相关内容： C++ STL: map自定义键值类型、C++ 函数对象（函数符）

本文目录

1. map定义
2. 按key排序
3. 按value排序
- 3.1 通过序列容器调用sort
- 3.2 替换map的key和value
4. 参考文章

1. map定义在将map的排序之前，我们要知道它是STL里的一个模板类，用来存放键值对的数据结构，定义如下。

template < class Key,//map::key_tpe class T,//map::mapped_type class Compare = less,//map::key_compare class Alloc = allocator>//map::allocator_type > class map;

第1个参数存储了key。
第2个参数存储了mapped value。
第3个参数是比较函数的函数对象。map用它来判断两个key的大小，并返回bool类型的结果。利用这个函数，map可以确定元素在容器中遵循的顺序以及两个元素键是否相等（！comp（a，b）&&！comp（b，a）），确保map中没有两个元素可以具有等效键。这里，它的默认值是less，定义如下。

template struct less { bool operator() (const T& x, const T& y) const {return x < y; } typedef T first_argument_type; typedef T second_argument_type; typedef bool result_type; };
第4个参数是用来定义存储分配模型的。

2. 按key排序实际上map内部所有的数据本来就是按key排序的。分析map结构定义，发现map的按key排序是通过第3个参数（比较函数的函数对象）实现的。
其中，less为其默认的函数对象，所以如果我们不指定参数3，map键值对就会按照默认方法进行存储。当我们希望它能以不同的方式进行排序，就需要重新指定参数3。
如果只是调用C++标准库自带的方法，我们只需如下所示，在声明map对象时指定第3参数即可。

#include #include #include using namespace std; int main(){ map, int, greater>> test; //指定参数3为greater test["Alice"] = 3; test["Cindy"] = 11; test["Bob"] = 7; for(auto itr = test.begin(); itr != test.end(); ++itr){ cout << itr->first << ": " << itr->second << endl; } return 0; }

然而，当我们自定义map的键值类型时，C++标准库往往没有对应的函数对象可供使用，这时候，我们就需要自定义函数对象了。关于方法，我在C++ STL: map自定义键值类型这篇文章里讲得非常详细，文中提出了针对自定义键值排序的4种方法。
3. 按value排序对value的排序，我查了很多资料，主要有以下两个思路。

一是通过将map转换到序列容器，再用STL提供的sort方法得以实现的。
二是通过将map的key和value位置替换

3.1 通过序列容器调用sort
为什么我们不能直接用sort给map排序呢？
这是因为sort算法只能对序列容器进行排序，就是线性的（如vector，list，deque）。map虽然也是一个集合容器，但是它不是线性存储的（比如红黑树）。因此，我们需要先把map中的元素放到序列容器中，然后再对这些元素进行排序。
根据定义，sort算法的第3个参数即可以是函数指针，也可以是函数对象（可以以函数方式与()结合使用的任意对象，包括函数名、指向函数的指针和重载了“operator()”操作符的类对象）。
下面的算法，给出了函数对象的两种情况。

#include #include #include #include using namespace std; typedef pair, int> Pair; //第3参数为函数名 bool my_compare(const Pair &p1, const Pair &p2){ return p1.second < p2.second; }//第3参数为重载了operator()操作符的类对象 struct MyCompare{ public: bool operator()(const Pair &p1, const Pair &p2) const{ return p1.second < p2.second; } }; int main(){ map, int> test; test["Alice"] = 3; test["Cindy"] = 5; test["Bob"] = 7; cout << "> sort by key" << endl; for(auto itr = test.begin(); itr != test.end(); ++itr){ cout << itr->first << ": " << itr->second << endl; } cout << endl; vector vec; for(auto itr = test.begin(); itr != test.end(); ++itr){ vec.push_back(make_pair(itr->first, itr->second)); } sort(vec.begin(), vec.end(), MyCompare()); //my_compare或者MyCompare()都可以 cout << "> sort by value" << endl; for(auto itr = vec.begin(); itr != vec.end(); ++itr){ cout << itr->first << ": " << itr->second << endl; } return 0; }

【结果】

> sort by key Alice: 3 Bob: 7 Cindy: 5> sort by value Alice: 3 Cindy: 5 Bob: 7

3.2 替换map的key和value
方法2通过std::transform实现替换，下面是transform的定义。

//一元操作 template OutputIterator transform (InputIterator first1, InputIterator last1, OutputIterator result, UnaryOperation op); //二元操作 template OutputIterator transform (InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, OutputIterator result, BinaryOperation binary_op);

对于一元操作，op将应用于[first1, last1]范围内的每个元素，并将每个操作返回的值存储在以result开头的范围内。给定的op将被连续调用last1-first1+1次。op可以是函数指针或函数对象或lambda表达式。二元操作，本文不会用到，这里不做说明。
因此，基于上面的定义，我们的程序如下所示。

#include #include #include #include using namespace std; typedef pair, int> Pair; int main(){ map, int> test; test["Alice"] = 3; test["Cindy"] = 5; test["Bob"] = 7; cout << "> sort by key" << endl; for(auto itr = test.begin(); itr != test.end(); ++itr){ cout << itr->first << ": " << itr->second << endl; } cout << endl; map result; transform(test.begin(), test.end(), inserter(result, result.begin()), [](pair, int> a) { return pair(a.second, a.first); }); cout << "> sort by value" << endl; for(auto itr = result.begin(); itr != result.end(); ++itr){ cout << itr->first << ": " << itr->second << endl; } return 0; }

【C++ STL: map的按key和按value排序】【结果】