常用 STL 操作

分割字符串

#include <sstream>
stringstream ss (s);
getline(ss, sno, ':');
// 结果放置在字符串 sno 中

Pair

pair<int, int> p;
p.first
p.second
make_pair(1, 2)
// <1, 2>

强制转换

stoi("123")  // 123  string -> int
to_string(123) // "123" int -> string

暴力枚举数组元素

// next_permutation
#include <iostream>     // std::cout
#include <algorithm>    // std::next_permutation, std::sort

int main () {
  int myints[] = {1,2,3};

  std::sort (myints,myints+3);

  do {
    // ...
  } while ( std::next_permutation(myints,myints+3) );

  return 0;
}

set 和 multiset

set 容器会将插入的元素以特定的顺序排列，默认是从小到大
set 和 multiset 的区别在于 multiset 中的元素允许重复

优点：使用红黑树实现，搜索操作拥有良好的性能插入，查看，删除的时间复杂度均为 O(n)

// 插入elem元素，返回新元素的位置，pos 指出插入操作的搜寻起点
// 如果 pos 恰当可以加快速度
c.insert(pos,elem)
c.insert(elem)
// 删除
c.erase(beg, end)

set 的交集，并集和差集

// 交集，共有元素插入 X
set_intersection(x1.begin(),x1.end(),x2.begin(),x2.end(),inserter(x,x.begin()));
// 并集，所有元素不重复插入 X
set_union(x1.begin(),x1.end(),x2.begin(),x2.end(),inserter(x,x.begin()));
// 差集
set_difference(x1.begin(),x1.end(),x2.begin(),x2.end(),inserter(x,x.begin()));

优先队列

priority_queue<int, vector<int>, greater<int>> pq;

pq.push(elem);
elem = pq.top();
pq.pop();

合并两个 vector

AB.reserve(A.size(), B.size());	// pre-allocate capacity
AB.insert(AB.end(), A.begin(), A.end());
AB.insert(AB.end(), B.begin(), B.end());

// 原地合并
A.insert(A.end(), B.begin(), B.end());

不小于和不大于

lower_bound(ForwardIterator first, ForwardIterator last, val) 从first找到 last 寻找小于等于这个元素的位置，等于就停下来

upper_bound 从头开始找第一个比该元素大的位置，存在等于的时候返回的是大于元素的第一个位置，所以要进行回退才能移到等于的位置，配合 prev() 可以进行回退如果没有找到，那么迭代器会在 begin() 的位置不动

大顶堆和小顶堆

// 大顶堆
priority_queue<int> q;
// 小顶堆
priority_queue<int, vector<int>, greater<int> > q;

#枚举 #字符串

Word Break 系列单词阶梯系列