<commit_before>---
layout: post
title: "C++ primer读书笔记（八）--- Containers "
categories: c++
tags: c++
---

* content
{:toc}

> 顺序容器(sequential container)为程序员提供了控制元素存储和访问顺序的能力。元素在顺序容器中的顺序与其加入容器时的位置相对应。

> 关联容器中元素的位置由元素相关联的关键字值决定。

> 所有容器类都共享公共的接口，不同容器按不同方式对其扩展。这个公共接口使容器的学习更加容易---基于某种容器所学习的内容也都适用于其他容器。每种容器都提供了不同的性能和功能的权衡。

##### 容器公共特性

###### 容器库概述

* 一般来说，每个容器都定义在一个头文件中，文件名与类型名相同。即，deque定义在头文件deque中，list定义在头文件list中，以此类推。

* 容器均定义为模板类。对大多数，但不是所有容器，还需要额外提供元素类型信息，如对与vector，必须提供额外信息来生成特定的容器类型:

      list<Sales_data>      // 保存Sales_data对象的list
      deque<double>         // 保存double的deque

* 可以在容器中保存几乎任何类型，但某些容器操作对元素类型有其自己的特殊要求，这时，定义的容器就无法执行这些容器操作。
  例如，顺序容器构造函数的一个版本接收容器大小参数，它使用了容器元素类型的默认构造函数。但某些类没有默认构造函数时，我们在构造这种元素类型的容器时，就不能使用该构造函数。

      // 假定 noDefault 是一个没有默认构造函数的类型
      vector<noDefault> v1(10, init);       // 正确:提供了元素初始化器
      vector<noDefault> v2(10);             // 错误:必须提供一个元素初始化器

###### 迭代器

* 与容器一样，迭代器有者公共的接口:如果一个迭代器提供某个操作，那么所有提供相同操作的迭代器对这个操作的实现方式都是相同的。例如，标准容器类型上的所有迭代器都允许我们访问容器中的元素，而所有迭代器都是通过解引用运算符来实现这个操作的。类似的，标准容器的所有迭代器都提供了递增运算符，从当前元素移动到下一元素。

* 标准容器迭代器的运算符

  *iter| 返回迭代器iter所指向元素的引用
  iter->mem | 解引用iter并获取该元素的名为mem的成员，等价于(*iter).mem
  ++iter | 令iter指向容器的下一个元素
  - -iter | 令iter指向容器的上一个元素
  iter1 == iter2 | 判断两个容器是否相等
  iter1 != iter2 | 判断两个容器是否不相等

  > 如果两个迭代器指示的是同一个元素或者是同一个容器的尾后迭代器，则相等；反之，不相等

  > **forward_list的迭代器不支持递减运算符(- -)**

  > 执行解引用的迭代器必须合法并确实指示着某个元素。试图解引用一个非法迭代器或者尾后迭代器都是未被定义的行为。


###### 容器类型成员

* 类型成员信息见下表

    iterator | 此容器类型的迭代器类型 
    const_iterator | 可以读取元素，但不能修改元素的迭代器类型 
    size_type | 无符号整数类型，足够保存此种容器类型最大可能容器的大小
    difference_type | 带符号整数类型，足够保存两个迭代器之间的距离
    value_type | 元素类型
    reference | 元素的左值类型: 与value_type&含义相同
    const_reference | 元素的const左值类型（即 const value_type& )
    reverse_iterator | 按逆序寻址元素的迭代器
    const_reverse_iterator | 不能修改元素的逆序迭代器

* 反向迭代器 **reverse_iterator 和 const_reverse_iterator 不支持forward_list**容器。它是一种反向遍历容器的迭代器，与正向迭代器相比，各种操作的含义都发生了颠倒。例如，对一个反向迭代器执行++操作，会得到上一个元素。

* 通过value_type、reference和const_reference，可以在不了解容器中元素类型的情况下使用它。如果需要元素类型，可以使用容器的value_type。如果需要元素的一个引用，可以使用reference或const_reference。这些元素相关的类型别名在泛型编程中非常有用。

* 容器类型成员使用举例:

      list<string>::iterator iter;
      vector<int>::difference_type count;



##### 顺序容器

###### 顺序容器类型

