C++ Primer(第4版)-第2部分：容器和算法

第9章 顺序容器



  3. vector、list 和 deque

  5. 顺序容器 | vector | 支持快速随机访问，支持下标访问 ，但在中间随机插入/删除速度慢 | | —- | —- | | list | 支持快速插入/删除，不支持随机访问。 | | deque | 双端队列 |

  6. 顺序容器适配器
    | stack | 后进先出（LIFO）堆栈 | | —- | —- | | queue | 先进先出（FIFO）队列 | | priority_queue | 有优先级管理的队列 |



  9. 容器类型最常用的构造函数是默认构造函数。在大多数的程序中，使用默认构造函数能达到最佳运行时性能，并且使容器更容易使用。 | C c; | 创建一个名为 c 的空容器。C 是容器类型名，如 vector，T 是元素类型，如 int 或 string 适用于所有容器。 | | —- | —- | | C c(c2); | 创建容器 c2 的副本 c；c 和 c2 必须具有相同的容器类型，并存放相同类型的元素。适用于所有容器。要求容器类型和容器里元素的类型都必须相同。 | | C c(b, e); | 创建 c，其元素是迭代器 b 和 e 标示的范围内元素的副本。适用于所有容器。不要求容器类型相同，容器里元素类型也可以不相同，相互兼容即可。 | | C c(n, t); | 用 n 个值为 t 的元素创建容器 c，其中值 t 必须是容器类型 C 的元素类型的值，或者是可转换为该类型的值。 只适用于顺序容器。 | | C c(n); | 创建有 n 个值初始化（第 3.3.1 节）（value-initialized）元素的容器 c。 只适用于顺序容器。 |

  10. 将一个容器复制给另一个容器时，容器类型和元素类型都必须相同。

  11. 不能直接将一种容器内的元素复制给另一种容器，但允许通过传递一对迭代器间接实现该实现该功能。使用迭代器时，不要求容器类型相同，容器内的元素类型也可以不相同，只要它们相互兼容，能够将要复制的元素转换为所构建的新容器的元素类型，即可实现复制。 list slist(svec.begin(), svec.end());


  13. • 元素类型必须支持赋值运算。• 元素类型的对象必须可以复制。关联容器的键还必须支持“<”操作符。

  15. | iter | 返回迭代器 iter 所指向的元素的引用 | | —- | —- | | iter->mem | 对 iter 进行解引用，获取指定元素中名为 mem 的成员。等效于(iter).mem | | ++iter,iter++ | 给 iter 加 1，使其指向容器里的下一个元素 | | —iter,iter— | 给 iter 减 1，使其指向容器里的前一个元素 | | iter1 == iter2,iter1 != iter2 | 比较两个迭代器是否相等（或不等）。当两个迭代器指向同一个容器中的同一个元素，或者当它们都指向同一个容器的超出末端的下一位置时，两个迭代器相等 |



  18. ++iter, iter++ 和 iter1 == iter2, iter1 != iter2 。

  20. | size_type | 无符号整型，足以存储此容器类型的最大可能容器长度 | | —- | —- | | iterator | 此容器类型的迭代器类型 | | const_iterator | 元素的只读迭代器类型 | | reverse_iterator | 按逆序寻址元素的迭代器 | | const_reverse_iterator | 元素的只读（不能写）逆序迭代器 | | difference_type | 足够存储两个迭代器差值的有符号整型，可为负数 | | value_type | 元素类型 | | reference | 元素的左值类型，是 value_type& 的同义词 | | const_reference | 元素的常量左值类型，等效于 const value_type& |


  22. c.begin() :第一个元素c.end() : 最后一个元素的下一位置c.rbegin() :最后一个元素 c.rend() : 第一个元素前面的位置
  23. 在容器中添加元素时，系统是将元素值复制到容器里（所以要求元素的类型必须支持复制）。类似地，使用一段元素初始化新容器时，新容器存放的是原始元素的副本。被复制的原始值与新容器中的元素各不相关，此后，容器内元素值发生变化时，被复制的原值不会受到影响，反之亦然。
  24. 如果用容器存副本，则容器销毁的时候，副本也会自动被删除。如果用容器存指针，则容器销毁的时候，不会删除这些指针所指向的对象，因此必须先手工删除完毕之后，再销毁容器。

  25. | c.push_back(t) | 在容器 c 的尾部添加值为 t 的元素。返回 void 类型。 | | —- | —- | | c.push_front(t) | 在容器 c 的前端添加值为 t 的元素。返回 void 类型。只适用于 list 和 deque 容器类型。 | | c.insert(p,t) | 在迭代器 p 所指向的元素前面插入值为 t 的新元素。返回指向新添加元素的迭代器。 | | c.insert(p,n,t) | 在迭代器 p 所指向的元素前面插入 n 个值为 t 的新元素。返回 void 类型 。 | | c.insert(p,b,e) | 在迭代器 p 所指向的元素前面插入由迭代器 b 和 e 标记的范围内的元素。返回 void 类型。 |


  27. 任何 insert 或 push 操作都可能导致某些或所有迭代器失效。当编写循环将元素插入到 vector 或 deque 容器中时，程序必须确保迭代器在每次循环后都得到更新。

  29. | c.size() | 返回容器 c 中的元素个数。返回类型为 c::size_type | | —- | —- | | c.max_size() | 返回容器 c 可容纳的最多元素个数，返回类型为c::size_type | | c.empty() | 返回标记容器大小是否为 0 的布尔值 | | c.resize(n) | 调整容器 c 的长度大小，使其能容纳 n 个元素，如果 n < c.size()，则删除多出来的元素；否则，添加采用值初始化的新元素 | | c.resize(n,t) | 调整容器 c 的长度大小，使其能容纳 n 个元素。所有新添加的元素值都为 t |

