C++ STL: map自定义键值类型

相关内容: C++ STL: unordered_map自定义键值类型
【C++ STL: map自定义键值类型】本文目录
  • 1. map定义
  • 2. 简单方法: 重载operator<()操作符
  • 3. 其它方法:比较函数的函数对象
    • 3.1 方法1: 利用std::function
    • 3.2 方法2: 重载operator()的类
    • 3.3 方法3: less函数的模板定制
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. 简单方法: 重载operator<()操作符在我们插入时,map会先通过比较函数地函数对象来比对key的大小,然后根据比对结果进行有序存储。c++标准库中,map比较函数的函数对象不可避免地会用到’<'运算,因此一种方法就是直接在自定义类里重载operator<()操作符,如下所示。
#include #include #include using namespace std; class Person{ public: string name; int age; Person(string n, int a){ name = n; age = a; }bool operator<(const Person &p) const //注意这里的两个const { return (age < p.age) || (age == p.age && name.length() < p.name.length()) ; } }; int main(int argc, char* argv[]){ map group; group[Person("Mark", 17)] = 40561; group[Person("Andrew",18)] = 40562; for (auto ii = group.begin() ; ii != group.end() ; ii++) cout << ii->first.name << " " << ii->first.age << " : " << ii->second << endl; return 0; }

这里,我们需要注意的是,在重载operator<(){}时,无论是参数还是整个函数的const都不能少。参照less的定义,less的参数和函数整体都是const,那么被调用的operator<()必然也是同等要求。
3. 其它方法:比较函数的函数对象如果不重载operator<()是不是就不行了?当然不是。除了直接重载operator<(),我们可以直接自定义比较函数的函数对象。
首先简要介绍一下函数对象的概念:在《C++ Primer Plus》里面,函数对象是可以以函数方式与()结合使用的任意对象。这包括函数名、指向函数的指针和重载了“operator()”操作符的类对象。基于此,我们提出3种定义方法。
3.1 方法1: 利用std::function
方法1利用std::function。它是一种通用、多态、类型安全的函数封装,其实例可以对任何可调用目标实体(包括普通函数、Lambda表达式、函数指针、以及其它函数对象等)进行存储、复制和调用操作,方法如下。
#include #include #include #include using namespace std; class Person{ public: string name; int age; Person(string n, int a){ name = n; age = a; } }; bool MyCompare(const Person &p1, const Person &p2) {//普通的函数 return (p1.age < p2.age) || (p1.age == p2.age && p1.name.length() < p2.name.length()); }int main(int argc, char* argv[]){ map> group(MyCompare); //需要在构造函数中指明 group[Person("Mark", 17)] = 40561; group[Person("Andrew",18)] = 40562; for ( auto ii = group.begin() ; ii != group.end() ; ii++ ) cout << ii->first.name << " " << ii->first.age << " : " << ii->second << endl; return 0; }

我们利用std::function为MyCompare()构建函数实例。初始化时,这个函数实例就会被分配那个指向MyCompare()的指针。因此,在对group进行申明时,需要构造函数指明函数实例。
另外,c++11增加了一个新的关键词decltype,它可以直接获取自定义哈希函数的类型,并把它作为参数传送。因此,group的声明可以如下修改。
map group(MyCompare);

3.2 方法2: 重载operator()的类
方法2就是利用重载operator()的类,将比较函数打包成可以直接调用的类。
#include #include #include using namespace std; class Person{ public: string name; int age; Person(string n, int a){ name = n; age = a; } }; struct MyCompare{//Function Object bool operator()(const Person &p1, const Person &p2) const{ return (p1.age < p2.age) || (p1.age == p2.age && p1.name.length() < p2.name.length()); } }; int main(int argc, char* argv[]){ map group; group[Person("Mark", 17)] = 40561; group[Person("Andrew",18)] = 40562; for ( auto ii = group.begin() ; ii != group.end() ; ii++ ) cout << ii->first.name << " " << ii->first.age << " : " << ii->second << endl; return 0; }

值得注意的是,这时group的声明不再需要将函数对象的引用传入构造器里。因为map会追踪类定义,当需要比较时,它可以动态地构造对象并传递数据。
3.3 方法3: less函数的模板定制
前面几种方法,无论我们怎么定义,在声明group的时候都需要指定第3个参数,有什么方法是需要指定的呢?当然有啦。
通过map的定义可知,第三个参数的默认值是less。显而易见,less属于模板类。那么,我们可以对它进行模板定制,如下所示。
#include #include #include using namespace std; class Person{ public: string name; int age; Person(string n, int a){ name = n; age = a; } }; template <> //function-template-specialization struct less{ public : bool operator()(const Person &p1, const Person &p2) const { return (p1.age < p2.age) || (p1.age == p2.age && p1.name.length() < p2.name.length()); } }; int main(int argc, char* argv[]){ map group; //无需指定第三个参数啦 group[Person("Mark", 17)] = 40561; group[Person("Andrew",18)] = 40562; for ( auto ii = group.begin() ; ii != group.end() ; ii++ ) cout << ii->first.name << " " << ii->first.age << " : " << ii->second << endl; return 0; }

    推荐阅读