C++Primer——第11章(关联容器)

• 或者是一个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 关联容器概述

• 定义一个map时，必须 既指明关键字类型 又指明值类型。（如：map<string, int> word_counts = { {"aa", 1}, {"bb", 2} };）
• 定义一个set时，只需指明关键字类型。（如：set<string> include = { "aa", "bb" };）

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函数" 来比较两个关键字）
    }
} 

• pair的数据成员是public的，在utility头文件中定义。
• 一个pair保存两个数据成员。（first 和 second）

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次
} 

• 解引用一个关联容器迭代器时，会得到一个类型为 容器的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;
    }
} 

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;    
    }
}  

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是 可以保存重复关键字的容器 ）
}     

• 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）
}   

• 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)，每个桶保存零个或多个元素。无序容器使用一个哈希函数 将元素映射到桶。

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 个桶中
}