常用STL

有些时候想开一个数组，但是却不知道应该开多大长度的数组合适，因为我们需要用到的数组可能会根据情况变动。这时候我们就需要用到动态数组。所谓动态数组，也就是不定长数组，数组的长度是可以根据我们的需要动态改变的。动态数组的实现也不难，但是在 C++ 里面有已经写好的标准模板库Standard Template Librarv，就是我们常说的 STL 库，实现了集合、映射表、栈、队列等数据结构和排序、查找等算法。我们可以很方便地调用标准库来减少我们的代码量

vector 动态数组

函数 C++ vector | 菜鸟教程

C++中动态数组写作vector，C语言中没有标准库，这也是为什么参加比赛推荐用C++而不用C的原因

引用库

#include<vector>

构造

构造一个vector 的语句为: vector<T> a

这样我们定义了一个名为 a 的储存类型数据的动态数组。其中是我们数组要储存的数据类型，可以是 int 、float 、double、或者其他自定义的数据类型等等。初始的时候 a 是空的。比如vector <int> a定义了一个储存整数的动态数组a。

插入元素

通过push_back()方法在数组最后面插入一个新的元素

删除

通过pop_back()方法在数组最后的一个元素

获取长度并且访问元素

通过size()获取数组长度 通过[]操作直接访问 vector 中的元素

清空

调用 clear() 方法就可清空 vector并不会清空开的内存。

新构建一个，用swap()方法与其交换可以清空vector的内存

vector<int> a;
vector<int>().swap(a);

#include<iostream>
#include<vector>
using namespace std;
vector<int> a;
int main() {
	cout << "初始化状态" << endl;
	cout << "size:" << a.size();
	for (int i = 0; i < a.size(); i++) {
		cout << a[i] << endl;
	}
	cout << endl;

	cout << "尾插" << endl;
	a.push_back(1);
	a.push_back(2);
	a.push_back(3);
	cout << "size:" << a.size()<<endl;
	for (int i = 0; i < a.size(); i++) {
		cout << a[i] << endl;
	}
	cout << endl;

	cout << "尾删" << endl;
	a.pop_back();
	cout << "size:" << a.size()<<endl;
	for (int i = 0; i < a.size(); i++) {
		cout << a[i] << endl;
	}
	cout << endl;

	cout << "清除" << endl;
	a.clear();
	cout <<"size:" << a.size()<<endl;
	for (int i = 0; i < a.size(); i++) {
		cout << a[i] << endl;
	}
	cout << endl;

	cout << "去内存" << endl;
	vector<int>().swap(a);
	cout << "size:" << a.size();
	for (int i = 0; i < a.size(); i++) {
		cout << a[i] << endl;
	}
}

vector():创建一个空vector

vector(n):创建一个vector,元素个数为n,mor

vector(n,x):创建一个vector，元素个数为n,且值均为x

vector(const vector&):复制构造函数

