test

命名风格

struct/class：驼峰
函数/变量：下划线

基础操作

String

// 获取String长度
s.size()    // size()来自STL容器统一接口, length()来自早期字符串库，两者功能相同，推荐使用size()
s.length()

// 截取
string t = s.substr(pos, len);   // 从pos开始，取len个字符

// 排序
sort(s.begin(), s.end());

// 二维数组按照a[0]从小到大排序
sort(meetings.begin(), meetings.end(), [](const vector<int>& x, const vector<int>& y) {
    return x[0] < y[0];
});

// char数组转string
string s;
s.push_back(c1);
s.push_back(c2);

// 逐个赋值
string base;
base.resize(2);
base[0] = a[x][y];
base[1] = a[x][y + 1];
避免使用s.push_back，每次都会构造string，耗时

struct

struct Node {
    int x, y;
};

// struct默认继承权限为public，class默认继承权限为private，其余完全相同
// 竞赛简单数据结构，一般使用struct

// 定义比较规则 - 1 - 重写< - 绑定类型本身，简单但定死
struct Node {
    int id, cnt, t;
    bool operator<(const Node& o) const {  // true的排在后面
        if (t != o.t) return t > o.t;
        return id > o.id;
    }
};
priority_queue<Node> pq;

// 定义比较规则 - 2 - 自定义比较函数 - 排序规则可自由切换
struct Cmp {
    bool operator()(const Node& a, const Node& b) const { ... }
};
priority_queue<Node, vector<Node>, Cmp> pq;

vector

编程比赛中，除全局数组外，一律推荐vector

// 初始化
vector<int> a;
vector<int> a(n);  //初始化为长度为n，初值为0的数组
vector<int> a(n, -1);  // 初始化为长度为n，初值为-1的数组
vector<vector<char>> a(n, vector<char>(n, '0'));  // n*n的二维矩阵



// 常用操作
a.push_back(x);   // 尾插
a.pop_back();     // 尾删
a.clear();        // 清空
a.empty();        // 是否为空
a.size();         // 元素个数


// vector数组遍历

// 1. 带下标遍历 (需要下标，易越界)
for (int i = 0; i < v.size(); ++i) { }    

// 2. 范围for遍历 ( 简单，安全，但是无下标 )
for (int x : v) { }  // 只读
for (int &x : v) { }  // 读写

// 3. 迭代器遍历 (适用于所有容器)
for (auto it = v.begin(); it != v.end(); ++it) { }


// vector数组从大到小排序
#include <algorithm>
#include <functional>
sort(happiness.begin(), happiness.end(), greater<int>());

map

// 创建
map<int, int> mp;             // 按键值顺序排列
unordered_map<int, int> ump;  // 无序map，速度更快

// 插入
mp[3] = 10;
mp.insert({5, 20});

// 访问
mp[key]              // 务必先检查是否存在，否则会报错

// 查找
mp.count(x);         // 是否存在（0/1）
mp.find(x);          // 返回迭代器

// 删除
mp.erase(x);         // 按 key
mp.erase(it);        // 按迭代器
mp.clear();

// 遍历
for (auto &p : mp) {
    // p.first, p.second
}

// 检查是否存在，存在才调数据
auto it = map.find(key);
if (it == map.end()) return false;
auto& on_list = it->second;

priority_queue

// 定义
priority_queue<int> pq;                    // 大根堆
priority_queue<int, vector<int>, greater<int>> pq2; // 小根堆，vector是默认的底层容易，默认将小的放在下面，使用greater将大的放在下面

// 常用操作
pq.push(x);    // 插入
pq.pop();      // 删除堆顶
pq.top();      // 访问堆顶
pq.empty();
pq.size();

// 自定义比较（结构体）
struct Node {
    int x;
    bool operator<(const Node& o) const {
        return x < o.x; // 大根堆
    }
};
priority_queue<Node> pq;

queue, deque

set, unordered_set, multiset

stack

常用算法

sort
stable_sort
binary_search
lower_bound
upper_bound
reverse
unique

时间优化建议

1. 函数参数尽量引用传递，特别是map和数组，减少拷贝时间
2. dfs一定要搭配记忆化搜索

---

转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。