[C++ 面试基础知识总结] 关联容器

关联容器类型

标准库共提供了8个关联容器
map 关联数组：保存关键字-值对
set 关键字即值，即只保存关键字的容器
multimap 关键字可重复出现的map
multiset 关键字可重复出现的set
unordered_map 用哈希函数组织的map
unordered_set 用哈希函数组织的set
unordered_multimap 用哈希函数组织,关键字可重复出现的map
unordered_multiset 用哈希函数组织,关键字可重复出现的set

map是关键字-值对的集合，通常被称为关联数组。关联数组与正常数组类似，不同之处在于其下标不必是整数，是一个关键字。而set就是关键字的简单集合。

关联容器概述

定义关联容器

    // 初始化map时，必须提供关键字类型和值类型。每个关键字-值对书写格式为{ key,value}
    map scores = {{"Summer",80},{"Seven",90},{"Leg",60}};
    set names = {"Summer","Seven","Leg"};

map和set的关键字必须是唯一的，而multimap和multiset没有此限制

   //定义一个有20个元素的vector，保存0-9每个整数的两个拷贝
    vector v;
    for (int i = 0; i != 10; ++i) {
        v.push_back(i);
        v.push_back(i);
    }

    //用vetor初始化set和multiset （关联容器支持容器通用的初始化，赋值和操作）
    set iset(v.begin(),v.end());
    multiset miset(v.begin(),v.end());

    cout << iset.size() << endl;  //结果为10
    cout << miset.size() << endl;  //结果为20

关键字类型的要求

有序关联容器的关键字类型必须定义元素比较的方法，默认情况下，标准库使用关键字类型的<运算符来比较两个关键字。也提供一个自定义的运算符。所提供的操作必须在关键字类型上定义一个严格弱序。即具备以下性质：
1.两个关键字不能同时“小于等于”对方。
2.如果k1“小于等于”k2，且k2“小于等于”k3，那么k1必须“小于等于”k3。
3.如果存在两个关键字，任何一个都不“小于等于”另一个，那么两个关键字“等价”，如果k1“等价于”k2，且k2“等价于”k3，那么k1必须“等价于”k3。

pair

pair定义在头文件utility中，一个pair保存两个数据对象，类似容器，创建pair时必须提供两个类型名，pair的数据成员将具有对应的类型。

    //将一个map容器中的元素保存到一个元素类型为pair的vector中
    map scores = {{"Summer",80},{"Seven",90},{"Leg",60}};
    vector> v;

    for(const auto &score : scores){
        //初始化一个pair，first和second分别为键值对中的关键字和值
        pair p (score.first,score.second);
        v.push_back(p);
    }

    for (const auto &p : v) {
        //pair的first和second分别为pair中的两个数据成员 输出结果Leg 60 Seven 90 Summer 80 （map已根据关键字自动排序）
        cout << p.first << " " << p.second << " ";
    }
    cout << endl;

关联容器操作

关联容器迭代器

map和set的关键字都为常量，不能改变。

    map scores = {{"Summer",80},{"Seven",90},{"Leg",60}};
    // mapIt类型为map::iterator，指向类型为pair的对象
    auto mapIt = scores.begin();
    while (mapIt != scores.end()) {
        //不能改变map关键字，但可以改变值
        cout << mapIt->first << " " << ++(mapIt++->second) << endl;
    }

    set names = {"Summer","Seven","Leg"};
    //setIt类型为set::iterator，指向类型为const string的对象
    for (auto setIt = names.begin(); setIt != names.end(); ++setIt) {
        //只能读取set关键字，不能改变
        cout << *setIt << endl;
    }

注意：由于关联容器关键字的const属性，不能讲关联容器传递给修改或重排容器元素的算法，所以通常不对关联容器使用泛型算法。

添加元素

调用insert函数可向map或set中添加一个元素或一个范围，若元素关键字已经存在，则不会有任何操作。

    set names = {"Summer","Seven","Leg"};
    names.insert("CannonFly");

    map scores = {{"Summer",80},{"Seven",90},{"Leg",60}};
    //以下4种写法等价
    scores.insert({"CannonFly",85});
    scores.insert(make_pair("CannonFly", 85));
    scores.insert(pair("CannonFly",85));
    scores.insert(map::value_type("CannonFly",85));

insert函数的返回值类型pair<指向指定关键字的迭代器,bool(成功标志)>

例如上述map执行insert后返回的类型为pair

    map scores = {{"Summer",80},{"Seven",90},{"Leg",60}};
    auto ret = scores.insert({"CannonFly",85});

可以使用insert的返回值

ret.first ret的第一个成员，是一个map迭代器，指向具有给定关键字的元素
ret.first->  ret的第一个成员解引，提取map中的元素，元素是一个pair
ret.first->first  map中元素的关键字部分
ret.first->second  map中元素的值部分
ret.second  ret的第二个成员，是一个bool值，表示是否插入成功

对于multimap，multiset，insert函数不返回标志是否成功bool值，因为可以插入相同关键字的元素。

删除元素

erase函数可以删除指定关键字的元素，迭代器所指的元素或者某个范围内的所有元素，返回值是实际删除的元素。

    map scores = {{"Summer",80},{"Seven",90},{"Leg",60}};
    scores.erase("Summer");  //删除map中关键字为Summer的元素
    scores.erase(scores.begin());  //删除map中第一个元素
    scores.erase(scores.begin(),scores.end());  //删除map中所有元素

访问元素

map和unordered_map可以采取下标的方式对其中与关键字相关联的值进行操作，而set只有关键字而没有与其关联的值，所以不支持下标。map下标的索引是关键字。

    map scores = {{"Summer",80},{"Seven",90},{"Leg",60}};
    scores["Summer"] = 85; 
    scores["CannonFly"] = 85;  // map中没有该关键字，则创建一个元素插入到map中，并对关联值初始化。   

除了下标之外，还有其他的查找元素的方法。

    map scores = {{"Summer",80},{"Seven",90},{"Leg",60}};
    scores.find("CannonFly");  //查找元素，找到返回该元素的迭代器，未找到返回尾后迭代器
    scores.count("Summer");  //返回元素在容器中出现的次数

    //下面是两种在允许重复关键字的关联容器中输出所有同名关键字的操作
    multiset names = {"Summer","Seven","Leg","Summer"};
    //lower_bound返回第一个不小于给定值的元素，names.upper_bound返回第一个大于给定值的元素
    for (auto begin = names.lower_bound("Summer"), end = names.upper_bound("Summer"); begin != end; ++begin) {
        cout << *begin << endl;
    }
    // equal_range返回一个迭代器pair，表示等于给定值的元素的范围
    for (auto pos = names.equal_range("Summer"); pos.first != pos.second; ++pos.first) {
        cout << *pos.first << endl;
    }

无序容器

无序关联容器不是使用比较运算法来组织元素，而是用一个哈希函数和关键字类型的==运算法。通常无序容器和其对应的有序容器是可以相互替换的，只是由于元素未按顺序存储，无序容器的输出通常会与有序容器不同。