c++Primer第九章：顺序容器

Dear 丶 2022-10-22 07:44 139阅读 0赞

### 目录 ###

*  顺序容器
 *   *  介绍
     *  一般操作
     *  初始化
     *   *  一般容器
         *  array
     *  赋值和swap
     *   *  assgin:替换
         *  swap:交换
     *  关系运算符
     *  添加元素
     *   *  vector和string
         *  list
         *  forward\_list
     *  访问
     *  删除
     *   *  vector和string
         *  list
         *  非单向链表删除代码
         *  单向链表删除代码
     *  改变容器大小
     *  代码
     *   *  在确定的位置之前插入
         *  在确定的位置之后插入
     *  管理容量
     *  string的额外操作
     *   *  string的添加删除修改
         *  string的查找
         *  字符串匹配
         *  string转数值
         *  把混合字符串转数字
         *  数字转字符串
     *  stack queue略

# 顺序容器 #

## 介绍 ##

<table> 
 <thead> 
  <tr> 
   <th>项目</th> 
   <th>介绍</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>vector</td> 
   <td>可变数组（建议）（auto）</td> 
  </tr> 
  <tr> 
   <td>deque</td> 
   <td>队列 （操作略）</td> 
  </tr> 
  <tr> 
   <td>list</td> 
   <td>双向链表（建议）（auto）</td> 
  </tr> 
  <tr> 
   <td>forward_list</td> 
   <td>单向链表</td> 
  </tr> 
  <tr> 
   <td>array</td> 
   <td>固定数组</td> 
  </tr> 
  <tr> 
   <td>string</td> 
   <td>可变</td> 
  </tr> 
 </tbody> 
</table>

## 一般操作 ##

类别名

iterator

const\_iterator

size\_type

different\_type : 两个迭代器之间的距离

value\_type : 元素类型

reverse\_iterator: 按照逆序的迭代器

## 初始化 ##

### 一般容器 ###

<table> 
 <thead> 
  <tr> 
   <th>项目</th> 
   <th>Value</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>C c</td> 
   <td></td> 
  </tr> 
  <tr> 
   <td>C c1(c2)</td> 
   <td></td> 
  </tr> 
  <tr> 
   <td>C c1=c2</td> 
   <td></td> 
  </tr> 
  <tr> 
   <td>C c{a,b,c,d…}</td> 
   <td></td> 
  </tr> 
  <tr> 
   <td>C c={a,b,c,d…}</td> 
   <td></td> 
  </tr> 
  <tr> 
   <td>C c(b,e)</td> 
   <td>迭代器指定的范围 [begin,end)</td> 
  </tr> 
  <tr> 
   <td>C seq(n)</td> 
   <td>包含了n个元素，并进行了初始化，string不可用</td> 
  </tr> 
  <tr> 
   <td>C seq(n,t)</td> 
   <td>包含 了n个初始化为t的元素</td> 
  </tr> 
 </tbody> 
</table>

### array ###

必须指定类型和大小，类型和数量一致可以直接赋值

array<int,10>
    array<int,10>::size_type i;

## 赋值和swap ##

### assgin:替换 ###

<table> 
 <thead> 
  <tr> 
   <th>项目</th> 
   <th>Value</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>seq.assign(b,e)</td> 
   <td>[begin,end)</td> 
  </tr> 
  <tr> 
   <td>seq.assign(il)</td> 
   <td>全替换为il</td> 
  </tr> 
  <tr> 
   <td>seq.assign(n,t)</td> 
   <td>替换为n个值为t的元素，原来有n-1个元素也无事</td> 
  </tr> 
 </tbody> 
</table>

不适合关联容器（按照键值进行保存和访问）以及array。

### swap:交换 ###

<table> 
 <thead> 
  <tr> 
   <th>项目</th> 
   <th>Value</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>swap(a,b)</td> 
   <td></td> 
  </tr> 
  <tr> 
   <td>a.swap(b)</td> 
   <td></td> 
  </tr> 
 </tbody> 
</table>

## 关系运算符 ##

