C++ STL容器详细笔记

Posted on | In | | Visitors:
Words count in article: 8.5k

C++ STL容器详细笔记

C++ 对模板（Template）支持得很好，STL 就是借助模板把常用的数据结构及其算法都实现了一遍，并且做到了数据结构和算法的分离。

Vector容器详解

使用vector容器前需要#include <vector>并且加上一句 using namespace std; 即可

vector容器常见用途：

1）存储数据

①作为数组使用，在数组元素个数不确定时能够很好的节省空间

②有些场合需要根据一些条件把部分数据输出在同-行，数据中间用空格隔开。由于输出数据的个数是不确定的，为了更方便地处理最后一个满足条件的数据后面不输出额外的空格，可以先用vector 记录所有需要输出的数据，然后-次性输出。

2）用邻接表存储图

vector容器的定义

1
2
3
4
5
6
7
8
9
//通用格式
vector<typename> Arrayname;
//举个例子
vector<int> vi;
//初始化方式1
vector<int> vi={1,2,3};
//初始化方式2
vector<int> vi(7,3);	//初始化为7个值为3的vector，若3缺省，则默认初始化为0
vector< vector<int> > arr( m, vector<int>(n) );   // 初始化m行 n列的二维vector容器

vector容器的访问

vector容器有两种访问形式：一种是和访问普通数组相同，另一种是通过迭代器访问。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <iostream>
#include <vector>
using namespace std;

int main(int argc, char** argv) {
	vector<int> vi;
	for(int i = 1; i <= 5; i++)
	{
		vi.push_back(i);	//push_back在vi的末尾添加元素i 
	}
	for(int i = 0; i < 5; i++)
	{
		printf("%d ", vi[i]);	//和数组相同的方式访问 
	}
	printf("\n");
	vector<int>::iterator it = vi.begin();
	for(int i = 0; i < 5; i++)
	{
		printf("%d ", *(it+i));	//使用迭代器访问 
	}
	return 0;
}

输出结果为：

1
2
1 2 3 4 5
1 2 3 4 5

vector常用函数

1. push_back()

在vector后面添加一个元素x，时间复杂度为O(1)，例如：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include <iostream>
#include <vector>
using namespace std;

int main(int argc, char** argv) {
	vector<int> vi;
	for(int i = 1; i <= 3; i++)
	{
		vi.push_back(i);	//push_back在vi的末尾添加元素i 
	}
	for(int i = 0; i < 3; i++)
	{
		printf("%d ", vi[i]);	//和数组相同的方式访问 
	}
	return 0;
}

输出结果：

1
1 2 3

2. pop_back()

删除vector的末尾元素，时间复杂度为O(1)，例如：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include <iostream>
#include <vector>
using namespace std;

int main(int argc, char** argv) {
	vector<int> vi;
	for(int i = 1; i <= 3; i++)
	{
		vi.push_back(i);	//push_back在vi的末尾添加元素i 
	}
	vi.pop_back(); 
	for(int i = 0; i < vi.size(); i++)
	{
		printf("%d ", vi[i]);	//和数组相同的方式访问 
	}
	return 0;
}

输出结果：

1
1 2

3. size()

size()用来获得vector中元素的个数，时间复杂度为O(1)，size()返回的是unsigned类型。（其他STL容器也是这样），样例代码：

1
2
3
4
5
6
7
8
9
10
11
12
#include <iostream>
#include <vector>
using namespace std;

int main(int argc, char** argv) {
	vector<int> vi;
	for(int i = 1; i <= 3; i++)
	{
		vi.push_back(i);	//push_back在vi的末尾添加元素i 
	}
	printf("%d\n", vi.size());	//输出vector长度 
}

输出结果：

1
3

4. clear()

用来清空vector中的所有元素，时间复杂度为O(N)。

1
2
3
4
5
6
7
8
9
10
11
12
13
#include <iostream>
#include <vector>
using namespace std;

int main(int argc, char** argv) {
	vector<int> vi;
	for(int i = 1; i <= 3; i++)
	{
		vi.push_back(i);	//push_back在vi的末尾添加元素i 
	}
	vi.clear();	//清空vector 
	printf("%d\n", vi.size());	//输出vector长度 
}

输出结果：

1
0

5. insert()

insert(it, x)用来向vector的任意迭代器it处插入一个元素x，时间复杂度为O(N)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include <iostream>
#include <vector>
using namespace std;

int main(int argc, char** argv) {
	vector<int> vi;
	for(int i = 1; i <= 5; i++)
	{
		vi.push_back(i);	//push_back在vi的末尾添加元素i 
	}
	vi.insert(vi.begin() + 2, -1);
	for(int i = 0; i < vi.size(); i++)
	{
		printf("%d ", vi[i]);
	}
}

输出结果:

1
1 2 -1 3 4 5

6. erase()

erase()有两种用法：删除单个元素和删除一个区间内的所有元素。时间复杂度均为O(N)。

①删除单个元素

erase(it)即删除迭代器为it处的元素

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include <iostream>
#include <vector>
using namespace std;

int main(int argc, char** argv) {
	vector<int> vi;
	for(int i = 1; i <= 5; i++)
	{
		vi.push_back(i);	//push_back在vi的末尾添加元素i 
	}
	vi.erase(vi.begin() + 2);	//擦除第3个元素 
	for(int i = 0; i < vi.size(); i++)
	{
		printf("%d ", vi[i]);
	}
}

