常用STL容器归纳

vector容器

1、对象的定义和初始化方式

vector v1 v1 是一个元素类型为 T 的空 vector
vector v2(v1) 使用 v2 中所有元素初始化 v1
vector v2 = v1 同上
vector v3(n, val) v3 中包含了 n 个值为 val 的元素
vector v4(n) v3 中包含了 n 个默认值初始化的元素
vector v5{a, b, c…} 使用 a, b, c… 初始化 v5
vector v1 同上
vector<vector> matrix(M,vector(N)); 二维数组初始化

2、常用基础操作

操作指令 时间复杂度 作用
v.empty() O(1) 如果 v 为空则返回 true，否则返回 false
v.size() O(1) 返回 v 中元素的个数
v.push_back(val) O(1) 向 vector 的尾端添加值为 val 的元素。
v.pop_back() O(1) 删除尾元素，返回void。vector同样 不支持 pop_front 操作。若想在同时弹出元素的值，就必须在执行弹出之前保存它（可以使用 v.back()）。
v.back() O(1) 返回 v 中最后一个元素的引用
v.front() O(1) 返回 v 中第一个元素的引用

1、消除相邻的重复元素 unique()

使用到的函数为 unique() ：将输入序列相邻的重复项“消除”，返回一个指向不重复值范围末尾的迭代器，一般配合 sort() 使用，函数原型：

举例：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
 
int main(void)
{
    vector<int> a{2, 0, 2, 2, 0, 3, 0, 9};
    sort(a.begin(), a.end());  // 先排序
    for(int i:a)   cout << i << " "; // 输出
    cout << endl;
    auto end_unique = unique(a.begin(), a.end());  //将输入序列相邻的重复项“消除”，返回一个指向不重复值范围末尾的迭代器
    a.erase(end_unique, a.end()); // 删除末尾元素
    for(int i:a)   cout << i << " "; // 输出
    return 0;
}
// 运行结果 //
0 0 0 2 2 2 3 9 
0 2 3 9

3、特殊方法

1、逆序 reverse()

++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
 
int main(void)
{
    vector<int> a{2, 0, 2, 2, 0, 3, 0, 9};
    reverse(a.begin(), a.end());  // 原位逆序排列
    for(int i:a)   cout << i << " "; // 输出
    return 0;
}
// 运行结果 //
9 0 3 0 2 2 0 2

2、vector 中找最值

1、最大值 auto it = max_element(v.begin, v,end())，返回最大值的迭代器。

2、最小值 auto it = min_element(v.begin, v,end())，返回最小值的迭代器。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
 
int main(void)
{
    vector<int> a({0,1,-2,3});
    auto b = distance(a.begin(), min_element(a.begin(), a.end()));
    cout << a[b] << endl;
    return 0;
}
// 输出 //
-2

如果不确定元素的确定个数，那么 vector 就是最好的选择。

map容器

1、对象的定义和初始化方式

1
map<T,T> m;

2、常用基础操作

操作指令 时间复杂度 作用
m.insert(pair<T, T>(111, “kk”)); O(logN) 插入pair
m.insert(map<T,T>:: value_type(val1, val2)); O(logN) 插入value_type数据
m[123] = “dd” O(logN) 数组方式插入
m.find(key) O(logN) 返回键是key的映射的迭代器
m.clear() O(logN) 清空
m.erase() O(logN) 删除一个元素

3、特殊方法

。。。。。。。。。装修中(´;ω;)

set容器

1、对象的定义和初始化方式

1
set<T> s;

2、常用基础操作

操作指令 时间复杂度 作用
s.begin() O(1) 返回set容器的第一个元素迭代器
s.end() O(1) 返回set容器的最后一个元素迭代器
s.clear() O(logN) 清空
s.empty() O(1) 判断set容器是否为空
s.earse() O(logN) 删除一个元素
s.size() O(1) 返回当前set容器中的元素个数

3、特殊方法

1、equal_range()

返回一对定位器，分别表示第一个大于或等于给定关键值的元素和 第一个大于给定关键值的元素，这个返回值是一个pair类型，如果这一对定位器中哪个返回失败，就会等于end()的值。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <iostream>
#include <set>
 
 using namespace std;
 
 int main()
 {
     set<int> s;
     set<int>::iterator iter;
     for(int i = 1 ; i <= 5; ++i)
     {
         s.insert(i);
     }
     for(iter = s.begin() ; iter != s.end() ; ++iter)
     {
         cout<<*iter<<" ";
     }
     cout<<endl;
     pair<set<int>::const_iterator,set<int>::const_iterator> pr;
     pr = s.equal_range(3);
     cout<<"第一个大于等于 3 的数是 ："<<*pr.first<<endl;
     cout<<"第一个大于 3的数是 ： "<<*pr.second<<endl;
     return 0;
 }

2、erase(first,second)

删除定位器first和second之间的值

1
2
3
set<T>::const_iterator iter1;
set<T>::const_iterator iter2;
earse(iter1, iter2)

multiset容器

multiset是库中一个非常有用的类型，它可以看成一个序列，插入一个数，删除一个数都能够在O(logn)的时间内完成，而且他能时刻保证序列中的数是有序的，而且序列中可以存在重复的数。

1、对象的定义和初始化方式

1
multiset<rec> s;

2、常用基础操作

操作指令 时间复杂度 作用
s.begin() O(1) 返回set容器的第一个元素迭代器
s.end() O(1) 返回set容器的最后一个元素迭代器
c.insert(val) O(logN) 插入一个val副本，返回新元素位置，无论插入成功与否。
c.insert(pos, val) O(logN) 安插一个val元素副本，返回新元素位置，pos为收索起点，提升插入速度。
s.earse() O(logN) 删除一个元素
s.size() O(1) 返回当前set容器中的元素个数

3、特殊方法

。。。。。。。。。装修中(´;ω;)

queue容器

1、对象的定义和初始化方式

1
queue<T> q;

2、常用基础操作

操作指令 时间复杂度 作用
q.push() O(1) 在队尾插入一个元素
q.pop() O(1) 删除队列第一个元素
q.front() O(1) 返回队列中的第一个元素
q.empty() O(1) 如果队列空则返回true
q.back() O(1) 返回队列中最后一个元素
q.size() O(1) 返回队列中元素个数

3、特殊方法

。。。。。。。。。装修中(´;ω;)

priority_queue容器

1、对象的定义和初始化方式

1
priority_queue<T> q;

2、常用基础操作

操作指令 时间复杂度 作用
q.push() O(logN) 在队尾插入一个元素
q.pop() O(logN) 删除队列第一个元素
q.top() O(1) 返回队列中的第一个元素
q.empty() O(1) 如果队列空则返回true
q.emplace() O(logN) 原地构造一个元素并插入队列
q.size() O(1) 返回队列中元素个数

3、特殊方法

。。。。。。。。。装修中(´;ω;)