向量 vector

#include <vector>
连续的顺序的储存结构（和数组一样的类别），但是有长度可变的特性。

常用方法

构造

vector<类型> arr(长度, [初值])

#include<vector>
vector<int> arr(100,0); //构造初始长为100的int一维数组,初始值全为0
vector<vector<int>>arr(100,vector<int>()); //构造行数为100,列数不定的二维数组
vector<vector<int>>arr(100,vector<int>(666,-1)); //构造行数为100,列数为666的二维数组,初始值为-1

尾接 & 尾删

  • .push_back(元素)：在 vector 尾接一个元素
  • .pop_back()：删除 vector 尾部的一个元素

    获取长度

    .size()
    获取当前 vector 的长度

    清空

    .clear()
    清空 vector

    判空

    .empty()
    如果是空返回 true 反之返回 false.

    改变长度

    .resize(新长度, [默认值])
    修改 vector 的长度
  • 如果是缩短，则删除多余的值
  • 如果是扩大，且指定了默认值，则新元素均为默认值（旧元素不变）
    #include<iostream>
    #include<vector>
    using namespace std;
    int main(){
        vector<int>arr(3,1);
        for(auto x:arr)
        cout<<x;  //111
        cout<<endl;
        arr.resize(4,0);
        for(auto x:arr)
        cout<<x; //1110
        cout<<endl;
        arr.resize(2);
        for(auto x:arr)
        cout<<x; //11
    }

栈 stack

通过二次封装双端队列 (deque) 容器，实现先进后出的栈数据结构。

常用方法

作用 用法 示例
构造 stack<类型> stk stack<int> stk;
进栈 .push(元素) stk.push(1);
出栈 .pop() stk.pop();
取栈顶 .top() int a = stk.top();
查看大小 / 清空 / 判空 略 略

队列 queue

#include <queue>
通过二次封装双端队列 (deque) 容器，实现先进先出的队列数据结构。

常用方法

作用 用法 示例
构造 queue<类型> que queue<int> que;
进队 .push(元素) que.push(1);
出队 .pop() que.pop();
取队首 .front() int a = que.front();
取队尾 .back() int a = que.back();
查看大小 / 清空 / 判空 略 略

优先队列 priority_queue

#include <queue>
提供常数时间的最大元素查找，对数时间的插入与提取，底层原理是二叉堆。

常用方法

构造

priority_queue<类型, 容器, 比较器> pque

  • 类型：要储存的数据类型
  • 容器：储存数据的底层容器，默认为 vector<类型>，竞赛中保持默认即可
  • 比较器：比较大小使用的比较器，默认为 less<类型>，可自定义
priority_queue<int> pque1;                            // 储存int的大顶堆
priority_queue<int, vector<int>, greater<int>> pque2; // 储存int的小顶堆
作用 用法 示例
进堆 .push(元素) que.push(1);
出堆 .pop() que.pop();
取堆顶 .top() int a = que.top();
查看大小 / 判空 略 略 
priority_queue<int>pque;
 pque.push(6);
 pque.push(5);
 pque.push(4);
 cout<<pque.top()<<endl; //6
 pque.pop();
 cout<<pque.top();  //5

集合 set

#include <set>
提供对数时间的插入、删除、查找的集合数据结构。底层原理是红黑树。

集合三要素 解释 set multiset unordered_set
确定性 一个元素要么在集合中，要么不在 ✔ ✔ ✔
互异性 一个元素仅可以在集合中出现一次 ✔ ❌（任意次） ✔
无序性 集合中的元素是没有顺序的 ❌（从小到大） ❌（从小到大） ✔

常用方法

构造

set<类型, 比较器> st

  • 类型：要储存的数据类型
  • 比较器：比较大小使用的比较器，默认为 less<类型>，可自定义
    set<int> st1;               // 储存int的集合（从小到大）
    set<int, greater<int>> st2; // 储存int的集合（从大到小）

    遍历

    可使用迭代器进行遍历：
    for (set<int>::iterator it = st.begin(); it != st.end(); ++it)
        cout << *it << endl;
    基于范围的循环（C++ 11）：
    for (auto &ele : st)
        cout << ele << endl;

    其他

作用 用法 示例
插入元素 .insert(元素) st.insert(1);
删除元素 .erase(元素) st.erase(2);
查找元素 .find(元素) auto it = st.find(1);
判断元素是否存在 .count(元素) st.count(3);
查看大小 / 清空 / 判空 略 略

对于查找元素的find

  • 找到了 → 返回指向该元素的 迭代器
  • 没找到 → 返回 st.end()
    set<int>s;
    s.insert(2);
    s.insert(1);
    s.insert(8);
    s.insert(8);
    for(auto x:s)
    cout<<x;
    auto it=s.find(2);
    cout<<s.count(4)<<s.count(8);
    set 的迭代器不能像 vector 一样相减得到下标。下面是错误用法：
    auto it = st.find(2);      // 正确，返回2所在位置的迭代器。
    int idx = it - st.begin(); // 错误！不可相减得到下标。

