《C++ Primer》 第九章 顺序容器_list类型支持双向顺序访问,在list中任何位置插入删除很快

《C++ Primer》 第九章 顺序容器

9.1 顺序容器概述

容器：特定类型对象的集合

顺序容器类型

• vector 可变大小数组，支持快速随机访问，在尾部之外的位置插入或删除元素可能很慢
• deque 双端队列。支持快速随机访问。在头尾位置插入/删除速度很快
• list 双向列表。只支持双向顺序访问。在list中任何位置进行插入/删除操作速度都很快
• forward_list 单向链表。只支持单向顺序访问。在链表任何位置进行插入/删除操作速度都很快
• array 固定大小数组。支持快速随机访问。不能添加或删除元素
• string 与vector相似的容器，但专门用于保存字符。随机访问快。在尾部插入/删除速度快

9.2 容器库概览

某些类没有默认构造函数，我们可以定义一个保存这种类型对象的容器，但我们在构造这种容器时不能只传递给它一个元素数目参数：

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

容器操作：

• iterator ：此容器类型的迭代器类型
• const_iterator：可以读取元素，但不能修改元素的迭代器类型
• size_type：无符号整数类型，足够保存此种容器类型最大可能容器的大小
• different_type：带符号整数类型，足够保存两个迭代器之间的距离
• value_type：元素类型
• reference：元素的左值类型；与value_type&含义相同
• const_reference：元素的const左值类型(const value_type&)
• C c; 默认构造函数，构造空容器。如果C是一个array, 则c中元素按默认方式初始化，否则c为空
• C c1(c2); 构造c2的拷贝c1，c1和c2必须是相同类型（相同的容器类型和元素类型；对于array类型，两者还必须具有相同大小）
• C c(b, e); 构造c，将迭代器b和e指定的范围内的元素拷贝到c（array不支持)，元素类型需相容。
• C c(a, b, c…); 列表初始化c
• c1 = c2 将c1中的元素替换为c2中元素
• c1={a, b, c…} 将c1中的元素替换为列表中元素（不适用于array）
• a.swap(b) 交换a和b中的元素
• c.size() c中元素的数目（不支持forward_list）
• c.max_size() c可保存的最大元素数目
• c.empty() 若c中存储了元素，返回false，否则返回true
• c.insert(args) 将args中的元素拷贝进c
• c.emplace(this) 使用inits构造c中的一个元素
• c.erase(args) 删除args指定的元素
• c.clear() 删除c中的所有元素，返回void
• ==, != 所有容器都支持相等（不等）运算符
• <，<=，>，>=: 关系运算符（无序关联容器不支持）
• c.begin(), c.end() 返回指向c的首元素和尾元素之后位置的迭代器
• c.cbegin(), c.end() 返回const_iterator
• 反向容器的额外成员（不支持forward_list）
• reverse_iterator 按逆序寻址元素的迭代器
• const_reverse_iterator 不能修改元素的逆序迭代器
• c.rbegin(), c.rend() 返回指向c的尾元素和首元素之前位置的迭代器
• c.crbegin(), c.crend() 返回const_reverse_iterator
• 只有顺序容器（不包括array）的构造函数才能接受大小参数
• C seq(n) seq 包含n个元素， 这些元素进行了值初始化；此构造函数是explicit的 (string不适用)
• C seq(n, t) seq包含n个初始化为值t的元素。
• swap(c1,c2) 交换c1和c2的元素，c1和c2必须具有相同的类型。swap通过比从c2向c1拷贝元素快得多
• c1.swap(c2)
• assign操作不适合关联容器和array
• seq.assign(b,e) 将seq中的元素替换为迭代器b和e所表示的范围中的元素。迭代器b和e不能指向seq中的元素
• seq.assign(i1) 将seq中的元素替换为初始化列表i1中的元素
• seq.assign(n, t) 将seq中的元素替换为n个值为t的元素

end()：指向尾元素之后的位置，因此迭代器范围[begin, end)。end可以与begin指向相同的位置，但不能指向begin之前的位置。

反向迭代器是一种反向遍历容器的迭代器，与正向迭代器相比，各种操作的含义也都发生了颠倒。如对于一个反向迭代器执行++操作，会得到上一个元素。

显示使用类名使用相应类型：

//iter是通过list<string>定义的一个迭代器类型
list<string>::iterator iter;
//count是通过vector<int>定义的一个difference_type类型
vector<int>::difference_type count;
1
2
3
4

