第九章 顺序容器

9.1 顺序容器概述

• 顺序容器（sequential container）：元素顺序不依赖于元素的值，而是与元素加入容器时的位置相对应。

顺序容器类型

• list 的额外内存开销相比其他大很多。
• 通常使用vector是最好的选择，除非你有很好的理由选择其他容器。
  • 如果不需要向中间插入数据，则先向vector中添加，再sort
  • 如果一定要向中间插入数据，则先使用list，输入完成后再拷贝到vector中

9.2 容器库概览

类型

• 迭代器范围begin和end，其中end是指向尾后地址，左闭右开
• 当不需要修改时，尽量使用const iterator

构造函数

• 三种构造方式：
  • 直接拷贝：将一个容器复制给另一个容器时，类型必须匹配：容器类型和元素类型都必须相同。
  • 迭代器范围构造：不要求容器类型相同，容器内的元素类型也可以不同，但是要能进行类型转换
  • 列表初始化
• array初始化
  • 定义array需要同时指定元素类型和大小，默认初始化为0
  • array只能默认初始化或列表初始化，如果定义的数组很大并且需要初始化，可以先默认初始化然后用 fill 函数填充值。

赋值和swap

• swap：
  • 对于array，swap会真正交换它们的元素；对于其他元素，swap不交换元素，只交换数据结构，因此很快
  • 对于 string，swap 后，指针、引用和迭代器会失效。对于其他容器，交换后指针指向了另一个容器的相同位置。
  • 建议统一使用swap(a,b)
• assign赋值：
  • assign操作不适用于关联容器和array
  • =赋值要求两边类型相同，assign只要求可以转换即可
• array赋值：
  • 不能对内置数组拷贝或赋值，但是 array 可以。
  • 使用一个 array 对另一个 array 赋值，需要两个array 元素类型与大小都相同。
  • 不能用花括号列表对 array 赋值（只可以初始化）

大小

• forward_list支持max_size和empty，但是不支持size

9.3 顺序容器操作

添加元素

• 向vector、string或deque插入元素会使所有指向容器的迭代器、引用和指针失效。
• 头尾添加返回void，中间添加返回指向新添加元素的迭代器
• push和insert传递的是元素类型的对象，emplace则将参数传递给元素类型的构造对象
  • 传递给emplace的参数必须和元素类型的构造函数相匹配。
• insert 返回值是指向添加的元素中第一个元素的迭代器
• 添加的都是元素的拷贝，不是元素本身。

访问元素

• 访问成员函数返回的是引用。

删除元素

• 头尾删除返回void，特定位置删除，返回被删除元素之后元素的迭代器
• 添加、删除操作可能使迭代器失效

特殊的forward_list操作

• forward_list 是单向链表，添加和删除操作都会同时改变前驱和后继结点
• forward_list定义了before_begin()，即【首前（off-the-beginning）迭代器】，允许我们再在首元素之前添加或删除元素。
• 前面的insert都是在当前元素之前插入，insert_after插入到当前元素之后

改变容器大小

迭代器

• 添加、删除操作可能使迭代器失效
  • 在向容器添加元素后：
    • 如果容器是vector或string，且存储空间被重新分配，则指向容器的迭代器、指针、引用都会失效。
    • 对于deque，插入到除首尾位置之外的任何位置都会导致指向容器的迭代器、指针、引用失效。如果在首尾位置添加元素，迭代器会失效，但指向存在元素的引用和指针不会失效。
    • 对于list和forward_list，指向容器的迭代器、指针和引用依然有效。
  • 在从一个容器中删除元素后：尾后迭代器总是会失效
    • 对于list和forward_list，指向容器其他位置的迭代器、引用和指针仍然有效。
    • 对于deque，如果在首尾之外的任何位置删除元素，那么指向被删除元素外其他元素的迭代器、指针、引用都会失效；如果是删除deque的尾元素，则尾后迭代器会失效，但其他不受影响；如果删除的是deque的头元素，这些也不会受影响。
    • 对于vector和string，指向被删元素之前的迭代器、引用、指针仍然有效。

9.4 vector对象是如何增长的

vector和string在内存中是连续保存的，如果原先分配的内存位置已经使用完，则需要重新分配新空间，将已有元素从就位置移动到新空间中，然后添加新元素。

管理容量的成员函数

• shrink_to_fit只适用于vector、string和deque
• capacity和reverse只适用于vector和string。

9.5 额外的string操作

构造string的其他方法

• 最初的构造函数：直接初始化（圆括号初始化）、迭代器范围初始化、列表初始化

substr操作

改变string的其他方法

string搜索操作

• string类提供了6个不同的搜索函数，每个函数都有4个重载版本。
• 每个搜索操作都返回一个string::size_type值，表示匹配发生位置的下标。如果搜索失败则返回一个名为string::npos的static成员（类型是string::size_type，初始化值是-1，也就是string最大的可能大小）。

args必须是一下的形式之一：

1
2
3
4
5
6

// 使用pos循环查找所有str包含的字符的位置
string::size_type pos = 0;
while((pos = s.find_first_of(str, pos)) != string::npos){
    cout<<pos<<endl;
    ++pos;
}

s.compare的几种参数形式

逻辑类似于C标准库的strcmp函数，根据s是等于、大于还是小于参数指定的字符串，s.compare返回0、正数或负数。

string和数值转换

9.6 容器适配器（adapter）

• 适配器是使一事物的行为看起来像另一事物的行为的一种机制，例如stack可以使任何一种顺序容器以栈的方式工作。
• 默认情况下，stack和queue是基于deque实现的，priority_queue是基于vector实现的，基础容器不能是array和forward_list
  • 因此可以直接使用一个deque来初始化stack和queue，使用一个有序vector初始化priority_queue
  • 也可以指定实现的顺序容器： stack<string, vector<string> > str_stk;

适配器的通用操作和类型

stack

• 定义在stack头文件中。
• stack可以基于deque（默认）、list、vector实现

queue和priority_queue

• 定义在queue头文件中。
• queue可以基于deque（默认）、list、vector实现，priority_queue可以基于deque（默认）、vector实现