vector(begin,end):复制（begin,end)区间内另一个数组的元素到vector中`

二维动态数组

vector<vector<int> > b

---

set 集合

引用库

#include<set>using namespace std;

构造

set<T> s

这样我们定义了一个名为s的、储存类型数据的集合，其中T是集合要储存的数据类型。初始的时候 s 是空集合。比如set<int> aa， set<string> bbb 等等。

插入

insert()

C++ 中用insert()函数向集合中插入一个新的元素。注意如果集合中已经存在了某个元素，再次插入不会产生任何效果，集合中是不会出现重复元素的。

删除

erase()

C++ 中通过erase(）函数删除集合中的一个元素，如果集合中不存在这个元素，不进行任何操作。

断元素是否存在

count()

C++ 中如果你想知道某个元素是否在集合中出现，你可以直接用 count()函数。如果集合中存在我们要查找的元素，返回1,否则会返回0。

遍历元素

C++ 通过迭代器可以访问集合中的每个元素，迭代器就好像一根手指，指向 set 中的某个元素。通过操作这个手指，我们可以改变它指向的元素。通过 * (解引用运算符，不是乘号的意思)操作可以获取迭代器指向的元素。通过++操作让送代器指向下一个元素，同理-- 操作让迭代器指向上一个元素。

迭代器的写法比较固定，set<T>::iterator it 就定义了一个指向 set<T>这种集合的送代器 it，T是任意的数据类型。其中::iterator 是固定的写法

begin 函数返回容器中起始元素的迭代器，end函数返回容器的尾后迭代器。

注意，在C++中遍历set 是从小到大遍历的，也就是说 set 会帮我们排序的。

set和结构体

struct Node {
	int x, y;
	bool operator<(const Node& rhs) const {
		if (x == rhs.x) {
			return y < rhs.y;
		}
		else {
			return x < rhs.x;
		}
	}
};

operator<表示我们要重载运算符<，可以看成是一个函数名。rhs 是right hand side的简称，有右操作数的意思，这里我们定义为一个const引用。因为该运算符重载定义在结构体内部，左操作数就当前调用operator<的对象 特别要注意，不要漏掉最后的const 。const 函数表示不能对其数据成员进行修改操作，并且 const 对象不能调用非 const 成员函数，只允许调用 const 成员函数。 上面重载规定了排序方式为，优先按照 x从小到大排序，如果x相同，那么再按照 y从小到大排序。经过了<运算符重载的结构体，我们就可以比较两个Node 对象的大小了，因此可以直接储存在set中了。

&避免建临时变量，const防止因传&而改变

map 映射

引用库

#include<map>using namespace std;

构造

map<T1,T2> m;

在C++中，我们构造一个map 的语句为: map<T1,T2>m;。这样我们定义了一个名为m的从T1类型到T2类型的映射。初始的时候m是空映射。

比如 map <string,int> m构建了一个字符串到整数的映射，这样我们可以把一个字符串和一个整数关联起来。

插入

pair<T1,T2> p;用于保存

insert(make_pair(T1,T2))

我们向映射中加入新映射对的时候就是通过插入 pair 来实现的。如果插入的 key 之前已经存在了，将不会用插入的新的 value替代原来的 value，也就是这次插入是无效的。

访问

m[ ]

C++ 中访问映射和数组一样，直接用[]就能访问。比如 dict["Tom"]就可以获取"Tom"的班级了。而这里有一个比较神奇的地方，如果没有对"Tom"做过映射的话，此时你访问dict["Tom"]，系统将会自动为"Tom"生成一个映射，其value为对应类型的默认值(比如int的默认值是0，string的默认值是空字符串)。

并且我们可以之后再给映射赋予新的值，比如 dict["Tom"] = 3，这样为我们提供了另一种方便的插入手段。实际上，我们常 常通过下标访问的方式来插入映射，而不是通过用insert 插入一个pair 来实现。

遍历

map<T1,T2> m::iterator it = m.begin();it !=m.enf(); it++;

在C++中遍历map 是按照关键字从小到大遍历的，这一点和 set 有些共性。

练习

1锯齿矩阵

#define _CRT_SECURE_NO_WARNINGS 1
#include<iostream>
#include<vector>
using namespace std;
vector<int> a[10005];
int main() {
	int n, m;
	int x, y;
	cin >> n >> m;
	for (int i = 0; i < m; i++) {
		cin >> x >> y;
		a[x].push_back(y);
	}
	for (int i = 1; i <= n; i++) {
		for (int j = 0; j < a[i].size(); j++) {
			if (j != a[i].size() - 1) {
				cout << a[i][j] << " ";
			}
			else {
				cout << a[i][j];
			}
		}
        cout<<endl;
	}
	return 0;
}

3 12
1 3
2 2
2 3
2 4
3 1
3 6
1 5
1 2
1 6
3 2
3 7
1 1

3 5 2 6 1
2 3 4
1 6 2 7