1.数量相等比数值。  
2.数量不等比数值，之后再比数量。

## 添加元素 ##

list<int> a{1,2,3,4,5,6,7};
    	auto t=a.insert(a.begin(),3,9);
    	cout<<*t<<endl;
    	cout<<*(++t)<<endl;
    	return 0;

结果，返回的是最新一个添加的元素位置，即最左边的  
![在这里插入图片描述][20210405151158242.png]

### vector和string ###

<table> 
 <thead> 
  <tr> 
   <th>项目</th> 
   <th>Value</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>c.push_back(t)</td> 
   <td>t必须和c类型一致</td> 
  </tr> 
  <tr> 
   <td>c.emplace_back(arg)</td> 
   <td>会调用构造函数，class C c.emplace_back(“hello”)，会自动调用class c相应的构造函数</td> 
  </tr> 
  <tr> 
   <td>c.insert(p,t)</td> 
   <td>指定p位置之前插入t，返回的是第一个新加入元素的迭代器</td> 
  </tr> 
  <tr> 
   <td>c.emplace(p,args)</td> 
   <td></td> 
  </tr> 
  <tr> 
   <td>c.insert(p,n,t)</td> 
   <td>p之前n个t</td> 
  </tr> 
  <tr> 
   <td>c.insert(p,b,e)</td> 
   <td></td> 
  </tr> 
  <tr> 
   <td>c.insert(p,il)</td> 
   <td>il是花括号包围得到元素值序列</td> 
  </tr> 
  <tr> 
   <td>c.front()</td> 
   <td>首元素</td> 
  </tr> 
  <tr> 
   <td>c.back()</td> 
   <td>尾元素</td> 
  </tr> 
 </tbody> 
</table>

### list ###

<table> 
 <thead> 
  <tr> 
   <th>项目</th> 
   <th>Value</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>c.push_back(t)</td> 
   <td>t必须和c类型一致</td> 
  </tr> 
  <tr> 
   <td>c.emplace_back(arg)</td> 
   <td>会调用构造函数，class C c.emplace_back(“hello”)，会自动调用class c相应的构造函数</td> 
  </tr> 
  <tr> 
   <td>c.push_front(t)</td> 
   <td>将元素插到头部 (头插法)</td> 
  </tr> 
  <tr> 
   <td>c.emplace_front(arg)</td> 
   <td></td> 
  </tr> 
  <tr> 
   <td>c.insert(p,t)</td> 
   <td>指定p位置之前插入t，返回的是第一个新加入元素的迭代器</td> 
  </tr> 
  <tr> 
   <td>c.emplace(p,args)</td> 
   <td></td> 
  </tr> 
  <tr> 
   <td>c.insert(p,n,t)</td> 
   <td>p之前n个t</td> 
  </tr> 
  <tr> 
   <td>c.insert(p,b,e)</td> 
   <td></td> 
  </tr> 
  <tr> 
   <td>c.insert(p,il)</td> 
   <td>il是花括号包围得到元素值序列</td> 
  </tr> 
  <tr> 
   <td>c.front()</td> 
   <td>首元素</td> 
  </tr> 
  <tr> 
   <td>c.back()</td> 
   <td>尾元素</td> 
  </tr> 
 </tbody> 
</table>

### forward\_list ###

<table> 
 <thead> 
  <tr> 
   <th>项目</th> 
   <th>Value</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>a.before_begin()</td> 
   <td></td> 
  </tr> 
  <tr> 
   <td>a.cbefore_begin()</td> 
   <td></td> 
  </tr> 
  <tr> 
   <td>a.insert_after(p,t)</td> 
   <td>返回指向最后一个插入元素的迭代器，下同</td> 
  </tr> 
  <tr> 
   <td>a.insert_after(p,n,t)</td> 
   <td>在p之后插入n个t</td> 
  </tr> 
  <tr> 
   <td>a.insert_after(p,b,e)</td> 
   <td>范围为空，返回p，下同</td> 
  </tr> 
  <tr> 
   <td>a.insert_after(p,il)</td> 
   <td>il是花括号包围得到元素值序列，</td> 
  </tr> 
  <tr> 
   <td>emplace_after(p,args)</td> 
   <td></td> 
  </tr> 
  <tr> 
   <td>a.erase_after§</td> 
   <td>删除p之后元素</td> 
  </tr> 
  <tr> 
   <td>a.erase_after(b,e)</td> 
   <td>删除范围(b,e)，不包括b不包括e</td> 
  </tr> 
  <tr> 
   <td>c.front()</td> 
   <td>首元素</td> 
  </tr> 
 </tbody> 
