为蓝桥杯而来-STL

STL二次学习

列表

vector//变长数组，空间扩容时倍增
string//字符串，substr返回字串，c_str()返回字符数组的头指针
queue//队列push（）队尾插入，front（）返回对头元素，pop（）把对头元素弹出，back（）返回队尾
priority_queue//优先队列，一种堆，push（)往堆中插入元素，top（）返回堆顶，pop（）把堆顶弹出
stack//栈，push（）往栈顶添加元素，top（）返回栈顶元素，pop（）弹出栈顶元素
deque//双端队列，对头队尾都可以插入弹出，支持随机访问
set,map,multiset,multimap//基于红黑树，平衡二叉树的一种，本质上是动态维护有序序列
unordered_set,unordered_map,unordered_multiset,unordered_multimap//基于哈希表实现
bitset//位存储，压位

系统为某一程序分配空间时，所需时间与空间大小无关，与申请次数有关

vector

#define _CRT_SECURE_NO_WARNINGS 1
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>

using namespace std;

int main()
{
	int n = 10;
	int m = 3;
	//vector初始化
	vector<int> a;//1
	vector<int> a(n);//2.特定长度
	vector<int> a(n, m);//3,特定长度且数组内每个元素为特定值
	vector<int> a[10];//4,定义vector类型数组
	//函数
	int k = a.size();//返回a数组的元素个数
	k = a.empty();//返回布尔值，判断是否为空	
	//size和empty是所有STL通用的函数，时间复杂度为O（1）
	a.clear();//清空vector,除了队列以外都能用
	k = a.front();//返回vector的第一个数
	k = a.back();//返回vector的最后一个数
	a.push_back(k);//向vector的最后插入一个数
	a.pop_back();//删除vector的最后一个数
	k = a.begin();//返回vector数组的第0个数
	k = a.end();//返回vector数组的最后一个数的后面一个数

	return 0;
}

代码示范

#define _CRT_SECURE_NO_WARNINGS 1
#include <iostream>
#include <vector>

using namespace std;

int main()
{
	vector<int> a;

	for (int i = 0;i < 10;++i) a.push_back(i);

	for (int i = 0;i < a.size();++i) cout << a[i]<<' ';
	cout << endl;

	//迭代器可以看作指针
	for (vector<int>::iterator i = a.begin(); i != a.end();++i) cout << *i << ' ';
	cout << endl;

	//auto遍历
	for (auto x : a) cout << x << ' ';
	cout << endl;
	return 0;
}

vector支持比较运算，按字典序比较

#include <iostream>
#include <vector>

using namespace std;

int main()
{
    vector<int> a(4, 3);//4个3
    vector<int> b(3, 4);//3个4

    printf("%d\n",a < b);//返回布尔值

    return 0;
}

pair

存储二元组

#define _CRT_SECURE_NO_WARNINGS 1
#include <iostream>
#include <cstring>
#include <vector>

using namespace std;

int main()
{
	pair<int, string> p;

	//构造pair数组
	p = make_pair(10, "abc");
	p = { 20,"abc" };//C++11

	int k = p.first;//取得pair数组的第一个元素
	string s = p.second;//取得pair数组的第二个元素

	//套娃式，能定义一个对象有多个属性
	pair<int, pair<int, int>> pp;
}

也能够支持比较运算，按字典序比较，以first为第一关键字，second为第二关键字

string

#define _CRT_SECURE_NO_WARNINGS 1
#include <iostream>
#include <string>

using namespace std;

int main()
{
	//定义
	string s = "abc";
	s += "def";//可以直接加字符串;
	s += 'g';//可以直接加字符
	//但要注意操作符两边必须有一个是string字符串
	
	//操作 
	//支持三种操作，size，empty，clear
	cout << s.substr(0, 3) << endl;//substr返回字串
	cout << s.substr(0, 100)<<endl;//长度超了不会报错，返回的是到字符串结束为止
	cout << s.substr(0)<<endl;//返回从特定下标到结束的字符串

	printf("%s", s.c_str());//直接用s会有问题，用c_str()返回起始地址就可以解决
}

substr的第二个参数代表长度

queue

#define _CRT_SECURE_NO_WARNINGS 1
#include <iostream>
#include <queue>

using namespace std;

int main()
{
	queue <int> q;

	for (int i = 0;i < 10;++i) q.push(i);//从队尾插入元素

	for (int i = 0; i < 10;++i)
	{
		cout << q.front() << ' ';//返回队头元素
		q.pop();//弹出队头元素
	}
	cout << endl;

	for (int i = 0;i < 10;++i) q.push(i);
	cout<<q.back()<<endl;//返回队尾元素

	q = queue<int>();//清空队列
}

queue没有clear函数

priority_queue

优先队列，即堆,默认大根堆

