C++ 最常用的容器最常用法与排序（持续增删改）_c++ 堆排序容器

C++ 最常用的容器最常用法与排序（持续增删改）

引述

C++ 的 STL 容器分为顺序容器和关联容器。
顺序容器：vector、deque、list（forward_list）、array、string
关联容器：map 和 set（及其 multi 和 无序版本）
容器适配器（不是容器）：stack、queue、priority_queue

所谓的顺序容器宏观上理解就是小鬼们按一定的顺序排排坐。关联式包括类似于数据库里面，有一个 key，有一个值这样的。只有顺序容器的构造函数才接受大小参数，关联容器并不支持。
顺序容器的 at 和下标操作值适用于 vector、string、deque、array。

容器那么多，操作那么杂，比如 array 不支持添加操作，forward_list 不支持 push_back，vector 和 string 不支持 push_front 等等，我也不住所有。既然如此，我们其实只要记一些关键容器的关键用法即可，其他等到需要的时候，百度查一查即可。下面，就是列出一些我们用得最多的容器的最最常用的一些操作和方法。

不考虑性能以及特殊数据结构专有特性，一般 vector+map+set+string 可以打天下了。记那么多干嘛，年纪大了，根本记不住。如果非要留一个，vector 其实也够了。配上结构体，什么都能干，操作麻烦一点性能差一点而已了。

vector

用法

