这一章介绍顺序容器,在之前的第三章中,了解到的vector就属于顺序容器的一种。
一个容器就是一些特定类型对象的集合。
除了vector,还有哪些顺序容器?
vector:
大小可变,随机访问的速度很快,但是在尾部之外的部分插入或删除元素可能会很慢。
deque :
随机访问的速度很快,在头和尾插入或删除的速度都很快。
list:
双向链表,只支持双向顺序访问,在任何位置插入或删除操作都很快(链表的特性)
forward_list:
单向链表,只支持单向的随机访问。在任何位置插入或删除都很快
array :
固定大小的数组,不能添加或删除元素
string:
类似vector,但专门用来保存字符。
string 和 vector 将元素存储在连续的内存空间中。所以使用下标来计算地址是很快的。
!但是在这两种容器中间插入或删除会很慢,因为内存空间的连续问题,每次插入或删除后,后面的元素都要做出相应的移动。
list 和 forward_list
设计目的是另容器在任何位置的添加或删除都很快速。但是不支持元素的随机访问。
为了访问元素,只能遍历整个容器。 与 vector deque 和 array相比 这两个容器的额外内存开销也很大。
forward_list的设计目的是达到与手写的单向链表相当的性能,不支持size操作,因为这样会导致额外的开销。
deque:
与string和vector类似, 但在deque两端添加或删除元素都很快。
array:
与内置数组类似,array对象的大小是固定的。array不支持添加和删除元素,以及改变大小的操作。
应当选择合适的顺序容器
本书说到,新版本的容器比旧版本快许多,C++程序应当尽量使用标准库容器。
然而我们应当如何选择合适的顺序容器呢?
只要记住每种容器的特性,尽量选择最快的即可。
list 和 forward_list 是链表,插入和删除对于任何位置都很快,因为链表的元素仅需要指向下一个元素的内存地址就可以了。不需要全盘移动,这样也意味着要在链表中找一个元素很麻烦。
vector和deque 随机访问元素很快,deque在前端插入或删除的速度很快。
在后面的章节学习到一些泛型算法后,实际上可以更灵活的使用这些容器。而不用太纠结其特性。
容器的操作
这部分其实不难,尤其是理解了后面的泛型算法后。
书中说了:
有些操作是所有容器都支持的。
其次 顺序容器 关联容器 无序容器 都有一些特有的操作
还有一些的操作只适用于小部分容器
容器均定义为模板类。所以我们需要提供额外的信息来生成容器类型。
迭代器
迭代器有公共的接口,如果一个迭代器提供某个操作,那么所有提供相同操作的迭代器对这个操作的实现方式都是相同的。
一个 迭代器范围 由 一对 迭代器表示。他们标记了容器中元素的一个范围。
使用左闭合范围蕴含的编程假定
假定begin 和 end 构成一个合法的迭代器范围,则:
1. 如果 begin == end ,范围为空。
2. 如果 begin != end , 则范围内至少有一个元素,且begin指向第一个元素
3.我跟可以对 begin 递增若干次,使得 begin == end
容器类型成员
第三章已经介绍过了,为了使用这些类型,必须显式使用其类名 , 如:
lise<string> :: iterator iter;
begin 和 end 成员
前缀为r的版本返回反向迭代器,c开头的版本返回const迭代器。
容器如何定义和初始化
除了array外,每个容器都定义了默认构造参数。
将一个新容器创建为另一个容器的拷贝有两种方法:
1.直接拷贝整个容器 (要求类型完全相同)
2.利用迭代器指定范围 (不要求相同,甚至元素类型不同也可以)
标准库array具有固定大小
array的大小也是类型的一部分。 如:
array<int,20>
array<int,20>::size_type
赋值和swap
c1 = c2 // 将c1的内容替换为c2中元素的拷贝
c1 = {a,b,c} // 赋值后 c1大小为3
标准库array与内置数组不同,允许赋值
array可以使用花括号列表进行初始化,但不能用花括号列表为其赋值。
使用assign(顺序容器)
顺序容器中,除了array,还定义了一个名为assign的成员。允许我们从一个不同但相容的类型赋值。
例如:
list<string> names;
vector<const char*> oldstyle;
names = oldstyle; //这样就会报错, 因为容器的类型不同,而且元素的类型也不同。
names.assign(oldstyle.cbegin(),oldstyle.cend());
names使用成员assign,将names中的元素替换为迭代器指定范围中的元素拷贝。
使用swap
swap操作交换两个相同类型容器的内容。
除了array,交换两个容器内容的操作会很快。因为:**元素本身没有交换,交换的只是容器的内部数据结构。
除了string外,调用swap不会导致迭代器,引用,指针失效。
c++11新标准中, swap分为成员函数和非成员函数两种,建议使用非成员函数的。
容器大小操作
除了forward_list,不支持size。其他均支持size,empty,和 max_size
顺序容器操作
首先,向一个vector,string 或 deque 插入元素会使所有指向容器的迭代器,指针,引用失效。
使用push_back
除了array和forward_list 都支持push_back
使用push_front
list , forward_list , deque 支持将元素插入容器头部。 (使用push_front)
在容器的特定位置添加元素
insert 成员提供了添加功能,允许我们在容器的任何位置添加元素。
除了array 都支持insert的操作 包括string。 forward_list 有自己特殊版本的insert
insert 接受一个迭代器作为第一个参数。迭代器指出在容器中的什么位置放新元素。
insert函数将元素插入在迭代器所指的位置 **之前。
需要注意的是,虽然有的容器不支持push_front ,但是可以使用insert并且把begin迭代器传进去。
*尽量不要在vector string deque中插入元素,尽管这样做是合法的。
插入范围内元素
insert可以接受更多的参数,比如:
svec.insert(svec.end() , 10 , “anna"); // 在容器末尾插入10个 "anna"
svec.insert(svec.begin(), a.begin(),a.end()); 在开始位置插入 a容器迭代器范围内的元素
使用insert的返回值
调用insert后的返回的迭代器会指向新元素的位置。
使用emplace操作
分为 emplace_front,emplac,emplac_back
使用emplace系列的函数意味着,我们不用传递一个对象,而是可以直接传递这个对象的构造所需的参数。
但传递给emplace的参数必须与元素类型的构造匹配
访问元素
如果容器中没有元素,访问操作的结果是未定义的。
包括array在内的每一个元素都有一个front成员函数,而除了forward_list以外的所有元素都有一个back成员函数。
front:返回首元素的引用
back:返回尾元素的引用
只适用于 string , vector , deque 和 array的操作:
c[n] 下标操作
c.at[n] 返回下标为n的引用
访问成员函数返回的是引用
也就是说,访问元素的成员函数的返回值全部都是引用类型。
但是如果容器是一个const对象,则返回值是const的引用。
下标操作和安全的随机访问
类似c[n] 有可能会引发下标越界异常。如果希望确保下标是合法的。
可以使用at成员函数。也就是c.at[n]。
如果下标越界,at会抛出一个out_of_range异常
删除元素
非array容器有多种删除元素的方式。
pop_front: 删除首元素,vector 和 string 不支持
pop_back:删除尾元素,forwar_list 不支持
erase() : 删除一个迭代器指定的元素, forward_list 有特殊版本的erase。erase允许我们删除一个范围内的元素。
clear() : 删除容器中所有元素
特殊的forward_List操作
insert_after
emplace_after
erase_after
before_begin 首前迭代器
改变容器大小
使用resize来增大或缩小容器,array不支持此操作。