</table>

## 访问 ##

<table> 
 <thead> 
  <tr> 
   <th>项目</th> 
   <th>Value</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>c.begin() , c.end();</td> 
   <td>$都能使用迭代器</td> 
  </tr> 
  <tr> 
   <td>c.at()</td> 
   <td>string,vector,deque,array访问失败抛出out_of_range异常</td> 
  </tr> 
  <tr> 
   <td>auto &amp;c=a.begin()</td> 
   <td>引用修改</td> 
  </tr> 
 </tbody> 
</table>

## 删除 ##

### vector和string ###

<table> 
 <thead> 
  <tr> 
   <th>项目</th> 
   <th>Value</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>c.pop_back()</td> 
   <td>最后一个</td> 
  </tr> 
  <tr> 
   <td>c.erase§</td> 
   <td>返回被删除元素之后的元素迭代器</td> 
  </tr> 
  <tr> 
   <td>c.erase(b,e)</td> 
   <td>删除[begin,end)</td> 
  </tr> 
  <tr> 
   <td>c.clear()</td> 
   <td></td> 
  </tr> 
 </tbody> 
</table>

### list ###

<table> 
 <thead> 
  <tr> 
   <th>项目</th> 
   <th>Value</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>c.pop_back()</td> 
   <td></td> 
  </tr> 
  <tr> 
   <td>c.pop_front()</td> 
   <td></td> 
  </tr> 
  <tr> 
   <td>c.erase§</td> 
   <td></td> 
  </tr> 
  <tr> 
   <td>c.clear()</td> 
   <td></td> 
  </tr> 
 </tbody> 
</table>

### 非单向链表删除代码 ###

for(vector<int>::iterator iter = ivec.begin();iter != ivec.end();){ 
    	if((*iter) %2 == 0)
    		iter = ivec.erase(iter);
    	else  
    		iter++;
    }

### 单向链表删除代码 ###

其实还是要保存前一位的位置

forward_list<int> list_1={ 1,2,3,4,5,6,7,8,9};
    	auto bb=list_1.before_begin();
    	auto b=list_1.begin();
    	while(b!=list_1.end()){ 
    		if(*b%2){ 
    			cout<<"delet "<<*b<<endl;
    			b=list_1.erase_after(bb);
    		}
    		else { 
    			bb=b;
    			++b;
    		}
    	}
    	cout<<"after:"<<endl;
    	for(auto it: list_1)
    		cout<<it<<endl;

结果  
![在这里插入图片描述][20210405162627600.png]

## 改变容器大小 ##

如果当前容器大小大于resize大小，容器后面的数据会被删除，注意迭代器失效

<table> 
 <thead> 
  <tr> 
   <th>项目</th> 
   <th>Value</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>list&lt; int &gt; list(10,42)</td> 
   <td>10个42</td> 
  </tr> 
  <tr> 
   <td>list.resize(15)</td> 
   <td>追加5个0</td> 
  </tr> 
  <tr> 
   <td>list.resize(25,-1)</td> 
   <td>追加10个-1</td> 
  </tr> 
  <tr> 
   <td>ist.resize(5)</td> 
   <td>删除后20个</td> 
  </tr> 
 </tbody> 
</table>

## 代码 ##

删除偶数复制奇数

### 在确定的位置之前插入 ###

