vector

介绍

特性

动态数组，可随时添加或删除元素，头文件 #include<vector>

初始化

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
// 一维初始化
vector<int> a;
vector<node> c;	// node为结构体类型

// 定长初始化，可以作为普通数组使用
vector<int> a(n);
vector<int> b(n, 1); // n为长度，1为初值

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

// 拷贝初始化
vector<int> a(n, 1);
vector<int> b(a); // b = a

// 二维初始化
vector<int> v[5]; // 固定第一维
vector<vector<int>> v;
vector<vector<int>> a(n, vector<int>(m, 0)); // m 行 n 列

函数

代码 功能
c.front() 返回第一个数据 O(1)
c.pop_back() 删除最后一个数据 O(1)
c.push_back(val) 尾部添加一个数据 O(1)
c.size() 返回数组大小 O(1)
c.clear() 清除所有元素 O(n)
c.resize(n, \val) 改变数组大小为 n 并赋为 val，默认赋值为 0
c.insert(it, x) 向任意迭代器 it 插入一个元素 x，O(n)
c.erase(s, t) 删除 [s, t) 的所有元素 O(n)
c.begin() 返回首元素迭代器（地址）O(1)
c.end() 返回最后一个元素 后一个位置 的迭代器 O(1)
c.empty() 判断是否为空，为空返回真，反之返回假 O(1)
  • 例：c.insert(c.begin()+2,-1) 表示将 -1 插入 c[2] 的位置
  • c.resize(n, \val) 中 \ 表示可选参数，不必须
  • c.end() 返回最后一个元素后面一个地址，遵循【左闭右开】原则

排序：

使用 sort 排序要： sort(c.begin(), c.end());

访问

下标访问

和数组一样使用

1
2
for(int i = 0; i < 5; i++)
    cout << vi[i] << " ";

迭代器访问

类似指针

1
2
3
4
5
6
7
8
//方式一：
vector<int>::iterator it = vi.begin(); 
for(int i = 0; i < 5; i++)
    cout << *(it + i) << " ";
//方式二：
vector<int>::iterator it;
for(it = vi.begin(); it != vi.end(); it++)
    cout << *it << " ";

智能指针

1
2
3
4
5
vector<int> v;
v.push_back(12);
v.push_back(241);
for(auto &val : v) // 加 & 可修改
    cout << val << " "; // 12 241

stack

介绍

栈为数据结构的一种，是 STL 中实现的一个先进后出，后进先出的容器。

1
2
3
4
5
6
//头文件
#include<stack>
//声明
stack<int> s;
stack<string> s;
stack<node> s; //node是结构体类型

函数

代码 含义
s.push(val) 元素 val 入栈，O(1)
s.pop() 移除栈顶元素 O(1)
s.top() 取得栈顶元素（但不删除）O(1)
s.empty() 检测栈内是否为空，空为真 O(1)
s.size() 返回栈内元素的个数 O(1)

栈模拟

栈只能对栈顶元素进行操作，如果想要进行遍历，只能将栈中元素一个个取出来存在数组中

可以用数组模拟栈，用一个存放下标的变量 top 模拟指向栈顶的指针

1
2
3
4
5
int s[100]; // 从左至右为栈底到栈顶
int top = -1; // 初始栈内无元素，top为 -1
for(int i = 0; i <= 5; ++i)
    s[++top] = i; //入栈
int top_element = s[top--]; // 出栈

queue

介绍

队列是一种先进先出的数据结构。

1
2
3
4
//头文件
#include<queue>
//定义初始化
queue<int> q;

函数

代码 含义
q.front() 返回队首元素 O(1)
q.back() 返回队尾元素 O(1)
q.push(val) 尾部添加一个元素 val 进队 O(1)
q.pop() 删除第一个元素 出队 O(1)
q.size() 返回队列中元素个数 O(1)
q.empty() 判断是否为空，空为真 O(1)

队列模拟

使用 q[] 数组模拟队列，hh 表示队首元素的下标，初始值为 0，tt 表示队尾元素的下标，初始值为 -1，表示刚开始队列为空。

1
2
3
4
5
6
7
int q[100];
int hh = 0, tt = -1;
// 入队
q[++tt] = 1;
q[++tt] = 2;
// 出队
int t = q[hh++];

