[C++]常见的STL使用

C C C++中的常见的 S T L STL STL使用

文章目录

  ~   一、 S T L STL STL基本介绍
  ~   二、栈 s t a c k stack stack
  ~   三、变长数组 v e c t o r vector vector
  ~   四、队列 q u e u e queue queue
  ~   五、优先队列 p r i o r i t y _ q u e u e priority_queue priority_queue
  ~   六、有序集合 s e t set set
  ~   七、映射 m a p map map
  ~   八、位图 b i t s e t bitset bitset
  ~   九、算法 a l g o r i t h m algorithm algorithm

一、 S T L STL STL基本介绍

S T L STL STL即 S t a n d a r d   T e m p l a t e   L i b r a r y Standard ~Template~ Library Standard Template Library，标准模板库。

狭义来说，提供了一些已经实现的数据结构。

其核心在于 c o n t a i n e r container container（容器）、 i t e r a t o r iterator iterator（迭代器）和 a l g o r i t h m algorithm algorithm（算法）。

• 容器，就是存储数据的一种数据结构。
• 迭代器，就是 S T L STL STL容器的指针。
  

二、栈 s t a c k stack stack 1.头文件与声明

• 头文件

#include

• 声明

stack sta; //声明一个数据类型为int的栈。

stack中的数据类型也可以是结构体或者类。

其余的容器同理，不逐一列举。

2.支持的操作

操作	用法
push	入栈
pop	出栈
top	获得栈顶元素
empty	判断栈是否为空
size	获取栈的大小
emplace	入栈（可自动调构造函数）
swap	栈的交换

3.操作示例

• emplace操作

所谓的emplace基本上与push类似。

所不同的，emplace可以自己调用构造函数构造对应的数据类型。

如下示例：

#include
#include
using namespace std;

class Data
{
    friend ostream& operator<<(ostream& cout, const Data d);
    int x, y;
public:
    Data(int x, int y) { this->x = x, this->y = y; }
};

ostream& operator<<(ostream& cout, const Data d)
{
    cout << "x = " << d.x << endl;
    cout << "y = " << d.y << endl;
    return cout;
}
stack sta; //声明一个数据类型为Data类的栈

int main()
{
    sta.emplace (1, 2);
    auto t = sta.top();
    cout << t;

    return 0;
}

• swap操作

#include
#include
using namespace std;

stack a, b;

int main()
{
    a.push(1);
    b.push(2);

    a.swap(b); //把栈a,b交换

    cout << a.top() << endl; //输出为2
    return 0;
}

4.遍历方法

注意：stack没有迭代器，无法使用迭代器遍历！

遍历方法如下：

    stack a; 

    while (a.size())
    {
        auto t = a.top();
        cout << t << " ";
        a.pop();
    }

三、变长数组 v e c t o r vector vector 1.头文件与声明

• 头文件

#include

• 声明

vector a;  //声明了一个长度动态变化的int数组

2.支持的操作

操作	用法
push_back	插入
pop_back	删除数组最后一个元素
clear	清空
empty	判断数组是否为空
size	获取数组的大小
emplace_back	插入（可自动调构造函数）
swap	数组的交换
front/back	返回第一个元素/最后一个元素
begin/end	指向第一个元素/最后一个元素的后一个位置的迭代器
下标访问	像数组一样访问元素

3.操作示例

• 下标访问

    vector a;
    for (int i = 0; i < 4; i++)
    {
        int x;
        cin >> x;
        a.push_back(x);
    }

    for (int i = 0; i < 4; i++)
        cout << a[i] << " ";  //像数组一样通过下标访问

• 迭代器

vector支持迭代器。

vector::iterator it; //声明一个数据类型为int的vector的迭代器

4.遍历方法 （1）下标遍历

• 示例：

    vector a;
    for (int i = 0; i < 4; i++)
    {
        int x;
        cin >> x;
        a.push_back(x);
    }
    //下标遍历
    for (int i = 0; i < a.size(); i++)
        cout << a[i] << " ";

（2）迭代器遍历

• 示例：

   //迭代器遍历
for (vector::iterator it = a.begin(); it ！= a.end(); it++)
    cout << *it << " ";

C C C++ 11 11 11支持auto关键字自动推断变量类型。

利用auto关键字，可以简化为：

for (auto it = a.begin(); it ！= a.end(); it++)
    cout << *it << " ";

（3）区间遍历

//区间遍历数据类型为int的vector
for (int x : a)
	cout << x << " ";

同理，利用auto关键字也可以改写为：

//区间遍历
for (auto x : a)
	cout << x << " ";

四、队列 q u e u e queue queue 1.头文件与声明

• 头文件

#include  //包含queue和priority_queue

• 声明

queue q; //声明一个数据类型为int的队列

2.支持的操作

