标准模版STL-关联容器

5. 关联容器
（1）关联容器的特点
（1）容器需要存放对象和key值，key值与对象之间是一种映射关系。

（2）每个对象被存入到关联容器中时，会对key进行排序，进过比较后找到合适的
    位置后存放。因此key的数据类型需要提供排序方法，可以通过提供orerator<()
    或者Compare这两个函数进行比较。


（3）map只支持双向迭代器，因此不支持随机访问，虽然map支持[key]的方式访问对象，
    但是这并不是随机访问。



（2）关联容器分类
（1）map类：不允许key重复
（2）multimap类：map的特例，允许key重复
（3）set类：对象本身就是key值，不允许重复
（4）multiset类：set的特例，允许重复
    

（3）map的模板
前面的vector和list模板原本需要两个模板参数，但是实际上我们基本都只
指定第一个模板参数。

map类的模板参数比较多，总共有四个模板参数，map的类模板定义如下：
template < class Key, class T, class Compare = less<Key>,
       class Allocator = allocator<pair<const Key,T> > > class map;

（1）模板参数1：key值的类型
（2）模板参数2：key对应数据的类型
（3）模板参数3：用于排序时进行比较的函数对象类型
（4）模板参数4：用于在map中分配存储空间的函数类型

一般情况下，我们只需要指定前两个模板参数即可。

（4）定义一个map
（1）定义一个空的map
    std::map<std::string, Student> stumap;
    
    调用map的默认构造函数，定义一个空的map对象，第一个模板类型参数
    string表示key值的类型为string，第二个Student表示需要存储的对象
    是Student类型。

    但是实际上key和存放的对象的类型可以使任何类型。

（2）定义一个map，利用另一个map的袁元素进行初始化
    std::map<std::string, Student> stumap<iter1, iter2>; 
    
    使用另一个map的[iter1, iter2)之间的元素初始化map。


（4）如何构建键值对
将key和对应对象构建成为键值对的方法有三个：
（1）std::make_pair("123", stu)
（2）std::map<string, Student> :: value_type("111",stu)
（3）std::pair<string, Student>("222",stu)

这三个函数在调用insert()插入新的键值对时很重要，比如：
enumMap.insert(map<int,CString> :: value_type("111", stu))
enumMap.insert(pair<int,string>("222", stu));   



（5）访问map
（1）使用[]
    （1）作为右值：Student stu = stumap["111"];
        如果"111"对应的对象比更不存在，便会使用Student的默认构造函数创
        建一个Student对象。实际上只有确保"111"对应的对象存在才有意义。


    （2）作为左值：Stumap["222"] = stu;    
        作为左值时，如果"222"对应的键值对不存在，就创建一个新的键值对，
        然后将内容赋值为stu，利用这样的方式可以实现插入新键值对的操作，
        当然还可以使用insert()成员函数实现插入操作。      
    
        不管是作为左值还是右值，提前确定键值对是否存在非常关键，所以我
        们可以使用find成员函数先查找该key值对应的对象是否存在，存在就返
        回指向该位置的迭代器，然后使用该迭代器进行操作，否者就不操作。
    
    
（2）迭代器遍历
    （1）使用的是双向迭代器，不支持随机访问
    （2）正向迭代器需要用到begin()和end()函数
    （3）逆向迭代器rbegin()函数和rend()函数。
    （4）通过iter->second成员和iter->first成员就可以获取数据和键值key，
        second成员中存放的是数据，first存放的是键值。
        这里只能使用->，不能使用*和.操作。