将一个容器初始化为另一个容器的拷贝：

• 直接拷贝整个容器
• (array除外) 拷贝由一个迭代器对指定的元素范围

当一个容器初始化另一个容器的拷贝时，两个容器的容器类型和元素类型必须相同

list<string> authors ={"Milton","Shakespeare","Austen"};
vector<const char*> articles = {"a", "an", "the"};

list<string> list2(authors);	//正确：类型匹配
deque<string> authList(authors);//错误：容器类型不匹配
vector<string> words(articles); //错误：容器类型必须匹配
//正确：可以将const char* 元素转换为string
forward_list<string> words(articles.begin(), articles.end());

//拷贝元素，直到（但不包括）it指向的元素
deque<string> authList(authors.begin(), it);
1
2
3
4
5
6
7
8
9
10
11

标准库array具有固定大小：

当定义一个array时，除了指定元素类型，还要指定容器大小：

array<int, 42>  //保存为42个int的数组
array<string, 10>//保存为10个string的数组
//使用array类型时需要同时指定元素类型和大小
array<int, 10>::size_type i;	//数组类型包括元素类型和大小
array<int>::size_type j;      //错误：array<int>不是一个类型
1
2
3
4
5

虽然我们不能对内置数组进行拷贝和对象赋值操作，但array并无此限制。

int digs[10] = {0,1,2,3,4,5,6,7,8,9};
int cpy[10] = digs;//错误：内置数组不支持拷贝或赋值
array<int,10> digits = {0,1,2,3,4,5,6,7,8,9};
array<int,10> copy = digits;//正确：只要数组类型匹配即合法
1
2
3
4

使用assign（仅顺序容器)

assign操作用参数所指定的元素（的拷贝）替换左边容器中的所有元素。

list<string> names;
vector<const char*> oldstyle;
names = oldstyle;//错误：容器类型不匹配
//正确：可以将const char* 转换成string
names.assign(oldstyle.cbegin(), oldstyle.cend())
1
2
3
4
5

assign的第二个版本接受一个整型值和一个元素值。它用指定数目且具有相同给定的元素替换容器中原有的元素：

//等价于slist1.clear()
//后跟slist1.insert(slist1.begin(), "Hiya!");
list<string> slist1(1);  //一个元素，为空string
slist1.assign(10,"Hiya!"); //10个元素， 每个都是"Hiya!“
1
2
3
4

使用swap：交换两个相同类型容器的内容。调用swap之后，两个容器内的元素将会交换：

vector<string> svec1(10);
vector<string> svec2(24);
swap(svec1, svec2);
1
2
3

9.3 顺序容器操作

使用push_front:

list<int> ilist;
//将元素添加到ilist开头
for (size_t ix=0; ix!=4;++ix)
	ilist.push_back(ix);
//ilist保存序列3,2,1,0
1
2
3
4
5

insert函数将元素插入到迭代器所指定的位置之前。

slist.insert(iter, "Hello!"); //将"Hello“添加到iter之前的位置
vector<string> svec;
list<string> slist;
//等价于调用slist.insert(iter, "Hello!")
slist.insert(slist.begin(),"Hello!");
//vector不支持push_front，但我们可以插入到begin()之前
svec.insert(svec.begin(), "Hello!");
1
2
3
4
5
6
7

插入范围元素：

svec.insert(svec.end(), 10, "Anna");
//将10个元素插入到svec的末尾，并将所有元素初始化为string "Anna"
vector<string> v={"quasi", "simba", "frollo","scar"}；
//将v的最后两个元素添加到slist的开始位置
slist.insert(slist.begin(), v.end()-2, v.end());
slist.insert(slist.end(),{"these", "words", "will",
							"go","at","the","end"});
//运行时错误：迭代器表示要拷贝的范围，不能指向与目的位置相同的容器
slist.insert(slist.begin(), slist.begin(), slist.end());
1
2
3
4
5
6
7
8
9

使用insert的返回值：通过使用insert的返回值，可以在容器中一个特定位置反复插入元素

list<string> lst;
auto iter = lst.begin();
while(cin>>word)
	iter = lst.insert(iter,word);//等价于调用push_front
1
2
3
4

使用emplace操作：emplace_front emplace和emplace_back，这些操作分别对应push_front、insert和push_back，允许我们将元素放置在容器头部、一个指定位置之前或容器尾部。