* 下表列出了标准库中的顺序容器，所有顺序容器都提供了快速顺序访问元素的能力。但是这些容器在以下方面都有不同的性能折中。
  + 向容器中添加或从容器中删除元素的代价
  + 非顺序访问容器中元素的代价

  类型|描述|添加删除元素操作|元素访问方式|尾部插入删除元素|头部插入删除元素|其他位置插入删除元素
  array| 固定大小数组 | X | 快速随机访问| X | X | X
  vector| 可变大小数组 | 支持 | 快速随机访问 | 快速 | 可能很慢 | 可能很慢 
  string| 与vector类似的容器，专门用于保存字符 | 支持 | 快速随机访问 | 快速 | 可能很慢 | 可能很慢
  list| 双向链表 | 支持 | 双向顺序访问 | 快速 | 快速 | 快速
  forward_list| 单向链表 | 支持 | 单向顺序访问 | 快速 | 快速 | 快速
  deque| 双端队列 | 支持 | 快速随机访问 | 快速 | 快速 | 可能很慢<commit_msg>add c++ primer containers notes 2<commit_after>---
layout: post
title: "C++ primer读书笔记（八）--- Containers "
categories: c++
tags: c++
---

* content
{:toc}

> 顺序容器(sequential container)为程序员提供了控制元素存储和访问顺序的能力。元素在顺序容器中的顺序与其加入容器时的位置相对应。

> 关联容器中元素的位置由元素相关联的关键字值决定。

> 所有容器类都共享公共的接口，不同容器按不同方式对其扩展。这个公共接口使容器的学习更加容易---基于某种容器所学习的内容也都适用于其他容器。每种容器都提供了不同的性能和功能的权衡。

##### 容器公共特性

###### 容器库概述

* 一般来说，每个容器都定义在一个头文件中，文件名与类型名相同。即，deque定义在头文件deque中，list定义在头文件list中，以此类推。

* 容器均定义为模板类。对大多数，但不是所有容器，还需要额外提供元素类型信息，如对于vector，必须提供额外信息来生成特定的容器类型:

      list<Sales_data>      // 保存Sales_data对象的list
      deque<double>         // 保存double的deque

* 可以在容器中保存几乎任何类型，但某些容器操作对元素类型有其自己的特殊要求，这时，定义的容器就无法执行这些容器操作。
  例如，顺序容器构造函数的一个版本接收容器大小参数，它使用了容器元素类型的默认构造函数。但某些类没有默认构造函数时，我们在构造这种元素类型的容器时，就不能使用该构造函数。

      // 假定 noDefault 是一个没有默认构造函数的类型
      vector<noDefault> v1(10, init);       // 正确:提供了元素初始化器
      vector<noDefault> v2(10);             // 错误:必须提供一个元素初始化器

###### 迭代器

* 与容器一样，迭代器有着公共的接口:
  如果一个迭代器提供某个操作，那么所有提供相同操作的迭代器对这个操作的实现方式都是相同的。例如，标准容器类型上的所有迭代器都允许我们访问容器中的元素，而所有迭代器都是通过解引用运算符来实现这个操作的。类似的，标准容器的所有迭代器都提供了递增运算符，从当前元素移动到下一元素。

* 标准容器迭代器的运算符

  *iter| 返回迭代器iter所指向元素的引用
  iter->mem | 解引用iter并获取该元素的名为mem的成员，等价于(*iter).mem
  ++iter | 令iter指向容器的下一个元素
  - -iter | 令iter指向容器的上一个元素
  iter1 == iter2 | 判断两个容器是否相等
  iter1 != iter2 | 判断两个容器是否不相等

  > 如果两个迭代器指示的是同一个元素或者是同一个容器的尾后迭代器，则相等；反之，不相等

  > **forward_list的迭代器不支持递减运算符(- -)**

  > 执行解引用的迭代器必须合法并确实指示着某个元素。试图解引用一个非法迭代器或者尾后迭代器都是未被定义的行为。

* 迭代器支持的算术运算

  |iter + n | 结果仍是一个迭代器，结果迭代器指示的位置与iter相比**向前移动**了n个元素。结果迭代器或者指示容器内的第一个元素，或者指示容器尾元素的下一位置|
  |iter - n | 结果仍是一个迭代器，结果迭代器指示的位置与iter相比**向后移动**了n个元素。结果迭代器或者指示容器内的第一个元素，或者指示容器尾元素的下一位置|
  |iter1 += n | 迭代器加法的复合赋值语句，将iter1加n的结果赋给iter1|
  |iter1 -= n | 迭代器减法的复合赋值语句，将iter1减n的结果赋给iter1|
  |iter1 - iter2 | 两个迭代器相减的结果是它们之间的距离。参与运算的两个迭代器必须指向的是同一个容器|
  |> >= < <= | 如果某个迭代器指向的容器位置在另一个迭代器所指向位置之前，则说前者小于后者。参与运算的两个迭代器必须指向的是同一个容器|

  > **上述的运算只能用于string、vector、deque和array的迭代器**。不能将它们用于其他任何容器类型的迭代器。

