STL常用容器

tiny_star Lv3
  2025-07-31 17:25:59 2025-07-31 17:25:59 Créé   2025-09-14 16:16:41 2025-09-14 16:16:41 Mis à jour      

一些常用的STL容器，能记住就记住吧，记不住就得自己写😭，不过好像有些自己写的更好用😝

STL容器底层实现，移步Cpp C++STL标准库与泛型编程C++STL标准库与泛型编程 | tiny_star_blog

vector

1.about

vector可理解为变长数组，内部实现基于倍增思想。
vector支持随机访问，即对于任意的下标0<=i<n，可以像数组一样用 [i] 取值。

2.声明

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include<vector>			//头文件
vector<int> a;				//相当于一个长度动态变化的int数组
vector<int> b[233];			//相当于第一维长233，第二维长度动态变化的int数组
vector<vector<int>> c;		//相当于一个第一维和第二维的长度动态变化的二维int数组

struct rec{...};
vector<rec> d;				//自定义的结构体类型也可以保存在vector中

vector<T> v1;				//v1 是一个元素类型为 T 的空 vector
vector<T> v2(v1);			//使 v1 中所有元素初始化 v2
vector<T> v2 = v1;			//使 v1 中所有元素初始化 v2
vector<T> v3(n, val);		//v3 中包含了 n 个值为 val 的元素
vector<T> v4(n);			//v4 中包含了 n 个默认值初始化的元素
vector<T> v5{a, b, c...};	//使用 a, b, c... 初始化 v5
vector<T> v6(*p, *q);		//使用另外一个数组的指针来初始化v6，这里即可以使用vector的指针，也可以使用普通数组的指针。

3.size/empty

size函数返回vector的实际长度（包含的元素个数）。
empty函数返回一个bool类型，表明vector是否为空。

注：所有的STL容易都支持这两个方法，含义也都相同。

1
2
a.size();			//返回数组vector a的长度
a.empty();			//返回一个bool值，true为vector为空，false为vector不为空

时间复杂度：常数，即 O(1)

4.clear

clear函数把vector清空。

1
a.clear();			//清空数组vector a

时间复杂度：线性，即 O(n)

5.迭代器
迭代器就像STL容器的”指针“，可以用星号”*“操作符解除引用。
vector的迭代器是”随机访问迭代器“，可以把vector的迭代器与一个整数相加减，其行为和指针的移动类似。可以把vector的两个迭代器相减，其结果也和指针相减类似，得到两个迭代器对应下标之间的距离。

一个保存int的vector的迭代器声明方法为：

1
vector<int>::iterator it;

6.begin/end
begin函数返回指向vector中第一个元素的迭代器。例如a是一个非空的vector，则 *a.begin() 与 a[0] 的作用相同。
所有容器都可以视作一个”前闭后开“的结构，end函数返回vector的尾部，即第n个元素再往后的”边界“。 *a.end() 与 a[n] 都是越界访问，其中 n=a.size()。

下标遍历vector数组

1
2
3
4
for(int i=0;i<a.size();i++)
{
    cout<<a[i]<<endl;
}

迭代器遍历vector数组

1
2
3
4
for(vector<int>::iterator it=a.begin();it!=a.end();it++)
{
    cout<<*it<<endl;			//遍历输出数组vector a的值
}

时间复杂度：常数，即 O(1)

7.front/back

front函数返回vector的第一个元素，等价于 *a.begin() 和 a[0]。
back函数返回vector的最后一个元素，等价于 *–a.end() 和 a[a.size()-1]。

1
2
a.front()			//返回数组vector a的第一个元素
a.back()			//返回数组vector a的最后一个元素

时间复杂度：常数，即 O(1)

8.push_back/pop_back

push_back(x)函数将元素x插入到vector的尾部。
pop_back()函数删除vector的最后一个元素。

1
2
a.push_back(x)			//把元素x插入到vector a的尾部
a.pop_back()			//删除vector a的最后一个元素

时间复杂度：常数，即 O(1)

9.resize

resize() 改变vector的大小。如果 n 小于当前大小，则销毁额外的元素。如果 n 大于当前容器大小，则在向量末尾插入新元素。

1
2
void resize (size_type n);
void resize (size_type n, const value_type& val);			//n为新容器的大小，val为容器元素的初始值

时间复杂度：线性，即 O(n)

10.emplace_back（C++ 11）

emplace_back()在向量的末尾插入新元素。如果需要更多空间，则会发生重新分配。此方法将容器大小增加一倍。

