常用c++ STL 汇总

常用STL：

• vector

  • 变长数组，倍增的思想
  • 初始化：

  //初始化
  vector<int> a;
  vector<int> a(n);
  vector<int> a[n];
  vector<int> a(n, 0);//长度为n，值为0
  

  • 操作：

  size() //返回元素个数
  empty() //返回是否为空
  clear() //清空
  front()/back() //返回第一个/最后一个元素
  push_back()/pop_back() //在尾端插入元素/删除元素
  begin()/end()  //迭代器
  [] //随机访问
  

  • 遍历：

  for(int i = 0; i < a.size(); ++ i)
  for(vector<int>::iterator/*auto*/ i = a.begin(); i != a.end(); ++ i)
  for(auto x : a)
  

  • 黑科技：
    • 支持比较运算，按字典序比较

• pair

  • 二元组
  • 初始化：

  pair<T, T> p;
  pair<T, pair<T, T>> p;
  p = make_pair(a, b);
  p = {a, b};
  p.first/p.second //第一个元素/第二个元素
  

  • 黑科技：
    • 也支持比较运算
    • 以first为第一关键字，以second为第二关键字

• string

  • 字符串
  • 初始化：

  string a = "adfb";
  a += "adf";
  a += 'c';
  

  • 操作：

  size()/length() //返回字符串长度
  empty() //返回是否为空
  clear() //清空
  substr() //求子串
  a.substr(st, len) //从下标st开始长度为len的子串
  a.substr(st) //从st开始到结尾的子串
  c_str() //返回字符串地址
  //printf()无法输出string，但是可以printf("%s", a.c_str);
  

• queue

  • queue
    • 队列
    • 初始化：同数组
    • 操作：

    size()
    empty()
    push() //想队尾插入元素
    pop() //弹出队头元素
    front() //返回队头元素
    back() //返回队尾元素
    //队列没有clear()函数
    

  • priority_queue
    • 优先队列（堆）
    • 初始化：

    priority_queue<int> heap; //堆默认为大根堆
    heap.push(-x); //将数反号实现小根堆
    priority_queue<int, vector<int>, greater<int> > heap //直接定义小根堆
    

    • 操作：

    push() //插入一个元素
    top() //返回堆顶元素
    pop() //弹出堆顶元素
    

• stack

  • 栈
  • 初始化：同数组
  • 操作：

  size()
  empty()
  push() //向栈顶插入元素
  top() //返回栈顶元素
  pop() //弹出栈顶元素
  

• deque

  • 双端队列
  • 初始化：
  • 操作：

  size()
  empty()
  clear()
  front()
  back()
  push_back()/pop_back()
  push_front()/pop_front()
  begin()/end()
  []
  //操作多效率低
  

• set

  • set
    • 集合：无重复元素
    • 基于平衡二叉树
    • 操作：

    size()
    empty()
    clear()
    insert() //插入一个数
    find() // 查找一个数
    count() //返回某个数的个数
    erase() //输入一个数x，删除所有x；输入一个迭代器，删除这个迭代器
    lower_bound() //返回大于等于x的最小的数的迭代器
    upper_bound() //返回大于x的最小的数的迭代器
    //增删查改时间复杂度为log(n)
    

  • multiset
    • 可以有重复元素
    • 操作：同set
  • 以下unoder 都不支持排序有关操作，因为是无序的，不支持lower_bound/upper_bound ，但是增删改查的时间复杂度为O(1)，不支持迭代器的加减
  • unordered_set
  • unordered_multiset

• map

  • map
    • 基于平衡二叉树
    • 元素是pair
  • multimap
    • 操作：

    insert() //插入的数是一个pair
    erase() //输入的参数是pair或者迭代器
    find()
    
    map<string, int> a;
    a["adf"] = 1; //支持随机插入/访问,时间复杂度为log(n)
    lower_bound()/upper_bound()
    //增删查改时间复杂度为log(n)
    

  • 以下unoder 都不支持排序有关操作，因为是无序的，不支持lower_bound/upper_bound ，但是增删改查的时间复杂度为O(1)，不支持迭代器的加减
  • unordered_map
  • unordered_multimap

• bitset

  • 压位
    • bool 类型位一个字节，8位
    • 如：压位将bool 占用内存压缩1/8，使bool类型只占一个二进制位
    • bitset 相当于一个二进制数组，数组里存0/1，一个数组元素占1个二进制位
  • 初始化：

  bitset<10000> s;
  

  • 操作：

  ~, &, |, ^
  >>, <<
  ==, !=
  []
  count() //返回有多少1
  any() //判断是否至少有一个1
  none() //判断是否全为0
  set() //把所有位置成1
  set(k, v) //将第k位变成v
  reset() //把所有位变成0
  flip() //等价于~
  flip(k) //把第k位取反