一幅长文细学算法（一）——C++STL

#include 
using namespace std;
int main(){
	cout << "hello world" <

#include 
using namespace std;
int main(){
	int a = 1;
	string b = "hello";
	cout << a << endl;
	cout << b << endl;
	cin.get();
	return 0;
}
1
2
3
4
5
6
7
8
9
10

int* number = new int;
int* arr = new int[100];
int* carr = (int*)malloc(100*sizeof(int));
1
2
3

void swapInt(int&a, int&b){
	int c = a;
	a = b;
	b = c;
}

int main(){
	int a = 1,b =2;
	swapInt(a,b);
}
1
2
3
4
5
6
7
8
9
10

int add(int a, int b){
	return a+b;
}
int add(int a){
	return a;
}
int minus(int a,int b = 0){
	return a-b;
}

int main(){
	add(0);
	add(0,0);
	minus(0);
	minus(0,0);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

struct node{
	int number;
	node* next;
};
//struct node* head;
node* head;
1
2
3
4
5
6

struct node{
	int number;
	node* next;
	node(int _number = 0,node* _next = nullptr){
		number = _number;
		next = _next;
	}
};

int main(){
	node a = node(0);
    node* b = new node(1,&a);
}
1
2
3
4
5
6
7
8
9
10
11
12
13

vector arr1(100);
vector arr2;
vector arr3 = {1,2,3,4,5};
vector arr4{1,2,3,4,5};
int arr2[100];

vector list;
list.push_back(1);
1
2
3
4
5
6
7
8

vector arr1(100);
int arr2[100];

vector::iterator p1;
int* p2;

for(p1 = arr1.begin();p1 != arr1.end();p1++){
	cout << *p1<

• 1
• 2
• 3
• 4
• 5
• 6
• 7
• 8
• 9
• 10
• 11
• 12
• 13

与普通的数组类似，vector也可以使用指针来访问遍历每一个元素。STL的指针被称为迭代器。

C++的迭代器需要指明类型，如需要访问整型向量的迭代器写作vector::iterator p1;。

begin()是首元素迭代器，begin默认在容器的首元素的地址。end同理，默认在容器的尾元素的下一个地址。

vector基本操作

声明：vector list;

1.3.2.2 string字符串

string简介

string str1 = "hello";
char str2[] = "world";
string str3;

str3.push_back('!');

cout << str1 << " " << str2 << str3 << endl;
1
2
3
4
5
6
7

• 字符串string可以看成一个特殊的vector。
• string和c语言字符串的关系就和vector和普通数组的关系一样。
• C++中的字符串可以很方便的拼接。
• vector有的操作string基本都有，唯一的区别就是size的复杂度。
• 所有参数为字符串的地方既可以是string也可以是C字符串。

string基本操作

声明：string str = “hello”

1.3.2.3 stack栈

stack sta;
sta.push(1);
int topElement = sta.top();
sta.pop();
sta.empty();
sta.size();
1
2
3
4
5
6

• STL大部分数据结构和vector一样，都会自带size()和empty()函数
• stack操作包括入、出、获取栈顶元素，复杂度都是O(1)

1.3.2.4 queue队列

queue que;
que.push(1);
int frontElement = que.front();
que.pop();
que.empty();
que.size();

priority_queue que2;
que2.push(1);
int minElement = que2.top();
que2.pop();
que2.empty();
que.size();
1
2
3
4
5
6
7
8
9
10
11
12
13

1.3.2.5 set集合

set st;
st.insert(1);
st.find(1);
st.erase(1);

multiset mst;
mst.insert(1);
mst.insert(1);
mst.count(1); //2
1
2
3
4
5
6
7
8
9

• set用于保存很多很多元素，能够在O(logn)的时间内查找、删除、添加某个元素
• 迭代器中的++和–能够在O(logn)的时间里找到第一个比它大（小）的数
• set自带去重，而multiset允许元素重复，通过count可以获得某个元素的数量
• set是用红黑平衡树实现的

1.3.2.6 map 映射

pair origin;
origin = make_mair(0,0);
origin.first == origin.second;
origin.swap;

pairid;
id = make_pair("somebody",110);
1
2
3
4
5
6
7

• 如果我们不像以pairid这样的方式写出数据结构，则可以使用make_pair方法来构造一个数对并返回。
• pair自带了比较函数，默认先比第一个元素再比较第二个。

pair id;
id = make_pair("somebody",110);

map studentHeight;
studentHeight["小明"] = 170;
studentHeight["小红"] = 150;
studentHeight.insert(id);
studentHeight.erase("小明");
1
2
3
4
5
6
7
8

• map可以看成一个超级数组，我们可以把字符串或者其他类型当成数组的下标
• 插入、查询、删除操作复杂度都是O(logn)
• map内部使用了pair，所以我们也可以通过insert一个pair来插入
• map可以使用大括号加大括号的方式初始化。

1.3.2.7 bitset 位集合

1.3.2.8 multiset哈希集合和multimap哈希表

和分别是和

有些毒瘤题目会卡map的时间，用unordered_map

1.3.3 Algorithm算法函数

algorithm和之前两个头文件不同，它没有定义什么新的类型，而是定义了很多算法，极大简化了代码量。

1.3.3.1 sort快排

sort的基本使用

语法：sort(数组首元素地址,数位尾元素的下一位地址)

int arr[] {2,3,1,5,4};
int n = 5;

sort(arr,arr+n);
for(int i = 0;i arr;
arr.push_back(2);
arr.push_back(3);
arr.push_back(1);
sort(arr.begin(),arr.end());

for(int var : arr){
	cout << var << endl;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

注：C++sort排序的复杂度是O(nlogn)

降序排列

bool cmpInt(int a, int b){
	return a>b;
}
vector arr;
arr.push_back(2);
arr.push_back(3);
arr.push_back(1);
sort(arr.begin(),arr.end(),cmpInt);
1
2
3
4
5
6
7
8

• 和C语言的qsort一样，sort可以使用自定义的比较函数。比较函数的参数时两个待比较的变量，返回值是比较的bool值。
• 内部排序函数是按小于关系来的，排序结果是升序。如果像上述代码一样按大于关系比较，则可以得到降序的排序结果。

结构体的排序

struct Point{
	int x,y;
};
Point points[1111];

bool cmp(Point a,Point b){
	if(a.x != b.x){
		return a.x