resize 操作可能会使迭代器失效。在 vector 或 deque 容器上做 resize 操作有可能会使其所有的迭代器都失效。30. | c.back() | 返回容器 c 的最后一个元素的引用。如果 c 为空，则该操作未定义 | | —- | —- | | c.front() | 返回容器 c 的第一个元素的引用。如果 c 为空，则该操作未定义 | | c[n] | 返回下标为 n 的元素的引用 如果 n <0 或 n >= c.size()，则该操作未定义。只适用于 vector 和 deque 容器 | | c.at(n) | 返回下标为 n 的元素的引用。如果下标越界，则该操作未定义。只适用于 vector 和 deque 容器 |

  1. 使用越界的下标，或调用空容器的 front 或 back 函数，都会导致程序出现严重的错误。

  2. | c.erase(p) | 删除迭代器 p 所指向的元素返回一个迭代器，它指向被删除元素后面的元素。如果 p 指向容器内的最后一个元素，则返回的迭代器指向容器的超出末端的下一位置。如果 p 本身就是指向超出末端的下一位置的迭代器，则该函数未定义。 | | —- | —- | | c.erase(b,e) | 删除迭代器 b 和 e 所标记的范围内所有的元素返回一个迭代器，它指向被删除元素段后面的元素。如果 e 本身就是指向超出末端的下一位置的迭代器，则返回的迭代器也指向容器的超出末端的下一位置。 | | c.clear() | 删除容器 c 内的所有元素。返回 void。 | | c.pop_back() | 删除容器 c 的最后一个元素。返回 void。如果 c 为空容器，则该函数未定义。 | | c.pop_front() | 删除容器 c 的第一个元素，返回 void。如果 c 为空容器，则该函数未定义。只适用于 list 或 deque 容器。 |


  4. | c1 = c2 | 删除容器 c1 的所有元素，然后将 c2 的元素复制给 c1。c1 和c2 的类型（包括容器类型和元素类型）必须相同。 | | —- | —- | | c1.swap(c2) | 交换内容：调用完该函数后，c1 中存放的是 c2 原来的元素，c2 中存放的则是 c1 原来的元素。c1 和 c2 的类型必须相同。该函数的执行速度通常要比将 c2 复制到 c1 的操作快。 | | c.assign(b,e) | 重新设置 c 的元素：将迭代器 b 和 e 标记的范围内所有的元素复制到 c 中。b 和 e 必须不是指向 c 中元素的迭代器 。 | | c.assign(n,t) | 将容器 c 重新设置为存储 n 个值为 t 的元素。 |


  6. 1). 如果程序要求随机访问元素，则应使用 vector 或 deque 容器。2). 如果程序必须在容器的中间位置插入或删除元素，则应采用 list 容器。 3). 如果程序不是在容器的中间位置，而是在容器首部或尾部插入或删除元素，则应采用 deque 容器。4). 如果只需在读取输入时在容器的中间位置插入元素，然后需要随机访问元素，则可考虑在输入时将元素读入到一个 list 容器，接着对此容器重新排序，使其适合顺序访问，然后将排序后的 list 容器复制到一个 vector 容器。

  8. | s.substr(pos, n) | 返回一个 string 类型的字符串，它包含 s 中从下标 pos开始的 n 个字符 | | —- | —- | | s.substr(pos) | 返回一个 string 类型的字符串，它包含从下标 pos 开始到s 末尾的所有字符 | | s.substr() | 返回 s 的副本 |


  10. | s.append(args) | 将 args 串接在 s 后面。返回 s 引用 | | —- | —- | | s.replace(pos, len, args) | 删除 s 中从下标 pos 开始的 len 个字符，用 args 指定的字符替换之（在pos位置插入args）。返回 s 的引用 | | s.replace(b, e, args) | 删除迭代器 b 和 e 标记范围内所有的字符，用 args 替换之（在pos位置插入args）。返回 s 的引用 |


  12. | s.find( args) | 在 s 中查找 args 的第一次出现 | | —- | —- | | s.rfind( args) | 在 s 中查找 args 的最后一次出现 | | s.find_first_of( args) | 在 s 中查找 args 的任意字符的第一次出现 | | s.find_last_of( args) | 在 s 中查找 args 的任意字符的最后一次出现 | | s.find_first_not_of( args) | 在 s 中查找第一个不属于 args 的字符 | | s.find_last_not_of( args) | 在 s 中查找最后一个不属于 args 的字符 |



  14. 第10章 关联容器
  15. 键位置

  16. | map | 关联数组，元素通过键来存储和读取 | | —- | —- | | set | 大小可变的集合，支持通过键实现的快速读取 | | multimap | 支持同一个键多次出现的 map 类型 | | multiset | 支持同一个键多次出现的 set 类型 |


  1. | pair p1; | 创建一个空的 pair 对象，它的两个元素分别是 T1 和 T2 类型，采用值初始化。 | | —- | —- | | pair p1(v1, v2); | 创建一个 pair 对象，它的两个元素分别是 T1 和 T2 ，其中 first 成员初始化为 v1，而 second 成员初始化为 v2。 | | make_pair(v1,v2); | 以 v1 和 v2 值创建一个新 pair 对象，其元素类型分别是v1 和 v2 的类型。 | | p1 < p2 | 两个 pair 对象之间的小于运算，其定义遵循字典次序：如果 p1.first < p2.first 或者 !(p2.first < p1.first) && p1.second < p2.second，则返回 true 。 | | p1 == p2 | 如果两个 pair 对象的 first 和 second 成员依次相等，则这两个对象相等。该运算使用其元素的 == 操作符。 | | p.first | 返回 p 中名为 first 的（公有）数据成员。 | | p.second | 返回 p 的名为 second 的（公有）数据成员 。 |




  4. | map m; | 创建一个名为 m 的空 map 对象，其键和值的类型分别为 k 和 v | | —- | —- | | map m(m2); | 创建 m2 的副本 m，m 与 m2 必须有相同的键类型和值类型 | | map m(b, e); | 创建 map 类型的对象 m，存储迭代器 b 和 e 标记的范围内所有元素的副本。元素的类型必须能转换为 pair |


  1. 关联容器的键类型必须支持 < 操作符

  2. | map::key_type | 在 map 容器中，用做索引的键的类型 | | —- | —- | | map::mapped_type | 在 map 容器中，键所关联的值的类型 | | map::value_type | 一个 pair 类型，它的 first 元素具有 const map::key_type 类型，而 second 元素则为 map::mapped_type 类型 |

  3. 谨记： value_type 是 pair 类型，它的值成员可以修改，但键成员不能修改。




  7. | m.insert(e) | e 是一个用在 m 上的 value_type 类型的值。如果键（e.first）不在 m 中，则插入一个值为 e.second 的新元素；如果该键在 m 中已存在，则保持 m 不变。该函数返回一个 pair 类型对象，包含指向键为 e.first 的元素的 map 迭代器，以及一个 bool 类型的对象，表示是否插入了该元素。 | | —- | —- | | m.insert(beg, end) | beg 和 end 是标记元素范围的迭代器，其中的元素必须为 m.value_type 类型的键－值对。对于该范围内的所有元素，如果它的键在 m 中不存在，则将该键及其关联的值插入到 m。返回 void 类型 。 | | m.insert(iter,e) | e 是一个用在 m 上的 value_type 类型的值。如果键（e.first）不在 m 中，则创建新元素，并以迭代器 iter 为起点搜索新元素存储的位置。返回一个迭代器，指向 m 中具有给定键的元素。 |


  9. | m.count(k) | 返回 m 中 k 的出现次数 | | —- | —- | | m.find(k) | 如果 m 容器中存在按 k 索引的元素，则返回指向该元素的迭代器。如果不存在，则返回超出末端迭代器。 |



  11. | m.erase(k) | 删除 m 中键为 k 的元素。返回 size_type 类型的值，表示删除的元素个数 | | —- | —- | | m.erase(p) | 从 m 中删除迭代器 p 所指向的元素。p 必须指向 m 中确实存在的元素，而且不能等于 m.end()。返回 void | | m.erase(b, e) | 从 m 中删除一段范围内的元素，该范围由迭代器对 b 和 e 标记。b 和 e 必须标记 m 中的一段有效范围：即 b 和 e 都必须指向 m 中的元素或最后一个元素的下一个位置。而且，b 和 e 要么相等（此时删除的范围为空），要么 b 所指向的元素必须出现在 e 所指向的元素之前。返回 void 类型 |


  1. map_itmap_itmap_it在使用迭代器遍历map 容器时，迭代器指向的元素按键的升序排列。





  6. 方法一：使用 find 和 count 操作string search_item(“Alain de Botton”);typedef multimap::size_type sz_type;sz_type entries = authors.count(search_item);multimap::iterator iter = authors.find(search_item);for (sz_type cnt = 0; cnt != entries; ++cnt, ++iter) cout << iter->second << endl; // print each title
    方法二：与众不同的面向迭代器的解决方案 | m.lower_bound(k) | 返回一个迭代器，指向键不小于 k 的第一个元素 | | —- | —- | | m.upper_bound(k) | 返回一个迭代器，指向键大于 k 的第一个元素 | | m.equal_range(k) | 返回一个迭代器的 pair 对象 它的 first 成员等价于 m.lower_bound(k)。而 second 成员则等价于 m.upper_bound(k) |




  9. 第11章 泛型算法 每个泛型算法的实现都独立于单独的容器，并且不依赖于容器存储的元素类型。 泛型算法需要使用迭代器，迭代器有如下要求： • 支持自增操作：从一个元素定位下一个元素 • 提供解引用：访问元素的值 • 支持相等和不等操作符：用于判断2个迭代器是否相等
    “普通”的迭代器不修改基础容器的大小。算法可能会改变存储在容器中的元素的值，也许会在容器内移动元素，但是，算法从不直接添加或删除元素。

  10. include #include

  11. find
    count
    accumulate
    find_first_of
  12. fill
    fill_nback_inserter
  13. copy
    replace
    replace_copy
  14. sort
    unique
    erase


  17. rbeginrend