【C++ Primer】第 11 章 关联容器

十一、关联容器

关联容器与顺序容器有着根本的不同：关联容器中的元素是按关键字来保存和访问的。与之相对，顺序容器中的元素是按它们在容器中的位置来顺序保存和访问的。

关联容器支持高效的关键字查找和访问。两个主要的关联容器类型是 map 和 set。标准库提供 8 个关联容器，这 8 个容器间的不同体现在三个维度上：

1. 或者是一个 set，或者是一个 map
2. 或者要求不重复的关键字，或者允许重复关键字（包含单词 multi）
3. 按顺序保存元素，或无序保存（包含单词 unordered）

11.1 使用关联容器

1. 使用 map：单词计数程序

   #include <iostream>
   #include <map>
   
   using namespace std;
   
   int main() {
       map<string, size_t> wordCount;
       string word;
       while (cin >> word) {
           ++wordCount[word];
       }
   
       for (const auto &w: wordCount) {
           cout << w.first << " occurs " << w.second << (w.second > 1 ? " times" : "time") << endl;
       }
   } 
   

2. 使用 set：排除常见单词

   set<string> exclude = {"The", "But", "And", "Or", "An", "A",
                          "the", "but", "and", "or", "an", "a"};
   map<string, size_t> wordCount;
   string word;
   while (cin >> word) {
       if (!exclude.count(word)) {
           ++wordCount[word];
       }
   }
   

11.2 关联容器概述

关联容器（有序的和无序的）都支持 9.2 节中介绍的普通容器操作。关联容器不支持顺序容器的位置相关的操作，例如 push_front 和 push_back。原因是关联容器中元素是根据关键字存储的，这些操作对关联容器没有意义。而且，关联容器也不支持构造函数或插入操作这些接受一个元素值和一个数量值的操作。

除了与顺序容器相同的操作之外，关联容器还支持一些顺序容器不支持的操作和类型别名。此外，无序容器还提供了一些用来调整哈希性能的操作。关联容器的迭代器都是双向的（参见 10.5.1 节）。

11.2.1 定义关联容器

每个关联容器都定义了要给默认构造函数，它创建一个指定类型的空容器。我们也可以将关联容器初始化为另一个同类型容器的拷贝，或是从一个值范围来初始化关联容器，这要这些值可以转化为容器所需类型就可以。

在 C++11 新标准下，我们也可以对关联容器进行值初始化：

// 空容器
std::map<std::string, size_t> word_count;
// 列表初始化
std::set<std::string> exclude = {"The", "But", "And", "Or", "An", "A",
                                 "the", "but", "and", "or", "an", "a"};
std::map<std::string, std::string> authors = {
        {"Joyce", "James"},
        {"Austen", "Jane"},
        {"Dickens", "Charles"},
};

1. 初始化 multimap 或 multiset：

   // 电话簿应用
   std::multimap<std::string, std::string> phoneBook = {
           {"Alice", "13624727245"},
           {"Alice", "18762462462"},
           {"Bob",   "16203523621"}
   };
   // Alice's phone number: 13624727245
   // Alice's phone number: 18762462462
   auto range = phoneBook.equal_range("Alice");
   for (auto it = range.first; it != range.second; ++it) {
       std::cout << "Alice's phone number: " << it->second << std::endl;
   }
   
   // 维护多个排序集合
   std::multiset<int> numbers = {10, 20, 30, 20, 10};
   // 10 10 20 20 30
   std::for_each(numbers.begin(), numbers.end(), [](int val) {
       std::cout << val << " ";
   });
   

11.2.2 关键字类型的要求

关联容器对其关键字类型有一些限制。对于有序容器，关键字类型必须定义元素比较的方法。默认情况下，标准库使用关键字类型的 < 运算符来比较两个关键字。

