算法笔记 [C++标准模板库(STL)介绍]

程序员文章站 2022-07-12 17:59:54

...

6.1 vector的常见用法详解

Vector 向量变长数组以邻接表的方式存储图

可以通过下标或者通过迭代器的方法访问
begin()函数取首元素地址，end() 函数取尾元素地址的下一个地址

两种遍历方法

通过下标访问
通过迭代器访问

STL中只有 vector 和 string 中允许使用vi.begin()+n(n为整数)这种写法

常用方法:

push_back() 时间复杂度为O(1)
pop_back() 时间复杂度为O(1)
size() 时间复杂度为O(1) 返回类型为 unsigned int
clear() 时间复杂度为O(N)
insert(it, x) 向任意迭代器it处插入一个元素 x 时间复杂度为O(N)
erase() 1️⃣ 删除单个元素 2️⃣删除一个区间的元素时间复杂度均为O(N)
1. erase(it) 删除迭代器为 it 处的元素
2. erase(first, last) 删除[first, last)内的所有元素

删除所有元素即为 vi.erase(vi.begin(), vi.end()) 也即 vi.clear()

#include <cstdio>
#include <vector> 
using namespace std;
int main()
{
	vector<int> vi;
	for(int i=1; i<=5; i++) 
	{
		vi.push_back(i);
	}
	vi.insert(vi.begin()+2, -1);
	vector<int>::iterator it = vi.begin();
	for(int i=0; i<5; i++)
	{
		printf("%d ", *(it+i));
	}
	printf("\n");
	for(int i=0; i<vi.size(); i++)
	{
		printf("%d ", vi[i]);
	}
	printf("\n");
	for(vector<int>::iterator it=vi.begin(); it!=vi.end(); it++)
	{
		printf("%d ", *it);
	}
	vi.clear();
	printf("%d\n", vi.size());
    return 0;
}

6.2 set的常见用法详解

内部自动有序且不含重复元素，set 只能通过迭代器访问

常用函数：

insert(x) 将 x 插入到 set 容器中，并自动递增和去重，时间复杂度为 O(logN)
find(value) 返回 set 中对应值为 value 的迭代器，时间复杂度为 O(logN)
erase() 1️⃣删除单个元素 2️⃣删除一个区间内的所有元素

3.1 erase(it) it为所要删除元素的迭代器，时间复杂度为 O(1)

3.2 erase(value) value为所要删除元素的值，时间复杂度为 O(logN)

3.3 erase(first, last) 时间复杂度为 O(last-first)
size() 时间复杂度为 O(1)
clear() 时间复杂度为 O(N)

用途：自动去重并按照升序排列，处理不唯一的情况需要使用 multiset unordered_set用来处理只去重不排序的需求

#include <cstdio>
#include <set>
using namespace std;
int main()
{
	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);
	}
	printf("\n");
	
	set<int>::iterator it = st.find(2);
	printf("%d\n", *it);
	
	st.erase(it);
	for(set<int>::iterator it=st.begin(); it!=st.end(); it++)
	{
		printf("%d ", *it);
	}
	printf("\n");
	
    return 0;
}

6.3 string的常见用法详解

常用函数

通过下标访问，输入输出使用 cin 和 cout
字典序比较

6.4 map的常见用法详解

字符串必须使用 string 而不能使用 char数组
map 中的键是唯一的，可以通过下标(键)直接进行访问得到
使用 it->first 访问键，使用 it->second 访问值
map 会以键大小从小到大的顺序自动排序(红黑树)

常用函数

find(key) 返回键为 key的迭代器，时间复杂度为 O(logN)
erase()

2.1 erase(it) it为要删除元素的迭代器，时间复杂度为 O(1)

2.2 erase(key) key为要删除元素的键,时间复杂度为 O(logN)

2.3 erase(first, last) 删除区间内所有元素，时间复杂度为 O(last-first)

size() 时间复杂度为 O(1)
clear() 时间复杂度为 O(N)

常见用途:

建立字符串与整数之间映射
判断大整数或其他类型的数据是否存在，把 map 当做 bool 数组使用
字符串和字符串的映射

map 的键和值是唯一的，一个键对应多个值需要使用 multimap
unordered_map使用散列代替红黑树实现来处理只映射不按照 key 排序的需求。

#include <iostream>
#include <string>
#include <map>
using namespace std;
int main()
{
	map<char, int> mp;
	mp['c'] = 20;
	mp['c'] = 30; // 20被覆盖
	printf("%d\n", mp['c']);
	mp.erase('c');
	
	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);
	}
	mp.clear();
	
	mp['a'] = 1;
	mp['b'] = 2;
	mp['c'] = 3;
	map<char, int>::iterator it = mp.find('b');
	printf("%c %d\n", it->first, it->second);
	 
    return 0;
}

6.5 queue的常见用法详解

front()访问队首元素，back() 访问队尾元素

常用函数：