输出结果：

1
1 2 4 5

②删除一个区间内的所有元素

erase(first, last)即删除[first, last)内的所有元素

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include <iostream>
#include <vector>
using namespace std;

int main(int argc, char** argv) {
	vector<int> vi;
	for(int i = 1; i <= 5; i++)
	{
		vi.push_back(i);	//push_back在vi的末尾添加元素i 
	}
	vi.erase(vi.begin() + 1,  vi.begin() + 4);	//擦除vi[1], vi[2], vi[3] 
	for(int i = 0; i < vi.size(); i++)
	{
		printf("%d ", vi[i]);
	}
}

输出结果：

1
1 5

6. max_element(),min_element()

需要#include <algorithm>

求最大值与最小值：

1
2
3
4
5
vector<int> v;
//最大值：
int max =  *max_element(v.begin(),v.end());  
//最小值：
int min = *min_element(v.begin(),v.end());

7. distance()

返回两个迭代器之间的距离，再配合使用上述的max_element/min_element就能很快的找到最大值最小值的索引

1
distance(v, max_element(v.begin(),v.end()))

set容器详解

使用set容器前需要#include <set>并且加上一句 using namespace std; 即可

set最主要的作用是自动去重并按升序排列，因此碰到需要去重但是却不方便直接开数组的情况，可以尝试用set解决

set容器的定义

1
2
3
4
//通用定义
set<typename> name;
//举例说明
set<int> st;

set容器内元素的访问

set只能通过迭代器（iterator）访问

除vector和string之外的STL容器都不支持*(it + i)的访问方式，因此只能按如下方式枚举。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include <iostream>
#include <set>
using namespace std;

int main(int argc, char** argv) {
	set<int> st;
	st.insert(3);	//插入元素
	st.insert(5);
	st.insert(2);
	st.insert(3);
	for (set<int>::iterator it = st.begin(); it != st.end(); it ++)
	{
		printf("%d ", *it);	//依次访问每个元素
	}
	return 0;
}

输出结果：

1
2 3 5

set常用函数

1. insert()

insert(x)可将x插入set容器中，并自动递增排序和去重，时间复杂度为O(logN)。样例代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include <iostream>
#include <set>
using namespace std;

int main(int argc, char** argv) {
	set<int> st;
	st.insert(3);	//插入元素
	st.insert(5);
	st.insert(2);
	st.insert(3);
	for (set<int>::iterator it = st.begin(); it != st.end(); it ++)
	{
		printf("%d ", *it);	//依次访问每个元素
	}
	return 0;
}

输出结果：

1
2 3 5

2. find()

find(value)返回set中对应值为value的迭代器，时间复杂度为O(logN)，N为set内的元素个数。样例代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
#include <iostream>
#include <set>
using namespace std;

int main(int argc, char** argv) {
	set<int> st;
	for(int i = 1; i <= 3; i++)
	{
		st.insert(i);
	}
	set<int>::iterator it = st.find(2);	//查找元素2
	printf("%d ", *it);
	return 0;
}

输出结果

1
2

3. erase()

erase()和vector一样，也有两种用法：删除单个元素、删除一个区间内的所有元素。

①删除单个元素

1）st.erase(it)，it为所需删除元素的迭代器。时间复杂度为O(1)，可以结合find()函数来使用。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include <iostream>
#include <set>
using namespace std;

int main(int argc, char** argv) {
	set<int> st;
	for(int i = 1; i <= 3; i++)
	{
		st.insert(i);
	}
	st.erase(st.find(1));	//删除值为1的元素
	st.erase(st.find(3));	//删除值为3的元素
	for(set<int>::iterator it = st.begin(); it != st.end(); it++)
	{
		printf("%d ",*it);
	}
	return 0;
}

输出结果：

1
2

2）st.erase(value)，value为所需删除元素的值。时间复杂度为O(logN)，样例代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include <iostream>
#include <set>
using namespace std;

int main(int argc, char** argv) {
	set<int> st;
	for(int i = 1; i <= 3; i++)
	{
		st.insert(i);
	}
	st.erase(1);	//删除值为1的元素
	st.erase(3);	//删除值为3的元素
	for(set<int>::iterator it = st.begin(); it != st.end(); it++)
	{
		printf("%d ",*it);
	}
	return 0;
}

输出结果：

1
2

②删除一个区间内的所有元素

st.erase(fisrt, last)可以删除一个区间内的所有元素，其中first为所需删除区间的起始迭代器，而last则为所需删除区间的末尾迭代器的下一个地址，即删除[first, last)。时间复杂度为O(last- first)。样例代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include <iostream>
#include <set>
using namespace std;

int main(int argc, char** argv) {
	set<int> st;
	for(int i = 1; i <= 3; i++)
	{
		st.insert(i);
	}
	set<int>::iterator it1 = st.find(2);	//找到值为2的元素迭代器 
	set<int>::iterator it2 = st.find(3);	//找到值为2的元素迭代器 
	st.erase(it1, it2);	//删除[2,3)
	for(it1 = st.begin(); it1 != st.end(); it1++)
	{
		printf("%d ",*it1);
	}
	return 0;
}