1. 有序容器的关键字类型：可以提供自己定义的操作来代替关键字上的 < 运算符。所提供的操作必须在关键字类型上定义一个严格弱序，可以将严格弱序看作小于等于，需要具备如下性质：

   • 两个关键字不能同时小于等于对方
   • k1 <= k2 && k2 <= k3 必须能够推导出 k1 <= k3
   • 如果存在两个关键字，任何一个都不小于等于另一个，那么我们称这两个关键字是等价的。如果 k1 等价于 k2，且 k2 等价于 k3，那么 k1 必须等价于 k3

   如果两个关键字是等价的，那么容器将它们视作相等来处理。当用作 map 的关键字时，只能有一个元素与这两个关键字关联，我们可以用两者中任意一个来访问对应的值。

   这段话的核心在于理解如何通过自定义比较逻辑来实现一种宽松的排序关系（即严格弱序），而不是严格的数学意义上的大小关系。这种自定义允许程序员根据具体需求灵活地处理关键字之间的顺序关系，同时保证了数据结构的基本一致性。

2. 使用关键字类型的比较函数：用来组织一个容器中元素的操作的类型也是该容器类型的一部分。为了指定使用自定义的操作，必须在定义关联容器类型时提供此操作的类型：

   #include <iostream>
   #include <set>
   
   class Sales_data {
   public:
       std::string isbn() const {
           return bookNo;
       }
   
   private:
       std::string bookNo;
   };
   
   bool compareIsbn(const Sales_data &item1, const Sales_data &item2) {
       return item1.isbn() < item2.isbn();
   }
   
   int main() {
       std::multiset<Sales_data, decltype(compareIsbn) *> bookstore(compareIsbn);
   }
   

11.2.3 pair 类型

一个 pair 保存两个数据成员。类似容器，pair 是一个用来生成特定类型的模板。当创建一个 pair 时，我们必须提供两个类型名，pair 的数据成员将具有对应的类型。pair 的默认构造函数对数据成员进行值初始化，也可以为每个成员提供初始化器。

与其他标准库类型不同，pair 的数据成员是 public 的。两个成员分别命名为 first 和 second：

#include <iostream>
#include <utility>
#include <vector>

int main() {
    std::pair<std::string, std::string> anno;
    std::pair<std::string, std::size_t> wordCount;
    std::pair<std::string, std::vector<int>> line;
    std::pair<std::string, std::string> author{"James", "Joyce"};
    // first = James, second = Joyce
    std::cout << "first = " << author.first << ", second = " << author.second << std::endl;
}

1. 创建 pair 对象的函数：在 C++11 新标准下，我们可以对返回值进行列表初始化：

   std::pair<std::string, int> process(std::vector<std::string> &v) {
       if (!v.empty()) {
           // 等价写法 return std::make_pair(v.back(), v.back().size());
           return {v.back(), v.back().size()};
       }
   
       // 早期版本的 C++ 必须显式构造 pair 返回，C++11 允许直接返回 {}
       return std::pair<std::string, int>();
   }
   

11.3 关联容器操作

除了 9.2 节中列出的类型，关联容器还定义了下表中的类型，这些类型表示容器关键字和值的类型：

std::set<std::string>::value_type v1;           // v1 是一个 string
std::set<std::string>::key_type v2;             // v2 是一个 string
std::map<std::string, int>::value_type v3;      // v3 是一个 pair<const string, int>
std::map<std::string, int>::key_type v4;        // v4 是一个 string
std::map<std::string, int>::mapped_type v5;     // v5 是一个 int

11.3.1 关联容器迭代器

当解引用一个关联容器迭代器时，我们会得到一个类型为容器的 value_type 的值的引用。对 map 而言，value_type 是一个 pair 类型，其 first 成员保存 const 的关键字，second 成员保存值：

std::map<std::string, int> word_count;
// *iter 是一个指向 pair<const string, int> 对象的引用
auto iter = word_count.begin();
std::cout << "key = " << iter->first << " value = " << iter->second << std::endl;
// 通过迭代器改变 value
++iter->second;
// 编译错误：key 是 const 的
iter->first = "newKey";