1
2
3
void emplace_back (Args&&... args);			//转发参数以构造新元素。

a.emplace_back(b);			//在a的末尾插入b

时间复杂度：常数，即 O(1)

11.insert

insert()在容器中的 position 插入新元素来扩展向量。如果需要更多空间，则会发生重新分配。此函数将容器大小增加一。

1
2
iterator insert (const_iterator position, const value_type& val);	
//position为向量中要插入新元素的索引。val为要分配给新插入元素的值。返回一个指向新插入元素的迭代器。

时间复杂度：线性，即 O(n)

12.erase

erase() 从vector中删除单个元素，从vector中删除元素范围。

1
2
3
4
iterator erase (const_iterator position);	
//position为迭代器指向向量元素。返回一个被删除元素后面的元素的迭代器。
iterator erase (const_iterator first, const_iterator last);
//first为输入迭代器到范围内的初始位置。last为输入迭代器到范围内的最终位置。返回一个被删除元素后面的元素迭代器。

时间复杂度：线性，即 O(n)

queue

1.about

头文件queue主要包括循环队列queue和优先队列priority_queue两个容器。

2.声明

1
2
3
4
5
6
7
8
9
10
#include <queue>						//头文件
queue<int> q1;							//存储int的队列

struct rec{...};
queue<rec> q2;

priority_queue<int> q3;
priority_queue<pair<int,int>> q4;
priority_queue<int,vector,less> q5;			//最大堆（默认为最大堆）
priority_queue<int,vector,greater> q6;		//最小堆

注：pair<>: C++内置的二元组，尖括号分别指定二元组的第一元、第二元的类型。可以用make_pair函数创建二元组，用成员变量first访问第一元、second访问第二元。在比较大小时，以第一元为第一关键字、第二元为第二关键字。

3.循环队列queue

方法 描述 实例 时间复杂度
push 入队（从队尾) q.push(element); O(1)
pop 出队（从队头） q.pop(); O(1)
front 队头元素 int x = q.front(); O(1)
back 队尾元素 int y = q.back(); O(1)
size 实际长度（包含的元素个数） int z = q.size(); O(1)
empty 是否为空 bool a=q.empty(); O(1)

4.优先队列priority_queue

方法 描述 实例 时间复杂度
size 实际长度（包含的元素个数） int x = q.size(); O(1)
empty 是否为空 bool y = q.empty(); O(1)
push 把元素插入堆 q.push(x); O(logn)
pop 删除堆顶元素 q.pop(); O(logn)
top 查询栈顶元素（最大值） int z = q.top(); O(1)

deque

1.about

双端队列deque是一个支持在两端高效插入或删除元素的连续线性存储空间。
它就像是vector和queue的结合。
与vector相比，deque在头部增删元素仅需要 O(1)；
与queue相比，deque像数组一样支持随机访问。

2.声明

1
2
3
4
5
6
#include <deque>								//头文件
deque<int> d1;    								//创建一个empty的int型队列
deque<int> d2(8);  								//创建一个有8个元素的int型队列，默认初始化值(value)为0
deque<int> d3(8, 50);  							//创建一个有8个元素的int型队列，默认初始化值(value)都设为50
deque<int> d4(d1.begin(), d1.end()); 			//通过迭代器创建队列
deque<int> d5(d1);    							//通过拷贝构造创建队列

3.method

方法 描述 示例 时间复杂度
size 实际长度（包含的元素个数） int x = d.size(); O(1)
empty d是否为空 bool y = d.empty(); O(1)
[] 随机访问 int z = d[0]; O(1)
begin deque的头迭代器 deque::iterator it1 = d.begin(); O(1)
end deque的尾迭代器 deque::iterator it2 = d.end(); O(1)
front 队头元素 int a = d.front(); O(1)
back 队尾元素 int b = d.back(); O(1)
push_back 从队尾入队 d.push_back(x); O(1)
push_front 从队头入队 d.push_front(y); O(1)
pop_front 从队头出队 d.pop_front(); O(1)
pop_back 从队尾出队 d.pop_back(); O(1)
clear 清空队列 d.clear(); O(n)

stack

1.about

stack<T>容器适配器中的数据是以 LIFO 的方式组织的，即先进后出，当想访问栈内某一元素时，必须将其顶部的元素都弹出出栈后，才能访问该元素。

2.声明

1
2
3
4
5
#include <stack>						//头文件
stack<int> s1;							//存储int的栈

struct rec{...};
stack<rec> s2;

3.method

