【C++STL】STL容器详解

创作不易，本篇文章如果帮助到了你，还请点赞关注支持一下♡>𖥦<)!!
主页专栏有更多知识，如有疑问欢迎大家指正讨论，共同进步！
🔥c++系列专栏：C/C++零基础到精通 🔥

给大家跳段街舞感谢支持！ጿ ኈ ቼ ዽ ጿ ኈ ቼ ዽ ጿ ኈ ቼ ዽ ጿ ኈ ቼ ዽ ጿ ኈ ቼ

在这里插入图片描述

c语言内容💖：

专栏：c语言之路重点知识整合

【c语言】全部知识点总结

容器（Container）：存储数据
算法（Algorithm）：操作数据
迭代器（Iterator）：借助迭代器操作容器数据
仿函数（Function object）：为算法提供更多策略
适配器（Adaptor）：为算法提供更多参数的接口
空间配置器（allocator）：动态分配、管理空间

容器中可以分为向量（vector），双端队列(deque)，表(list)，队列（queue），堆栈(stack)，集合(set)，多重集合(multiset)，映射(map)，多重映射(multimap)。
序列性容器：容器内元素位置保持插入元素的原始顺序

Vector
List
Deque

关联性容器：元素位置与插入顺序无关（取决于排序规则），容器自动申请、释放内存

map
set
hash_map

Vector

动态数组，里面有一个指针指向一片连续的内存空间，与数组的差别在于对空间利用的灵活性。

vector 中删除数据时，vector 的容量不变；扩容时可能导致迭代器失效

扩容：

1.申请新空间
2.拷贝数据到新空间
3.释放原空间

#include <vector>
using namespace std;
class Vector
{
Protected:
	Iterator start;					//表示目前使用空间的头
	Iterator finish;				//表示目前使用空间的尾
	Iterator end_of_storage;		//表示目前可用空间的尾
Public:
	Iterator begin();				//获取头元素迭代器
	Iterator end();					//获取尾元素迭代器
	Reference front();				//返回首元素的值
	Reference back();				//返回尾元素的值
	Size_type size();				//返回使用空间的大小
	Size_type capacity();			//返回容量的大小
	void push_back(const T& x);		//将元素插入到最尾端
	void pop_back();				//将最尾端的元素取出
	Iterator erase(iterator position);//清除某位置上的元素，返回下一节点迭代器
	void insert(位置，数值);		    //在某个位置插入多少个元素
	void clear();			    	//清除所有元素
};

List

双向循环链表，List 在任何位置添加删除效率都为 O(1)，查找效率为 O(n)

#include <list>
using namespace std;
class List
{
Protected:
	Iterator start;					//链表头节点
	Iterator finish;				//链表尾节点
Public:
	Iterator begin();				//获取头节点迭代器
	Iterator end();					//获取尾节点迭代器
    Reference front();				//返回头节点的值
	Reference back();				//返回尾节点的值
	void push_front(const T &x);	//插入一个结点，作为头结点
	void push_back(const T &x);		//插入一个结点，作为尾结点
	void pop_front();				//移除头结点
	void pop_back();				//移除尾结点
	void remove(const T&value);		//将数值为value的所有元素移除
	void unique();					//将“连续而相同的元素”移除只剩一个
	Iterator erase(iterator position);//清除某位置上的元素，返回下一节点迭代器
    Iterator insert(iterator position);	//在指定位置插入元素，返回插入元素迭代器
	void clear();			    	//清除所有元素
    void sort();					//将list 的元素进行升序排序
    bool empty();					//查看链表是否为空
    int size();						//返回链表长度（元素个数）
    void reverse();					//翻转链表
};

vector 与 list 的区别

1.vector 顺序存储，list 链式存储
2.vector 支持快速访问 O(1)，插入删除效率低 O(n)；list 访问性能差 O(n)，支持快速插入删除 O(1)
3.vector 先分配内存不够再扩容，list 插入新节点就要申请新内存

Deque

双端队列，可以在头尾两端分别做元素的插入和删除操作。支持 [] 下标访问。

deque采用类似索引的结构管理内存：采用一块map作为主控，其为一小块连续空间，其中每个元素都是指针，指向另一段较大的连续空间（缓冲区）

deque的迭代器包含4个内容：
1）cur：迭代器当前所指元素
2）first：此迭代器所指的缓冲区的头。
3）last：缓冲区尾。
4）node：指向管控中心。