1. set 的迭代器是 const 的：虽然 set 类型同时定义了 iterator 和 const_iterator 类型，但两种类型都只允许只读 set 中的元素，其关键字是 const 的：

   std::set<int> ints = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
   std::set<int>::iterator iter = ints.begin();
   while (iter != ints.end()) {
       std::cout << *iter++ << " ";
       // *iter = 42; // 编译错误：set 中的关键字是只读的
   }
   

2. 遍历关联容器：

   std::map<std::string, int> word_count;
   auto iter = word_count.cbegin();
   while (iter != word_count.cend()) {
       std::cout << iter->first << " occurs " << iter->second << " times" << std::endl;
       ++iter;
   }
   

3. 关联容器和算法：我们通常不对关联容器使用泛型算法。关键字是 const 这一特性意味着不能将关联容器传递给修改或重排容器元素的算法。

   关联容器可用于只读取元素的算法。但是，很多这类算法都要搜索序列。由于关联容器中的元素不能通过它们的关键字进行（快速）查找，因此对其使用泛型搜索算法几乎总是个坏主意。

   在实际编程中，如果我们真要对一个关联容器使用算法，要么是将它当作一个源序列，要么当作一个目的位置。例如，可以用泛型算法 copy 从一个关联容器拷贝到另一个序列等。

11.3.2 添加元素

1. 向 map 添加元素：对一个 map 进行 insert 操作时，必须记住元素类型是 pair:

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

   在 C++11 标准下，创建一个 pair 最简单的方法时在参数列表中使用花括号初始化。

2. 检测 insert 的返回值：insert（或 emplace）返回的值依赖于容器类型和参数。对于不包含重复关键字的容器，添加单一元素的 insert 和 emplace 版本返回一个 pair，告诉我们插入操作是否成功。pair 的 first 成员是一个迭代器，指向具有给定关键字的元素；second 成员是一个 bool 值，指出元素是插入成功还是已经存在于容器中。如果关键字已在容器中，则 insert 什么事情也不做，且返回值中 bool 部分为 false。如果关键字不存在，元素被插入容器中，且 bool 值为 true。

   std::map<std::string, std::size_t> word_count;
   std::string word;
   while (std::cin >> word) {
       std::pair<std::map<std::string, std::size_t>::iterator, bool> ret = word_count.insert({word, 1});
       // word 已在 word_count 中，insert 什么也不做，手动递增计数器
       if (!ret.second) {
           ++ret.first->second;
           ++((ret.first)->second);
       }
   }
   

3. 展开递增语句：++ret.first->second <=> ++((ret.first)->second)

4. 向 multiset 或 multimap 添加元素：对于允许重复关键字的容器，接受单个元素的 insert 操作返回一个指向新元素的迭代器：

   std::multimap<std::string, std::string> authors;
   authors.insert({"Barth, John", "Sot-Weed Factor"});
   authors.insert({"Barth, John", "Lost in the Funhouse"});
   

11.3.3 删除元素

11.3.4 map 的下标操作

map 和 unordered_map 容器提供了下标运算符和一个对应的 at 函数。set 类型不支持下标，因为 set 中没有与关键字相关联的值。我们不能对一个 multimap 或一个 unordered_multimap 进行下标操作，因为这些容器中可能有多个值与一个关键字相关联。

// 1. 在 word_count 中搜索关键字为 Anna 的元素，未找到
// 2. 保存一个新的键值对插入到 word_count 中。值进行值初始化，在本例中初始化为 0
// 3. 提取出新插入的元素，并将值 1 赋予它
std::map<std::string, std::size_t> word_count;
word_count["Anna"] = 1;

1. 使用下标操作的返回值：通常情况下，解引用一个迭代器所返回的类型与下标运算符返回的类型是一样的。但对 map 则不然：

   • 当对一个 map 进行下标操作时，会获得一个 mapped_value 对象
   • 当解引用一个 map 迭代器时，会得到一个 value_type 对象

   // map 的下标运算符返回一个左值，因而既可以读也可以写
   std::map<std::string, std::size_t> word_count;
   word_count["Anna"] = 1;
   std::cout << word_count["Anna"] << std::endl;   // 1
   ++word_count["Anna"];
   std::cout << word_count["Anna"] << std::endl;   // 2
   

