STL是一个统一的整体，map的很多用法都和STL中其它的东西结合在一起
map中由于它内部有序，由红黑树保证，因此很多函数执行的时间复杂度都是log2N的，如果用map函数可以实现的功能，而STL Algorithm也可以完成该功能，建议用map自带函数，效率高一些。
sort算法有个限制，利用sort算法只能对序列容器进行排序，就是线性的（如vector，list，deque）。map是一个集合容器，它里面存储的元素是pair，但是它不是线性存储的（像红黑树），所以利用sort不能直接和map结合进行排序。
operator()重载必须是常成员函数，因为常对象只能调用常成员函数
STL中默认是采用小于号来排序的
键和值的数据类型是不相同的，这与set不同。set中的key和value是Key类型的，而map中的key和value是一个pair结构中的两个分量
stl-map
greater <int> >最右边的两个>之间要有空格，否则 Dev C++ 会将它们当作右移运算符，导致编译出错
对map的排序

key值排序

按照Key值自动进行了排序
上面的按key值排序有个缺点：即当插入的有多个相等的值时，由于key的唯一性，会只保留一个。

map的定义

1 2	template < class Key, class T, class Compare = less<Key>, class Allocator = allocator<pair<const Key,T> > > class map;

它有四个参数，其中我们比较熟悉的有两个: Key 和 Value。第四个是 Allocator，用来定义存储分配模型的
现在重点看下第三个参数： class Compare = less<Key>
这也是一个class类型的，而且提供了默认值 less<Key>。 less是stl里面的一个函数对象，那么什么是函数对象呢？
所谓的函数对象：即调用操作符的类，其对象常称为函数对象（function object），它们是行为类似函数的对象。表现出一个函数的特征，就是通过“对象名+(参数列表)”的方式使用一个类，其实质是对operator()操作符的重载。
- less的实现：

template <class T> struct less : binary_function <T,T,bool> {
	bool operator() (const T& x, const T& y) const
	    {return x<y;}
};

是一个带模板的struct，里面仅仅对()运算符进行了重载，实现很简单，但用起来很方便，这就是函数对象的优点所在。stl中还为四则运算等常见运算定义了这样的函数对象，与less相对的还有greater
map这里指定less作为其默认比较函数(对象)，所以我们通常如果不自己指定Compare，map中键值对就会按照Key的less顺序进行组织存储
可以在定义map的时候，指定它的第三个参数Compare，比如我们把默认的less指定为greater：要加#include <functional>
- map<string, int, greater<string> > name_score_map;

只要我们自己写一个函数对象，实现想要的逻辑，定义map的时候把Compare指定为我们自己编写的这个就ok啦。
1
2
3
4
5
struct CmpByKeyLength {
bool operator()(const string& k1, const string& k2) const {
return k1.length() < k2.length();
}
};
map<string, int, CmpByKeyLength> name_score_map;

按照value排序

思路1：可以考虑将value作为key值进行自动排序。

思路2：可以把map中的key值和value值分别转存到一个pair类型的vector中，在对vector按照一定的规则排序即可。这样的方法对值一样的情况也能够使用。

typedef pair<string, int> PAIR;
map<string, int> name_score_map;
name_score_map.insert(make_pair("Bing", 99));
name_score_map.insert(make_pair("Albert", 86));
vector<PAIR> name_score_vec(name_score_map.begin(), name_score_map.end());
sort(name_score_vec.begin(), name_score_vec.end(), cmp);

map的构造

在 C++ 中通过 insert() 方法向集合中插入一个新的映射，参数是一个 pair 类型的结构。pair<int,char>(1,’a’)定义了一个整数 1 和字符 a 的 pair。我们向映射中加入新映射对的时候就是通过 pair 来实现的。如果插入的 key 之前已经有 value，不会用插入的新的 value 替代原来的 value，也就是插入无效，但并不会报错。
- 如果插入语句没有生效，那么这就涉及到我们怎么知道 insert 语句是否插入成功的问题了，可以通过 pair 来获得是否插入成功，程序如下：
  1
  2
  pair<map<int, string>::iterator, bool> insert_pair;
  insert_pair = mapStudent.insert(map<int, string>::value_type (1, "student_one"));
- 我们通过 pair 的第二个变量来知道是否插入成功，它的第一个变量返回的是一个 map 迭代器，如果插入成功的话，insert_pair.second应该是 true，否则为 false。
用数组方式就不同了，它可以覆盖以前该关键字对应的值
是否已经有映射了。需要用到 count() 函数进行判断或者find
- std::map::count
  - size_type count( const Key& key ) const;
  - template< class K > size_type count( const K& x ) const;
  - 返回拥有关键比较等价于指定参数的元素数，因为此容器不允许重复故为 1 或 0。
  - 1) 返回拥有关键 key 的元素数。
  - 2) 返回拥有关键比较等价于值 x 的元素数。此重载仅若有限定 id Compare::is_transparent合法且指代一个类型才参与重载决议。这允许调用此函数而不构造 Key 的实例。
  - 参数
    - key
      
      要计量元素数的关键值
    - x
      
      要与关键比较的替用值
  - 返回值
    拥有比较等价于 key 或 x 的关键的元素数，对于 (1) 为 1 或 0。

mapStudent.insert(pair<int, string>(2, "student_two"));
mapStudent.insert(map<int, string>::value_type (1, "student_one"));
mapStudent[1] = "student_one";

总结：

对key 排序的话，直接使用greater<string>在map定义的时候就。而要对value排序，则是使用函数对象，先将map转换为vector，调用sort函数中传入一个函数对象，则可以实现对value 的排序。还有一点是pair 只重载了<，则stl 则不能使用 == 运算符。

对map的排序

key值排序

map的定义

按照value排序

map的构造

总结：