输出结果：

1
1 3

4. size()

获得set内元素的个数，时间复杂度为O(1)。样例代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
#include <iostream>
#include <set>
using namespace std;

int main(int argc, char** argv) {
	set<int> st;
	for(int i = 1; i <= 3; i++)
	{
		st.insert(i);
	}
	printf("%d\n", st.size());
	return 0;
}

输出结果：

1
3

5. clear()

clear()用来清空set中的所有元素，时间复杂度为O(N)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
#include <iostream>
#include <set>
using namespace std;

int main(int argc, char** argv) {
	set<int> st;
	for(int i = 1; i <= 3; i++)
	{
		st.insert(i);
	}
	st.clear();
	printf("%d\n", st.size());
	return 0;
}

输出结果：

1
0

string容器详解

使用string容器前需要#include <string>并且加上一句 using namespace std; 即可

string容器的定义

1
2
3
4
5
//通用定义 string + 变量名
string str;
//初始化
string str = "abcd"
string str = string(5, 'x')   //将后一个字符重复5次初始化

string的输入和输出

一般读入和输出整个字符串，只能用cin和cout（如果要使用printf的话需要用c_str()函数将string类型转化为字符数组）

1
2
3
4
5
6
7
8
9
10
#include <iostream>
#include <string>
using namespace std;

int main(int argc, char** argv) {
	string str;
	cin>>str;	//输入字符串 
	cout<<str;	//输出字符串 
	return 0;
}

string内容的访问

1）通过下标访问（类似于字符数组）：

1
2
3
4
5
6
7
8
9
10
11
12
#include <iostream>
#include <string>
using namespace std;

int main(int argc, char** argv) {
	string str = "abcd";
	for (int i = 0; i < str.length(); i++)
	{
		printf("%c", str[i]);
	}
	return 0;
}

输出结果：

1
abcd

2）通过迭代器访问：

1
2
3
4
5
6
7
8
9
10
11
12
#include <iostream>
#include <string>
using namespace std;

int main(int argc, char** argv) {
	string str = "abcd";
	for (string::iterator it = str.begin(); it != str.end(); it++)
	{
		printf("%c", *it);
	}
	return 0;
}

string常用函数

1. operator +

string的加法，可以将两个string直接拼接起来

1
2
3
4
5
6
7
8
9
10
11
#include <iostream>
#include <string>
using namespace std;

int main(int argc, char** argv) {
	string str1 = "abc", str2 = "xyz", str3;
	str3 = str1 + str2;
	str1+=str2;
	cout<<str1<<endl<<str3<<endl;
	return 0;
}

输出结果：

1
2
abcxyz
abcxyz

2. compare operator

两个string类型可以直接用 ==, !=, <, <=, >, >= 按照字典序比较大小。样例代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <iostream>
#include <string>
using namespace std;

int main(int argc, char** argv) {
	string str1 = "aa", str2 = "aaa", str3 = "abc", str4 = "xyz";
	if(str1 < str2)
	{
		printf("ok1\n");
	}
	if(str1 != str3)
	{
		printf("ok2\n");
	}
	if(str4 >= str3)
	{
		printf("ok3\n");
	}
	return 0;
}

输出结果：

1
2
3
ok1
ok2
ok3

3. length()/size()

返回string的长度，时间复杂度为O(1)。

1
2
3
4
5
6
7
8
9
#include <iostream>
#include <string>
using namespace std;

int main(int argc, char** argv) {
	string str = "abcdef";
	printf("%d,%d\n",str.length(), str.size());
	return 0;
}

输出结果：

1
6,6

4. insert()

string的insert()函数有很多种写法，以下是几个常用的写法，时间复杂度为O(N)。

①insert(pos, string)，在pos位置插入字符串string。样例代码：

1
2
3
4
5
6
7
8
9
10
#include <iostream>
#include <string>
using namespace std;

int main(int argc, char** argv) {
	string str1 = "abcdef", str2 = "111";
	str1.insert(3, str2);	//等价于 str1.insert(3, "111");
	cout<<str1;
	return 0;
}

输出结果：

1
abc111def

②insert(it, it2, it3)，it为需要插入位置的迭代器，it2和it3为待插入字符串的首尾迭代器。

1
2
3
4
5
6
7
8
9
10
#include <iostream>
#include <string>
using namespace std;

int main(int argc, char** argv) {
	string str1 = "abcdef", str2 = "111";
	str1.insert(str1.begin() + 3,str2.begin(), str2.end());	//等价于 str1.insert(3, "111");
	cout<<str1;
	return 0;
}

输出结果:

1
abc111def

5. erase()

erase()有两种用法：删除单个元素和删除一个区间内的所有元素，时间复杂度均为O(N)。

①删除单个元素：

str.erase(it)用于删除单个元素，it为需要删除元素的迭代器。样例代码：

1
2
3
4
5
6
7
8
9
10
#include <iostream>
#include <string>
using namespace std;

int main(int argc, char** argv) {
	string str = "abcdef";
	str.erase(str.begin()+4);	//即删除字母e
	cout<<str<<endl; 
	return 0;
}

输出结果：

1
abcdf

②删除一个区间内的所有元素

str.erase(first, last)，其中first，last为需要删除区间的其实迭代器，即删除[first,last)。样例代码：