deque

介绍

首尾都可插入和删除的队列为双端队列。

1
2
3
4
//头文件
#include<deque>
//初始化定义
deque<int> dq;

函数

代码 含义
push_back(x)/push_front(x) 把x插入队尾后 / 队首 O(1)
back()/front() 返回队尾 / 队首元素 O(1)
pop_back() / pop_front() 删除队尾 / 队首元素 O(1)
erase(it) 删除双端队列中的地址为 it 的元素
erase(s, t) 删除双端队列中 [s, t) 中的元素
empty() 判断 deque 是否空 O(1)
size() 返回 deque 的元素数量 O(1)
clear() 清空 deque

deque可以进行排序

1
2
3
4
5
//从小到大
sort(q.begin(), q.end());
//从大到小排序
sort(q.begin(), q.end(), greater<int>());
sort(q.begin(), q.end(), greater()); //高版本C++才可以用

priority_queue

介绍

优先队列是在正常队列的基础上加了优先级，保证每次的队首元素都是优先级最大的。可以实现每次从优先队列中取出的元素都是队列中 优先级最大 的一个。它的底层是通过 堆 实现的。

函数

代码 含义
q.top() 访问队首元素 O(1)
q.push() 入队 O(log(n))
q.pop() 堆顶（队首）元素出队 O(log(n))
q.size() 队列元素个数 O(1)
q.empty() 是否为空 O(1)

优先级

基本数据类型

1
2
priority_queue<int> pq; // 默认大根堆, 即每次取出的元素是队列中的最大值
priority_queue<int, vector<int>, greater<int>> q; // 小根堆

参数解释：

  • vector<int> 是用来承载底层数据结构堆的容器
  • less<int> 表示数字大的优先级大，堆顶为最大的数字
  • greater<int>表示数字小的优先级大，堆顶为最小的数字

自定义排序

麻烦，不建议

1
2
3
4
5
6
struct cmp1 {
    bool operator()(int x,int y) {
        return x > y;
    }
};
priority_queue<int, vector<int>, cmp1> q1; // 小根堆

结构体

1
2
3
4
//要排序的结构体（存储在优先队列里面的）
struct Point {
    int x, y;
};
自定义排序
1
2
3
4
5
6
struct cmp {
    bool operator()(const Point& a,const Point& b) {
        return a.x < b.x;
    }
};
priority_queue<Point, vector<Point>, cmp> q; // x大的在堆顶

方式二：

重载 < 符号

方式一：

1
2
3
4
5
6
7
struct node {
    int x, y;
    friend bool operator < (Point a, Point b) { 
        //为两个结构体参数，结构体调用一定要写上friend
        return a.x < b.x; x大的在堆顶
    }
};

方式二：

1
2
3
4
5
6
7
struct node {
    int x, y;
    bool operator < (const Point &a) const {
        //直接传入一个参数，不必要写friend
        return x < a.x; //x大的在堆顶
    }
};

优先队列自定义排序规则和 sort() 函数定义 cmp 函数很相似，但是最后返回的情况是 相反 的。

特殊类型

默认先对 pair 的 first 进行降序排序，然后再对 second 降序排序。

map

介绍

映射类似于函数的对应关系，每个 x 对应一个 y ，而 map 是每个键对应一个值。

1
2
3
4
5
//头文件
#include<map>
//初始化定义
map<string,int> mp;
map<int,node> mp; //node是结构体类型

map会按照键的顺序从小到大自动排序，键的类型必须可以比较大小

函数

代码 含义
mp.find(key) 返回键为 key 的映射的迭代器，数据不存在时返回 mp.end() O(logN)
mp.erase(it) 删除迭代器对应的键和值 O(1)
mp.erase(key) 根据映射的键删除键和值 O(logN)
mp.erase(first,last) 删除左闭右开区间迭代器对应的键和值 O(last−first)
mp.size() 返回映射的对数 O(1)
mp.clear() 清空map中的所有元素 O(N)
mp.insert() 插入元素，插入时要构造键值对 O(logN)
mp.empty() 空为真 O(1)
mp.begin() 返回指向map第一个元素的迭代器 O(1)
mp.end() 返回指向map尾部的迭代器（最后一个元素的下一个地址）O(1)
mp.rbegin() 返回指向map最后一个元素的迭代器 O(1)
mp.rend() 返回指向map第一个元素前面一个的迭代器 O(1)
mp.count(key) 查看元素个数 O(logN) （0或1）
mp.lower_bound() 返回一个迭代器，指向键值 >= key 的第一个元素 O(logN)
mp.upper_bound() 返回一个迭代器，指向键值 > key 的第一个元素 O(logN)