（3）例子
    #include <iostream>
    #include <algorithm>
    #include<iterator>
    #include<sstream>
    #include<stdlib.h>
    #include<stdio.h>
    #include <map>

    using namespace std;
    class Student {
    public:
            Student(const string name=" "):name(name) { }

            string getname() const { return name; }
    private:
            string name;
    };

    /* 使用迭代器遍历map */
    template <class Iter> void show_map(Iter first, Iter last) {
            for( ;first!=last; first++) {
                        /* 使用first访问键值，使用second访问对象，注意，通过迭代器访问到的
                    只是键值对，必须使用->访问first和second才能访问到具体的键值和对应数据，
                    由于存储的对象是地址，访问Student的name时，必须再次使用-> */
                 cout << first->first<<"        "<< ((first)->second)->getname()<<endl;
            }
    }

    int main(void)
    {   
            /* 定义一个空的map */
            std::map<string, Student*> map1;

            cout<< "使用[]做为左值插入新元素" <<endl;
            map1["111"] = new Student("zhangsan");
            map1["222"] = new Student("wangwu");
            map1["333"] = new Student("lisi");
        map1["333"] = new Student("wwwwww");
            map1["444"] = new Student("zhaosi");

            /* 使用正向迭代起遍历 */
            cout<< "显示map1中的元素" <<endl;
            show_map(map1.begin(), map1.end());

            /* 使用map1中的内容去初始化map2 */
            cout<< "\n使用map1中[++map1.begin(), --map1.end())之间的元素初始化map2" <<endl;
            std::map<string, Student*> map2(++map1.begin(), --map1.end());

            /* 使用逆向迭代起遍历 */
            cout<< "显示map2中的元素" <<endl;
            show_map(map2.rbegin(), map2.rend());

            return 0;
    }
    
    运行结果：
    使用[]做为左值插入新元素
    显示map1中的元素
    111        zhangsan
    222        wangwu
    333        wwwwww
    444        zhaosi

    使用map1中[++map1.begin(), --map1.end())之间的元素初始化map2
    显示map2中的元素
    333        lisi
    222        wangwu

    例子分析：
    map中不允许出现重复的key，如果出现，最后出现的key的对象将会覆盖
    之前同名key对应的对象，比如例子中有两个"333"的key值，但是map只存放
    最后一个"333"对用的对象。