1
2
3
4
5
6
7
8
9
10
#include <iostream>
#include <string>
using namespace std;

int main(int argc, char** argv) {
	string str = "abcdef";
	str.erase(str.begin()+2, str.end()-1);	//即删除cde
	cout<<str<<endl; 
	return 0;
}

输出结果：

1
abf

6. clear()

清空string中的数据，时间复杂度一般为O(1)。

1
2
3
4
5
6
7
8
9
10
#include <iostream>
#include <string>
using namespace std;

int main(int argc, char** argv) {
	string str = "abcdef";
	str.clear();
	printf("%d", str.length());
	return 0;
}

输出结果：

1
0

7. substr()

substr(pos, len)返回从pos号位开始、长度位len的字串，时间复杂度位O(len)。样例代码：

1
2
3
4
5
6
7
8
9
10
11
#include <iostream>
#include <string>
using namespace std;

int main(int argc, char** argv) {
	string str = "Thank you for your smile.";
	cout<<str.substr(0, 5)<<endl;
	cout<<str.substr(14, 4)<<endl;
	cout<<str.substr(19, 5)<<endl;
	return 0;
}

输出结果：

1
2
3
Thank
your
smile

8. string::npos

string::opos是一个常数值，本身的值为-1（由于是unsigned int类型，实际上是unsigned int的最大值），作为find函数失配时的返回值。代码样例：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
#include <iostream>
#include <string>
using namespace std;

int main(int argc, char** argv) {
	if(string::npos == -1)
	{
		cout<<"-1 is ture"<<endl;
	}
	if(string::npos == 4294967295)
	{
		cout<<"4294967295 is ture"<<endl;
	}
}

输出结果：

1
2
-1 is ture
4294967295 is ture

9. find()

有两种用法：

str.find(str2)，当str2是str的子串时返回str第一次出现的位置，如果str2不是str的字串，那么返回string::npos。

str.find(str2, pos)，从str的pos号位开始匹配str2，返回值与上述相同。

时间复杂度为O(nm)，其中n和m分别为str和str2的长度。

如果没要找到给定字符串返回-1

还有其他类似的函数find_first_not_of()和find_last_not_of()

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
#include <iostream>
#include <string>
using namespace std;

int main(int argc, char** argv) {
	string str1 = "Thank you for your smile.";
	string str2 = "you";
	string str3 = "me";
	if(str1.find(str2) != string::npos)
	{
		cout<<str1.find(str2)<<endl;
	}
	if(str1.find(str2,7) != string::npos)
	{
		cout<<str1.find(str2,7)<<endl;
	}
	if(str1.find(str3) != string::npos)
	{
		cout<<str1.find(str3)<<endl;
	}
	else
	{
		cout<<"I know there is no position for me."<<endl;
	}
	return 0;
}

输出结果：

1
2
3
6
4
I know there is no position for me.

10. replace()

replace()有两种使用方法：

str.replace(pos, len, str2)把str从pos号位开始、长度位len的子串替换为str2。

str.repalce(it1, it2, str2)，把迭代器[it1, it2)范围的字串替换位str2。

样例代码：

1
2
3
4
5
6
7
8
9
10
11
12
#include <iostream>
#include <string>
using namespace std;

int main(int argc, char** argv) {
	string str1 = "Maybe you will turn around.";
	string str2 = "will not";
	string str3 = "surely";
	cout<< str1.replace(10, 4, str2)<<endl;
	cout<< str1.replace(str1.begin(), str1.begin() + 5, str3)<< endl;
	return 0;
}

输出结果：

1
2
Maybe you will not turn around.
surely you will not turn around.

11.to_string()

1
2
3
4
5
6
7
8
9
10
函数原型：
string to_string (int val);
string to_string (long val);
string to_string (long long val);
string to_string (unsigned val);
string to_string (unsigned long val);
string to_string (unsigned long long val);
string to_string (float val);
string to_string (double val);
string to_string (long double val);

将数值转化为字符串

map容器详解

使用map容器前需要#include <map>并且加上一句 using namespace std; 即可

map容器的定义

1
2
3
4
//通用定义
map<typename1, typename2> mp;
//举个例子
map<string, int> mp;

map容器内元素的访问

1）通过下标进行访问（和数组类似）

样例代码：

1
2
3
4
5
6
7
8
9
10
11
#include <iostream>
#include <map>
using namespace std;

int main(int argc, char** argv) {
	map<char, int> mp;
	mp['c'] = 20;
	mp['c'] = 30;	//20被覆盖 
	printf("%d\n", mp['c']);
	return 0;
}

输出结果：

1
30

2）通过迭代器访问

样例代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include <iostream>
#include <map>
using namespace std;

int main(int argc, char** argv) {
	map<char, int> mp;
	mp['m'] = 20;
	mp['r'] = 30;
	mp['a'] = 40;
	for (map<char, int>::iterator it = mp.begin(); it != mp.end(); it++)
	{
		printf("%c %d\n", it ->first, it -> second);
	}	//it ->first是映射前的键，it->second是映射后的键 
	return 0;
}

输出结果：

1
2
3
a 40
m 20
r 30

map会以键从小到大的顺序自动排序， 即按a<m<r的顺序排列这三对映射

map常用函数

1. find()