方法 描述 实例 时间复杂度
size 实际长度（包含的元素个数） int x = s.size(); O(1)
empty 是否为空 bool y = s.empty(); O(1)
top 栈顶元素 int z = s.top(); O(1)
push 入栈（从栈顶） s.push(a); O(1)
pop 出栈（从栈顶） s.pop(); O(1)

set

1.about

头文件set主要包括set和multiset两个容器，分别是“有序集合”和“有序多重集”，即前者的元素不能重复，而后者可以包含若干个相等的元素。set和multiset的内部实现是一颗红黑树（平衡树的一种），它们支持的函数基本相同。

2.声明

1
2
3
4
5
6
7
8
9
10
11
12
13
14
#include <set>							//头文件
set<int> s1;							//存储int的有序集合set

struct rec{...};
set<rec> s2;

multiset<double> s3;

set<Type> s						      	//定义一个set容器
set<Type> s(s1)			              	//定义一个set容器，并用容器s1来初始化
set<Type> s(b, e)					  	//b和e分别为迭代器的开始和结束的标记
set<Type> s(s1.begin(), s1.begin()+3) 	//用容器s1的第0个到第2个值初始化s
set<Type> s(a, a + 5)      		      	//将a数组的元素初始化vec向量，不包括a[4]
set<Type> s(&a[1], &a[4]) 			  	//将a[1]~a[4]范围内的元素作为s的初始值

set和multiset存储的元素必须定义“小于号”运算符。

3.迭代器

set和multiset的迭代器称为“双向访问迭代器”。不支持“随机访问”，支持星号 (*) 解除引用，仅支持“++”和“–”两个与算术相关的操作。

1
2
3
4
5
6
7
8
9
set<int>::iterator it;

it = s.begin();
it++;
//it将指向“下一个”元素。这里的“下一个”是指在元素从小到大排序的结果中，排在it下一名的元素。
it--;
//同理，it将会指向排在“上一个”的元素。
//执行“++”和“--”操作的时间复杂度都是O(logn)。
//执行操作前后，务必仔细检查，避免迭代器指向的位置超出首、尾迭代器之间的范围。

4.method

方法 描述 实例 时间复杂度
size 实际长度（包含的元素个数） int x = s.size(); O(1)
empty 是否为空 bool y = s.empty(); O(1)
clear 清空 s.clear(); O(n)
begin 返回集合的首迭代器 set::iterator it1 = s.begin(); O(1)
end 返回集合的尾迭代器 set::iterator it2 = s.end(); O(1)
insert 将一个元素插入到集合 s.insert(x); O(logn)
find 在集合中查找等于x的元素，并返回指向该元素的迭代器。如不存在，返回s.end() set::iterator it = s.find(x); O(logn)
lower_bound 查找>=x的元素中最小的一个，并返回指向该元素的迭代器 set::iterator it = s.lower_bound(x); O(logn)
upper_bound 查找>x的元素中最小的一个，并返回指向该元素的迭代器 set::iterator it = s.upper_bound(x); O(logn)
erase 从集合中删除迭代器 it 指向的元素 从集合中删除所有等于x的元素 s.erase(it); s.erase(x); O(logn) O(k+logn)，k为被删除元素个数
count 返回集合中等于x的元素个数 int y = s.count(x); O(k+logn)，k为元素x个数

bitset

1.about

bitset可看作一个多位二进制数，每8位占用1个字节，相当于采用了状态压缩的二进制数组，并支持基本的位运算。
在估算程序运行的时间时，一般以32位整数的运算次数为基准，因此n位 bitset 执行一次位运算的复杂度可视为n/32，效率较高。

2.声明和初始化

1
2
3
4
5
6
7
#include <bitset>				//头文件
bitset<10000> b;				//表示一个10000位二进制数，<>中填写位数。

bitset<n> b;	          		//b有n位，每位都为0
bitset<n> b(u);	          		//b是unsigned long型u的一个副本
bitset<n> b(s);	          		//b是string对象s中含有的位串的副本
bitset<n> b(s, pos, n);	  		//b是s中从位置pos开始的n个位的副本

3.位运算操作符

~b：返回对bitset b按位取反的结果。
&, |, ^：返回对两个位数相同的bitset执行按位与、或、异或运算的结果。
>>, <<：返回把一个bitset右移、左移若干位的结果。
==, !=：比较两个bitset代表的二进制数是否相等。

4.[ ]操作符

**b[k]**表示b的第k位，既可以取值，也可以赋值。
在10000位二进制数中，最低位为 b[0] ，最高位为 b[9999] 。

