开发: C++知识库 Java知识库 JavaScript Python PHP知识库人工智能区块链大数据移动开发嵌入式开发工具数据结构与算法开发测试游戏开发网络协议系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑笔记本显卡显示器固态硬盘硬盘耳机手机 iphone vivo oppo 小米华为单反装机图拉丁

-> 系统运维 -> 从零开始学C++之STL容器、位运算与常用库函数 -> 正文阅读

[系统运维]从零开始学C++之STL容器、位运算与常用库函数

STL容器、位运算与常用库函数
所有题目来自ACWing
点这注册AcWing 邀请码：SMDRN

👇从零开始学C++系列👇

从零开始学C++之基本知识
 从零开始学C++之数组和字符串
 从零开始学C++之函数、结构体、类、指针、引用
 从零开始学C++之STL容器、位运算与常用库函数

STL容器

vector

在数组末尾插入删除O(1) ，在开头插入删除O ( n )

定义

??向量（Vector）是一个封装了动态大小数组的顺序容器。跟任意其它类型容器一样，它能够存放各种类型的对象。
??可以简单的认为，向量是一个能够存放任意类型的动态数组

特性

顺序序列
顺序容器中的元素按照严格的线性顺序排序。可以通过元素在序列中的位置访问对应的元素。
动态数组
支持对序列中的任意元素进行快速直接访问，甚至可以通过指针算述进行该操作。提供了在序列末尾相对快速地添加/删除元素的操作。
能够感知内存分配器的
容器使用一个内存分配器对象来动态地处理它的存储需求

代码

定义

Vector<类型>标识符
Vector<类型>标识符(最大容量)
Vector<类型>标识符(最大容量,初始所有值)
Int i[5]={1,2,3,4,5}
Vector<类型>vi(I,i+2);//得到i索引值为3以后的值
5.0 Vector< vector< int> >v; 二维向量(这里最外的<>要有空格。否则在比较旧的编译器下无法通过)

#include <vector>//头文件

// 定义
vector<int> a;      // 一维数组
vector<int> a[N];   // 二维数组

// 初始化
vector<int> a({1, 2, 3});

操作

// 操作
a[k];         // 取值
a.size();     // 长度
a.empty();    // 判空
a.clear();    // 清空

a.front();              // 读取第1个元素
a.back();               // 读取最后1个元素
a.push_back(x);          // 在末尾插入元素
int x = a.pop_back();    // 删除末尾元素并返回

// 取地址
int* p = lower_bound(a, a + a.size(), x);// 查找数组在指定范围内大于等于x的元素地址（要求数组有序）
int* p = upper_bound(a, a + a.size(), x);// 查找数组在指定范围内大于x的元素地址（要求数组有序）

//取值
int index = lower_bound(a, a + a.size(), x); - a;   // 查找数组在指定范围内大于等于x的元素下标（要求数组有序）
int index = upper_bound(a, a + a.size(), x); - a;   // 查找数组在指定范围内大于x的元素下标（要求数组有序）

// 遍历
for (int i = 0; i < a.size(); i++) {...}                            // 方式1，通过a[i]读取元素值

for (vector<int>::iterator i = a.begin(); i < a.end(); i++) {...}     // 方式2（迭代器），通过*i读取元素值

for (auto i = a.begin(); i < a.end(); i++) {...}                     // 方式3（迭代器简化版）  常用版

for (int x : a) {...}                                             // 方式4，通过x读取元素值

注意：

a.begin()返回的是vector第1个元素的地址，而a.end()返回的是最后一个元素的下一个位置的地址

队列(queue)

定义

队列：
??队列就是允许在一端进行插入，在另一端进行删除的线性表。允许插入的一端称为队尾，通常用一个队尾指针r指向队尾元素，即r总是指向最后被插入的元素;允许删除的一端称为队首，通常也用一个队首指针f指向排头元素的前面。初始时f=r=0

优先队列：
??priority_queue为优先队列，一般用来解决一些贪心问题，其底层是用“堆”来实现的。在优先队列中，任何时刻，队首元素一定是当前队列中优先级最高（优先值最大)的那一个(大根堆），也可以是最小的那一个（小根堆)。可以不断往优先队列中添加某个优先级的元素，也可以不断弹出优先级最高的那个元素，每次操作其会自动调整结构，始终保证队首元素的优先级最高

先进先出特性

可参考之前的文章 C++学习之队列&&优先队列

代码

队列：

#include <queue>

//初始化
queue<int>vis; //vis 是名字，可自由替换 || int是变量类型，如果是结构体就是结构体名称
vis.push(x);      // 入队（末尾插入元素）
int x = vis.pop();  // 出队（删除第1个元素）
vis.front();       // 查看队首元素
vis.back();       // 查看队尾元素
vis = queue<int>(); //初始化即可清空

优先队列

#include <queue>

//默认优先队列
// 大根堆
priority_queue<int> a; 
priority_queue<int, vector<int>, less<int>> a;//两个都可以
// 小根堆                                 
priority_queue<int, vector<int>, greater<int>> b;  

//自定义优先队列
priority_queue<type> name;//type通常为结构体
//其中，type可以是任何基本类型或者容器，name为优先队列的名字
//例如
struct Rec {
    int a, b;

