一、map简介

map一般采用红黑树存储数据，是一种映射类型的关联容器，map中的元素是关键字 - 值（key-value）对：关键字起到索引的作用，值则表示与索引相关联的数据。

map按关键字有序保存元素，元素在insert容器后就被按照某种规则（map默认按照key的大小从小到大排序元素）自动排序。

二、自定义key

默认情况下，map使用关键字类型的 < 运算符来比较元素，因此默认情况下我们可以直接定义关键字是内置类型，比如string ，int 等。string ，int等内置类型可以直接用 < 运算符来比较元素。
自定义类型key没有默认的比较函数，因此我们要重载< 运算符，也可以自定义模板参数。

map是一个模板类，有四个参数：

  /**
   *  @brief A standard container made up of (key,value) pairs, which can be
   *  retrieved based on a key, in logarithmic time.
   *
   *  @ingroup associative_containers
   *
   *  @tparam _Key  Type of key objects.
   *  @tparam  _Tp  Type of mapped objects.
   *  @tparam _Compare  Comparison function object type, defaults to less<_Key>.
   *  @tparam _Alloc  Allocator type, defaults to
   *                  allocator<pair<const _Key, _Tp>.
   *
   *  For a @c map<Key,T> the key_type is Key, the mapped_type is T, and the
   *  value_type is std::pair<const Key,T>.
   *
   *  Maps support bidirectional iterators.
   *
   *  The private tree data is declared exactly the same way for map and
   *  multimap; the distinction is made entirely in how the tree functions are
   *  called (*_unique versus *_equal, same as the standard).
  */
  template <typename _Key, typename _Tp, typename _Compare = std::less<_Key>,
	    typename _Alloc = std::allocator<std::pair<const _Key, _Tp> > >
    class map
    {
    public:
      typedef _Key					key_type;
      typedef _Tp					mapped_type;
      typedef std::pair<const _Key, _Tp>		value_type;
      typedef _Compare					key_compare;
      typedef _Alloc
    ......
    }

第一个参数是key，根据key值来比较来排序容器元素，定义容器的时候必须要指定 key 的比较函数。只不过这个函数通常是默认的 less，表示小于关系。

第二个参数就是mapped对象的类型。

其中第三个参数是比较函数，这个函数通常是默认的 less（小于），默认的 std::less 会去调用 key 类型的 operator() 函数，比较内置类型的key值。map用它来判断两个key的大小，并返回bool类型的结果。

typename _Compare = std::less<_Key>

  /// One of the @link comparison_functors comparison functors@endlink.
  template<typename _Tp>
    struct less : public binary_function<_Tp, _Tp, bool>
    {
      _GLIBCXX14_CONSTEXPR
      bool
      operator()(const _Tp& __x, const _Tp& __y) const
      { return __x < __y; }
    };

当我们重载比较函数less时，由于less的比较函数参数和函数体都有const修饰，因此我们重载的比较函数参数和函数体也要有const修饰。

三、demo演示

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

 
struct student_id_info
{
    std::string name;
    int arge;
    int height;
 
    student_id_info(std::string a, int b, int c) : name(a), arge(b), height(c){}
    student_id_info(){}
 
 	//重载operator<，即重载less函数
 	//首先比较结构体成员的arge的大小，如果成员的arge的大小，则比较成员height的大小
 	//这里重载时参数和函数体的const修饰要与默认less函数保持不变
    bool operator<(const student_id_info& id) const {
        return (arge < id.arge) || (arge == id.arge && height < id.height);
    }

};
 

struct student_score
{
    int math;
    int chinese;
    int english;
 
    student_score(int a, int b, int c) : math(a), chinese(b), english(c){}
    student_score(){}

};

int main()
{
 
    std::map<student_id_info , student_score> _map = 
    {
        {{"xiaoming", 20, 175}, {100, 90, 80}},
        {{"xiaohong", 19, 180}, {95, 90, 85}},
    };

    _map.emplace(student_id_info("xiaoli", 19, 175), student_score(90, 80, 95));

    for (const auto &student: _map)
    {
        std::cout << "{" << student.first.name<< "," << student.first.arge << ","<< student.first.height <<"}: "
                  << "{" << student.second.math<< "," << student.second.chinese<< ","<< student.second.english <<"}" 
                  << std::endl;  
    }

    _map.clear();
 
    return 0;
}

在这里插入图片描述

四、自定义模板参数

除了上述的重载map模板默认比较函数less外，我们还可以自定义模板参数，也就是自己来写map模板的第三个参数。这样我们可以编写专门的函数对象或者 lambda 表达式，然后在容器的第三个模板参数里指定。这种方式更灵活，而且可以实现任意的排序准则。

代码演示：

#include <iostream>
#include <string>

#include <map>
//#include <functional>

 
struct student_id_info
{
    std::string name;
    int arge;
    int height;
 
    student_id_info(std::string a, int b, int c) : name(a), arge(b), height(c){}
    student_id_info(){}

};

//自定义map模板的第三个参数：
bool map_comapre(const student_id_info& id1, const student_id_info& id2) {
        return (id1.arge < id2.arge) || (id1.arge == id2.arge && id1.height < id2.height);
}
 

struct student_score
{
    int math;
    int chinese;
    int english;
 
    student_score(int a, int b, int c) : math(a), chinese(b), english(c){}
    student_score(){}

};

int main()
{
	//decltype用来指出map模板的第三个参数自定义操作的类型
    std::map<student_id_info , student_score, decltype(map_comapre) *> _map(map_comapre);
    //std::map<student_id_info , student_score, std::function<bool (const student_id_info&, const student_id_info&)>> _map(map_comapre);
    _map =  
    {
        {{"xiaoming", 20, 175}, {100, 90, 80}},
        {{"xiaohong", 19, 180}, {95, 90, 85}},
    };

    _map.emplace(student_id_info("xiaoli", 19, 175), student_score(90, 80, 95));

    for (const auto &student: _map)
    {
        std::cout << "{" << student.first.name<< "," << student.first.arge << ","<< student.first.height <<"}: "
                  << "{" << student.second.math<< "," << student.second.chinese<< ","<< student.second.english <<"}" 
                  << std::endl;  
    }

    _map.clear();
 
    return 0;
}