查找元素是否存在时，可以使用
①mp.find() ② mp.count() ③ mp[key]
但是第三种情况，如果不存在对应的key时，会自动创建一个键值对（产生一个额外的键值对空间）所以为了不增加额外的空间负担，最好使用前两种方法

遍历 map

1
2
3
4
5
6
7
8
9
10
11
12
13
map<int,int> mp;
// 正向遍历
auto it = mp.begin();
while(it != mp.end()) {
    cout << it->first << " " << it->second << "\n";
    ++it;
}
// 逆向遍历
auto it = mp.rbegin();
while(it != mp.rend()) {
    cout << it->first << " " << it->second << "\n";
    ++it;
}

添加元素

1
2
3
4
5
6
7
8
map<string,string> mp;
// 方式一
mp["学习"] = "看书";
mp["玩耍"] = "打游戏";
// 方式二
mp.insert(make_pair("vegetable","蔬菜"));
mp.insert(pair<string,string>("fruit","水果"));
mp.insert({"hahaha","wawawa"});

访问元素

1
2
3
4
5
6
7
8
9
10
11
12
13
// 迭代器访问
map<string,string>::iterator it;
for(it = mp.begin(); it != mp.end(); it++)
    cout << it->first << " " << it->second << endl;
// 智能指针
for(auto &i : mp)
    cout << i.first << " " << i.second << endl;
// 访问单个元素
map<char,int>::iterator it = mp.find('a');
cout << it->first << " " <<  it->second << endl;
// 新特性，结构化绑定
for(auto [x, y] : mp)
    cout << x << " " << y << endl;

unordered_map

内部实现原理

map：内部用红黑树实现，具有自动排序（按键从小到大）功能。

unordered_map：内部用哈希表实现，内部元素无序杂乱。

效率比较

map：

  • 优点：内部用红黑树实现，内部元素具有有序性，查询删除等操作复杂度为O(logN)
  • 缺点：占用空间，红黑树里每个节点需要保存父子节点和红黑性质等信息，空间占用较大。

unordered_map：

  • 优点：内部用哈希表实现，查找速度非常快（适用于大量的查询操作）。
  • 缺点：建立哈希表比较耗时。

使用 [] 查找元素时，如果元素不存在，两种容器都是创建一个空的元素，所以查询容器内部元素的最优方法是：先判断存在与否，再索引对应值

还有一种映射：multimap，键可以重复，即一个键对应多个值

set

介绍

set 容器中的元素不会重复，当插入集合中已有的元素时，并不会插入进去，而且 set 容器里的元素自动从小到大排序。即 set 里面的元素不重复 且有序

1
2
3
4
//头文件
#include<set>
//初始化定义
set<int> s;

函数

