元素在顺序容器中的顺序与其加入容器时的位置相对应。
string和vector将元素保存在连续的内存空间中。与内置数组相比,array是一种更安全、更容易使用的数组类型。forward_size的设计目标是达到与最好的手写的单向链表数据结构相当的性能。因此,forward_list没有size操作,因为保存或计算其大小就会比手写链表多出额外的开销。对其他容器而言,size保证是一个快速的常量时间的操作。
一、容器库概览
容器均定义为模板类。每个容器都定义在一个头文件中,文件名与类型名相同。
1. 迭代器
迭代器范围
一个迭代器范围是由一对迭代器表示,两个迭代器分别指向同一个容器中的元素或者说尾元素之后的位置。这两个迭代器通常被称为begin和end,它们标记了容器中元素的一个范围。
2. 容器类型成员
size_type、iterator、const_iterator、difference_type、value_type(元素类型)、reference(引用) / const_reference
3. begin和end成员
带r的版本返回反向迭代器;带c开头的版本则返回const迭代器。
4. 容器定义和初始化
每个容器类型都定义了一个默认构造函数。除array之外,其他容器的默认构造函数都会创建一个指定类型的空容器,且都可以接受指定容器大小和元素初始值的参数。
将一个容器初始化为另一个容器的拷贝
①直接拷贝整个容器:两个容器的类型及其元素类型必须匹配
②(array除外)拷贝由一个迭代器对指定的元素范围:不要求容器类型是相同的,且新容器和原容器中的元素类型也可以不同,只要能将要拷贝的元素转换为要初始化的容器的元素类型即可。
列表初始化
与顺序容器大小相关的构造函数
顺序容器(array除外)提供了另一个构造函数,它接受一个容器大小和一个(可选的)元素初始值。如果我们不提供元素初始值,则标准库会创建一个值初始化器:
标准库array具有固定大小
当定义一个array时,要指定元素类型和容器大小。
一个默认构造的array是非空的:它包含了与其大小一样多的元素。这些元素都被默认初始化。如果我们对array进行列表初始化,初始值的数目必须等于或小于array的大小。
对array可以进行拷贝或对象赋值操作。(对内置数组则不能。)
5. 赋值和swap
array类型进行赋值,赋值号两边的运算对象必须具有相同的类型。由于右边运算对象的大小可能与左边运算对象的大小不同,因此array类型不支持assign,也不允许用花括号包围的值列表进行赋值。
使用assign(仅顺序容器)
assign允许从一个不同但相容的类型赋值,或者从容器的一个子序列赋值。
assign的第二个版本接受一个整数值和一个元素值。它用指定数目且具有相同给定值的元素替换容器中原有的元素:
使用swap
swap操作交换两个相同类型容器的内容。
6. 容器大小操作
成员函数size返回容器中元素的数目;
empty当size为0时返回布尔值true,否则返回false;
max_size返回一个大于或等于该类型容器所能容纳的最大元素数的值。
forward_list支持max_size和empty,但不支持size。
7. 关系运算符
比较两个容器实际上是进行元素的逐对比较。
二、顺序容器特有操作
1. 向顺序容器添加元素
使用push_front
list、forward_list和deque容器支持push_front操作。
在容器中的特定位置添加元素
insert函数将元素插入到迭代器所指定的位置之前。
插入范围内元素
insert函数(重载)①接受迭代器参数,一个元素数目和一个值:将指定数量的元素添加到指定位置之前,这些元素都按给定值初始化:
②接受一对迭代器或者一个初始化列表的insert版本将给定范围中的元素插入到指定位置之前:
接受元素个数或范围的insert版本返回指向第一个新加入元素的迭代器。如果范围为空,不插入任何元素,insert操作会将第一个参数返回。
使用emplace操作
emplace_front、emplace和emplace_back(构造元素)分别对应push_front, insert 和 push_back(拷贝元素)。
emplace函数的参数根据元素类型而变化,参数必须与元素类型的构造函数相匹配:
// iter指向c中一个元素,其中保存了Sales_data元素
2. 访问元素
访问成员函数(即,front、back、下标和at)返回的是引用。
3. 删除元素
vector和string不支持pop_front。forward_list不支持pop_back。
从容器内部删除一个元素
成员函数erase从容器中指定位置删除元素。我们可以删除由一个迭代器指定的单个元素,也可以删除由一对迭代器指定的范围内的所有元素。两种形式的erase都返回指向删除的(最后一个)元素之后位置的迭代器。
4. 特殊的forward_list操作
为了删除elem3,应该用指向elem2的迭代器调用erase_after。
forward_list定义了before_begin,它返回一个首前迭代器。这个迭代器允许我们在链表首元素之前并不存在的元素“之后”添加或删除元素(亦即在链表首元素之前添加删除元素)。
例子:从forward_list中删除奇数元素:
5. 改变容器大小
6. 容器操作可能使迭代器失效
对于list和forward_list, 在向容器添加或删除元素后,指向容器的迭代器(包括尾后迭代器和首前迭代器)、引用和指针仍有效。
在向容器添加元素后:
当我们删除一个元素后:
编写改变容器的循环程序
三、vector对象是如何增长的
当不得不获取新的内存空间时,vector和string的实现通常会分配比新的空间需求更大的内存空间。容器预留这些控件作为备用,可用来保存更多的新元素。这样,就不需要每次添加新元素都重新分配容器的内存空间。重新分配内存空间时都要移动所有元素。
管理容量的成员函数
传递给reserve的参数即为需求大小。
区分capacity和size: 容器的size是指它已经保存的元素的数目;而capacity则是在不分配新的内存空间的前提下它最多可以保存多少元素。
四、额外的string操作
1. 构造string的其他方法
substr操作
2. 改变string的其他方法
string类型支持顺序容器的赋值运算符以及assign、insert和erase操作。除此之外,它还定义了额外的insert和erase版本。
除了接受迭代器的insert和erase版本外,string还提供了接受下标的版本。下标指出了开始删除的位置,或是insert到给定值之前的位置。
标准库string类型还提供了接受C风格字符数组的insert和assign版本。
// 首先通过调用assign替换s的内容。
我们也可以指定将来自其他string或子字符串的字符插入到当前string中或赋予当前string:
append和replace函数
append操作在string末尾进行插入。
replace操作时调用erase和insert的一种简写形式。
(待练习题)
3. string搜索操作
逆向搜索
4. compare函数
5. 数值转换
五、容器适配器
标准库定义了三个顺序容器适配器:stack、queue和priority_queue。一个容器适配器接受一种已有的容器类型,使其行为看起来像一种不同的类型。例如:stack适配器接受一个顺序容器(除array或forward_list外),并使其操作起来像一个stack一样。
定义一个适配器
每个适配器都定义两个构造函数:默认构造函数创建一个空对象,接受一个容器的构造函数拷贝该容器来初始化适配器。
默认情况下,stack和queue是基于deque实现的,priority_queue是在vector之上实现的。我们可以在创建一个适配器时将一个命名的顺序容器作为第二个类型参数,来重载默认容器类型。
栈适配器
stack类型定义在stack头文件中。
队列适配器
queue和priority_queue适配器定义在queue头文件中。