关联容器和顺序容器的区别:关联容器中的元素 是按照关键字 来保存和访问的。
关联容器支持 通过关键字 来高效地查找和读取元素,基本的关联容器类型是 mapset
关联容器类型:
按关键字有序保存元素:
map
关联数组:保存关键字-值对
set
关键字即值,即只保存关键字的容器
multimap
支持同一个键多次出现的map
multiset
支持同一个键多次出现的set
无序集合:
unordered_map
用哈希函数组织的map
unordered_set
用哈希函数组织的set
unordered_multimap
哈希组织的map,关键字可以重复出现
unordered_multiset
哈希组织的set,关键字可以重复出现
这8个容器间的不同体现在三个维度上:
  • 或者是一个set,或者是一个map。
  • 或者要求不重复的关键字,或者允许重复关键字。
  • 或者按顺序保存元素,或无序保存元素。

11.1 使用关联容器

  • map:是关键字-值对的集合。(map中的元素是一个 pair类型的对象)
  • set:是关键字的简单集合。
int main() {
    // 统计数组中 单词出现的次数(map):
    map<string, size_t> word_counts;
    vector<string> words = { "aa","bb","cc","cc" ,"bb","cc" };

    for (auto w : words) {
        ++word_counts[w];         // w为"键",word_counts[w]为"值"。若map中存在这样的单词w 就将键对应的"值"+1; 若不存在w,则将w作为"键"插入map(其对应的"值"初始为0),再将"值"+1
    }
    for (auto counts : word_counts) {
        cout << counts.first << ": 有 " << counts.second << " 个" << endl;        // 输出: "aa"有1个,"bb"有2个,"cc"有3个
    }                                                                             // counts为map中的元素(pair类型对象): couts.first为"键"、count.second为"值"
       

    // 检查数组中 是否有重复的单词(set):
    set<string> include;
    vector<string> words1 = { "aa","bb","aa","cc" ,"bb" };
    
    for (auto w : words1) {
        if (include.find(w) == include.end()) {        // include.find(w)查找set中是否存在w。如果返回的迭代器为end,说明set中不存在w,则将w插入set; 如果返回迭代器不为end,说明set中已经存在w,因此重复
            include.insert(w);
        }
        else {
            cout << w << " 重复出现!" << endl;         // 输出: "aa"重复出现,"bb"重复出现
        }
    }
}     

11.2 关联容器概述