    // 大根堆需要自定义类重载<号
    bool operator< (const Rec& t) const {
        return a < t.a;
    }

    // 小根堆需要自定义类重载>号
    bool operator> (const Rec& t) const {
        return a > t.a;
    }
}
priority_queue<Rec> a; // 大根堆
priority_queue<Rec, vector<Rec>, greater<Rec>> b; // 小根堆

操作：
??和queue不一样的是，priority_queue没有front()和back()，而只能通过top()或pop()访问队首元素（也称堆顶元素），也就是优先级最高的元素。

q.empty()	//检测是否为空
q.size()	//返回实际数据个数
q.top()	    //返回顶端元素
q.pop()	    //移除队首元素
q.push(x)	//插入一个元素x

注意：除了队列、优先队列、栈之外，其他所有STL容器均有clear()函数

栈(Stack)

顾名思义：先进后出

#include <stack>

// 定义
stack<int> s;

// 操作
s.push(x);          // 入栈
s.top();            // 查看栈顶元素
s.pop();            // 栈顶元素出栈（不放回出栈元素！）

双端队列(deque)

扩展版vector
deque在数组开头/结尾插入删除都是O(1)的

#include <deque>

// 定义
deque<int> q;

// 操作
q[i]                // 随机访问
q.begin();          // 队头元素地址，用*q.begin()读取元素
q.end();            // 队尾元素地址，用*q.end()读取元素
q.front();          // 队头元素值
q.back();           // 队尾元素值
q.clear(); 			//清空队列

//插入
push_back(x);        // 队尾插入元素
push_front(x);       // 队头插入元素
//删除
pop_back();         // 队尾删除元素
pop_front();        // 队头删除元素

set

有序
特点：元素不能重复

#include <set>

// 定义
set<int> s;   // 集合（不允许元素重复）
multiset<int> ms;  // 多重集合（允许元素重复）

// 操作
s.size();
s.empty();
s.claer();

s.begin();
s.end();

s.insert(x);
s.find(x);              // 返回迭代器，可用if(s.find(x) == s.end())判断是否存在元素x
s.lower_bound(x);        // 返回大于等于x的最小元素的迭代器
s.upper_bound(x);        // 返回大于x的最小元素的迭代器

s.erase(x);             // 删除x并返回迭代器
s.count(x);             // 统计x出现的次数（普通集合只会返回0或1，多重集合可能返回大于1的数）

重载小于符合

//因为set中间会做比较，所以结构体中需要重载小于号
struct Rec
{
	int x, y;
	bool operator< (const Rec& t) const
	{
		return x < t.x; 
	}
};
set<int> Rec;

find()、erase()、lower_bound()和upper_bound()都是O(logn)复杂度
count()是O(k+logn)复杂度

unordered_set

无序set 底层实现哈希表

#include <unordered_set>

unordered_set<int> s;           // 哈希表
unordered_multiset<int> s;

bitset

位运算
很长的二进制01串

#include <bitset>

// 定义二进制串
bitset s;

// 操作
s.count();      // 1的个数
s.set(p);       // 第p位设为1
s.reset(p);     // 第p位设为0

bitset元素支持位运算符&、|和~等等
求x的第k位二进制数：x >> k & 1
求x从右起的第1个1：lowbit(x) = x & -x;
实际上是原码和补码做与操作
例如110110返回10，11000返回1000

pair

有序对
将两个数据变为一个数据

//定义
//模板
template<class T1,class T2> struct pair

//例如
pair<int, int> a = {5, 6};
pair<int, int> b = make_pair(5, 6);
pair<int, string> a;
a = {3, "test"};
a = make_pair(4, "check"); //c++99的赋值

a.first()和a.second()分别输出第一个和第二个值

map

有序对

#include <map>

// 定义
map<string, int> m;
//Map的key和value可以是任意类型，其中key必须定义小于号运算符


// 操作
a["a"] = 4;     // 类似数组的操作
m.insert();
m.find();//可以很方便地通过该函数来得到key对应的value，还可以对h[key]进行赋值操作，改变key对应的value。

algorithm库

头文件
#include <algorithm>

reverse 翻转

// 翻转数组反转
reverse(a.begin(), a.end());
reverse(a, a + a.size());

unique 去重

??返回去重之后的尾迭代器（或指针），仍然为前闭后开，即这个迭代器是去重之后末尾元素的下一个位置。该函数常用于离散化，利用迭代器（或指针）的减法，可计算出去重后的元素个数

unique(a, a + a.size());
返回去重后最后一个元素的地址

int m = unique(a, a + a.size()) - a;
去重后数组的长度
a.erase(unique(a.begin(), a.end()), a.end());
真删除重复元素

random 随机打乱

// 随机打乱用法与reverse相同
random_shuffle(a.begin(), a.end());

sort 排序

sort(a.begin(), a.end());                       // 升序
sort(a.begin(), a.end(), greater<int>());         // 降序
bool cmp(int a, int b) {return a - b;}              // 自定义比较方法
sort(a.begin(), a.end(), cmp);                      // 自定义排序