5.method

方法 描述 实例 时间复杂度
size bitset 的长度 int x = b.size(); O(1)
count 返回有多少位为1 int y = b.count(); O(n/w)，w一般为64注
any 若所有位都为0，返回false； 若s至少一位为1，返回true bool a = b.any(); O(n/w)，w一般为64
none 若所有位都为0，返回true； 若s至少一位为1，返回falseb bool c = b.none(); O(n/w)，w一般为64
set 把所有位变为1； 把第k位改为v，即 b[k] = v b.set(); b.set(k,v); O(1)
reset 把所有位变为0； 把第k位改为0，即 b[k] = 0 b.reset(); b.reset(k); O(1)
flip 把所有位取反，即 s = ~s； 把第k位取反，即 b[k]^=1 b.flip(); b.flip(k); O(1)

注：bitset的count操作的复杂度未在C++ Reference 中标注。一般来说，其复杂度为关于bitset位数的线性复杂度，但实际效率可能稍快一些。

map

1.about

map容器是一个键值对 key-value 的映射。其内部实现是一棵以 key 为关键码的红黑树。map的 key 和 value 可以是任意类型，其中 key 必须定义“小于号”运算符。
在很多时候， map容器被当作Hash表使用，建立从复杂信息 key （如字符串）到简单信息 value （如一定范围内的整数）的映射。
因为map基于平衡树实现，所以它的大部分操作的时间复杂度都在 O(logn) 级别，略慢于使用Hash函数实现的传统Hash表。从C++11开始，STL中新增了unordered_map等基于Hash函数实现的传统Hash表。

2.声明和初始化

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include <map>							//头文件
map<key_type, value_type> name;

map<long long, bool> vis;
map<string, int> hash;
map< pair<int, int>, vector<int> > test;

// 初始化构造
map<int, string> map_test1;		// 默认构造
map<int, string> map_test2(map_test1.begin(), map_test1.end());	// 范围构造

map<int, string> map_test3 = map_test2;			// 赋值构造 
map<int, string> map_test4(map_test2);			// 复制构造 

// 内部是一个pair对象
map<int, string> map_test5{ pair<int, string>(1, "aaa"),pair<int, string>(2, "bbb") };

// 使用make_pair 构造 pair
map<int, string> map_test6{ make_pair(1, "abc"), make_pair(2, "xyz") };

注：pair<>: C++内置的二元组，尖括号分别指定二元组的第一元、第二元的类型。可以用make_pair函数创建二元组，用成员变量first访问第一元、second访问第二元。在比较大小时，以第一元为第一关键字、第二元为第二关键字。

3.迭代器

map的迭代器与set一样，也是“双向访问迭代器”。对map的迭代器解除引用后，将得到一个二元组 pair<key_type, value_type>。

1
2
map<key_type, value_type>::iterator it;
map<string,int>::iterator it;

4.[ ]操作符

**h[key]**返回key映射到的value的引用，时间复杂度为O(logn)。
可以通过 h[key] 来得到 key 对应的 value，还可以对 h[key] 进行赋值操作，改变 key 对应的 value。
若查找的 key 不存在，则执行 h[key] 后，h会自动新建一个二元组 (key, zero)，并返回 zero 的引用。这里 zero 表示一个广义“零值”，如整数 0、空字符串等。如果查找之后不对 h[key] 进行赋值，那么时间一长， h会包含很多无用的“零值二元值”，白白地占用了空间，降低了程序运行效率。强烈建议在用 [ ] 操作符查询之前，先用 find 方法检查 key 的存在性。

5.method

方法 描述 实例 时间复杂度
size 实际长度（包含的元素个数） int x = m.size(); O(1)
empty 是否为空 bool y = m.empty(); O(1)
clear 清空 m.clear(); O(n)
begin 首迭代器 map<key_type, value_type>::iterator it = m.begin(); O(1)
end 尾迭代器 map<key_type, value_type>::iterator it = m.end(); O(1)
insert 插入，参数为pair<key_type,value_type> m.insert(make_pair(1,2)); O(logn)
erase 删除，参数可以是key或者迭代器 m.erase(2); m.erase(it); O(logn)
find 查找，查找key为x的二元组，返回指向该二元组的迭代器。若不存在，返回h.end() map<key_type, value_type>::iterator it = m.find(x) O(logn)

unordered_map

1.about