find(key)返回键位key的映射的迭代器（未找到返回end()），时间复杂度位O(logN)，N位map中映射的个数。示例代码：

值得注意的是，访问不存在的map元素时最好先进行find，否则放回会返回默认值并且会创建该键值对！

1
2
3
4
5
6
7
8
9
10
11
12
13
#include <iostream>
#include <map>
using namespace std;

int main(int argc, char** argv) {
	map<char, int> mp;
	mp['m'] = 20;
	mp['r'] = 30;
	mp['a'] = 40;
	map<char, int>::iterator it = mp.find('a');
	printf("%c %d\n", it ->first, it -> second);
	return 0;
}

输出结果：

1
a 40

2. erase()

erase()有两种用法：删除单个元素、删除一个区间内的所有元素。

①删除单个元素：

1）mp.erase(it)，it为需要删除的元素的迭代器。时间复杂度为O(1)。

代码样例

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include <iostream>
#include <map>
using namespace std;

int main(int argc, char** argv) {
	map<char, int> mp;
	mp['m'] = 20;
	mp['r'] = 30;
	mp['a'] = 40;
	map<char, int>::iterator it = mp.find('a');
	mp.erase(it);
	for (it = mp.begin(); it != mp.end(); it++)
	{
		printf("%c %d\n", it ->first, it -> second);
	}	//it ->first是映射前的键，it->second是映射后的键 
	return 0;
}

输出结果：

1
2
m 20
r 30

2）mp.erase(key)，key为欲删除的映射的键。时间复杂度为O(logN)。

代码样例：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include <iostream>
#include <map>
using namespace std;

int main(int argc, char** argv) {
	map<char, int> mp;
	mp['m'] = 20;
	mp['r'] = 30;
	mp['a'] = 40;
	mp.erase('a');
	for (map<char, int>::iterator it = mp.begin(); it != mp.end(); it++)
	{
		printf("%c %d\n", it ->first, it -> second);
	}	//it ->first是映射前的键，it->second是映射后的键 
	return 0;
}

输出结果：

1
2
m 20
r 30

②删除一个区间内的所有元素

mp.erase(first, last)，其中first为需要删除的区间的起始迭代器，而last则为需要删除的区间的末尾迭代器的下一个地址，即删除区间[first, last)，时间复杂度O(last - first)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include <iostream>
#include <map>
using namespace std;

int main(int argc, char** argv) {
	map<char, int> mp;
	mp['m'] = 20;
	mp['r'] = 30;
	mp['a'] = 40;
	map<char, int>::iterator it = mp.find('m');
	mp.erase(it, mp.end());
	for (map<char, int>::iterator it = mp.begin(); it != mp.end(); it++)
	{
		printf("%c %d\n", it ->first, it -> second);
	}	//it ->first是映射前的键，it->second是映射后的键 
	return 0;
}

输出结果：

1
a 40

3. size()

size()用来获得map中映射的对数，时间复杂度为O(1)。

样例代码

1
2
3
4
5
6
7
8
9
10
11
12
#include <iostream>
#include <map>
using namespace std;

int main(int argc, char** argv) {
	map<char, int> mp;
	mp['m'] = 20;
	mp['r'] = 30;
	mp['a'] = 40;
	printf("%d\n", mp.size());
	return 0;
}

输出结果：

1
3

4. clear()

清空map中所有元素，复杂度为O(N)，其中N为map中元素的个数。样例代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
#include <iostream>
#include <map>
using namespace std;

int main(int argc, char** argv) {
	map<char, int> mp;
	mp['m'] = 20;
	mp['r'] = 30;
	mp['a'] = 40;
	mp.clear();
	printf("%d\n", mp.size());
	return 0;
}

输出结果：

1
0

queue容器详解

使用queue容器前需要#include <queue>并且加上一句 using namespace std; 即可

queue容器的定义

1
2
3
4
//通用定义
queue<typename> name;
//举个例子
queue<int> q;

queue容器内元素的访问

由于队列本身就是一种先进先出的限制性数据结构，因此在STL中只能通过front()来访问队首元素，或者back()来访问队尾元素。

样例代码

1
2
3
4
5
6
7
8
9
10
11
12
13
#include <iostream>
#include <queue>
using namespace std;

int main(int argc, char** argv) {
	queue<int> q;
	for(int i = 1; i <= 5; i++)
	{
		q.push(i);	//依次将1，2，3，4，5压入队列 
	}
	printf("%d %d\n", q.front(), q.back()) ;
	return 0;
}

输出结果：

1
1 5

queue常用函数

1. push()

push(x)将x压入队列，在上文已经有使用

2. front() back()

front()和back()分别可以获得队首元素和队尾元素，时间复杂度为O(1)，在上文已经有使用

3. pop()

pop()令队首元素出队，时间复杂度为O(1)。

代码示例：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include <iostream>
#include <queue>
using namespace std;

int main(int argc, char** argv) {
	queue<int> q;
	for(int i = 1; i <= 5; i++)
	{
		q.push(i);	//依次将1，2，3，4，5压入队列 
	}
	for(int i = 1; i <= 3; i++)
	{
		q.pop();	//出队首元素三此（依次为1，2，3） 
	}
	printf("%d\n", q.front()) ;
	return 0;
}

输出结果：