操作	用法
push/pop	入队/出队
front/back	获取队头/队尾元素
empty	判断队列是否为空
size	获取队列长度
emplace	入队（可自动调用构造函数）
swap	交换

3.遍历方式

queue也无迭代器，其遍历与stack的遍历类似。

五、优先队列 p r i o r i t y _ q u e u e priority_queue priority_queue

优先队列本质上就是一个大根堆。

较大的元素默认会放在堆顶。

1.头文件与声明

• 头文件

#include //包含了queue和priority_queue

• 声明

priority_queue heap; //声明了一个数据类型为int的堆

2.支持的操作

基本上与queue的操作一样。略。

3.重载<运算符

priority_queue中的元素必须定义<，较大的元素会被放在堆顶。

内置的string、int本身可以比较大小，自定义的数据需要重载<。

#include
#include
using namespace std;

struct dot
{
	int x, y;  //横、纵坐标
	dot(int a, int b)
	{
		x = a; y = b;
	}
};

//重载:按照点的坐标之和的大小定义<
bool operator<(const dot& a, const dot& b)
{
	return a.x + a.y < b.x + b.y;
}

priority_queue heap; //定义数据类型为dot的堆

int main()
{
	for (int i = 0; i < 3; i++)
	{
		int x, y;
		cin >> x >> y;

		heap.push(dot(x, y));
	}
	
	while (heap.size())
	{
		auto t = heap.top();
		cout << t.x << " " << t.y << endl;

		heap.pop();
	}
	return 0;
}

4.小根堆的定义

priority_queue, greater> heap; //数据类型int的小根堆

第一个参数是堆的数据类型，第二个参数是堆的容器，第三个参数是堆的排序方式。

greater是与正常定义<相反的排序方式。

5.遍历方式

priority_queue也无迭代器，其遍历与stack的遍历类似。

六、有序集合 s e t set set 1.头文件与声明

• 头文件

#include

• 声明

set S; //声明数据类型为int的set

由于set是有序集合，若自定义数据类型先要重载<。

2.支持的操作

操作	用法	时间复杂度
insert	插入	O ( n l o g n ) O(nlogn) O(nlogn)
begin/end	首/尾迭代器	O ( 1 ) O(1) O(1)
S.find(x)	查找 S S S中 x x x所在的位置，返回迭代器(无则返回end)	O ( l o g n ) O(logn) O(logn)
S.lower_bound(x)	查找 S S S中 ≥   x geq~x ≥ x元素中最小的一个，返回迭代器	O ( l o g n ) O(logn) O(logn)
S.upper_bound(x)	查找 S S S中 >   x >~x > x元素中最小的一个，返回迭代器	O ( l o g n ) O(logn) O(logn)
erase()	删除元素或者迭代器指向的元素	O ( l o g n [ + k ] ) O(logn[+k]) O(logn[+k])
count	统计元素出现的次数	O ( l o g n + k ) O(logn+k) O(logn+k)

• find操作

返回指向这个元素的迭代器，若无此元素返回S.end。

set::iterator it = S.find(x);

• erase操作

（1）如果是迭代器，删除迭代器指向的元素；

（2）如果是元素，删除所有对应的元素。

//设it是一个迭代器
S.erase(it);   //删除it指向的元素
//设x是一个元素
S.erase(x);    //删除所有等于x的元素

3.操作示例

数据类型为自定义类型dot的set：

#include
#include
using namespace std;

struct dot
{
	dot(int x, int y)
	{
		this->x = x, this->y = y;
	}
	int x, y;
};
//必须重载<
bool operator < (const dot& a, const dot& b)
{
	return a.x * a.y < b.x* b.y;
}

int main()
{
	set S;

	for (int i = 0; i < 3; i++)
	{
		int x, y;
		cin >> x >> y;

		S.emplace(x, y); //自动调用构造函数
	}

	for (auto t : S)
		cout << t.x << " " << t.y << endl;

	return 0;
}

4.遍历方式

可采用迭代器遍历和区间遍历。

七、映射 m a p map map

m a p map map容器是一个键值对 k e y − v a l u e key-value key−value的映射，其内部实现一棵以 k e y key key为关键码的红黑树。

k e y key key中必须定义<。

1.头文件与声明

• 头文件

#include

• 声明

map M;

2.支持的操作

操作	用法
M.insert(p)	插入一个映射p，p是一个pair
erase	删除
M.find(x)	查找 M M M中 k e y key key为 x x x的二元组，返回迭代器
[]	返回 k e y key key映射到 v a l u e value value的引用，若不存在自动创建零值
size	返回映射的大小
empty	返回映射是否为空
clear	清空映射
begin/end	首/尾迭代器

3.操作示例

• insert操作

map M; //创建一个map
pair t = make_pair("Flying", 100); //创建pair
M.insert(t); //创建映射:"Flying"->100

可以简化为：

M.insert(make_pair("Flying", 100));

• []操作