unordered_map 容器，直译过来就是”无序 map 容器”的意思。所谓“无序”，指的是 unordered_map 容器不会像 map 容器那样对存储的数据进行排序。换句话说，unordered_map 容器和 map 容器仅有一点不同，即 map 容器中存储的数据是有序的，而 unordered_map 容器中是无序的。
具体来讲，unordered_map 容器和 map 容器一样，以键值对（pair类型）的形式存储数据，存储的各个键值对的键互不相同且不允许被修改。但由于 unordered_map 容器底层采用的是哈希表存储结构，该结构本身不具有对数据的排序功能，所以此容器内部不会自行对存储的键值对进行排序。

2.定义和初始化

1
2
3
4
5
6
#include <unordered_map>							//头文件
unordered_map<key_type, value_type> name;

unordered_map<long long, bool> vis;
unordered_map<string, int> hash;
unordered_map< pair<int, int>, vector<int> > test;

注：pair<>: C++内置的二元组，尖括号分别指定二元组的第一元、第二元的类型。可以用make_pair函数创建二元组，用成员变量first访问第一元、second访问第二元。在比较大小时，以第一元为第一关键字、第二元为第二关键字。

3.迭代器

对unordered_map的迭代器解除引用后，将得到一个二元组 pair<key_type, value_type>。

1
2
unordered_map<key_type, value_type>::iterator it;
unordered_map<string,int>::iterator it;

遍历unordered_map：

1
2
3
4
for(unordered_map<string,int>::iterator it = hash.begin(); it != hash.end(); it++)
{
    cout<<(*it).first<<' '<<(*it).second<<endl;
}

4.[ ]操作符

**h[key]**返回key映射到的value的引用，时间复杂度为O(logn)。
可以通过 h[key] 来得到 key 对应的 value，还可以对 h[key] 进行赋值操作，改变 key 对应的 value。
若查找的 key 不存在，则执行 h[key] 后，h会自动新建一个二元组 (key, zero)，并返回 zero 的引用。这里 zero 表示一个广义“零值”，如整数 0、空字符串等。如果查找之后不对 h[key] 进行赋值，那么时间一长， h会包含很多无用的“零值二元值”，白白地占用了空间，降低了程序运行效率。强烈建议在用 [ ] 操作符查询之前，先用 find 方法检查 key 的存在性。

5.method

方法 描述 实例 时间复杂度
size 实际长度（包含的元素个数） int x = m.size(); O(1)
empty 是否为空 bool y = m.empty(); O(1)
clear 清空 m.clear(); O(n)
begin 首迭代器 map<key_type, value_type>::iterator it = m.begin(); O(1)
end 尾迭代器 map<key_type, value_type>::iterator it = m.end(); O(1)
insert 插入，参数为pair<key_type,value_type> m.insert(make_pair(1,2)); O(logn)
erase 删除，参数可以是key或者迭代器 m.erase(2); m.erase(it); O(logn)
find 查找，查找key为x的二元组，返回指向该二元组的迭代器。若不存在，返回h.end() map<key_type, value_type>::iterator it = m.find(x) O(logn)
  • Titre: STL常用容器
  • Auteur: tiny_star
  • Créé à : 2025-07-31 17:25:59
  • Mis à jour à : 2025-09-14 16:16:41
  • Lien: https://tiny-star3.github.io/2025/07/31/Algorithm/STL常用容器/
  • Licence: Cette œuvre est sous licence CC BY-NC-SA 4.0.
Commentaires
Sur cette page
STL常用容器
  1. vector
    1. 1.about
    2. 2.声明
    3. 3.size/empty
    4. 4.clear
    5. 7.front/back
    6. 8.push_back/pop_back
    7. 9.resize
    8. 10.emplace_back（C++ 11）
    9. 11.insert
    10. 12.erase
  2. queue
    1. 1.about
    2. 2.声明
    3. 3.循环队列queue
    4. 4.优先队列priority_queue
  3. deque
    1. 1.about
    2. 2.声明
    3. 3.method
  4. stack
    1. 1.about
    2. 2.声明
    3. 3.method
  5. set
    1. 1.about
    2. 2.声明
    3. 3.迭代器
    4. 4.method
  6. bitset
    1. 1.about
    2. 2.声明和初始化
    3. 3.位运算操作符
    4. 4.[ ]操作符
    5. 5.method
  7. map
    1. 1.about
    2. 2.声明和初始化
    3. 3.迭代器
    4. 4.[ ]操作符
    5. 5.method
  8. unordered_map
    1. 1.about
    2. 2.定义和初始化
    3. 3.迭代器
    4. 4.[ ]操作符
    5. 5.method