代码 含义
s.begin() 返回 set 容器的第一个元素的迭代器 O(1)
s.end() 返回 set 容器的最后一个元素的下一个迭代器 O(1)
s.rbegin() 返回逆序迭代器，指向容器元素最后一个位置 O(1)
s.rend() 返回逆序迭代器，指向容器第一个元素前面的位置 O(1)
s.clear() 删除set容器中的所有的元素 O(N)
s.empty() 空为真 O(1)
s.insert() 插入一个元素，返回插入地址的迭代器和是否插入成功的 bool 并成的 pair O(logN)
s.size() 返回当前set容器中的元素个数 O(1)
s.erase(iterator) 删除定位器iterator指向的值 O(logN)
s.erase(first,second） 删除定位器first和second之间的值 O(logN)
s.erase(key_value) 删除键值key_value的值 O(logN)
s.find(element) 查找set中的某一元素，有则返回该元素对应的迭代器，无则返回结束迭代器 O(logN)
s.count(element) 查找set中的元素出现的个数 （0或1）O(logN)
s.lower_bound(k) 返回大于等于k的第一个元素的迭代器 O(logN)
s.upper_bound(k) 返回大于k的第一个元素的迭代器 O(logN)

比较

基本数据结构

greater函数

1
2
set<int> s1; // 默认从小到大排序
set<int, greater<int> > s2; // 从大到小排序

重载运算符

1
2
3
4
5
6
struct cmp {
    bool operator () (const int& u, const int& v) const {
       return u > v;
    }
};
set<int, cmp> s;

初始化时使用匿名函数定义比较规则

1
2
3
set<int, function<bool(int, int)>> s([&](int i, int j){
    return i > j; // 从大到小
});

结构体

直接重载结构体运算符即可，让结构体可以比较。

1
2
3
4
5
6
7
8
9
10
struct Point {
    int x, y;
    bool operator < (const Point &p) const {
        // 按照点的横坐标从小到大排序,如果横坐标相同,纵坐标从小到大
        if(x == p.x)
            return y < p.y;
        return x < p.x;
    }
};
set<Point> s;

其他set

  • multiset ：元素可以重复，且元素有序
  • unordered_set ：元素无序且只能出现一次
  • unordered_multiset ： 元素无序可以出现多次

pair

介绍

pair只含有两个元素，可以看作是只有两个元素的结构体。

应用：

  • 代替二元结构体
  • 作为map键值对进行插入
1
2
3
4
5
6
7
//头文件
#include<utility>
//初始化定义
pair<string,int> p("wangyaqi",1);
pair<string,int> p;
//赋值
p = {"wang",18};

访问

1
2
3
4
5
6
//定义结构体数组
pair<int,int> p[20];
for(int i = 0; i < 20; i++) {
    //first代表第一个元素，second代表第二个元素
    cout << p[i].first << " " << p[i].second;
}

string

介绍

string 是一个字符串类，和 char 型字符串类似。可以把 string 理解为一个字符数组。可以用 [] 访问单个字符。

1
2
3
4
5
6
7
8
9
// 头文件
#include<string>
// 初始化
string str1; //生成空字符串
string str2("123456789"); //生成"1234456789"的复制品 
string str3("12345", 0, 3);//结果为"123" ，从0位置开始，长度为3
string str4("123456", 5); //结果为"12345" ，长度为5
string str5(5, '2'); //结果为"22222" ,构造5个字符'2'连接而成的字符串
string str6(str2, 2); //结果为"3456789"，截取第三个元素（2对应第三位）到最后

特性

支持比较运算符。

string 字符串支持常见的比较操作符 （>,>=,<,<=,==,!=），支持 string 与 C-string 的比较（如 str < "hello" ）。按 字典序 排大小。

支持 + 运算符。代表拼接字符串。

1
2
3
string s1 = "123";
string s2 = "456";
string s = s1 + s2; //123456

string 是 C++ 的一个类，专门实现字符串的相关操作。具有丰富的操作方法，数据类型为 string ，字符串结尾没有 \0 字符

读入

读入一个字符串，遇空格，回车结束

1
2
string s;
cin >> s;

读入一行字符串，遇回车结束

1
2
string s;
getline(cin, s);

注意: getline(cin, s) 会获取前一个输入的换行符，需要在前面添加读取换行符的语句。如：getchar() 或 cin.get()，或者直接忽略：cin.ignore()

getline 函数是取一整行，行末的换行符也会被读取，但不会被保存，所以获得的内容不包含换行符，且可以直接读取下一行

cin 和 cout 解锁

代码（写在main函数开头）：

1
2
ios::sync_with_stdio(false);
cin.tie(0),cout.tie(0);

为什么要进行解锁？

在一些题目中，读入的数据量很大，往往超过了1e5（10^5^）的数据量，而 cin 和 cout 的读入输出的速度很慢（为了兼容C语言的读入输出在性能上做了妥协），远不如 scanf 和 printf 的速度。所以对 cin 和 cout 进行解锁其速度几乎接近 scanf 和 printf ，避免输入输出超时。

cin cout解锁使用时，不能与 scanf,getchar, printf,cin.getline()混用，一定要注意，会出错。

string 向 char 数组的转换

1
2
string s = "liano";
char s2[] = s.c_str();

函数

获取长度

代码 含义
s.size()和s.length() 返回 string 对象的字符个数，他们执行效果相同
s.max_size() 返回 string 对象最多包含的字符数
s.capacity() 重新分配内存之前，string 对象能包含的最大字符数

插入

代码 含义
s.push_back(ch) 在末尾插入字符 ch
s.insert(pos, ch) 在 pos 位置插入 ch
s.append(str) 在 s 字符串结尾添加 str 字符串

删除

代码 含义
erase(p) 删除字符串中 p 所指的字符
erase(s, t) 删除字符串中迭代器区间 [s,t) 上所有字符
erase(pos, len) 删除字符串中从索引位置 pos 开始的 len 个字符
clear() 删除字符串中所有字符

字符替换

代码 含义
s.replace(pos,n,str) 把当前字符串从索引 pos 开始的 n 个字符替换为 str
s.replace(pos,n,n1,ch) 把当前字符串从索引 pos 开始的 n 个字符替换为 n1个字符 ch
s.replace(it1,it2,str) 把当前字符串 [it1,it2) 区间替换为 str
tolower(s[i]) 转换为小写
toupper(s[i]) 转换为大写

大小写转换可以通过 transform 函数实现

1
2
3
string s;
transform(s.begin(),s.end(),s.begin(),::tolower);//转换小写
transform(s.begin(),s.end(),s.begin(),::toupper);//转换大写

前2个指定要转换的容器的起止范围，第3个参数是结果存放容器的起始位置，第4个参数是一元运算。

分割

代码 含义
s.substr(pos,n) 截取从pos索引开始的n个字符

查找

代码 含义
s.find(str, pos) 从 pos 索引位置（默认为0）开始，查找子串 str，返回索引，-1 表示查找不到
s.find(c, pos) 从 pos 索引位置开始，查找字符 c，返回索引
s.rfind(str, pos) 从 pos 索引位置开始，反向查找子串 str，返回索引
s.rfind(c,pos) 从 pos 索引位置开始，反向查找字符 c，返回索引
s.find_first_of(str, pos) 从 pos 索引位置开始，查找子串 str 中的字符，返回第一次出现的位置
s.find_first_not_of (str,pos) 从 pos 索引位置开始，查找不在子串 str 中的字符，返回第一次出现的位置
s.find_last_of(str, pos) 从 pos 索引位置开始，查找最后一个位于子串 str 的字符，返回找到的位置
s.find_last_not_of ( str, pos) 从 pos 索引位置开始，查找最后一个不位于子串 str 的字符，返回找到的位置

排序

1
sort(s.begin(), s.end());  //按ASCII码排序

bitset

介绍

类似数组，但每一个元素只能是 0 或 1，每个元素只用 1 bit空间

1
2
3
//头文件
#include<bitset>
bitset <n> a

初始化

代码 含义
bitset<n> a a 有 n 位，每位都为0
bitset<n> a(b) a 是 unsigned long 型 b 的一个副本
bitset<n> a(s) a 是二进制字符串 s 中含有的位串的副本，前面用 0 补充
bitset<n> a(s,pos,n) a 是 s 中从位置 pos 开始的 n 个位的副本

特性

位操作

1
2
3
4
5
6
7
bitset<4> foo(string("1001"));
bitset<4> bar(string("0011"));
cout << (bar << 1) << endl; // 左移
cout << (bar >> 1) << endl; // 右移
cout << (foo == bar) << endl; // ==
cout << (foo != bar) << endl; // !=
cout << (foo ^ bar) << endl; // 或

访问

可以通过 [] 访问元素(类似数组)

1
2
3
bitset<4> foo ("1011"); 
cout << foo[0] << endl;　　//1
cout << foo[2] << endl;　　//0

函数

代码 含义
b.any() b 中是否有 1 的，有 返回 true
b.none() b 中是否没有 1 ，没有 返回 true
b.count() b 中为 1 的个数
b.size() b 中二进制位的个数
b.test(pos) 测试 b 在 pos 位置是否为 1，是 返回 true
b[pos] 返回 b 在 pos 处的二进制位
b.set() 把 b 中所有位都置为 1
b.set(pos) 把 b 中 pos 位置置为 1
b.reset() 把 b 中所有位都置为 0
b.reset(pos) 把 b 中 pos 位置置为 0
b.flip() 把 b 中所有二进制位取反
b.flip(pos) 把 b 中 pos 位置取反
b.to_ulong() 用 b 中同样的二进制位返回一个 unsigned long 值

array

介绍

array 是 C++11 新增的容器，效率与普通数据相差无几，比 vector 效率要高，自身添加了一些成员函数。

和其它容器不同，array 容器的大小是固定的，无法动态的扩展或收缩，只允许访问或者替换存储的元素。

1
2
3
4
5
6
7
8
9
// 头文件
#include<array>
// 声明一个大小为100的int型数组，元素的值不确定
array<int, 100> a;
// 初始值均为0
array<int, 100> a{};
// 初始化部分值，其余全部为0
array<int, 100> a{1, 2, 3};
array<int, 100> a = {1, 2, 3};

不同于数组的是对元素类型不做要求，可以套结构体

1
2
array<string, 2> s = {"ha", string("haha")};
array<node, 2> a;

访问

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
array<int, 4> a = {1, 2, 3, 4};
// 下标访问
for(int i = 0; i < 4; i++) 
    cout << a[i] << endl;
// auto
for(auto i : a)
    cout << i << endl;
// 迭代器
for(auto it = a.begin(); it != a.end(); it++) 
    cout << *it << endl;
// at()
int res = a.at(1) + a.at(2);
cout << res << endl; // 2+3=5
// get,将a数组下标为1位置处的值改为x
get<1>(a) = x;

函数

成员函数 功能
begin() 返回容器中第一个元素的迭代器
end() 返回容器最后一个元素之后一个位置的迭代器
rbegin() 返回最后一个元素的迭代器
rend() 返回第一个元素之前一个位置的迭代器
size() 返回容器中元素的数量，其值等于初始化 array 类的第二个模板参数 n
max_size() 返回容器可容纳元素的最大数量，其值始终等于初始化 array 类的第二个模板参数 n
empty() 判断容器是否为空
at(n) 返回容器中 n 位置处元素的引用
front() 返回容器中第一个元素的直接引用
back() 返回容器中最后一个元素的直接引用
data() 返回一个指向容器首个元素的指针
fill(x) 将 x 这个值赋值给容器中的每个元素
array1.swap(array2) 交换 array1 和 array2 容器中的所有元素，要求它们具有相同的长度和类型 
1
2
3
4
// 将 a 数组 [begin,end) 全部值变为 x
fill(a.begin(), a.end(), x);
// 排序
sort(a.begin(), a.end());

tuple

介绍

tuple 模板是 pair 的泛化，可以封装不同类型任意数量的对象。可以把 tuple 理解为 pair 的扩展，tuple 可以声明二元组，也可以声明三元组。

tuple 可以等价为结构体使用

1
2
3
4
5
6
7
8
9
10
11
// 头文件
#include <tuple>
// 声明一个空的tuple三元组
tuple<int, int, string> t1;
// 赋值
t1 = make_tuple(1, 1, "hahaha");
// 声明同时赋值
tuple<int, int, int, int> t2(1, 2, 3, 4);
 //将pair对象赋给tuple对象，但tuple对象必须是两个元素
auto p = make_pair("wang", 1);
tuple<string, int> t3{p};

访问

1
2
3
4
// 获取tuple对象t的第一个元素
int first = get<0>(t);
// 修改tuple对象t的第一个元素
get<0>(t) = 1;

函数

1
2
3
4
5
6
7
8
9
10
11
tuple<int, int, int> t(1, 2, 3);
// 获取元素个数
cout << tuple_size<decltype(t)>::value << endl; // 3
// 获取元素值
cout << get<0>(1) << endl; // 2
// 通过tie解包获取元素值
int one, three;
string two; 
tuple<int, string, int> t(1, "hahaha", 3);
tie(one, two, three) = t;
cout << one << two << three << endl; // 1hahaha3