C++七种序列容器类型

偏执的太偏执、 2022-11-21 04:26 150阅读 0赞

### 七种序列容器 ###

*  1，vector-向量
 *  2，deque-双端队列
 *  3，list-双向链表
 *  4，forward\_list-单链表（C++11）
 *  5，queue-队列（适配器）
 *  ,6，priority\_queue-优先队列
 *  7，stack-栈
 *  8，array-数组类（非STL容器）

# 1，vector-向量 #

**vector模板类是最简单的序列类型，除非其他类型的特殊优点能更好地满足需求，否则应默认使用vector。**

*  自动内存管理
 *  随机访问元素
 *  在尾部插入或删除元素，固定时间–O(1)
 *  在头部插入和删除元素，线性时间—O(n)
 *  可反转容器（rbegin(),rend()）

# 2，deque-双端队列 #

*  自动内存管理
 *  随机访问元素
 *  在头部和尾部插入或删除元素都是固定时间—O(1)  
    如果多数操作发生在序列的起始和结尾出，则应考虑使用deque数据结构。deque对象的设计比vector对象更复杂一些。

# 3，list-双向链表 #

除了第一个元素和最后一个元素外，每个元素都与前后相连。可以实现双向遍历链表。

*  在任意位置插入和删除元素都是固定的。强调元素的快速删除和插入。
 *  不支持数组表示法和随机访问。
 *  可反转容器。
 *  具有链表专用成员函数。  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2x1b2xhaWh1YTIwMTg_size_16_color_FFFFFF_t_70_pic_center]

#include <iostream>
    #include<list>
    #include<iterator>
    #include<algorithm>
    using std::cout;
    using std::cin;
    using std::endl;
    using namespace std;
    
    void outint(int n) {
        
    	cout << n <<" " ;
    }
    int main(void) {
        
    	//声明一个名为one的由5个2组成的双向链表
    	list<int> one(5, 2);
    
    	int stuff[5] = {
         1,2,3,8,6 };
    	list<int> two;
    	two.insert(two.begin(), stuff, stuff + 5);
    	int more[6] = {
         6,4,2,4,6,5 };
    	
    	//使用拷贝构造函数
    	list<int> three(two);
    	three.insert(three.end(), more, more + 6);
    
    	cout << "List one:" << endl;
    	for_each(one.begin(), one.end(), outint);
    
    	cout<<endl << "List two:" << endl;
    	for_each(two.begin(), two.end(), outint);
    
    	cout<<endl << "List three:" << endl;
    	for_each(three.begin(), three.end(), outint);
    	
    	//remove(const T & val)---从链表中删除所有val的实例
    	three.remove(2);//删除three中所有的2
    	cout << endl << "After removing,List three:" << endl;
    	for_each(three.begin(), three.end(), outint);
    
    	//splice(pos,x)--将链表x的内容插入到pos前面，x将为空，复杂度为O(1)
    	three.splice(three.begin(), one);
    	cout << endl << "After splicing,List three:" << endl;
    	for_each(three.begin(), three.end(), outint);
    
    	cout<<endl << "List one:" << endl;
    	for_each(one.begin(), one.end(), outint);
    	cout << endl << "List one'size: "<<one.size() << endl;
    
    	//unique()--将连续重复的元素压缩成单个元素--O(1)
    	three.unique();
    	cout << endl << "After unique,List three:" << endl;
    	for_each(three.begin(), three.end(), outint);
    
    	//sort()--使用运算符“<”对链表元素进行排序：n个元素的复杂度为 nlogn
    	three.sort();
    	three.unique();
    	cout << endl << "After sorting and unique,List three:" << endl;
    	for_each(three.begin(), three.end(), outint);
    
    	two.sort();
    	cout << endl << "After sorting,List two:" << endl;
    	for_each(three.begin(), three.end(), outint);
    	//merge(x)融合两个已排序的链表，合并后的链表保存在调用链表中，被融合的x将为空。复杂度为O(1)
    	three.merge(two);
    	cout << endl << "Sorted two merged into three,List three:" << endl;
    	for_each(three.begin(), three.end(), outint);
    	cout << endl << "List two'size: " << two.size() << endl;
    
    	return 0;
    }
    /*
    结果：
    List one:
    2 2 2 2 2
    List two:
    1 2 3 8 6
    List three:
    1 2 3 8 6 6 4 2 4 6 5
    After removing,List three:
    1 3 8 6 6 4 4 6 5
    After splicing,List three:
    2 2 2 2 2 1 3 8 6 6 4 4 6 5
    List one:
    
    List one'size: 0
    
    After unique,List three:
    2 1 3 8 6 4 6 5
    After sorting and unique,List three:
    1 2 3 4 5 6 8
    After sorting,List two:
    1 2 3 4 5 6 8
    Sorted two merged into three,List three:
    1 1 2 2 3 3 4 5 6 6 8 8
    List two'size: 0
    */