调用push或Insert成员函数时，我们将元素类型的对象传递给它们，这些对象被拷贝到容器中。当我们调用一个emplace成员函数时，则是将参数传递给元素类型的构造函数。emplace成员使用这些参数在容器管理的内存空间中直接构造函数。

//在c的末尾构造一个Sales_data对象
//使用三个参数的Sales_data构造函数
c.emplace_back("978-33743673",25,15.99);
//错误：没有接受三个参数的push_back版本
c.push_back("978-33743673",25,15.99);
//正确：创建一个临时的Sales_data对象传递给push_back
c.push_back(Sales_data("978-33743673",25,15.99));

1
2
3
4
5
6
7
8

在调用emplace_back时，会在容器管理的内存空间中直接创建对象。而调用push_back则会创建一个局部临时对象，并将其压入容器中。

emplace函数的参数根据元素类型而变换，参数必须与元素类型的构造函数相匹配：

//iter指向c中一个元素，其中保存了Sales_data元素
c.emplace_back();//使用Sales_data的默认构造函数
c.emplace(iter, "999-9999999");//使用Sales_data(string)
//使用Sales_data的接受一个ISBN、一个count和一个price的构造函数
c.emplace_front("999-99999",25,25.9);
1
2
3
4
5

emplace函数在容器中直接构造元素。传递给emplace函数的参数必须与元素类型的构造函数相匹配。

包括array在内的每个顺序容器都有一个front成员函数，而除forward_list之外的所有顺序容器都有一个back成员函数。这两个操作分别返回首元素和尾元素的引用：

//在解引用一个迭代器或调用front或back之前检查是否有元素
if(!c.empty()){
	//val和val2是c中第一个元素值的拷贝
	auto val = *c.begin(), val2 = c.front();
	//val3和val4是c中最后一个元素值的拷贝
	auto last = c.end();
	auto val3 = *(--last);//不能递减forward_list迭代器
	auto val4 = c.back();
}
1
2
3
4
5
6
7
8
9

访问成员函数返回的是引用：在容器中访问元素的成员函数(front、back、下标和at ) 返回的都是引用。如果容器是一个const对象，则返回值是const的引用。

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中元素
}
1
2
3
4
5
6
7

如果我们希望确保下标是合法的，可以使用at成员函数。at成员函数类似下标运算符，如果下标越界，at会抛出一个out_of_range异常。

成员函数erase从容器中指定位置删除元素：

list<int> lst={0,1,2,3,4,5,6,7,89};
auto it=lst.begin();
while(it!=lst.end())
	if(*it%2)
		it = lst.erase(it);
	else
		++it;

//删除两个迭代器表示的范围内的元素
//返回指向最后一个被删元素之后位置的迭代器
elem1 = slist.erase(elem1, elem2); //调用后，elem1==elem2
1
2
3
4
5
6
7
8
9
10
11

forward_list操作：

从forward_list中删除元素：

forward_list<int> flst = {0,1,2,3,4,5,6,7,8,9};
auto prev = flst.before_begin();   //表示flst的"首前元素"
auto curr = flst.begin();	//表示flst中的第一个元素
while(curr!=flst.end()){
	if(*curr%2)
		curr = flst.erase_after(prev);
	else{
		prev = curr;//移动迭代器curr，指向下一个元素，prev指向curr之前的元素
		++curr;
	}
}
1
2
3
4
5
6
7
8
9
10
11

改变容器大小resize()：如果当前大小小于所要求的大小，容器后部的元素会被删除；如果当前大小小于新大小，会将新元素添加到容器后部。

编写改变容器的循环：

vector<int> vi={0,1,2,3,4,5,6,7,8,9};
auto iter=vi.begin();//调用begin而不是cbegin，因为要改变vi
while(iter!=vi.end()){
	if(*iter % 2){
		iter = vi.insert(iter,*iter);//复制当前元素
		iter += 2;//向前移动迭代器，跳过当前元素以及插入到它之前的元素
	}else
		iter = vi.erase(iter); //删除偶数元素
		//不应向前移动迭代器，iter指向我们删除元素之后的元素
}
1
2
3
4
5
6
7
8
9
10

不要保存end返回的迭代器：此代码会导致无线循环。问题在于我们将end操作返回的迭代器保存在一个名为end的局部变量中。在循环体中，我们向容器中添加了一个元素，这个操作使保存在end中的迭代器失效了。这个迭代器不再指向任何元素或是v中尾元素之后的位置。