1
4

4. empty()

判断queue是否为空，返回ture则空，返回false则非空。时间复杂度为O(1)。

样例代码：

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
#include <iostream>
#include <queue>
using namespace std;

int main(int argc, char** argv) {
	queue<int> q;
	if(q.empty() == true)
	{
		printf("Empty\n");
	}
	else
	{
		printf("Not Empty\n");
	}
	q.push(1);
	if(q.empty() == true)
	{
		printf("Empty\n");
	}
	else
	{
		printf("Not Empty\n");
	}
	return 0;
}

输出结果：

1
2
Empty
Not Empty

5. size()

返回queue内元素的个数，时间复杂度为O(1)。

样例代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
#include <iostream>
#include <queue>
using namespace std;

int main(int argc, char** argv) {
	queue<int> q;
	for(int i = 1; i <= 5; i++)
	{
		q.push(i);	//依次将1，2，3，4，5压入队列 
	}
	printf("%d\n", q.size());
	return 0;
}

输出结果：

1
5

priority_queue容器详解

使用priority_queue容器前需要#include <queue>并且加上一句 using namespace std; 即可

priority_queue可以用来解决一些贪心问题，也可以对Dijkstra算法进行优化。

有一点需要注意，在使用top函数前，必须用empty()判断优先队列是否为空，否则可能因为队空而出现错误。

priority_queue容器的定义

1
2
3
4
//通用定义
priority_queue<typename> name;
//举个例子
priority_queue<int> q;

priority_queuer容器内元素的访问

和队列不一样，优先队列没有front()函数和back()函数，而只能通过通过top()函数来访问队首元素，也就是优先级最高的元素。

1
2
3
4
5
6
7
8
9
10
11
12
#include <iostream>
#include <queue>
using namespace std;

int main(int argc, char** argv) {
	priority_queue<int> q;
	q.push(3);
	q.push(4);
	q.push(1);
	printf("%d\n", q.top());
	return 0;
}

输出结果：

1
4

priority_queue常用函数

1. push()

同queue的用法，时间复杂度为O(logN)。

2. top()

获取队首元素，即堆顶元素，时间复杂度为O(1)。

3. pop()

pop()令队首元素出队，时间复杂度为O(logN)，同queue，在此不赘述。

4. empty()

检查队列是否非空，返回true则空，返回false则非空，时间复杂度为O(1)（同queue）

5. size()

size()返回优先队列内元素的个数，时间复杂度为O(1)，同queue。

priority_queue内元素优先级的设置

1. 基本数据类型的优先级设置

此处的基本数据类型就是int、double、char等数据类型（char通过字典序排序），以下两种优先队列是等价的（如果是double和char型，只需将int替换即可）：

1
2
priority_queue<int> q;
priority_queue<int, vector<int>, less<int>> q;

less表示数字大的优先级越大，greater表示数字小的优先级越大。

1
priority_queue<int, vector<int>, greater<int>> q;

代码实例

1
2
3
4
5
6
7
8
9
10
11
12
#include <iostream>
#include <queue>
using namespace std;

int main(int argc, char** argv) {
	priority_queue<int, vector<int>, greater<int> > q;	//两个>>之间可能需要用空格隔开，否则可能会被当成移位符
	q.push(3);
	q.push(4);
	q.push(1);
	printf("%d\n", q.top());
	return 0;
}

输出结果：

1
1

2. 结构体的优先级设置

现在希望水果的价格高的为优先级高，就需要重载（overload）小于号

代码示例：

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
#include <iostream>
#include <queue>
#include <string>
using namespace std;
struct fruit
{
	string name;
	int price;
	friend bool operator < (fruit f1, fruit f2)
	{
		return f1.price > f2.price;	//重载小于号 
	}
}f1, f2, f3; 
int main(int argc, char** argv) {
	priority_queue<fruit> q;
	f1.name = "桃子";
	f1.price = 3;
	f2.name = "梨子";
	f2.price = 4;
	f3.name = "苹果";
	f3.price = 1;
	q.push(f1);
	q.push(f2);
	q.push(f3);
	cout<< q.top().name << " " << q.top().price <<endl;
	return 0;
}

输出结果：

1
苹果 1

另一种写法，将cmp函数写在外面

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
#include <iostream>
#include <queue>
#include <string>
using namespace std;
struct fruit
{
	string name;
	int price;
	friend bool operator < (fruit f1, fruit f2)
	{
		return f1.price > f2.price;	//重载小于号 
	}
}f1, f2, f3; 
struct cmp{
	bool operator()(fruit f1, fruit f2){
		return f1.price > f2.price;
	}
};
int main(int argc, char** argv) {
	priority_queue<fruit, vector<fruit>, cmp> q;
	f1.name = "桃子";
	f1.price = 3;
	f2.name = "梨子";
	f2.price = 4;
	f3.name = "苹果";
	f3.price = 1;
	q.push(f1);
	q.push(f2);
	q.push(f3);
	cout<< q.top().name << " " << q.top().price <<endl;
	return 0;
}

输出同上。

如果结构体内的数据较为庞大（比如大的字符串或者数组），建议使用引用来提高效率。

1
2
3
4
5
6
7
8
9
struct fruit
{
	string name;
	int price;
	friend bool operator < (const fruit &f1, const fruit &f2)
	{
		return f1.price > f2.price;	//重载小于号 
	}
}f1, f2, f3;