*  **remove**(const T & val)—从链表中删除所有val的实例
 *  **splice**(pos,x)–将链表x的内容插入到pos前面，**x将为空**，复杂度为O(1)
 *  **insert和splice的区别**：insert是将原始区间的副本插入到目标地址，而splice则将原始区间移到目标地址。因此，在one的内容和three合并后，one为空，但是splice方法执行后，迭代器仍然有效，也就是说如果迭代器设置为指向one中的某个元素，在执行three.splice(three.begin(),one)之后,该迭代器仍然指向相同的元素。可以把迭代器看作是指针，只要该迭代器指向的内存没有被释放，该迭代器仍然指向该元素。
 *  **unique**()–将连续重复的元素压缩成单个元素–O(1)
 *  **sort**()–使用运算符“<”对链表元素进行排序：n个元素的复杂度为 nlogn
 *  **merge**(x)融合两个已排序的链表，合并后的链表保存在调用链表中，**被融合的x将为空**。复杂度为O(1)

# 4，forward\_list-单链表（C++11） #

在单链表中，每个节点都只链接到下一个节点。它不可反转，相对于list，forward\_list更简单、更紧凑，但功能也更少。

# 5，queue-队列（适配器） #

队列的规则是FIFO，先进先出，可以将元素添加到队尾，从队首删除元素。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2x1b2xhaWh1YTIwMTg_size_16_color_FFFFFF_t_70_pic_center 1]

# ,6，priority\_queue-优先队列 #

它支持和queue相同的操作，但在优先队列中，最大的元素被移到队首。内部的区别在于，默认的底层类是vector。可以修改用于确定哪个元素放到队首的比较方式。方法是提供一个可选的构造函数参数。

priority_queue<int> pq1;//默认声明
    priority_queue<int> pq2(greater<int>);//使用greater去排序

greater<>()函数是一个预定义的函数对象。

# 7，stack-栈 #

栈的规则是LIFO，后进先出。栈的限制有很多，不能随机访问栈元素，甚至不允许遍历栈。只能将元素从栈顶压入或者从栈顶弹出。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2x1b2xhaWh1YTIwMTg_size_16_color_FFFFFF_t_70_pic_center 2]

# 8，array-数组类（非STL容器） #

因为array类对象的长度是固定的，不能调整容器的大小。所以它不是STL容器。但是许多STL算法适用于array对象。比如：operator 和 at()，copy()和for\_each().

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2x1b2xhaWh1YTIwMTg_size_16_color_FFFFFF_t_70_pic_center]: /images/20221120/743cdacec9c0437280251fc292e9c39a.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2x1b2xhaWh1YTIwMTg_size_16_color_FFFFFF_t_70_pic_center 1]: https://img-blog.csdnimg.cn/2020103018082275.jpg?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2x1b2xhaWh1YTIwMTg=,size_16,color_FFFFFF,t_70#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2x1b2xhaWh1YTIwMTg_size_16_color_FFFFFF_t_70_pic_center 2]: https://img-blog.csdnimg.cn/20201030181702544.jpg?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2x1b2xhaWh1YTIwMTg=,size_16,color_FFFFFF,t_70#pic_center