（6）使用map的成员函数实现插入和删除元素等操作   
（1）涉及成员函数
        （1）clear(）        删除所有元素
        （2）count()         返回指定元素出现的次数
        （3）empty()         如果map为空则返回true
        （4）erase()         删除一个元素
        void erase ( iterator position );
        size_type erase ( const key_type& x );
            void erase ( iterator first, iterator last );
        （5）find()          查找一个元素
        iterator find ( const key_type& x );
        const_iterator find ( const key_type& x ) const;
        （6）insert()        插入元素
        pair<iterator,bool> insert ( const value_type& x );
            iterator insert ( iterator position, const value_type& x );
        template <class InputIterator>
            void insert ( InputIterator first, InputIterator last );
        （7）max_size()      返回可以容纳的最大元素个数
        （8）size()          返回map中元素的个数
        （9）swap()           交换两个map


（2）举例
    例子1：（1）—（5）函数举例 
    #include <iostream>
    #include <algorithm>
    #include<iterator>
    #include<sstream>
    #include<stdlib.h>
    #include<stdio.h>
    #include <map>

    using namespace std;
    class Student {
    public:
            Student(const string name=" "):name(name) { }

            string getname() const { return name; }
    private:
            string name;
    };

    /* 使用迭代器便利map */
    template <class Iter> void show_map(Iter first, Iter last) {
            for( ;first!=last; first++) {
                    cout << first->first<<"        "<< ((first)->second)->getname()<<endl;
             }
    }

    int main(void)
    {
            /* 定义一个空的map */
            std::map<string, Student*> map1;

            cout<< "使用[]做为左值插入新元素" <<endl;
            map1["111"] = new Student("zhangs");
            map1["222"] = new Student("wangwu");
            map1["333"] = new Student("lisssi");
            map1["444"] = new Student("dsfsfd");
            map1["555"] = new Student("werrre");
            map1["666"] = new Student("qwewss");
            map1["777"] = new Student("sdgfgf");
            map1["888"] = new Student("zzcvvv");
            map1["999"] = new Student("cxbnhh");
            map1["000"] = new Student("zqwerz");

            if(map1.empty()) cout <<"\nmap1为空"<<endl;
            else cout <<"\nmap1不为空"<<endl;

            cout<<"\n333键值出现的次数："<<map1.count("333")<<endl;

            cout<< "使用erase删除指定元素" <<endl;
            map1.erase(++map1.begin());
            map1.erase("222");
            map1.erase(++map1.begin(), --map1.end());
            cout<< "\nmap1剩余的元素为" <<endl;
            show_map(map1.begin(), map1.end());

            cout<< "\n查在map1中查找“333”键值对" <<endl;
            if(map1.find("333") != map1.end()) {
                    cout <<"\n333对应的对象找到：" <<(map1["333"])->getname()<<endl;
            }

            return 0;
    }       
        
        
        
    例子2：（6）—（9）函数举例
    #include <iostream>
    #include <algorithm>
    #include<iterator>
    #include<sstream>
    #include<stdlib.h>
    #include<stdio.h>
    #include <map>

    using namespace std;
    class Student {
    public:
            Student(const string name=" "):name(name) { }

            string getname() const { return name; }
    private:
            string name;
    };

    /* 使用迭代器便利map */
    template <class Iter> void show_map(Iter first, Iter last) {
            for( ;first!=last; first++) {
                    cout << first->first<<"        "<< ((first)->second)->getname()<<endl;
            }
    }

    int main(void)
    {       
            /* 定义一个空的map */
            std::map<string, Student*> map1;
            std::map<string, Student*> map2;

            cout<< "使用[]做为左值插入新元素" <<endl;
            map1["333"] = new Student("lisssi");
            map1["111"] = new Student("zhangs");
            map1["555"] = new Student("werrre");
            map1["777"] = new Student("sdgfgf");
            map1["222"] = new Student("wangwu");
            map1["444"] = new Student("dsfsfd");
            map1["666"] = new Student("qwewss");
            map1["888"] = new Student("zzcvvv");
            map1["999"] = new Student("cxbnhh");
            map1["000"] = new Student("zqwerz");

            cout <<"\n交换map1和map2"<<endl;
            map1.swap(map2);
            cout <<"显示交换后map1的内容"<<endl;
            show_map(map1.begin(), map1.end());
            cout <<"\n显示交换后map2的内容"<<endl;
            show_map(map2.begin(), map2.end());

            cout <<"\n使用insert函数向map1中插入新元素"<<endl;
            map1.insert(make_pair("123", new Student("zzzzzzz")));
            map1.insert(make_pair("234", new Student("bbbbbbb")));
            map1.insert(pair<string, Student*>("345", new Student("bbbbbbb")));
            map1.insert(map<string, Student*>::value_type("456", new Student("ccccccc")));
            map1.insert(map<string, Student*>::value_type("567", new Student("ddddddd")));
            show_map(map1.begin(), map1.end());

            cout <<"\nmap1中可以容纳的最大元素个数："<< map1.max_size()<<endl;
            cout <<"\nmap1中实际元素个数："<< map1.size()<<endl;

            return 0;
    }
    
    运行结果：

    使用[]做为左值插入新元素

    交换map1和map2
    显示交换后map1的内容

    显示交换后map2的内容
    000        zqwerz
    111        zhangs
    222        wangwu
    333        lisssi
    444        dsfsfd
    555        werrre
    666        qwewss
    777        sdgfgf
    888        zzcvvv
    999        cxbnhh

    使用insert函数向map1中插入新元素
    123        zzzzzzz
    234        bbbbbbb
    345        bbbbbbb
    456        ccccccc
    567        ddddddd

    map1中可以容纳的最大元素个数：178956970

    map1中实际元素个数：5
    

    例子分析：
    从打印结果可以明显的看出，插入map时，会对key值进行自动排序，
    主动排序使用的时map提供的默认比较函数。       
    

（7）multimap
与map一样，操作的成员函数与map都一样，只是multimap允许出现键值对重复。
但是与map也有些其它不同。
（1）multimap不能使用[]
（2）find函数只返回指向重复key的第一个键值对的迭代器

例子：
    #include <iostream>
    #include <algorithm>
    #include<iterator>
    #include<sstream>
    #include<stdlib.h>
    #include<stdio.h>
    #include <map>

    using namespace std;
    class Student {
    public:
            Student(const string name=" "):name(name) { }
            string getname() const { return name; }
    private:
            string name;
    };

    /* 使用迭代器便利map */
    template <class Iter> void show_map(Iter first, Iter last) {
            for( ;first!=last; first++) {
                    cout << first->first<<"        "<< ((first)->second)->getname()<<endl;
            }
    }

    int main(void)
    {
            /* 定义一个空的map */
            std::multimap<string, Student*> map1;

            cout <<"\n使用insert函数向map1中插入新元素"<<endl;
            map1.insert(make_pair("123", new Student("aaazzzzzzz")));
            map1.insert(make_pair("123", new Student("zzzzzzz")));
            map1.insert(make_pair("123", new Student("zzzzzzz")));
            map1.insert(make_pair("234", new Student("bbbbbbb")));
            map1.insert(pair<string, Student*>("345", new Student("bbbbbbb")));
            map1.insert(map<string, Student*>::value_type("456", new Student("ccccccc")));
            map1.insert(map<string, Student*>::value_type("567", new Student("ddddddd")));
            show_map(map1.begin(), map1.end());

            cout <<"\n查找123对应的对象："<< map1.max_size()<<endl;
            cout<<(map1.find("123")->second)->getname() << endl;

            cout <<"\nmap1中可以容纳的最大元素个数："<< map1.max_size()<<endl;
            cout <<"\nmap1中实际元素个数："<< map1.size()<<endl;

            return 0;
    }

    运行结果：
    使用insert函数向map1中插入新元素
    123        aaazzzzzzz
    123        zzzzzzz
    123        zzzzzzz
    234        bbbbbbb
    345        bbbbbbb
    456        ccccccc
    567        ddddddd

    查找123对应的对象：aaazzzzzzz

    map1中可以容纳的最大元素个数：178956970

    map1中实际元素个数：7


（8）函数类类型（函数对象）

（1）函数指针类型
    讲函数类类型之前先回忆函数指针类型，函数指针类型的形式，
    返回类型 （*）（形参类型列表）;

    比如：void *(*)(void *);
    这就是我们之前讲的线程函数的函数类型，由于该类型比较复杂，因此
    往往会使用typedef将其简化。

    typedef void *(*ftype)(void *);
    ftype fp =NULL;
    通过ftype定义的fp就是我们希望得到的函数指针变量。
    
    
（2）函数类类型与函数指针类型的区别
    使用函数指针类型定义的变量只是用于存储函数地址，必须明白，函数指针变量
    并不是函数本身，该变量只是指向了某个函数。

    换句话说，不能使用函数指针类型定义一个函数，只能用它定义一个存放函数
    地址的函数指针变量，至于该函数指针变量指向的函数，我们需要另外定义。

    但是c++中扩展了函数类类型，有了这个类型后，就可以实例化一个函数
    对象，也就是可以像定义一个类对象一样定义一个函数，使用非常的方便。

    
（3）函数类类型如何定义和使用

   （1）函数类类型 
    使用函数类类型，我们可以像实例化一个普通对象一样去实例化一个函数对象，
    在实例化的时候，这个函数对象包含了函数的实现，可以将函数对象直接作为
    参数进行传递时非常的方便。
    
    如果没有函数对象，那么我们就必须使用函数指针实现，实际上如果没有函数
    对象，c++并不会因此而少了什么，完全可以使用函数指针替代，不过在c++在STL
    模板库中大量的使用到了函数对象。
    
    有了函数类类型，我们就可以根据需求实例化任何我们需要的函数对象。

    （2）函数类类型的实现原理
    声明一个类型（class/struct），在类型中对()操作符进行重载，对()重载了
    的类型就被认为是函数类类型。

    使用该函数类类型就可以实例化函数对象，实例化对象时就实现了一个函数，
    对象名字可以被认为就是函数的的名字。
    
    可以使用结构体实现函数类类型，只是在使用结构体时，它成员默认是public的，
    请自行测试使用结构体方式实现的函数类类型。

（4）将函数作为参数进行传递时
    （1）传统方式：传递函数地址
    （2）新的方法：传递函数对象


    例子：
    #include <iostream>
    #include <algorithm>
    #include<iterator>
    #include<sstream>
    #include<stdlib.h>
    #include<stdio.h>
    #include <map>


    using namespace std;
    class Student { 
    public:
            Student(const string name=" "):name(name) { } 

            string getname() const { return name; }
    private:
            string name;
    }
    
    /* 声明一个函数类类型，使用typedef为其定义一个别名 */
    typedef class Funclass {
    public:
            void operator()(const Student &stu) {
                    cout<<stu.getname() <<endl;
            }
    }Funtype;   
        
    /* 定义一个普通函数，使用函数对象进行传参 */
    void display(Funtype func1, Funtype &func2, Funtype *func3, const Student &stu){
            cout << "通过函数对象调用实例化的函数" <<endl;
            func1(stu);
            cout << "\n通过函数对象引用调实例化的用函数" <<endl;
            func2(stu);
            cout << \n"通过函数对象指针调用实例化的函数" <<endl;
            (*func3)(stu);
    }

    int main(void)
    {
            Student stu("zhangsan");
            Funtype func;//定义一个函数对象

            /* 将函数对象作为参数进行传递
            *参数1：传递对象
            *参数2：传递对象引用
            *参数3：传递对象地址 */
            display(func, func, &func, stu);

            return 0;
    }

    运行结果：
    通过函数对象调用函数
    zhangsan

    通过函数对象引用调用函数
    zhangsan

    通过函数对象指针调用函数
    zhangsan


（2）函数类类型模板  
    继续上面的例子，将上面例子中的函数类类型改为函数类模板。
    #include <algorithm>
    #include<iterator>
    #include<sstream>
    #include<stdlib.h>
    #include<stdio.h>
    #include <map>

    using namespace std;
    class Student { 
    public:
            Student(const string name=" "):name(name) { } 

            string getname() const { return name; }
    private:
            string name;
    }; 
            
    /* 声明一个函数类模板，使用typedef为其定义一个别名 */
    template<class T> class Funclass {
    public:
            void operator()(const T &stu) {
                    cout<<stu.getname() <<endl;
            }
    };

    /* 定义一个普通函数，使用函数对象进行传参 */
    void display(Funclass<Student> func1, Funclass<Student> &func2, Funclass<Student> *func3, const Student &stu){
            cout << "通过函数对象调用实例化的函数" <<endl;
            func1(stu);
            cout << "\n通过函数对象引用调实例化的用函数" <<endl;
            func2(stu);
            cout << "\n通过函数对象指针调用实例化的函数" <<endl;
            (*func3)(stu);
    }

    int main(void)
    {
            Student stu("zhangsan");
            Funclass<Student> func;//定义一个函数对象

            /* 将函数对象作为参数进行传递
             *参数1：传递对象
            *参数2：传递对象引用
            *参数3：传递对象地址 */
            display(func, func, &func, stu);

            return 0;
    }

    运行结果：
    通过函数对象调用实例化的函数
    zhangsan

    通过函数对象引用调实例化的用函数
    zhangsan

    通过函数对象指针调用实例化的函数
    zhangsan

    例子分析：
    例子并没有做太大的改动，只是将函数类类型改成了函数类模板。

（3）给map自定义比较函数
  （1）给基本类型的key定义比较函数
    前面讲到，向map中插入数据时，map会自动调用默认的比较函数进行排序
    （默认的是升序排序）。

    但是map中的排序实在插入的时候进行的，目的是为插入的元素找到一个合
    适的位置，排序只在插入元素时进行，之后不能单独对map进行调用sort函
    数进行排序。

    但是map只对key为基本类型时，实现了默认的升序排序，如果希望对基本
    类型实现降序排序，或者想对非基本类型的key实现自定义类型排序，需要
    自己实现比较函数。

    如果比较函数返回true，小的在前，大的在后，这里的大小概念只是逻辑
    上的，不是数据的真实大小，我们完全可以定义数值大的为小，数值小的
    为大。

    通过map模板的第三个模板参数给map指定函数类类型或者函数类模板后，
    map会用它实例化一个比较函数。
    

    例子：对map中string类型key值进行降序排序
    #include <iostream>
    #include <algorithm>
    #include<iterator>
    #include<sstream>
    #include<stdlib.h>
    #include<stdio.h>
    #include <map>

    using namespace std;
    class Student { 
    public:
            Student(const string name=" "):name(name) { } 

            string getname() const { return name; }
    private:
            string name;
    };     

    /* 使用迭代器便利map */
    template <class Iter> void show_map(Iter first, Iter last) {
            for( ;first!=last; first++) {
                    cout << first->first<<"        "<< ((first)->second)->getname()<<endl;
            }
    }

    /* 声明一个函数类模板，使用typedef为其定义一个别名 */
    template<class T> class Funclass {
    public:
            bool operator()(const T &op1, const T &op2) {
                    return op1 > op2;//按照从大到小比较
            }
    };

    int main(void)
    {           
            std::map<string, Student *> map1;
            /* 利用map的第三个模板参数指定用于比较函数的类模板,
            * map会使用该函数类模板自动实例化一个比较函数，
            * 如果该比较函数返回 */
            std::map<string, Student *, Funclass<string> > map2;

            map1["444"] = map2["444"] =  new Student("mnjnkkl");
            map1["222"] = map2["222"] =  new Student("qqqqqqs");
            map1["111"] = map2["111"] =  new Student("ddsfass");
            map1["888"] = map2["888"] =  new Student("asdfdff");
            map1["666"] = map2["666"] =  new Student("eqwewqe");
            map1["555"] = map2["555"] =  new Student("sdfsfds");
    
            cout<<"显示map1的内容"<<endl;
            show_map(map1.begin(), map1.end());
            cout<<"\n显示map2的内容"<<endl;
            show_map(map2.begin(), map2.end());

            return 0;
    }

    运行结果：
    显示map1的内容
    111        ddsfass
    222        qqqqqqs
    444        mnjnkkl
    555        sdfsfds
    666        eqwewqe
    888        asdfdff

    显示map2的内容
    888        asdfdff
    666        eqwewqe
    555        sdfsfds
    444        mnjnkkl
    222        qqqqqqs
    111        ddsfass

    例子分析：
    从运行的结果中很容易看出，如果不给map1指定比较函数类类型或者模板
    的话，默认会提供升序排序的比较函数。

    在给map2提供了降序排序的比较函数模板后，map2便进行降序排序，从打
    印结果中很容易看出这一点。

   （2）给map类类型的key自定义比较函数
    如果map中键值对的key是类类型的话，必须给map指定自定义的比较函数类
    类型或者模板，否则将无法通过编译。
    
    例子：
    #include <iostream>
    #include <algorithm>
    #include<iterator>
    #include<sstream>
    #include<stdlib.h>
    #include<stdio.h>
    #include <map>

    using namespace std;
    class Stukey{
    public:
            Stukey(int key=1):key(key) {}
            int key;
    };

    class Student {
    public:
            Student(const string name=" "):name(name) { }

            string getname() const { return name; }
    private:
            string name;
    };

    /* 使用迭代器便利map */
    template <class Iter> void show_map(Iter first, Iter last) {
            for( ;first!=last; first++) {
                    cout << (first->first).key<<"     "<< ((first)->second)->getname()<<endl;
            }
    }
    class Funclass {
    public:
            bool operator()(const Stukey &op1, const Stukey &op2) {
                    return op1.key > op2.key;//按照从大到小比较
            }
    };

    int main(void)
    {
            /* 如果不给map1和map2指定自定义的比较函数类
             * 类行或者模板，将无法通过编译 */
            std::map<Stukey, Student *, Funclass> map1;

            /* 利用map的第三个模板参数指定比较函数类模板,
            * map会使用该函数类模板自动实例化一个比较函数 */
            std::map<Stukey, Student *, Funclass> map2;

            map1[Stukey(444)] = map2[Stukey(444)] =  new Student("mnjnkkl");
            map1[Stukey(222)] = map2[Stukey(222)] =  new Student("qqqqqqs");
            map1[Stukey(111)] = map2[Stukey(111)] =  new Student("ddsfass");
            map1[Stukey(888)] = map2[Stukey(888)] =  new Student("asdfdff");
            map1[Stukey(666)] = map2[Stukey(666)] =  new Student("eqwewqe");
            map1[Stukey(555)] = map2[Stukey(555)] =  new Student("sdfsfds");

            cout<<"显示map1的内容"<<endl;
            show_map(map1.begin(), map1.end());
            cout<<"\n显示map2的内容"<<endl;
            show_map(map2.begin(), map2.end());

            return 0;
    }

    运行结果：
    显示map1的内容
    888        asdfdff
    666        eqwewqe
    555        sdfsfds
    444        mnjnkkl
    222        qqqqqqs
    111        ddsfass

    显示map2的内容
    888        asdfdff
    666        eqwewqe
    555        sdfsfds
    444        mnjnkkl
    222        qqqqqqs
    111        ddsfass