push() 时间复杂度为 O(1)
front() back() 时间复杂度为 O(1)
pop() 队首元素出队时间复杂度为 O(1)
empty() 时间复杂度为 O(1)
size() 时间复杂度为 O(1) 时间复杂度为 O(1)

常见用途

广度优先搜素

在使用 front() 和 back() 之前必须使用 empty() 判断队列是否为空
双端队列(deque) 收尾皆可插入和删除的队列
优先队列(priority_queue) 默认将当前队列最大元素至于队首的容器

#include <iostream>
#include <queue>
using namespace std;
int main()
{  
	queue<int> q;
	for(int i=1; i<=5; i++)
	{
		q.push(i);
	}
	printf("%d %d\n", q.front(), q.back());
	
	q = queue<int>();
	for(int i=1; i<=5; i++)
	{
		q.push(i);
	}
	for(int i=1; i<=3; i++)
	{
		q.pop();
	}
	printf("%d\n", q.front());
	
	if(q.empty() == true)
	{
		printf("Empty\n");
	}
	else
	{
		printf("NotEmpty\n");
	}
	printf("元素个数%d\n", q.size());
	
    return 0;
}

6.6 priority_queue的常见用法详解

优先队列
底层使用堆实现队首元素是当前队列中优先级最高的那一个。
只能通过 top() 函数访问队首元素(堆顶元素) 优先级最高的元素。

常用函数:

push() 入队时间复杂度为 O(logN)
top() 获取队首元素(堆顶元素) 时间复杂度为 O(1)
pop() 队首元素出队时间复杂度为 O(logN)
empty() 时间复杂度为 O(1)
size() 时间复杂度为 O(1)

优先级设置问题：

对于基本的数据类型，优先级一般是数字大的优先级越高，队首元素就是优先队列内元素最大的那个。

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

以上两个定义等价。

less<int> 表示对第一个参数的比较类，数字大的优先级越大

// 优先队列将最小的元素放在队首
priority_queue<int, vector<int>, greater<int> > q;

6.7 stack的常见用法详解

常用函数：

push() 入栈时间复杂度为 O(1)
top() 取栈顶元素时间复杂度为 O(1)
pop() 弹出栈顶元素时间复杂度为 O(1) 不保留值
empty() 时间复杂度为 O(1)
size() 时间复杂度为 O(1)

#include <cstdio>
#include <stack>
using namespace std;
int main()
{
	stack<int> st;
	for(int i=1; i<=5; i++)
	{
		st.push(i);
	}
	for(int i=1; i<=3; i++)
	{
		st.pop();
	}
	printf("%d\n", st.top());
	
	if(st.empty() == true)
	{
		printf("Empty\n");
	}
	else
	{
		printf("Not Empty\n");
	}
	
	printf("元素个数%d\n", st.size());
    return 0;
}

6.8 pair的常见用法详解

将两个元素绑定在一起作为一个合成元素，可以看成一个内部有两个元素的结构体。两个元素分别为 first 和 second

struct pair
{
	typeName1 first;
	typeName2 last;
}

头文件为 <utility> 或者直接 #include <map>

临时构建一个 pair

pair<string, int>("haha", 5) 类型定义写在前面，后面加上两个元素
make_pair("haha", 5)

两个 pair 类型的数据可以直接使用 == != > < >= <= 比较大小，以 first大小为标准，当 first 相等时才比较second

用途：

作为二元结构体及其构造函数，节省编码时间
作为 map 的键值对来进行插入

#include <iostream>
#include <string>
#include <map>
using namespace std;
int main()
{
	pair<string, int> p;
	p.first = "haha";
	p.second = 5;
	cout << p.first << " " << p.second <<endl;
	p = make_pair("xixi", 55);
	cout << p.first << " " << p.second <<endl;
	p = pair<string, int>("heihei", 555);
	cout << p.first << " " << p.second << endl;
	
	map<string, int> mp;
	mp.insert(make_pair("heihei", 5));
	mp.insert(pair<string, int>("haha", 10));
	for(map<string, int>::iterator it=mp.begin(); it!=mp.end(); it++)
	{
		cout << it->first << " " << it->second <<endl;
	}
    return 0;
}

6.9 `algorithm` 头文件下的常用函数

6.9.1 `max()`、`min()`、`abs()`

max(x, y) min(x, y) 参数必须是两个，abs(x) 得到 x 的绝对值，此时的 x 必须是整数；浮点数的绝对值需要使用 math 头文件下的 fabs

6.9.2 `swap`

交换 x 和 y 的值。

6.9.3 `reverse()`

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

#include <iostream>
#include <algorithm>
using namespace std;

int main()
{
	int a[10] = {10, 11, 12, 13, 14, 15};
	reverse(a, a+4);
	for(int i=0; i<6; i++)
	{
		printf("%d\n", a[i]);
	}
	return 0;
}

6.9.4 `next_permutation()`

给出一个序列在全排列中的下一个序列

#include <iostream>
#include <algorithm>
using namespace std;

int main()
{
	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;
}

6.9.5 `fill()`