#include <deque>
using namespace std;
class Deque
{
Protected:
	Iterator start;					//首元素
	Iterator finish;				//尾元素
Public:
	Iterator begin();				//获取头元素迭代器
	Iterator end();					//获取尾元素迭代器
	Reference front();				//返回首元素的引用
	Reference back();				//返回尾元素的引用
	Size_type size();				//返回deque的长度大小
    void push_front(const T &x);	//将元素插入到头部
	void push_back(const T& x);		//将元素插入到最尾端
    void pop_front();				//移除头结点
	void pop_back();				//将最尾端的元素取出
	Iterator erase(iterator position);//清除某位置上的元素
	void insert(位置，数值);		    //在某个位置才插入多少个元素
	void clear();			    	//清除所有元素
    void resize();					//重新设置deque的长度大小
};

deque与vector的区别

1.vector是单向开口的连续线性空间，deque是双向开口的连续线性空间
2.deque 的迭代器更复杂

Map

所有元素都会根据元素的键值自动被排序，map的所有元素都是pair，同时拥有实值(value)和键值(key)。Pair的第一元素被视为键值，第二元素被视为实值。Map 不允许两个元素拥有相同的键值。
查找效率：O( $log_2n$ )

#include <map>
using namespace std;
class Map
{
    iterator find(key);						//查找指定键值map的迭代器
    pair<string,int> pairTemp(string(“A”),5);		//pair的构造函数
    iterator insert(iterator position, pairTemp);		//将pairTemp 插入到map 中
	void erase(iterator position);				//删除指定位置上的 map 元素
	size_type count(key);						//判断该键值的Map 元素是否存在
	size_type size();							//返回map 中的元素的个数
	iterator lower_bound(key);		 		//返回该键值或者大于该键值的map 的迭代器
    iterator upper_bound的(key);				//返回大于该键值的map 的迭代器
};

元素较少时使用 map（底层：红黑树）
元素很多时使用 hash_map（底层：哈希表）

Set

所有元素都会根据元素的键值自动被排序，Set 的元素不像Map那样可以同时拥有实值和键值，Set 元素的键值就是实值，实值就是键值。Set 不允许两个元素有相同的键值。
查找效率：O( $log_2n$ )

#include <set>
using namespace std;
class Set
{
    iterator find(key);						//查找指定键值map的迭代器
    pair<string,int> pairTemp(string(“A”),5);		//pair的构造函数
    iterator insert(iterator position, pairTemp);		//将pairTemp 插入到map 中
	void erase(iterator position);				//删除指定位置上的 map 元素
	size_type count(key);						//判断该键值的Map 元素是否存在
	size_type size();							//返回map 中的元素的个数
	iterator lower_bound(key);		 		//返回该键值或者大于该键值的map 的迭代器
    iterator upper_bound的(key);				//返回大于该键值的map 的迭代器
};

总结

容器	底层实现	描述	包含头文件
向量vector	数组，快速访问	可以在O(1) 时间内访问和修改任意元素，在序列尾部进行插入和删除时，具有 O(1)时间复杂度，对任意项的插入和删除就有的时间复杂度较高，尤其对向量头的添加和删除开销非常高	<vector>
双端队列deque	一个中央控制器和多个缓冲区	基本上与向量相同，唯一的不同是，其在序列头部插入和删除操作时间复杂度也为 O（1）	<deque>
表list	双向链表，快速增删	对任意元素的访问时间复杂度为 O(n)，支持快速插入删除 O(1)	<list>
队列queue	list 或 deque	先进先出	<queue>
堆栈stack	list 或 deque	先进后出	<\stack>
集合set	红黑树，不可重复	由节点组成的红黑树，每个节点都包含着一个元素，具有快速查找的功能，插入删除操作效率低	<set>
多重集合multiset	红黑树，有序，可重复	和 set 基本相同，但可以支持重复元素具有快速查找能力	<set>
映射map	红黑树，有序，不可重复	由{键，值}对组成的集合，具有快速查找能力	<map>
多重映射 multimap	红黑树，有序，可重复	与 map 相比，一个键可以对应多个值，具有快速查找能力	<map>
哈希表 hash_map	哈希表，无序，不可重复	增删查时间复杂度都是O(1)	<hash_map>/<unordered_map>
多重哈希 hash_multimap	哈希表，无序，可重复	增删查时间复杂度都是O(1)	<hash_map>/<unordered_map>