vector<int> l={ 1,2,3,4,5,6,7,8,9};
    	auto it = l.begin();
    	while (it!=l.end())
    	{ 
    		if(*it%2){ 
    			it = l.insert(it,*it);
    			it = it+2; //注意此处，insert在it之前插入，并且要跳过当前处理的值
    		}
    		else it=l.erase(it);
    	}
    	cout<<"after:"<<endl;
    	for(auto it: l)
    		cout<<it<<endl;

结果  
![在这里插入图片描述][20210405164957231.png]

### 在确定的位置之后插入 ###

在每一个值之后插入42
    	vector<int> l={ 1,2,3,4,5,6,7,8,9};
    	auto it = l.begin();
    	while (it!=l.end())
    	{ 
    		++it;
    		it = l.insert(it,42);
    		++it;
    	}
    	cout<<"after:"<<endl;
    	for(auto it: l)
    		cout<<it<<endl;

结果  
![在这里插入图片描述][20210405165623616.png]

## 管理容量 ##

都不一定能退回内存空间

<table> 
 <thead> 
  <tr> 
   <th>项目</th> 
   <th>Value</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>c.shringk_to_fit</td> 
   <td>vector string deque 将capacityj减少至==size()</td> 
  </tr> 
  <tr> 
   <td>c.capacity()</td> 
   <td>vector string 不重新分配内存时的最大容量</td> 
  </tr> 
  <tr> 
   <td>c.reserve(n)</td> 
   <td>vector string 分配至少容纳n个元素的内存空间</td> 
  </tr> 
 </tbody> 
</table>

## string的额外操作 ##

### string的添加删除修改 ###

超出范围会扔out\_of\_range

<table> 
 <thead> 
  <tr> 
   <th>项目</th> 
   <th>Value</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>string s(cp,n)</td> 
   <td>cp前n个</td> 
  </tr> 
  <tr> 
   <td>string s(s2,pos2)</td> 
   <td>从s2下标pos2开始拷贝</td> 
  </tr> 
  <tr> 
   <td>string s(s2,pos2,len2)</td> 
   <td>从s2下标pos2开始拷贝长为len2</td> 
  </tr> 
  <tr> 
   <td>s.substr(pos,n)</td> 
   <td>返回一个string 从s的pos开始n个字符拷贝</td> 
  </tr> 
  <tr> 
   <td>s.inster(s.size(),5,’!’)</td> 
   <td>末尾插入5个！</td> 
  </tr> 
  <tr> 
   <td>s.erase(s.size()-5,5)</td> 
   <td>删除后5个</td> 
  </tr> 
  <tr> 
   <td>s.insert(pos,n,c)</td> 
   <td>在下标 pos 的元素之前插入 n 个字符 c</td> 
  </tr> 
  <tr> 
   <td>s.insert(pos,s2)</td> 
   <td>在下标 pos 的元素之前插入 string 对象 s2</td> 
  </tr> 
  <tr> 
   <td>s.insert(pos,s2,pos2,len)</td> 
   <td>在下标为 pos 的元素之前插入 s2 中从下标 pos2 开始的 len 个字符</td> 
  </tr> 
  <tr> 
   <td>s.insert(pos,cp,len)</td> 
   <td>/在下标为 pos 打元素之前插入 cp 所指向数组的前len 个字符</td> 
  </tr> 
  <tr> 
   <td>s.insert(pos,cp)</td> 
   <td>在下标为 pos 的元素之前插入 cp 所指向的以空字符结束的字符串副本</td> 
  </tr> 
  <tr> 
   <td>s.assign(s2)</td> 
   <td>用 s2 的副本替换 s</td> 
  </tr> 
  <tr> 
   <td>s.assign(s2,pos2,len)</td> 
   <td>用 s2 中从下标 pos2 开始的 len 个字符替换 s</td> 
  </tr> 
  <tr> 
   <td>s.assign(cp,len)</td> 
   <td>用 cp 所指向数组的前 len 个字符副本替换 s</td> 
  </tr> 
  <tr> 
   <td>s.assign(cp)</td> 
   <td>用 cp 所指向的以空字符结束的字符串替换 s</td> 
  </tr> 
  <tr> 
   <td>s.erase(pos,len)</td> 
   <td>删除从下标 pos 开始的 len 个字符</td> 
  </tr> 
 </tbody> 
