常用容器 (Containers)

vector 动态数组

   vector v;
   vector v(100);      // 创建容量为容器
   v.push_back(1);          // 尾部插入
   v.pop_back();            // 尾部删除
   v.size();                // 元素数量
   v.empty();               // 判空
   v[0];                    // 随机访问（无边界检查）
   v.begin(); v.end();      // 迭代器
   sort(v.begin(), v.end()); // 默认升序排序
   // 自定义排序（降序）
    sort(v.begin(), v.end(), greater());
// lambda 自定义排序规则
    sort(v.begin(), v.end(), [&](int& a, int& b) {
return a > b;
});

string 字符串

   string s = "abc";
   s += "def";               // 拼接
   s.substr(1, 2);           // 子串 "bc"（起始位置，长度）
   s.find("cd");             // 返回索引或 string::npos

queue 队列（FIFO）

   queue q;
   q.push(1);                // 入队
   q.pop();                  // 出队（无返回值）
   q.front();                // 队首元素

priority_queue 优先队列（默认大根堆）

   priority_queue pq;                   // 大根堆
   priority_queue, greater> min_pq; // 小根堆
   pq.push(3); pq.top(); pq.pop();           // 堆顶操作

stack 栈（LIFO）

   stack stk;
   stk.push(1); stk.top(); stk.pop();

deque 双端队列

   deque dq;
   dq.push_front(1); dq.push_back(2);
   dq.pop_front(); dq.pop_back();

set/multiset 有序集合/多重集合

   set s;
   s.insert(3); s.erase(3);          // 插入/删除
   auto it = s.lower_bound(2);       // 首个 >=2 的元素
   auto it = s.upper_bound(2) // 首个 > 2 的位置

map/multimap 有序映射

   map mp;
   mp["key"] = 5;                    // 插入或修改
   if (mp.count("key")) { ... }      // 判断键存在

unordered_set/unordered_map 哈希表（C++11）

   unordered_map ump;
   ump.reserve(1024);                // 预分配空间避免哈希冲突

常用算法 (Algorithms)

排序与查找

   sort(v.begin(), v.end());                     // 快速排序
   sort(v.begin(), v.end(), greater());      // 降序排序
   auto it = lower_bound(v.begin(), v.end(), 5); // 第一个 >=5 的位置
   auto it = upper_bound(v.begin(), v.end(), 5) // 第一个 > 5 的位置
   bool found = binary_search(v.begin(), v.end(), 5); // 二分查找

去重

   sort(v.begin(), v.end());
   auto last = unique(v.begin(), v.end());        // 去重，返回新结尾
   v.erase(last, v.end());                        // 删除重复元素

排列生成

   next_permutation(v.begin(), v.end()); // 生成下一个排列
   prev_permutation(v.begin(), v.end()); // 生成上一个排列

数值操作

   max(a, b); min(a, b); swap(a, b);     // 最值、交换
   reverse(v.begin(), v.end());          // 反转容器
   fill(v.begin(), v.end(), 0);          // 填充值

实用工具

pair 与 tuple

   pair p = {1, "a"};
   auto t = make_tuple(1, "a", 2.0);

位运算

   __builtin_popcount(x);    // 二进制中 1 的个数
   __builtin_clz(x);         // 前导零数量（32/64位）

快速输入输出（竞赛优化）

   ios::sync_with_stdio(false);  // 关闭同步
   cin.tie(0);                   // 解绑 cin 和 cout

典型应用场景

• BFS/DFS: queue 或 stack
• Dijkstra算法: priority_queue（小根堆）
• 哈希计数: unordered_map
• 区间查询: lower_bound/upper_bound
• 离散化: vector + sort + unique

注意事项

1. 使用 map 时，优先用 emplace 替代 insert 避免构造临时对象。

   // 使用 insert（需要构造临时对象）
   myMap.insert(std::make_pair(1, "Hello"));
   
   // 使用 emplace（直接在容器内部构造对象）
   myMap.emplace(2, "World");

2. 多组数据时，STL容器需清空（如 vector.clear()）。