(1) 定义关联容器:
  • 定义一个map时,必须 既指明关键字类型 又指明值类型。(如:map<string, int> word_counts = { {"aa", 1}, {"bb", 2} };
  • 定义一个set时,只需指明关键字类型。(如:set<string> include = { "aa", "bb" };
注:我们也可以将关联容器初始化为 另一个同类型容器的拷贝,或是从一个值范围 来初始化关联容器,只要这些值可以转化为 容器所需类型就可以。

(2) 关键字类型的要求:
对于有序容器,关键字类型必须定义 元素比较的方法。(默认情况下,标准库使用 关键字类型的<运算符 来比较两个关键字)
bool compare_len(const string& str1, const string& str2) {        // 单词按 短到长的顺序 排序
    return str1.size() < str2.size();
}

int main() {
    vector<string> words = { "aaaa","bb","d","ccc","d" };

    // 默认情况下,标准库使用 关键字类型的<运算符 来比较两个关键字:
    multiset<string> multi_set1(words.begin(), words.end());
    for (auto w : multi_set1) {
        cout << w << " ";              // 输出: {"aaaa","bb","ccc","d","d"} (默认情况下,用string类型的"<运算符" 来比较两个关键字)
    }


    // 显式地传递一个比较函数 来比较两个关键字:
    multiset<string, decltype(compare_len)*> multi_set2(compare_len);        // decltype用于compare_len函数,返回函数类型而非函数指针类型,因此加上* 来指出我们需要一个函数类型的指针
    for (auto w : words) {                                                   // 把函数作为一个值使用时,该函数自动地转换成指针。(使用 compare_len 和 &compare_len 是一样的)
        multi_set2.insert(w);
    }
    for (auto w : multi_set2) { 
        cout << w << " ";             // 输出: {"d","d","bb","ccc","aaaa"} (显式地用 自定义的"compare_len函数" 来比较两个关键字)
    }
} 

(3) pair类型:
  • pair的数据成员是public的,在utility头文件中定义。
  • 一个pair保存两个数据成员。(first 和 second)
pair的操作:
pair<T1, T2> p;
p是一个pair,两个类型分别是T1和T2的成员 都进行了值初始化。
pair<T1, T2> p(v1, v2);
first和second分别用 v1和v2进行初始化。
pair<T1, T2>p = {v1, v2};
等价于p(v1, v2)。
make_pair(v1, v2);
返回一个 用v1和v2初始化的pair。pair的类型从v1和v2的类型推断出来。
p.first
返回p的 名为first的数据成员。
p.second
返回p的 名为second的数据成员。
p1 relop p2
关系运算符(<,>,<=,>=) 按字典序定义。关系运算 利用元素的relop运算符来实现。
p1 == p2
当first和second成员 分别相等时,两个pair相等。
p1 != p2
同上。
int main() {
    pair<string, int> pa1{ "aaa",1 };
    auto pa2 = std::make_pair("bbb", 2);

    cout << pa1.first << " 出现" << pa1.second << "次";         // 输出: "aaa" 出现1次
    cout << pa2.first << " 出现" << pa2.second << "次";         // 输出: "bbb" 出现2次
} 

11.3 关联容器操作

关联容器额外的类型别名:
key_type
此容器类型的 关键字类型。
mapped_type
每个关键字关联的类型 ("值"的类型),只适用于map
value_type
对于map,是pair<const key_type, mapped_type>类型; 对于set,和key_type相同。

(1) 关联容器迭代器:
  • 解引用一个关联容器迭代器时,会得到一个类型为 容器的value_type的值 的引用。
  • map的关键字是const的。
  • set的迭代器是const的。
  • 使用begin和end,遍历map、multimap、set、multiset时,迭代器按关键字升序遍历元素。(因为这些是有序容器)
int main() {
    vector<string> words{ "bb","aa","dd","cc" ,"aa" };
    set<string> set(words.begin(), words.end());
    map<string, int> map;
    for (auto w : words) {
        ++map[w];
    }
    
    // map的关键字是const的,set的迭代器是const的(只可读不可写):
    auto map_iter = map.begin();
    auto set_iter = set.begin();
    cout << "map——键: " << map_iter->first << "  值: " << map_iter->second << endl;        // 输出: map——键: "aa"  值: 2
    cout << "set——键: " << *set_iter << endl;                                              // 输出: set——键: "aa"
    map_iter->first = "bb";        // 错误: map的关键字是const的
    *set_iter = "bb";              // 错误: set的迭代器是const的
    

    // 遍历关联容器:
    for (auto map_iter = map.begin(); map_iter != map.end(); ++map_iter) {
        cout << "map——键: " << map_iter->first << "  值: " << map_iter->second << endl;
    }
    for (auto set_iter = set.begin(); set_iter != set.end(); ++set_iter) {
        cout << "set——键: " << *set_iter << endl;
    }
} 
 
(2) 添加元素:
关联容器insert操作:
c.insert(v)
v是value_type类型的对象;args用来构造一个元素。 函数返回一个pair,包含一个迭代器,指向具有指定关键字的元素,以及一个 指示插入是否成功的bool值。
对于map和set,只插入关键字不在c中的元素。对于multimap和multiset 则总会插入给定元素,并返回一个 指向新元素的迭代器。
c.emplace(args)
c.insert(b, e)
b和e是迭代器,表示一个c::value_type类型值的范围;il是这种值的花括号列表。 函数返回void。 
对于map和set,只插入关键字不在c中的元素。对于multimap和multiset 则总会插入给定元素,并返回一个 指向新元素的迭代器。
c.insert(il)
c.insert(p, v)
类似insert(v)或c.emplace(args),但将迭代器p作为一个提示,指出从哪里开始搜索 新元素应该存储的位置。返回一个迭代器,指向具有给定关键字的元素。
c.emplace(p, args)
int main() {
    map<string, int> word_count;
    multimap<string, string> authors;

    // 向map插入元素的 4种方法:
    word_count.insert({ "aa",1 });
    word_count.insert(std::make_pair("aa", 1));
    word_count.insert(pair<string, int>("aa", 1));
    word_count.insert(map<string, int>::value_type("aa", 1));


    // 检测insert的返回值:
    auto ret1 = word_count.insert({ "aa",1 });              // ret1和ret2 都为pair类型 (first为 map<string,int>::iterator类型,second为 bool类型)
    auto ret2 = word_count.insert({ "bb",1 });
    
    cout << ret1.first->first << " 出现" << ret1.first->second << " 次" << endl;        // 输出: "aa" 出现1 次     
    cout << (ret1.second ? "插入成功" : "关键字已存在,插入失败") << endl;                // 输出: "关键字已存在,插入失败" 
    cout << ret2.first->first << " 出现" << ret2.first->second << " 次" << endl;        // 输出: "bb" 出现1 次
    cout << (ret2.second ? "插入成功" : "关键字已存在,插入失败") << endl;                // 输出: "插入成功"


    // 向multimap添加元素:
    auto ret3 = authors.insert({ "Bob","book1" });         // ret3和ret4 都为multimap<string,int>::iterator类型
    auto ret4 = authors.insert({ "Bob","book2" });

    for (auto pa : authors) {                              // 输出: "Bob——book1","Bob——book2"(允许重复关键字存在)
        cout << pa.first << "——" << pa.second << endl;    
    }
}  

(3) 删除元素:
从关联容器中删除元素:
c.erase(k)
从c中删除每个 关键字为k的元素。返回一个size_type值,指出删除的元素的数量。
c.erase(p)
从c中删除 迭代器p指定的元素。p必须指向c中一个真实元素,不能等于c.end()。返回一个指向p之后元素的迭代器,若p指向c中的尾元素,则返回c.end()。
c.erase(b, e)
删除迭代器对b和e所表示范围中的元素。返回e。
int main() {
    map<string, int> _map{ {"aaa",1},{"aaa",1 } };
    multimap<string, int> multi_map{ {"aaa",1},{"aaa",1 } };

    cout << _map.erase("aaa") << endl;               // 输出: 1 (删掉关键字为"aaa"的元素,返回删除的元素个数1,因为map是 保存不重复关键字的容器)
    cout << multi_map.erase("aaa") << endl;          // 输出: 2 (删掉关键字为"aaa"的元素,返回删除的元素个数2,因为multimap是 可以保存重复关键字的容器 )
}     

(4) map的下标操作:
map和unordered_map的下标操作:
c[k]
 返回关键字为k的元素;如果k不在c中,添加一个关键字为k的元素,并对其值初始化。
c.at(k)
访问关键字为k的元素,带参数检查;若k不存在c中,则抛出一个out_of_range异常。
  • set类型不支持下标,因为set中没有与关键字相关联的“值”。
  • 不能对 multimap或unordered_multimap 进行下标操作,因为这些容器中 可能有多个值与一个关键字相关联。
  • 下标和at操作只适用于 非const的map和unordered_map。
  • map下标运算符[ ]接受一个索引(即一个关键字),获取与此关键字 相关联的值。但是,与其他下标运算符不同的是,如果关键字不存在map中,则会为它创建一个元素 并插入到map中,关联值 将进行值初始化。
int main() {
    map<string, int> _map;

    int n = _map["aaa"];          // n=0 (因为"aaa"并不存在于_map中,因此为之创建一个元素,并插入到_map中,关联值 进行值初始化为0)
}   

(5) 查找元素:
在一个关联容器中查找元素的操作:
c.find(k)
返回一个迭代器,指向第一个关键字为k的元素,若k不在容器中,则返回尾后迭代器。
c.count(k)
返回关键字等于k的元素 的数量。对于不允许重复关键字的容器,返回值永远是0或1。
c.lower_bound(k)
返回一个迭代器,指向第一个关键字 不小于k的元素。
c.upper_bound(k)
返回一个迭代器,指向第一个关键字 大于k的元素。
c.equal_range(k)
返回一个迭代器pair,表示关键字等于k的元素 的范围。若k不存在,pair的两个成员均等于c.end()。
  • lower_bound和upper_bound不适用于 无序容器。
int main() {
    // 在map中使用find来查找元素:
    map<string, int> _map{ {"aaa",1} ,{"bbb",1},{"ccc",1} };

    auto iter1 = _map.find("bbb");                                       // iter1为 map<string,int>::iterator类型 (指向第一个关键字为"bbb"的元素 的迭代器)
    cout << iter1->first << " —— " << iter1->second << endl;             // 输出: "bbb —— 1"



    // 在multimap中查找元素:
    multimap<string, string> multi_map{ {"Bob","book1"},{"Bob","book2"},{"Alice","book1"},{"Alice","book2"},{"Tom","book1"} };

    // (方法1)
    auto iter2 = multi_map.find("Alice");                                // 指向第一个关键字为"Alice"的元素 的迭代器
    auto counts = multi_map.count("Alice");                              // 关键字为"Alice"的元素的数量

    while (counts) {
        cout << iter2->first << " —— " << iter2->second << endl;         // 输出: "Alice —— book","Alice —— book2"
        ++iter2;
        --counts;
    }

    // (方法2)
    auto beg = multi_map.lower_bound("Alice");                           // 指向第一个关键字为"Alice"的元素 的迭代器
    auto end = multi_map.upper_bound("Alice");                           // 指向最后一个关键字为"Alice"的元素 之后的迭代器

    while (beg != end) {
        cout << beg->first << " —— " << beg->second << endl;             // 输出: "Alice —— book","Alice —— book2"
        ++beg;
    }

    // (方法3)
    auto pos = multi_map.equal_range("Alice");                                   // pos为一个pair (first和second为 标识关键字等于k的元素的范围 的迭代器)
    
    while (pos.first != pos.second) {                           
        cout << pos.first->first << " —— " << pos.first->second << endl;         // 输出: "Alice —— book","Alice —— book2"
        ++pos.first;
    }
}     

11.4 无序容器

  • 有序容器使用 比较运算符 来组织元素;无序容器使用 哈希函数关键字类型的==运算符
  • 无序容器在存储上组织为一组桶(bucket),每个桶保存零个或多个元素。无序容器使用一个哈希函数 将元素映射到桶。
无序容器管理操作:
桶接口
c.bucket_count()
正在使用的桶的数目。
c.max_bucket_count()
容器能容纳的最多的 桶的数目。
c.bucket_size(n) 
第n个桶中 有多少个元素。
c.bucket(k)
关键字为k的元素 在哪个桶中。
桶迭代:
local_iterator
可以用来访问 桶中元素的迭代器类型。
const_local_iterator
同上,const版本。
c.begin(n),c.end(n)
桶n的 首元素迭代器和尾后迭代器。
c.cbegin(n),c.cend(n)
同上,const版本。
哈希策略:
c.load_factor()
每个桶的平均元素数量,返回float值。
c.max_load_factor()
c试图维护的 平均桶大小,返回float值。c会在需要时添加新的桶,以使得 load_factor<=max_load_factor。
c.rehash(n)
重组存储,使得 bucket_count>=n,且 bucket_count>size/max_load_factor。
c.reverse(n)
重组存储,使得c可以保存n个元素 且不必rehash。

无序容器对关键字类型的要求:
默认情况下,无序容器使用 关键字类型的==运算符 来比较元素,它们还使用一个 hash<key_ type>类型的对象 来生成每个元素的 哈希值
标准库为内置类型(包括指针) 提供了hash模板。还为一些标准库类型(包括string和的智能指针类型) 定义了hash。
因此,我们可以直接定义 关键字是内置类型(包括指针类型)、string还是智能指针类型 的无序容器。
注:但是,我们不能直接定义 关键字类型为自定义类类型 的无序容器。与容器不同,不能直接使用哈希模板,而必须提供我们自己的 hash模板版本
class Demo{
public:
    Demo(const string& s = "") :str(s) {}

    string str;
};

size_t hasher(const Demo& de) {                       // 自定义哈希函数 
    return std::hash<string>()(de.str);               // 根据标准库为string 设置的hash模板,来生成hash<string>类型的对象,从而生成每个元素的哈希值
}

bool eqOp(const Demo& de1, const Demo& de2) {         // 自定义比较相等函数
    return de1.str.size() == de2.str.size();          // 如果Demo类型的元素的 成员对象str的长度相等 则元素相等
}


int main() {
    Demo d1("aaa");
    Demo d2("bbb");
    Demo d3("ccc");
    Demo d4("aaa");

    unordered_set<Demo> words1{ {Demo("aaa")}, { Demo("bbb")}, { Demo("bbb")}};                    // 错误: 标准库没有为 Demo类型定义 "==运算符"和哈希函数 (Demo是自定义类类型)
    unordered_multiset<Demo, decltype(hasher)*, decltype(eqOp)*> words2{ 10,hasher, eqOp };        // 正确 (参数分别为: 桶的大小,哈希函数指针,相等性判断运算符指针)
    words2.insert(d1);                   
    words2.insert(d2);
    words2.insert(d3);
    words2.insert(d4);

    auto ret1 = words2.bucket(d1);
    auto ret2 = words2.bucket(d2);
    auto ret3 = words2.bucket(d3);
    auto ret4 = words2.bucket(d4);
    cout << "d1在第 " << ret1 << " 个桶中" << endl;        // 输出: d1在第 2 个桶中
    cout << "d2在第 " << ret2 << " 个桶中" << endl;        // 输出: d2在第 5 个桶中
    cout << "d3在第 " << ret3 << " 个桶中" << endl;        // 输出: d3在第 0 个桶中
    cout << "d4在第 " << ret4 << " 个桶中" << endl;        // 输出: d4在第 2 个桶中
}        
注:如果我们的类定义了 ==运算符,则可以只重载哈希函数。