将数组或容器中的某一段区间赋为某个相同的值，这里的赋值可以是数组类型对应=范围中的任意值

#include <iostream>
#include <algorithm>
using namespace std;

int main()
{
	int a[5] = {1, 2, 3, 4, 5};
	fill(a, a+5, 233);
	for(int i=0; i<5; i++)
	{
		printf("%d ", a[i]);
	}
	return 0;
}

6.9.6 `sort()`

1.使用 sort 排序

sort(首元素地址(必填), 尾元素地址的下一个地址(必填), 比较函数(非必填))

不填写比较函数会默认对前面给出的区间进行递增排序。

#include <stdio.h>
#include <algorithm>
using namespace std;
int main()
{
	int a[6] = {9, 4, 2, 5, 6, -1};
	// 将 a[0]~a[3] 从小到大排序
	sort(a, a+4);
	for(int i=0; i<6; i++)
	{
		printf("%d ", a[i]);
	} 
	printf("\n");
	// 将 a[0] - a[5] 从小到大排序
	sort(a, a+6) ;
	for(int i=0; i<6; i++)
	{
		printf("%d ", a[i]);
	} 
	printf("\n");
	return 0;
}

double 类型的排序：

#include <stdio.h> 
#include <algorithm>
using namespace std;
int main()
{
	double a[] = {1.4, -2.1, 9};
	sort(a, a+3);
	for(int i=0; i<3; i++)
	{
		printf("%.1f ", a[i]);
	}
	printf("\n");
	return 0;
}

char 类型默认的顺序是字典序。

#include <stdio.h> 
#include <algorithm>
using namespace std;
int main()
{
	char c[] = {'T', 'W', 'A', 'K'};
	sort(c, c+4);
	for(int i=0; i<4; i++)
	{
		printf("%c", c[i]);
	}
	printf("\n");
	return 0;
}

2.如何实现比较函数 cmp

默认是按照从小到大的顺序来实现的，如果想要让元素大小的关系反过来，重写 cmp 函数：

bool cmp(int a, int b)
{
	return a > b; // a 大于 b 时将 a 放在 b 的前面
}

调用函数 sort(a, a+4, cmp) 使用重写的 cmp函数作为排序的规则进行排序。

记忆方法，要把数据从小到大排列，就使用 <，因为 a<b 就是左小右大；如果要把数据从大到小排列，就使用 > ,因为 a>b 就是左大右小。

结构体数组排序

struct node
{
	int x;
	int y;
}ssd[10];

bool cmp(node a, node b)
{
	return a.x > b.x;
}

二级排序：先按照 x 从大到小进行排序，当 x 相等的情况下，按照 y 的大小从小到大来排序。

bool cmp(node a, node b)
{
	if(a.x != b.x) return a.x>b.x;
	else return a.y < b.y;
}

容器的排序：在 STL 标准容器中，只有 vector string deque 是可以使用 sort 的。

vector 排序重写 cmp 函数时使用的是容器中承载的类型

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

// vector 中的元素为int，因此还是 int 的比较 
bool cmp(int a, int b)
{
	return a > b;
}

int main()
{
	vector<int> v1;
	v1.push_back(3) ;
	v1.push_back(1);
	v1.push_back(2);
	sort(v1.begin(), v1.end(), cmp);
	for(int i=0; i<3; i++)
	{
		printf("%d\n", v1[i]);
	}
	return 0;
}

默认是按照字典序进行排序

#include <iostream>
#include <string>
#include <algorithm>
using namespace std;

int main()
{
	string str[3] = {"bbbb", "cc", "aaa"};
	sort(str, str+3);
	for(int i=0; i<3; i++)
	{
		cout << str[i] << endl;
	}
	return 0;
}

按照字符串的长度进行排序

#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
bool cmp(string str1, string str2)
{
	return str1.length() > str2.length();
}
int main()
{
	string str[3] = {"bbbb", "cc", "aaa"};
	sort(str, str+3, cmp);
	for(int i=0; i<3; i++)
	{
		cout << str[i] << endl;
	}
	return 0;
}

算法笔记 [C++标准模板库(STL)介绍]

6.1 vector的常见用法详解

6.2 set的常见用法详解

6.3 string的常见用法详解

6.4 map的常见用法详解

6.5 queue的常见用法详解

6.6 priority_queue的常见用法详解

6.7 stack的常见用法详解

6.8 pair的常见用法详解

6.9 `algorithm` 头文件下的常用函数

6.9.1 `max()`、`min()`、`abs()`

6.9.2 `swap`

6.9.3 `reverse()`

6.9.4 `next_permutation()`

6.9.5 `fill()`

6.9.6 `sort()`

6.9.7 `lower_bound()` 和 `upper_bound()`

C++标准库和标准模板库介绍

C++标准库笔记：算法--min/max/swap/iter_swap

C++之标准模板库STL续（容器，算法）

C++ STL标准模板库（list）

[算法笔记]C++标准模板库（STL）（3）map

C++ STL标准模板库

C++之标准模板库STL