顺序容器
- 元素在顺序容器中的顺序与加入容器时的位置相对应
- 关联容器中元素的位置由元素相关联的关键字值决定
顺序容器概述
- 所有顺序列表都提供了快速顺序访问元素的能力，但是，这些容器在以下方面都有不同程度的性能折中
- [x] 向容器添加或从容器中删除元素的代价
- [x] 非顺序访问容器中元素的代价
vector //可变大小数组，支持快速随机访问，在尾部之外的位置插入或删除元素可能很慢
deque //双端队列，支持快速随机访问，在头尾位置插入/删除速度很快
list //双向链表，只支持双向顺序访问，在list中任何位置进行插入/删除都很快
forward_list //单向链表，只支持单向顺序访问，在链表任何位置进行插入/删除都很快
array //固定大小数组，支持快速随机访问，不能添加或删除元素
string //与vector相似的容器，但专门用于保存字符，随机访问快，在尾部插入/删除速度快
- 除了对固定大小的array外，其他容器都提供高效、灵活的内存管理
- 容器保存元素的策略对容器操作的效率有着固有的，甚至是重大的影响，在某些情况下，存储策略还会影响特定容器是否支持特定操作
-
string和vector将元素保存在连续的内存空间中，由于元素是连续存储的，由元素的下标来计算其地址是十分快速的，但是，在这两种容器的中间位置添加或删除元素就会非常耗时
- 与内置数组相比，array是一种更安全，更容器使用的数组类型
- 通常，使用vector是最好的选择
- 选择容器的基本原则
- [x] 除非有很好的理由选择其他容器，否自使用vector
- [x] 如果程序要求随机访问，使用vector或deque
- [x] 如果程序要求在容器的中间插入或删除元素，应该使用list或forward_list
- [x] 如果程序需要在头尾插入或删除元素，但不会在中间位置进行插入或删除操作，使用deque
- 如果不确定使用哪种容器，那么可以在程序中只使用vector和list公共的操作:使用迭代器，不使用下标操作，避免随机访问，这样在必要时选择使用vector或list都很方便
容器库概览
- 每个容器都定义在一个头文件中，文件名与类型名相同
- 顺序容器几乎可以保存任意类型的元素，包括元素类型可以是另一个容器
vector<vector<string>> lines; //vector的vector
迭代器
-
forward_list迭代器不支持递减运算符(--)
- 迭代器范围的概念是标准库的基础
- 一个迭代器范围由一对迭代器表示，两个迭代器分别指向同一个容器中首元素或者是尾元素之后的位置，它们标记了容器中元素的一个范围
begin和end成员
- begin和end有多个版本:带r的版本返回反向迭代器,以c开头的版本返回cosnt迭代器
list<string> a;
auto it1 = a.begin(); //list<string>::iterator
auto it2 = a.rbegin(); //list<string>::reverse_iterator
auto it3 = a.cbegin(); //list<string>::const_iterator
auto it4 = a.crbegin(); //list<string>::const_reverse_iterator
容器定义和初始化
- 每个容器类型都定义了一个默认的构造函数，除array之外，其他容器的默认构造函数都会创建一个指定类型的空容器，且都可以接受指定容器大小和元素初始值的参数
- 当将一个容器初始化为另一个容器的拷贝时，两个容器的容器类型和元素类型必须相同
- 只有顺序容器的构造函数才接受大小参数，关联容器并不支持
- 当定义一个array时，必须指定元素类型和容器大小
array<int,10> temp;
赋值和swap
- 赋值相关运算会导致指向左边容器内部的迭代器、引用和指针失效，而swap操作将容器内容交换不会导致指向容器的迭代器、引用和指针失效(容器类型为array和string的情况除外)
容器大小操作
- [x] size 返回容器中元素的数目
- [x] empty 当size为0时返回true，反之返回false
- [x] max_size 返回一个大于或等于该类型容器所能容纳的最大元素数的值
- [x] forward_list支持max_list和empty，但不支持size
关系运算符
- 除无序关联容器外的所有容器都支持关系运算符，关系运算符左右两边的运算对象必须是相同类型的容器，且必须保存相同类型的元素
vector<int> v1 = {1,3,5,7,9,12};
vector<int> v2 = {1,3,9};
vector<int> v3 = {1,3,5,7};
vector<int> v4 = {1,3,5,7,9,12};
v1 < v2 //true v1和v2在元素[2]处不同，v1[2]小于v2[2]
v1 < v3 //false 所有元素相等，但v3中元素数目少
v1 == v4 //true 每个元素相等，且v1和v4大小相同
v1 == v2 //false v2元素数目比v1少
- 只有当其元素运算符也定义了相应的比较运算符时，我们才可以使用关系运算符来比较两个容器
顺序容器操作
- 顺序容器和关联容器的不同之处在于两者组织元素的方式，这些不同之处直接关系到了元素如何存储、访问、添加以及删除
顺序容器添加元素
- 除了array外，所有标准库容器都提供灵活的内存管理，在运行时可以动态添加或删除元素来改变容器大小
- 向一个vector、string或deque插入元素会使所有指向容器的迭代器、引用和指针失效
- 将元素插入到vector、deque和string中的任何位置都是合法的，然而，这样做可能会很耗时
- C++11引入了三个新成员
- [x] emplace_front对应push_fromt
- [x] emplace对应insert
- [x] emplace_back对应push_back
- emplace函数在容器中直接构造元素，传递给emplace函数的参数必须与元素类型的构造函数相匹配，并且emplace操作比相对应的push操作更快
访问元素
- 对一个空容器调用front和back，就像使用一个越界的下标一样，是一种严重的程序设计错误
- 访问成员函数返回的是引用
if(!c.empty()){
c.front() = 42; //将42赋予c中的第一个元素
auto & v = c.back(); //获得指向最后一个元素的引用
v = 1024; //改变c中的元素
auto v2 = c.back(); //v2不是一个引用，它是c.back()的一个拷贝
v2 = 0; //未改变c中的元素
}
- [x] `string`、`vector`、`deque`、 `array`这几个容器都提供快速随机访问
删除元素
- 删除元素的成员函数并不检查其参数，在删除元素之前，程序猿必须确保它是存在的
-
vector和string不支持pop_front
- 成员函数erase从容器中指定位置删除元素，返回指向删除的最后一个元素之后的位置的迭代器
- ww36可以用resize来增大或缩小容器，但array不支持resize
向容器中添加或删除元素的操作可能会使指向容器元素的指针、引用、迭代器失效，失效的指针、引用、迭代器将不再表示任何元素，使用它们是严重的程序设计错误由于向迭代器添加元素和从迭代器删除元素的代码可能会使迭代器失效，因此必须保证每次改变容器的操作之后都正确地重新定位迭代器，对于vector、string、deque尤为重要- 不要保存end返回地迭代器
- [x] 添加或删除元素地循环程序必须反复调用end，而不能在循环之前保存end返回的迭代器
vector对象是如何增长的
- 当不得不获取新的内存空间时，vector和string地实现通常会分配比新地空间需求更大的内存空间，容器预留这些空间作为备用
- capacity函数表示在不分配新的内存的情况下vector或string最多可以保存多少个元素
- size函数表示vector或string当前已经保存的元素的数量
- 可以调用shrink_to_fit函数来要求vector将超出当前大小的多余内存退回给系统
- 每个vector实现都可以选择自己的内存分配策略，但是必须遵守的一条原则是:只有当迫不得已时才可以分配新的内存空间
- 通过在一个初始为空的vector上调用n次push_back来创建一个n个元素的vector，所花费的时间不能超过n的常数倍
额外的string操作
- 通常当我们从一个const char *创建string时，指针指向的数组必须以空字符结尾
substr操作
string s("hello world");
string s2 = s.substr(0,5); //s2 = hello
数值转换
int i = 42;
string s = to_string(i); //将整数i转换为字符表示形式
double d = stod(s); //将字符串s转换为浮点数