* 获取迭代器

  c.begin() | c.end() | 返回指向容器c的首元素和尾元素之后位置的迭代器
  c.cbegin() | c.cend() | 返回const_iterator
  c.rbegin() | c.rend() | 返回指向容器c的尾元素和首元素之前位置的迭代器
  c.crbegin() | c.crend() | 返回const_reverse_iterator

  > 反向迭代器不支持forward_list

  > 一个迭代器范围（iterator range）由一对迭代器表示，它是一个左闭合区间 [begin, end)，表示范围自begin开始，于end之前（不包括end）结束。
    其中begin和end必须满足下面两个条件:
    1)它们指向同一个容器中的元素，或者是容器最后一个元素之后的位置。
    2)end可以与begin指向相同的位置，但不能指向begin之前的位置，即可以通过反复递增begin来到达end

  > 因为end()操作返回的迭代器并不实际指向某个元素，所以不能对其进行递增或解引用操作。

  不以c开头的函数都是被重载过的。也就是说，实际上有两个名为begin/rbegin的成员。以c开头的版本是C++11新标准引入的，用于支持auto与begin和end函数的结合使用。

      // 显示指定类型
      list<string>::iterator it5 = a.begin();
      list<string>::const_iterator it6 = a.begin();

      // 是iterator还是const_iterator依赖与a的类型
      auto it7 = a.begin();   // 仅当a是const时，it7是const_iterator
      auto it8 = a.cbegin();  // it8是const_iterator

  当auto与begin或end结合使用时，获得的迭代器类型依赖于容器类型。但以c开头的版本还是可以获得const_iterator的，而不管容器的类型是什么。


###### 容器类型成员

* 类型成员信息见下表

    iterator | 此容器类型的迭代器类型 
    const_iterator | 可以读取元素，但不能修改元素的迭代器类型 
    size_type | 无符号整数类型，足够保存此种容器类型最大可能容器的大小
    difference_type | 带符号整数类型，足够保存两个迭代器之间的距离
    value_type | 元素类型
    reference | 元素的左值类型: 与value_type&含义相同
    const_reference | 元素的const左值类型（即 const value_type& )
    reverse_iterator | 按逆序寻址元素的迭代器
    const_reverse_iterator | 不能修改元素的逆序迭代器

    > 反向迭代器 **reverse_iterator 和 const_reverse_iterator 不支持forward_list**容器。它是一种反向遍历容器的迭代器，与正向迭代器相比，各种操作的含义都发生了颠倒。例如，对一个反向迭代器执行++操作，会得到上一个元素。

    > 通过value_type、reference和const_reference，可以在不了解容器中元素类型的情况下使用它。如果需要元素类型，可以使用容器的value_type。如果需要元素的一个引用，可以使用reference或const_reference。这些元素相关的类型别名在泛型编程中非常有用。

* 容器类型成员使用举例:

      list<string>::iterator iter;
      vector<int>::difference_type count;

###### 容器定义和初始化



###### 容器赋值和swap



###### 容器关系运算


###### 容器大小


###### 容器添加/删除元素



##### 顺序容器

###### 顺序容器类型

* 下表列出了标准库中的顺序容器，所有顺序容器都提供了快速顺序访问元素的能力。但是这些容器在以下方面都有不同的性能折中。
  + 向容器中添加或从容器中删除元素的代价
  + 非顺序访问容器中元素的代价

  类型|描述|添加删除元素操作|元素访问方式|尾部插入删除元素|头部插入删除元素|其他位置插入删除元素
  array| 固定大小数组 | X | 快速随机访问| X | X | X
  vector| 可变大小数组 | 支持 | 快速随机访问 | 快速 | 可能很慢 | 可能很慢 
  string| 与vector类似的容器，专门用于保存字符 | 支持 | 快速随机访问 | 快速 | 可能很慢 | 可能很慢
  list| 双向链表 | 支持 | 双向顺序访问 | 快速 | 快速 | 快速
  forward_list| 单向链表 | 支持 | 单向顺序访问 | 快速 | 快速 | 快速
  deque| 双端队列 | 支持 | 快速随机访问 | 快速 | 快速 | 可能很慢
{'fraction_non_alphanumeric': 0.11058315334773218, 'fraction_numerical': 0.005615550755939525, 'mean_word_length': 5.263300270513977, 'pattern_counts': {'":': 0, '<': 19, '<?xml version=': 0, '>': 39, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '3821847', 'n_tokens_mistral': 4934, 'n_tokens_neox': 5540, 'n_words': 346}