当前位置:   article > 正文

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

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 顺序容器操作

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-6JU6NL4O-1677738374134)(C:\Users\21147\AppData\Roaming\Typora\typora-user-images\1673515074120.png)]

使用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是固定大小数组,内存一次性分配,大小不变,不会变化。
声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/羊村懒王/article/detail/178365?site
推荐阅读
相关标签
  

闽ICP备14008679号