chapter11/chapter11-关联容器.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 第11章 关联容器"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "- 关联容器支持高效的关键字查找和访问，两个主要的关联容器（associative-container）类型是map和set\n",
    "- 标准库提供8个关联容器，这8个容器间的不同体现在三个维度上：每个容器（1）或者是一个set，或者是一个map；（2）或者要求不重复的关键字，或者允许重复关键字；（3）按顺序保存元素，或无序保存"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 11.1 使用关联容器"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "- map中的每个元素都是一个pair类型的对象，它用first成员保存关键字，用second成员保存对应的值"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    " ## 11.2 关联容器概述"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 11.2.2 关键字类型的要求"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "- 关联容器对其关键字类型有一些限制，对于无序容器中关键字的要求，我们将在11.4节中介绍，对于有序容器，关键字类型必须定义元素比较的方法\n",
    "- 默认情况下，标准库使用关键字类型的`<`运算符来比较两个关键字；在集合类型中，关键字类型就是元素类型，在映射类型中，关键字类型\n",
    "- 可以向一个算法提供我们自己定义的比较操作，与之类似，也可以提供自己定义的操作来代替关键字上的`<`运算符"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 11.3 关联容器操作"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "- 关联容器还定义了以下类型：key_type，此容器的关键字类型；mapped_type，每个关键字关联的类型，只适用于map；value_type，对于set，与key_type相同，对于map，为pair<const key_type, mapped_type>\n",
    "```c++\n",
    "set<string>::value_type v1; // v1是一个string\n",
    "set<string>::key_type v2; // v2是一个string\n",
    "map<string, int>::value_type v3; // v3是一个pair<const string, int>\n",
    "map<string, int>::key_type v4; // v4是一个string\n",
    "map<string, int>::mapped_type v5; // v5是一个int\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 11.3.1 关联容器迭代器"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "- 当解引用一个关联容器迭代器时，我们会得到一个类型为容器的value_type的值的引用；对map而言，value_type是一个pair类型，其first成员保存const关键字，second成员保存值\n",
    "- 一个set中的关键字也是const的，可以用一个set迭代器来读取元素的值，但不能修改\n",
    "- map和set类型都支持begin和end操作，与往常一样，我们可以用这些函数获取迭代器，然后用迭代器来遍历容器；当使用一个迭代器遍历一个map、multimap、set或multiset时，迭代器按关键字升序遍历元素\n",
    "- 我们通常不对关联容器使用泛型算法；关键字是const这一特性意味着不能将关联容器传递给修改或重排容器元素的算法，因为这类算法需要向元素写入值，而set类型中的元素是const的，map中的元素是pair，其第一个成员是const的"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 11.3.2 添加元素"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "- 关联容器的insert成员向容器中添加一个元素或一个元素范围；由于map和set（以及对应的无序类型）包含不重复的关键字，因此插入一个已存在的元素对容器没有任何影响；insert有两个版本，分别接受一对迭代器，或是一个初始化列表"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### 向map添加元素"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "- 对一个map进行insert操作时，必须记住元素类型是pair，通常，对于想要插入的数据，并没有一个现成的pair对象，可以在insert的参数列表中创建一个pair：\n",
    "```c++\n",
    "// 向word_count插入word的4种方法\n",
    "word_count.insert({word, 1});\n",
    "word_count.insert(make_pair(word, 1));\n",
    "word_count.insert(pair<string, size_t>(word, 1));\n",
    "word_count.insert(map<string, size_t>::value_type(word, 1));\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 11.3.4 map的下标操作"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "- map和unordered_map容器提供了下标运算符和一个对应的at函数，set类型不支持下标\n",
    "- 类似我们用过的其它下标运算符，map下标运算符接受一个索引（即，一个关键字），获取与此关键字相关联的值；但是，与其他下标运算符不同的是，如果关键字并不在map中，会为它创建一个元素并插入到map中，关联值将进行值初始化\n",
    "- map的下标运算符与我们用过的其它下标运算符的另一个不同之处是其返回类型，通常情况下，解引用一个迭代器所返回的类型与下标运算符返回的类型是一样的，但对map则不然：当对一个map进行下标操作时，会获得一个mapped_type对象；但当解引用一个map迭代器时，会得到一个value_type对象\n",
    "- 下标和at只适用于非const的map和unordered_map"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 11.3.5 访问元素"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "- 关联容器提供多种查找一个指定元素的方法，应该使用哪个操作依赖于我们要解决什么问题；如果我们所关心的只不过是一个特定元素是否已在容器中，可能find是最佳选择，对于不允许重复关键字的容器，可能使用find还是count没什么区别，但对于允许重复关键字的容器，count还会做更多的工作：如果元素在容器中，它还会统计有多少个元素有相同的关键字；如果不需要计数，最好使用find"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### 对map使用find代替下标操作"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "- 对map和unordered_map类型，下标运算符提供了最简单的提取元素的方法，但是，如我们所见，使用下标操作有一个严重的副作用：如果关键字还未在map中，下标操作会插入一个具有给定关键字的元素，这种行为是否正确完全依赖于我们的预期是什么"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### 在multimap或multiset中查找元素"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "- 在一个不允许重复关键字的关联容器中查找一个元素是一件很简单的事情——元素要么在容器中，要么不在；但对于允许重复关键字的容器来说，过程就更为复杂：在容器中可能有很多元素具有给定的关键字，如果一个multimap或multiset中有多个元素具有给定关键字，则这些元素在容器中会相邻存储"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 11.4 无序容器"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "- 新标准定义了4个无序关联容器（unordered associative container），这些容器不是使用比较运算符来组织元素，而是使用一个哈希函数（hash function）和关键字类型的==运算符；在关键字类型的元素没有明显的序关系的情况下，无序容器时非常有用的；在某些应用中，维护元素的序代价非常高昂，此时无序容器也很有用\n",
    "- 如果关键字类型固有就是无序的，或者性能测试发现问题可以用哈希技术解决，就可以使用无序容器"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "- 通常可以用一个无序容器替换对应的有序容器，反之亦然，但是，由于元素未按顺序存储，一个使用无序容器的程序的输出（通常）会与使用有序容器的版本不同"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### 管理桶"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "- 无序容器在存储上组织为一组桶，每个桶保存零个或多个元素，无序容器使用一个哈希函数将元素映射到桶，为了访问一个元素，容器首先计算元素的哈希值，它指出应该搜索哪个桶，容器将具有一个特定哈希值的所有元素都保存在相同的桶中；如果容器允许重复关键字，所有具有相同关键字的元素也都会在同一个桶中；因此，无序容器的性能依赖于哈希函数的质量和桶的数量和大小"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### 无序容器对关键字类型的要求"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "- 默认情况下，无序容器使用关键字类型的==运算符来比较元素，它们还使用一个hash<key_type>类型的对象来生成每个元素的哈希值\n",
    "- 我们不能直接定义关键字类型为自定义类类型的无序容器，需要提供我们自己的hash模板版本"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 2",
   "language": "python",
   "name": "python2"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 2
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython2",
   "version": "2.7.10"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}