#define _CRT_SECURE_NO_WARNINGS 1
#include <iostream>
#include <queue>

using namespace std;

int main()
{
	//定义堆，堆的好处之一就是插入的时候就相当于排序了一次
	priority_queue<int> pq;//默认大根堆.由大到小排序

	for (int i = 0;i <= 10;++i) pq.push(i);//向堆中插入元素

	for (int i = 0;i < 10;++i)
	{
		cout << pq.top()<<' ';//返回堆顶元素
		pq.pop();//弹出堆顶元素
	}

	return 0;
}

改成小根堆的两种方法

变号法

#define _CRT_SECURE_NO_WARNINGS 1
#include <iostream>
#include <queue>

using namespace std;

int main()
{
	priority_queue<int> pq;//默认大根堆.由大到小排序

	//改成小根堆的方法，插入一个数时，改成插入一个负数
	for (int i = 10;i >= 0;--i) pq.push(-i);

	for (int i = 0;i < 10;++i)
	{
		cout << -pq.top()<<' ';//输出时再变号
		pq.pop();
	}

	return 0;
}

定义法

#define _CRT_SECURE_NO_WARNINGS 1
#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>

using namespace std;

int main()
{
	priority_queue<int, vector<int>, greater<int>> heap;//得到小根堆

	for (int i = 10;i >= 0;--i) heap.push(i);

	for (int i = 0;i < 10;++i)
	{
		cout << heap.top() << ' ';
		heap.pop();
	}

	return 0;
}

stack

栈

#define _CRT_SECURE_NO_WARNINGS 1
#include <iostream>
#include <stack>

using namespace std;

int main()
{
	stack<int> s;

	for (int i = 0;i < 10;++i) s.push(i);//向栈顶插入元素

	for (int i = 0;i < 10;++i)
	{
		cout << s.top() << ' ';//返回栈顶元素
		s.pop();//弹出栈顶元素
	}

	return 0;

}

deque

双端队列，加强版vector

#define _CRT_SECURE_NO_WARNINGS 1
#include <iostream>
#include <deque>

using namespace std;

int main()
{
	deque<int> q;

	//操作
	int k = q.size();
	k = q.empty();//返回布尔值
	q.clear();

	k = q.front();//返回第一个元素
	k = q.back();//返回最后一个元素
	q.push_back(k);//在最后一个位置插入元素
	q.pop_back();//删除最后一个元素
	q.push_front(k);//向队头插入一个元素
	q.pop_front(k);//弹出队头元素
	//支持随机寻址，还有begin和end迭代器
	//速度很慢
}

set/multiset

set定义数组不允许出现重复元素，如果出现就会忽略掉

multiset是可以有重复元素的

所有set操作的时间复杂度都为logN

#define _CRT_SECURE_NO_WARNINGS 1
#include <iostream>
#include <set>

using namespace std;

int main()
{
	set<int> s;//不能有重复元素
	multiset <int> Ms;//可以有重复元素

	//操作
	for (int i = 0;i < 10;++i) s.insert(i);	 

	cout << *s.find(2) << endl;//不存在则返回end迭代器,否则返回他的位置地址

	cout << s.count(1) << endl;//返回某个数的个数,set只会返回0和1，multiset返回他的个数

	s.erase(1);//如果参数是一个数，则删除所有等于这个数的节点
	//时间复杂度为 O（k + logN）k,为这个数的个数
	set<int>::iterator i = s.end();
	s.erase(i);//如果参数是一个迭代器，则删除该位置的节点

	//核心操作
	int x = 1;
	i = s.lower_bound(x);//返回数组中第一个大于或等于被查数的值的迭代器
	i = s.upper_bound(x);//返回数组中第一个大于被查数的值的迭代器

	return 0;
}

迭代器里两个名词的意思

前驱：前面的一个数
后继：后面一个数

map/multimap

map存储的是一种映射关系

同样可以用insert和erase

insert可以用pair插入

erase的参数可以是pair也可以是迭代器

find操作也和set一样

set操作能做的map大多都能做

实用操作，可以让任意类型作为下标，(时间复杂度为O（logN）)

#define _CRT_SECURE_NO_WARNINGS 1
#include <iostream>
#include <map>

using namespace std;

int main()
{
	map<string, int> a;//讲string 映射成整数

	a["abc"] = 1;

	cout << a["abc"] << endl;

	return 0;
}

unordered

优化set/multiset和map/multimap的时间复杂度，基于哈希表，使大多数操作的时间复杂度都为O（1）

但不支持lower_bound和upper_bound

，也不支持迭代器相关的操作

bitset

可以比正常的内存占用省掉八倍

c++中布尔数组为1字节，1024个字节也就是1kb内存

如果用bitset压位的话，让布尔数组每一个位都能被充分利用，那么就只需128个字节

bitset也支持位运算操作，也支持count操作