Stack容器详解

使用stack容器前需要#include <stack>并且加上一句 using namespace std; 即可

stack容器的定义

1
2
3
4
//通用定义
stack<typename> name;
//举个例子
stack<int> st;

stack容器内元素的访问

由于栈是一种后进先出的数据结构，在STL的stack只能通过top()来访问栈顶元素。

样例代码：

1
2
3
4
5
6
7
8
9
10
11
12
#include <iostream>
#include <stack>
using namespace std;
int main(int argc, char** argv) {
	stack<int> st;
	for(int i = 1; i <= 5; i++)
	{
		st.push(i);	//依次将1，2，3，4，5压入栈 
	}
	printf("%d\n", st.top()) ;
	return 0;
}

输出结果：

1
5

stack常用函数

1. push()

同队列queue

2. top()

获得栈顶元素，时间复杂度为O(1)，上文已有使用。

3. pop()

同队列

4. empty()

同队列

5. size()

同队列

pair容器详解

要使用pair，应添加头文件#include<utility>（或者添加#include<map> ,由于map内部的实现设计pair，所以添加map头文件会自动添加pair头文件），再加上using namespace std;即可

pair的常见用途：

  • 用来替代二元结构体及其构造函数，节省编码时间
  • 作为map的键值对来进行插入 map.insert(pair)

pair容器的定义

1
2
3
4
//通用定义
pair<typeName1, typeName2> name;
//举个例子
pair<string, int> p;

pair容器的赋值和访问

样例代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
#include <iostream>
#include <utility>
using namespace std;
int main(int argc, char** argv) {
	pair<string, int> p;	//有三种赋值方式 
	p.first = "haha";	//分开赋值 
	p.second = 5;
	cout<< p.first << " " << p.second <<endl;
	p = make_pair("xixi", 55) ;	//使用自带的make_pair函数 
	cout<< p.first << " " << p.second <<endl;
	p = pair<string, int>("heihei", 555);	//使用类型定义赋值 
	cout << p.first << " " << p.second <<endl;
	return 0;
}

输出结果：

1
2
3
haha 5
xixi 55
heihei 555

pair比较操作数

两个pair类型数据可以直接使用==, !=, <, <=, >, >= 比较大小，比较规则是先以first的大小为标准，当first相等时才去判别second的大小。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include <iostream>
#include <utility>
using namespace std;
int main(int argc, char** argv) {
	pair<int, int> p1 (5, 10);
	pair<int, int> p2 (5, 15);
	pair<int, int> p3 (10, 5);
	if(p1 < p3){
		printf("p1 < p3\n");
	}
	if(p1 < p2){
		printf("p1 < p2\n");
	}
	return 0;
}

输出结果：

1
2
p1 < p3
p1 < p2

algorithm头文件下的常用函数

使用时需加入头文件#include <algorithm> ，并且using namespace std;即可

1. max(), min(), abs()

max(x, y)返回x和y中的较大值，参数必须是两个，如果需要比较三者可以max(x, max(y, z))，min同max。

abs(x)返回x的绝对值，x必须是整数，浮点值的绝对值可以使用math头文件下的fabs。

样例代码：

1
2
3
4
5
6
7
8
9
#include <iostream>
#include <algorithm>
using namespace std;
int main(int argc, char** argv) {
	int x = 1, y = -2;
	printf("%d %d\n", max(x, y), min(x, y));
	printf("%d %d\n", abs(x), abs(y));
	return 0;
}

输出结果：

1
2
1 -2
1 2

2. swap()

swap(x, y)交换x和y的值，x和y都是整形数

样例代码：

1
2
3
4
5
6
7
8
9
#include <iostream>
#include <algorithm>
using namespace std;
int main(int argc, char** argv) {
	int x = 1, y = -2;
	swap(x, y);
	printf("%d %d\n", x, y);
	return 0;
}

输出结果：

1
-2 1

3. reverse()

reverse(it, it2)可以将数组指针再[it, it2)之间的元素或容器的迭代器在[it, it2)范围内的元素进行反转。

数组反转示例：

1
2
3
4
5
6
7
8
9
10
11
12
#include <iostream>
#include <algorithm>
using namespace std;
int main(int argc, char** argv) {
	int a[6] = {10, 11, 12, 13, 14, 15};
	reverse(a, a+4);
	for(int i = 0; i < 6; i++)
	{
		printf("%d ", a[i]);
	}
	return 0;
}

输出结果：

1
13 12 11 10 14 15

容器反转示例：

1
2
3
4
5
6
7
8
9
#include <iostream>
#include <algorithm>
using namespace std;
int main(int argc, char** argv) {
	string str = "abcdefghi";
	reverse(str.begin() +2, str.begin() + 6);
	cout<<str<<endl;
	return 0;
}

输出结果：

1
abfedcghi

4. next_permutation()

给出序列在全排列中的下一个序列，例如n = 3的一个全排序为：123，132，213，231，312，321。

代码示例：

1
2
3
4
5
6
7
8
9
10
#include <iostream>
#include <algorithm>
using namespace std;
int main(int argc, char** argv) {
	int a[10] = {1, 2, 3};
	do{
		printf("%d%d%d\n", a[0], a[1], a[2]);
	}while(next_permutation(a, a+3));
	return 0;
}