//此循环的行为是未定义的
auto begin = v.begin(), end = v.end();//保存尾迭代器的一个坏主意
while(begin != end){
	//插入新值，对begin重新赋值，否则的话它会失效
	++begin;//向前移动begin，因为我们想在此元素之后插入元素
	begin = v.insert(begin, 42);	//插入新值
	++begin;//向前移动begin跳过刚刚加入的元素
}
1
2
3
4
5
6
7
8

如果在一个循环中插入/删除 deque, string或vector中的元素，不要缓存end返回的迭代器。

必须在每次插入操作后重新调用end()，而不能在循环开始前保存它返回的迭代器。

//安全的方法：在每个循环步添加/删除元素后都重新计算end
while(begin!=v.end()){
	++begin;
	begin = v.insert(begin, 42);
	++begin;
}
1
2
3
4
5
6

9.4 vector 对象是如何增长的

管理容量的成员函数：

capacity和size: 容器中的size是指它已经保存的元素的数目；而capacity则是在不分配新的内存空间的前提下它最多可以保存多少元素。可以调用shrink_to_fit来要求vector将超出当前大小的多余内存退回给系统。

9.5 额外的string操作

通常从一个const char*创建string时，指针指向的数组必须以空字符结尾，拷贝操作遇到空字符时停止。

substr操作：返回原始string的一部分或全部的拷贝。

string s("hello world");
string s2=s.substr(0,5);//s2=hello
string s3=s.substr(6); //s3=world
string s4=s.substr(6,11);//s4=world
string s5=s.substr(12);//抛出一个out_of_range异常
1
2
3
4
5

如果开始位置超过了string的大小，则substr函数抛出一个out_of_range异常。如果开始位置加上技术支持大于string的大小，则substr会调整计数值，只拷贝到string的末尾。

改变string: assign、insert和erase操作。

string 搜索：

compare函数：

数值转换：

9.6 容器适配器

栈适配器：

队列适配器：

9.7 概念总结

begin和cbegin之间的区别：

• cbegin与auto结合使用。它返回指向容器第一个元素的const迭代器，可以用来只读地访问容器元素，但不能对容器元素进行修改。因此，当不需要写访问时，应该使用cbegin
• begin则是被重载过的，有两个版本：其中一个是const成员函数，也返回const迭代器；另一个则返回普通迭代器，可以对容器元素进行修改。

vector初始化方式：

• vector list1; 默认初始化，vector为空，size返回0，表明容器中尚未有元素；capacity返回0，意味着尚未分配存储空间。这种方式适用于元素个数位置，需要在程序运行中动态添加的情况
• vector list2(list1); list2初始化list1的拷贝, list1必须与list2类型相同，且具有相同的容量和元素。
• vector list = {1, 2, 3.0, 4, 5, 6, 7}; 初始化为列表中元素的拷贝，列表中的元素类型必须与list的元素类型相同。对于整型，对直接拷贝其值，对于其它类型，则需进行类型转换。
• vector list3(list.begin()+2, list.end()-1); list3初始化为两个迭代器指定范围中元素的拷贝，范围中的元素类型必须与list3的元素类型相容。
• vector list4(7); 默认初始化，list4中将包含7个元素，每个元素进行缺省的值初始化。
• vector list5(7,3); 指定值初始化，list5被初始化为包含7个值为3的int。

为什么list或array没有capacity成员函数？

• list是链表，当有新元素加入时，会从内存空间中分配一个新节点保存它；当从链表中删除元素时，该节点占用的内存空间会被立刻释放。因此，一个链表占用的内存空间总是与它当前保存的元素所需空间相等，即capacity总是等于size
  表中的元素类型必须与list的元素类型相同。对于整型，对直接拷贝其值，对于其它类型，则需进行类型转换。
• vector list3(list.begin()+2, list.end()-1); list3初始化为两个迭代器指定范围中元素的拷贝，范围中的元素类型必须与list3的元素类型相容。
• vector list4(7); 默认初始化，list4中将包含7个元素，每个元素进行缺省的值初始化。
• vector list5(7,3); 指定值初始化，list5被初始化为包含7个值为3的int。

为什么list或array没有capacity成员函数？

• list是链表，当有新元素加入时，会从内存空间中分配一个新节点保存它；当从链表中删除元素时，该节点占用的内存空间会被立刻释放。因此，一个链表占用的内存空间总是与它当前保存的元素所需空间相等，即capacity总是等于size
• array是固定大小数组，内存一次性分配，大小不变，不会变化。