可以把上述写法写为：

M["Flying"] = 100; //创建映射:"Flying"->100

4.遍历方式

支持迭代器遍历和区间遍历。

八、位图 b i t s e t bitset bitset

所谓的bitset，其实就是一个多位的二进制数。

1.头文件与声明

• 头文件

#include

• 声明

bitset<1000> s; //声明了一个1000位的二进制数s

2.支持的操作

操作	用法
位运算操作符	与位运算一致
==、! =	比较两个bitset是否相等
s[k]	表示s的第 k k k位，可以取值也可以赋值
count	返回有多少位 1 1 1
any	所有位都为 0 0 0则any返回 f a l s e false false，至少有一个 1 1 1则any返回 t r u e true true
none	所有位都为 0 0 0则none返回 t r u e true true，至少有一个 1 1 1则none返回 f a l s e false false
set	s.set()所有位变 1 1 1，s.set(k,v)把第 k k k位变为 v v v
reset	s.reset()所有位变 0 0 0，s.reset(v)把第 k k k位变为 0 0 0
flip	s.flip把s的所有位取反，s.flip(k)把s的第 k k k位取反

九、算法 a l g o r i t h m algorithm algorithm 1.头文件

• 头文件

#include

2.支持的函数 （1）翻转 r e v e r s e reverse reverse

• 翻转一个vector

reverse(a.begin(), a.end());

• 翻转一个数组，下标存在 1 − n 1-n 1−n

reverse(a + 1, a + n + 1);

（2）去重 u n i q u e unique unique

其返回值为去重之后的尾迭代器。

注意：只是把不重复的元素放到前面，重复的元素移到了后面。

• vector去重并得到不重复的元素

使用：unique(a.begin(), a.end());

#include
#include
#include
using namespace std;

int n, x;
vector a;

int main()
{
	cout << "请输入元素个数" << endl;
	cin >> n;

	while (n--)
	{
		cin >> x;
		a.push_back(x);
	}
	vector::iterator it = unique(a.begin(), a.end()); //去重
	int m = it - a.begin();

	cout << "不重复的元素个数为" << m << endl;

	for (auto temp = a.begin(); temp != it; temp++)
		cout << *temp << " ";

	return 0;
}

对数组去重也是同理的，注意第二个参数必须是最后一个元素的后一个元素的指针。

（3）下一个排列 n e x t _ p e r m u t a t i o n next_permutation next_permutation

• 含义

把两个迭代器（指针）之间的部分看成一个排列，求出这些元素构成的全排列中字典序排在下一个的排列并直接在序列上更新。

• 返回值

返回值为bool类型，若存在下一个排列返回 t r u e true true，否则返回 f a l s e false false

如实现字典序输出 1 1 1到 n n n的全排列：

#include
#include
using namespace std;

int n;

int main()
{
	cout << "请输入个数" << endl;
	cin >> n;

	int* a = new int[n + 2];
	for (int i = 1; i <= n; i++)
		a[i] = i;

	do
	{
		for (int i = 1; i <= n; i++)
			cout << a[i] << " ";
		cout << endl;
	} while (next_permutation(a + 1, a + n + 1));
	return 0;
}

（4）上一个排列 p r e v _ p e r m u t a t i o n prev_permutation prev_permutation

与下一个排列类似。

（5）快速排序 s o r t sort sort

对两个指针指定的部分进行快速排序。

注意第二个指针是尾迭代器或者指向最后一个元素的后一个元素的指针。

可以在第三个参数中传入大小比较的函数或者重载<。

• 实现自定义数据类型dot的排序

#include
#include
#include
using namespace std;
//自定义dot数据类型
struct dot
{
	int x;
	dot(int x) { this->x = x; }
};
//重载<
bool operator<(const dot& a, const dot& b)
{
	return a.x < b.x;
}

vector arr;

int main()
{
	int n;
	cin >> n;
	while (n--)
	{
		int x;
		cin >> x;
		arr.emplace_back(x);
	}
    //快速排序
	sort(arr.begin(), arr.end());
	for(auto t : arr)
		cout << t.x << " ";

	return 0;
}

（6）二分查找

在两个指针之间查找满足条件的元素。

当然，两个指针之间的部分应当是提前排好序的。

函数	含义
lower_bound	返回第一个 ≥ x geq x ≥x的元素的迭代器或指针
upper_bound	返回第一个 > x > x >x的元素的迭代器或指针

假定查找的是 x x x。

• 在有序vector中查找 ≥ x geq x ≥x最小整数的下标

#include
#include
#include
using namespace std;

vector a;

int main()
{
	for (int i = 1; i <= 10; i++)
		a.push_back(i);

	int x;
	cin >> x;
	x %= 11;

	int idx = lower_bound(a.begin(), a.end(), x) - a.begin();

	cout << "idx = " << idx << endl;

	return 0;
}