Cheatsheet: C++

本文整理了一些 C++ 的常见语法及特性。

常见容器

顺序容器

vector

• 特点：连续内存、动态数组、支持随机访问 $O(1)$

• 常用操作：

  v.push_back(x)
  v.pop_back()
  v[i]
  v.size()

• 复杂度：

  操作	复杂度
  随机访问	O(1)
  push_back	O(1) amortized
  插入中间	O(n)
  删除中间	O(n)

deque

• 特点：双端队列、两端插入都 $O(1)$、内存分段连续

• 常用操作：

  dq.push_front(x)
  dq.push_back(x)

• 复杂度：

  操作	复杂度
  随机访问	O(1)
  两端插入	O(1)
  中间插入	O(n)

list（双向链表）

• 特点：非连续内存、插入删除快

• 复杂度：

  操作	复杂度
  插入删除（已知位置）	O(1)
  查找	O(n)
  随机访问	❌ 不支持

有序关联容器（基于红黑树）

set

• 特点：自动排序、元素唯一、底层是红黑树

• 复杂度：

  操作	复杂度
  插入	O(log n)
  查找	O(log n)
  删除	O(log n)

• 常见操作：

  s.insert(x)
  s.find(x)
  s.erase(x)

map

• 特点：key-value 对、自动排序

• 常见操作：

  mp[key] = value
  mp.find(key)

无序关联容器（Hash）

unordered_set / unordered_map

• 特点：基于哈希表、无序、平均 $O(1)$

• 复杂度：

  操作	平均	最坏
  插入	O(1)	O(n)
  查找	O(1)	O(n)

适配器（Adapters）

stack

• 特点：基于 deque

• 常见操作：

  stack<int> st;
  st.push(x)
  st.pop()
  st.top()

queue

• 常见操作：

  queue<int> q;
  q.push(x)
  q.pop()
  q.front()

priority_queue

• 特点：默认大顶堆

• 常见操作：

  priority_queue<int> pq;  // 最大堆（默认）
  priority_queue<int, vector<int>, greater<int>> pq; // 最小堆
  pq.push(x)
  pq.top()
  pq.pop()

  struct Task {
      int priority;
      int timestamp;
  };
  
  struct cmp {
      bool operator()(const Task& a, const Task& b) {
          if (a.priority == b.priority)
              return a.timestamp > b.timestamp;  // 时间小的优先
          return a.priority < b.priority;  // 优先级大的优先
      }
  };
  
  priority_queue<Task, vector<Task>, cmp> pq;

• 复杂度：

  操作	复杂度
  push	O(log n)
  pop	O(log n)
  top	O(1)

常见输入输出

• 基础输入输出：cin / cout

  int a;
  cin >> a;
  
  int x, y;
  cin >> x >> y;
  
  string s;
  cin >> s;
  
  cout << a << endl;

• 读一整行：

  string line;
  getline(cin, line);

  • 如果前面用过 cin >>，需要 cin.ignore(); 先清掉换行：

• 处理多组输入 / 不定长输入：

  while (cin >> x) {
      // 直到 EOF
  }

  或者

  int n;
  cin >> n;
  while (n--) {
      ...
  }

• 输入一整行再解析：

  string line;
  getline(cin, line);
  
  stringstream ss(line);
  int x;
  while (ss >> x) {
      // 处理 x
  }

• 输出格式控制：

  #include <iomanip>
  
  double x = 3.14159;
  cout << fixed << setprecision(2) << x; // 3.14

• 快速输入输出：

  ios::sync_with_stdio(false);
  cin.tie(nullptr);

• printf / scanf：

  int x;
  scanf("%d", &x);
  
  printf("%d\n", x);