</table>

### string的查找 ###

<table> 
 <thead> 
  <tr> 
   <th>项目</th> 
   <th>Value</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>s.find( args)</td> 
   <td>在 s 中查找 args 的第一次出现</td> 
  </tr> 
  <tr> 
   <td>s.rfind( args)</td> 
   <td>在 s 中查找 args 的最后一次出现</td> 
  </tr> 
  <tr> 
   <td>s.find_first_of( args)</td> 
   <td>在 s 中查找 args 的任意字符的第一次出现</td> 
  </tr> 
  <tr> 
   <td>s.find_last_of( args)</td> 
   <td>在 s 中查找 args 的任意字符的最后一次出现</td> 
  </tr> 
  <tr> 
   <td>s.find_first_not_of( args)</td> 
   <td>在 s 中查找第一个不属于 args 的字符</td> 
  </tr> 
  <tr> 
   <td>s.find_last_not_of( args)</td> 
   <td>在 s 中查找最后一个不属于 args 的字符</td> 
  </tr> 
 </tbody> 
</table>

例如

string numbers("0123456789"),name("r2d2");
    name.find_first_of(numbers)

输出为1，即name中第一个出现在numbers中的字符位置

### 字符串匹配 ###

指定搜索位置，从pos开始

string::size_type pos=0;
    while(pos=name.find_first_of(number,pos)!=string::npos){ 
    	cout<<"find string "<<pos<<end;
    	++pos;
    }

### string转数值 ###

<table> 
 <thead> 
  <tr> 
   <th>项目</th> 
   <th>Value</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>to_string(val)</td> 
   <td>把val转换成string</td> 
  </tr> 
  <tr> 
   <td>stoi(s,p,b)</td> 
   <td>把字符串s从p开始转换成b进制的int</td> 
  </tr> 
  <tr> 
   <td>stol(s,p,b)</td> 
   <td>把字符串s从p开始转换成b进制的long</td> 
  </tr> 
  <tr> 
   <td>stoul(s,p,b)</td> 
   <td>把字符串s从p开始转换成b进制的unsigned long</td> 
  </tr> 
  <tr> 
   <td>stoll(s,p,b)</td> 
   <td>把字符串s从p开始转换成b进制的long long</td> 
  </tr> 
  <tr> 
   <td>stoull(s,p,b)</td> 
   <td>把字符串s从p开始转换成b进制的unsigned long long</td> 
  </tr> 
  <tr> 
   <td>stof(s,p)</td> 
   <td>把字符串s从p开始转换成float</td> 
  </tr> 
  <tr> 
   <td>stod(s,p)</td> 
   <td>把字符串s从p开始转换成double</td> 
  </tr> 
  <tr> 
   <td>stold(s,p)</td> 
   <td>把字符串s从p开始转换成long double</td> 
  </tr> 
 </tbody> 
</table>

### 把混合字符串转数字 ###

string ss = "pi = 3.14";
    	auto d = stod(ss.substr(ss.find_first_of("+-.0123456789")));
    	cout<<d<<endl;

结果  
![在这里插入图片描述][20210405173153845.png]

### 数字转字符串 ###

double a = 123.32;
    string res;
    stringstream ss;
    ss << a;
    ss >> res;//或者 res = ss.str();

## stack queue略 ##

[20210405151158242.png]: /images/20221022/4d4197b179ab4c04820524bea62277e2.png
[20210405162627600.png]: /images/20221022/87b4e322d52143ddb1c69e0cdf147ff0.png
[20210405164957231.png]: /images/20221022/0f652dcabfeb463aa4190b604a711cab.png
[20210405165623616.png]: /images/20221022/f31d527acd2b401bb17ecdcd703431dd.png
[20210405173153845.png]: /images/20221022/51e6c02523084500bdb5755b84f4dbbb.png