11.3.5 访问元素

• lower_bound 和 upper_bound 不适用于无序容器
• 下标和 at 操作只适用于非 const 的 map 和 unordered_map

1. 对 map 使用 find 代替下标操作：对 map 和 unordered_map 类型，下标运算符提供了最简单的提取元素的方法。但其存在一个严重的副作用：如果关键字还未在 map 中，下标操作会插入一个具有给定关键字的元素。当我们仅仅想知道一个关键字是否在 map 中而不想改变 map 时，此种情况下我们应该使用 find。

2. 在 multimap 或 multiset 中查找元素：如果一个 multimap 或 multiset 中有多个元素具有给定关键字，则这些元素在容器中会相邻存储：

   std::multimap<std::string, std::string> authorBooks = {
           {"spring",     "java"},
           {"bear",       "python"},
           {"springbear", "c"},
           {"springbear", "cpp"},
           {"springbear", "go"},
   };
   std::string target = "springbear";
   auto cnt = authorBooks.count(target);
   auto iter = authorBooks.find(target);
   while (cnt > 0) {
       std::cout << "author = " << target << ", book = " << iter->second << std::endl;
       ++iter;
       --cnt;
   }
   

3. 一种不同的，面向迭代器的解决方法：用相同的关键字调用 lower_bound 和 upper_bound 会得到一个迭代器范围，表示所有具有该关键字的元素的范围：

   • 如果关键字在容器中，lower_bound 返回的迭代器指向第一个具有给定关键字的元素，而 upper_bound 返回的迭代器指向最后一个匹配给定关键字的元素之后的位置
   • 如果元素不在容器中，则 lower_bound 和 upper_bound 会返回相等的迭代器，指向一个不影响排序的关键字插入位置

   std::multimap<std::string, std::string> authorBooks = {
           {"spring",     "java"},
           {"bear",       "python"},
           {"springbear", "c"},
           {"springbear", "cpp"},
           {"springbear", "go"},
   };
   std::string target = "springbear";
   for (auto beg = authorBooks.lower_bound(target), end = authorBooks.upper_bound(target);
        beg != end; ++beg) {
       std::cout << "author = " << target << ", book = " << beg->second << std::endl;
   }
   

4. equal_range 函数：

   std::multimap<std::string, std::string> authorBooks = {
           {"spring",     "java"},
           {"bear",       "python"},
           {"springbear", "c"},
           {"springbear", "cpp"},
           {"springbear", "go"},
   };
   std::string target = "springbear";
   for (auto pos = authorBooks.equal_range(target); pos.first != pos.second; ++pos.first) {
       std::cout << "author = " << target << ", book = " << pos.first->second << std::endl;
   }
   

11.3.6 一个单词转换的 map

• mapping.txt

  brb be right back
  k okay?
  y why
  r are
  u you
  pic picture
  thk thanks!
  l8r later
  

• input.txt

  where r u
  y dont u send me a pic
  k thk l8r
  

• 程序输出：

  where are you
  why dont you send me a picture
  okay? thanks! later
  

#include <iostream>
#include <map>
#include <fstream>
#include <sstream>

using namespace std;

map<string, string> build_map(ifstream &map_file) {
    map<string, string> trans_map;
    string key, value;
    // key 保存第一个单词，value 存入剩余行内容
    while (map_file >> key && getline(map_file, value)) {
        if (value.size() > 1) {
            trans_map[key] = value.substr(1);   // 跳过前导空格
        } else {
            throw runtime_error("no rule for " + key);
        }
    }
    return trans_map;
}

const string &transform(const string &s, const map<string, string> &m) {
    auto iter = m.find(s);
    if (iter != m.cend()) {
        return iter->second;
    } else {
        return s;
    }
}