#include<iostream>
#include<vector>
#include <algorithm>
using namespace std;
int main() {
	vector<int> vec;
	vec.push_back(1);
	vector<int> vec1;
	vec1.resize(10);//10 个 0
	vector<int> vec2(10);//10个元素，每个元素都是 0
	vector<int> vec3(10, 1);//10 个 1
	vec3.assign(10, 1);//分配 10 个 1
	vector<int> vec4(vec3);
	vec.size();
	vec.empty();
	vec.front();//返回一个元素，即迭代器start指向的元素
	vec.back();
	vector<int>::iterator it;
	it = vec1.begin() + 5;
	vec1.erase(it);//清除某个位置的元素，erase 也并不回收空间
	vec.clear();//清除所有的元素
	it = find(vec3.begin(), vec3.end(), 10);//查找
	sort(vec3.begin(), vec3.end());//vector没有自带排序方法，调用算法包，升序排序(默认)
	sort(vec3.begin(), vec3.end(), less<int>());//升序排序
	sort(vec3.begin(), vec3.end(), greater<int>());//降序排序
	for (auto& it : vec) it++;//C++11 方式引用变量
	sort(vec.begin(), vec.end());
    vec.erase(unique(vec.begin(), vec.end()), vec.end());

	vec3.capacity();获取包括备用空间在内的总容量大小
	vec3.at(5);作用同上，增加异常处理，越界抛出out of range
	vec3.max_size();//最大容量，即最多可以存储多少个当前类型元素
	vec3.pop_back();//清除位于最后一个的元素，capacity 不变，size -1
	vec3.erase(vec3.begin(), vec3.end());
	vec3.swap(vec2);//交换容器中各元素的内存地址，并不是交换各个元素变量所存储的值。
	reverse(vec.begin(), vec.end());//元素翻转
	for (int i = 0; i < vec.size(); i++) cout << vec[i] << endl;
	for (it = vec.begin(); it != vec.end(); it++) cout << *it << endl;
	for (auto it : vec) cout << it << endl;
	vector<int>::reverse_iterator rit;
	for (rit = vec.rbegin(); rit != vec.rend(); rit++) cout << *rit << endl;
	
	return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45

其他说明

通常，使用 vecotr 是最好的选择，除非你有很好的理由选择其他容器。这也是我几乎不介绍其他顺序容器的原因。什么时候不用 vector 呢？比如说，当你基于性能的考虑，或者基于数据结构典型用法的考虑。这里说的数据结构典型性，指的是譬如你要写的一个算法，用到了非常典型 “先进后出” 的特征，而且有高强度的弹出和推入的操作，这时候你不妨考虑用 stack，而不是 vector。

在 vector 中间插入是合法但是是耗时的。很多人写算法，想到哪个就用哪个，这是很不对的，在选择容器的时候，我们要考虑程序的性能。那么应该如何选择合适的容器呢？如果你想表达的数据，stack 或者 queue 的特征已经非常明显了，直接用他俩；如果对数据后续要有大量的查找，就用关联式容器，其中又以无序的查找最快，但是它无序；如果有大量的添加和删除操作(特别是在中间)，选择 list，而尽可能地避免 vector 和 array；如果对元素的次序要求比较高，且没有元素在中间的插入或者删除，且没有极其大量的查找，可以选择 vector 和 array…

vector 其实也支持 insert 操作，但是因为中间的插入对于 vector 来说是致命的耗时，所以我们一般不这么干，不这么干，那就没写这个了。

map

用法

#include<iostream>
#include<map>
using namespace std;
int main() {
	map<int, string> st;
	st[0] = "str1";
	st[1] = "str3";
	st[2] = "str2";
	st.insert(make_pair(3, "str3"));
	st.insert(pair<int,string>(4, "str4"));
	for (auto& it : st) cout << it.second << endl;
	for (int i = 0; i < st.size(); i++) {//直接访问
		cout << st[i] << endl;
	}
	map<int, string>::iterator it = st.begin();//通过迭代器访问
	for (it;it != st.end(); it++) {
		cout << it->first << " " << it->second << endl;
	}
	it = st.find(0);
	cout << it->first << " " << it->second << endl;

	st.erase(1);//通过键删除
	st.erase(st.find(0));//通过迭代器（指针）删除
	st.erase(st.begin(), st.end());//相当于st.clear()

	return 0;

}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

其他说明

对一个 map 使用下标操作，其行为与数组或者 vector 上的下标操作很不相同：使用一个不在容器中的关键字作为下标，会添加一个具有此关键字的元素到 map 中。

map 是插入元素的时候就已经排好序了，当你需要排好序的数据结构的时候，可以考虑 map 和 set。

multimap 使用的头文件依然是 map，而 unordered_map 需要加入头文件 unordered_map.h 。

set

用法

#include<iostream>
#include<set>
using namespace std;
int main() {
	set<int> s;
	s.insert(3);
	s.insert(5);
	s.insert(1);
	for (auto& it : s) cout << it << endl;
	set<int>::iterator it; 
	for (it = s.begin();it != s.end(); it++) {
		cout << *it<< endl;
	}

	s.erase(s.find(1));
	s.erase(3);
	s.erase(s.find(5), s.end());//删除了5,9 
	s.clear();
	cout << s.size();//输出为
	return 0;

} 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

其他说明

与 map 不同的地方，不能通过下标 key 来访问了，只能直接 find。

string

#include<cstdio>
#include<string>
using namespace std;
int main() {
	//增
	string str1 = "abc";
	string str2 = "def";
	string str = str1 + str2;
	str > str2;//字典序比较
	str.insert(2, str1);	//在下标为 2 的地方插入str1
	str.insert(str.begin() + 1, str1.begin(), str1.end());
	s.substr(pos, n)    截取s中从pos开始（包括0）的n个字符的子串，并返回
	s.substr(pos)        截取s中从从pos开始（包括0）到末尾的所有字符的子串，并返回
	string str(n,'a');

	//删
	str.erase(str.begin() + 1);
	str.erase(str.begin() + 2, str.end());
	str.erase(1, 2);//删除从 1 开始的 2 个元素

	//改
	str.replace(0, 2, str1);//把起始位置为 0，长度为 2 的源子串替换为str1
	str.replace(str.begin(), str.begin() + 2, str1);

	//查（包括访问）
	int pos = str.find("bc");//返回查找字符串第一次在源串中的位置，找不到则返回 str.npos
	pos = str.find("bc", 2);//从源串的第 2 个位开始查找, 返回在 str 中的下标，逆向查找用 rfind
	for (auto& it : str) printf("%c\n", it);//
	for (auto it = str.begin(); it < str.end(); it++) {
		printf("%c\n", *it);
	}

	return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

用法

其他说明

string 和 vector 一样，支持数字下标访问。

直接读入或者输出一个 string 类型，用 cin 和 cout。str[i] 要用 printf 输出的。

本质上，可以直接把 string 理解成一个 char 型数组，char 数组的用法，它也要支持的。

一般要 erase 或者 find 的输入标标签的话，如果是迭代器，末尾一个位置一般是最后一个要迭代的 +1 ，也就是左闭右开区间。典型的例子有从 s.begin() 到 s.end()，事实上，s.end 就是最后一个位子 +1。

其他

大顶堆小顶堆

priority_queue<int> heap;  //使用优先队列构造大顶堆
priority_queue<int,vector<int>,greater<int> > heap2;  //小顶堆
1
2

• top 访问队头元素
• empty 队列是否为空
• size 返回队列内元素个数
• push 插入元素到队尾 (并排序)
• emplace 原地构造一个元素并插入队列
• pop 弹出队头元素
• swap 交换内容