输出结果

1
2
3
4
5
6
123
132
213
231
312
321

5. fill()

fill()可以把数组或容器中的某一段区间赋为某个相同的值，和memset不同（menset是按字节赋值，所以一般赋0或-1），如果对数组赋其他数字，一般用fill（但menset的执行速度更快）。

样例代码：

1
2
3
4
5
6
7
8
9
10
11
#include <iostream>
#include <algorithm>
using namespace std;
int main(int argc, char** argv) {
	int a[5] = {1, 2, 3, 4, 5};
	fill(a, a + 5, 111);	//将a[0]~a[4]均赋值为233
	for(int i = 0; i < 5; i++){
		printf("%d ", a[i]);
	} 
	return 0;
}

输出结果：

1
111 111 111 111 111

6. sort()

sort(首元素地址（必填），尾元素的下一个地址（必填），比较函数（可选） );

使用默认的 cmp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include <iostream>
#include <algorithm>
using namespace std;
int main(int argc, char** argv) {
	int a[6] = {9, 4, 2, 5, 6, -1};
	sort(a, a+4);
	for (int i = 0; i < 6; i++)
	{
		printf("%d ",a[i]);
	}
	printf("\n");
	sort(a, a+6);
	for (int i = 0; i < 6; i++)
	{
		printf("%d ",a[i]);
	}
	return 0;
}

输出结果：

1
2
2 4 5 9 6 -1
-1 2 4 5 6 9

自己实现cmp

1）基本数据类型

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <iostream>
#include <algorithm>
using namespace std;
bool cmp(int a, int b)
{
	return a > b;	//当a>b时将a放在b前面 
}
int main(int argc, char** argv) {
	int a[6] = {9, 4, 2, 5, 6, -1};
	sort(a, a+6);
	for (int i = 0; i < 6; i++)
	{
		printf("%d ",a[i]);
	}
	printf("\n");
	sort(a, a+6, cmp);
	for (int i = 0; i < 6; i++)
	{
		printf("%d ",a[i]);
	}
	return 0;
}

输出结果：

1
2
-1 2 4 5 6 9
9 6 5 4 2 -1

2）结构体

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
#include <iostream>
#include <algorithm>
using namespace std;
struct node{
	int x,y;
};
bool cmp(node a, node b)
{
	return a.x > b.x;	//按照x值进行降序排序 
}
int main(int argc, char** argv) {
	node ssd[10];
	ssd[0].x = 2;	//(2,2)
	ssd[0].y = 2;
	ssd[1].x = 1;	//(1,3)
	ssd[1].y = 3;
	ssd[2].x = 3;	//(3,1)
	ssd[2].y = 1;
	sort(ssd, ssd + 3, cmp);
	for (int i = 0; i < 3; i++)
	{
		printf("%d %d\n",ssd[i].x,ssd[i].y);
	}
	return 0;
}

输出结果：

1
2
3
3 1
2 2
1 3

如果想按x降序排序，但是当x相等时，按y的大小升序排序，cmp函数可以按如下写法：

1
2
3
4
5
bool cmp(node a, node b)
{
    if(a.x != b.x) return a.x > b.x;	//按照x值进行降序排序 
	else return a.y < b.y;	//按照y值进行升序排序 
}

结构体还可以通过重载运算符实现

1
2
3
4
friend bool operator < (fruit f1, fruit f2)
{
	return f1.price > f2.price;	//重载小于号 
}

3）容器的排序

在STL标准容器中，只有vector、string、deque时可以使用sort的。因为像set、map这种容器是用红黑树实现的，元素本身有序，不允许使用sort排序。

样例代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
bool cmp(int a, int b)
{
	return a > b;	//降序排序 
}
int main(int argc, char** argv) {
	vector<int> vi;
	vi.push_back(3);
	vi.push_back(1);
	vi.push_back(2);
	sort(vi.begin(), vi.end(), cmp);
	for (int i = 0; i < 3; i++)
	{
		printf("%d ", vi[i]);
	}
	return 0;
}

输出结果：

1
3 2 1

7. lower_bound()和upper_bound()

lower_bound()和upper_bound()需要用在一个有序的数组或者容器中。

lower_bound(first, last, val)用来寻找在数组或者容器中在[fisrt, last)范围内第一个值大于等于val的元素的位置，如果是数组，则返回该位置的指针；如果是容器，则返回该位置的迭代器。

upper_bound(first, last, val)用来寻找在数组或者容器中在[fisrt, last)范围内第一个值大于val的元素的位置，如果是数组，则返回该位置的指针；如果是容器，则返回该位置的迭代器。

（如果需要小于可以最后添加一个 greater<int>() 参数，对于结构体可以自定义cmp函数）

1
2
3
4
5
6
7
8
9
10
#include <iostream>
#include <algorithm>
using namespace std;
int main(int argc, char** argv) {
	int a[10] = {1,2,2,3,3,3,5,5,5,5};
	int * lowerPos = lower_bound(a, a+10, 3);
	int * upperPos = upper_bound(a, a+10, 3);
	printf("%d %d\n", lowerPos - a, upperPos - a);
	return 0;
}

输出结果：

1
3 6