void word_transform(ifstream &map_file, ifstream &input) {
    auto trans_map = build_map(map_file);
    string text;
    while (getline(input, text)) {
        istringstream iss(text);    // 读取每个单词
        string word;
        bool first = true;
        while (iss >> word) {
            if (first) {
                first = false;
            } else {
                cout << " ";
            }
            cout << transform(word, trans_map);
        }
        cout << endl;
    }
}

int main() {
    ifstream mapping(R"(D:\Repository\study\cpp-study\mapping.txt)");
    if (!mapping) {
        cerr << "Mapping file could not be opened for reading." << endl;
        return EXIT_FAILURE;
    }

    ifstream input(R"(D:\Repository\study\cpp-study\input.txt)");
    if (!input) {
        cerr << "Input file could not be opened for reading." << endl;
        return EXIT_FAILURE;
    }

    try {
        word_transform(mapping, input);
    } catch (const runtime_error &e) {
        cerr << e.what() << endl;
        return EXIT_FAILURE;
    }

    return EXIT_SUCCESS;
}

11.4 无序容器

C++11 新标准定义了 4 个无序关联容器。这些容器不是使用比较运算符来组织元素，而是使用一个哈希函数和关键字类型的 == 运算符。在关键字类型的元素没有明显的序关系的情况下，无序容器是非常有用的。在某些应用中，维护元素的序的代价非常高昂，此时无需容器也很有用。

1. 使用无序容器：除了哈希管理操作之外，无序容器提供了与有序容器相同的操作。由于元素未按顺序存储，一个使用无序容器的程序的输出（通常）会与使用有序容器的版本不同。

2. 管理桶：无序容器在存储上组织为一组桶，每个桶保存零个或多个元素。无序容器使用一个哈希函数将元素映射到桶。为了访问一个元素，容器首先计算元素的哈希值，它指出应该搜索哪个桶。容器将具有一个特定哈希值的所有元素都保存在相同的桶中。

   

   无序容器提供了一组管理桶的函数，这些成员函数允许我们查询容器的状态以及在必要时强制进行重组：

   • 桶接口：

     桶接口管理操作	说明
     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)	桶 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

3. 无序容器对关键字类型的要求：默认情况下，无序容器使用关键字的 == 运算符来比较元素，它们还使用一个 hash<key_type> 类型的对象来生成每个元素的哈希值。标准库为内置类型（包括指针）提供了 hash 模板。还为一些标准库类型，包括 string 和智能指针类型定义了 hash。因此，我们可以直接定义关键字是内置类型、string 或是智能指针的无序容器。

   但是，我们不能定义关键字类型为自定义类类型的无序容器。与容器不同，不能直接使用哈希模板，而必须提供我们自己的 hash 模板版本。

   我们不使用默认的 hash，而是使用另一种方法，类似于为有序容器重载关键字类型的默认比较操作。为了能将 Sales_data 用作关键字，我们需要提供函数来替代 == 运算符和哈希值计算函数：

   #include <iostream>
   #include <unordered_set>
   #include <utility>
   
   using namespace std;
   
   class Sales_data {
   public:
       std::string isbn() const {
           return this->bookNo;
       }
   
       Sales_data() = default;
   
       explicit Sales_data(string s) : bookNo(std::move(s)) {}
   
   private:
       string bookNo;
   };
   
   
   size_t hasher(const Sales_data &sd) {
       return hash<string>()(sd.isbn());
   }
   
   bool eqOp(const Sales_data &lhs, const Sales_data &rhs) {
       return lhs.isbn() == rhs.isbn();
   }
   
   using SD_multiset = unordered_multiset<Sales_data, decltype(hasher) *, decltype(eqOp) *>;
   
   int main() {
       // 参数是桶大小、哈希函数指针和相等性判断运算符指针
       SD_multiset bookstore(42, hasher, eqOp);
   
       bookstore.insert(Sales_data("c"));
       bookstore.insert(Sales_data("cpp"));
   }