映射 map

include <map>
提供对数时间的有序键值对结构。底层原理是红黑树。

性质 解释 map multimap unordered_map
互异性 一个键仅可以在映射中出现一次 ✔ ❌（任意次） ✔
无序性 键是没有顺序的 ❌（从小到大） ❌（从小到大） ✔

常用方法

构造

map<键类型, 值类型, 比较器> mp

  • 键类型：要储存键的数据类型
  • 值类型：要储存值的数据类型
  • 比较器：键比较大小使用的比较器，默认为 less<类型>，可自定义
    map<int, int> mp1;               // int->int 的映射（键从小到大）
    map<int, int, greater<int>> st2; // int->int 的映射（键从大到小）

    遍历

    可使用迭代器进行遍历：
    for (map<int, int>::iterator it = mp.begin(); it != mp.end(); ++it)
        cout << it->first << ' ' << it->second << endl;
    基于范围的循环（C++ 11）：
    for (auto &pr : mp)
        cout << pr.first << ' ' << pr.second << endl;
    结构化绑定 + 基于范围的循环（C++17）：
    for (auto &[key, val] : mp)
        cout << key << ' ' << val << endl;

    其他

作用 用法 示例
增 / 改 / 查元素 中括号 mp[1] = 2;
查元素（返回迭代器） .find(元素) auto it = mp.find(1);
删除元素 .erase(元素) mp.erase(2);
判断元素是否存在 .count(元素) mp.count(3);
查看大小 / 清空 / 判空 略 略 
map<int,int> m;
m[1]=8;
m[7]=9;
for(auto [key,val]:m)
cout<<key<<":"<<val<<endl;
m[9];
for(auto [key,val]:m)
cout<<key<<":"<<val<<endl;

如果使用中括号访问 map 时对应的键不存在，那么会新增这个键，并且值为默认值，因此中括号会影响键的存在性。

map<char, int> mp;
cout << mp.count('a') << endl; // 0
mp['a'];                       // 即使什么都没做，此时mp['a']=0已经插入了
cout << mp.count('a') << endl; // 1
cout << mp['a'] << endl;       // 0

迭代器简介

迭代器是什么？

对于一个 vector，我们可以用下标遍历：

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

我们同时也可以用迭代器来遍历：
for (vector<int>::iterator it = a.begin(); it != a.end(); ++it)
    cout << *it << endl;

  • a.begin() 是一个迭代器，指向的是第一个元素
  • a.end() 是一个迭代器，指向的是最后一个元素再后面一位
  • 上述迭代器具有自增运算符，自增则迭代器向下一个元素移动
  • 迭代器与指针相似，如果对它使用解引用运算符，即 *it，就能取到对应值了

迭代器用法

  • .begin()：头迭代器
  • .end()：尾迭代器
  • .rbegin()：反向头迭代器
  • .rend()：反向尾迭代器
  • 迭代器 + 整型：将迭代器向后移动
  • 迭代器 - 整型：将迭代器向前移动
  • 迭代器 ++：将迭代器向后移动 1 位
  • 迭代器 --：将迭代器向前移动 1 位
  • 迭代器 - 迭代器：两个迭代器的距离
  • prev(it)：返回 it 的前一个迭代器
  • next(it)：返回 it 的后一个迭代器

lower_bound() / upper_bound()

在已升序排序的元素中，应用二分查找检索指定元素，返回对应元素迭代器位置。找不到则返回尾迭代器。

  • lower_bound(): 寻找大于等于x的第一个元素的位置
  • upper_bound(): 寻找小于等于x的第一个元素的位置
    返回的是迭代器，如何转成下标索引呢？减去头迭代器即可。
    用法示例
    template< class ForwardIt, class T >
    ForwardIt lower_bound( ForwardIt first, ForwardIt last, const T& value );
vector<int> arr{0, 1, 1, 1, 8, 9, 9};
vector<int>::iterator it = lower_bound(arr.begin(), arr.end(), 7);
int idx = it - arr.begin();
// idx = 4

我们通常写成一行：

vector<int> arr{0, 1, 1, 1, 8, 9, 9};
idx = lower_bound(arr.begin(), arr.end(), 7) - arr.begin(); // 4
idx = lower_bound(arr.begin(), arr.end(), 8) - arr.begin(); // 4
idx = upper_bound(arr.begin(), arr.end(), 7) - arr.begin(); // 4
idx = upper_bound(arr.begin(), arr.end(), 8) - arr.begin(); // 5