常用c++ STL 汇总

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

//初始化vector a;vector a(n);vector a[n];vector 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::iterator/*auto*/ i = a.begin(); i != a.end(); ++ i)for(auto x : a)

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

• 二元组
• 初始化：

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

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

• 字符串
• 初始化：

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
  • 队列
  • 初始化：同数组
  • 操作：

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

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

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

  • 操作：

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

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

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

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

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

• 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
  • 基于平衡二叉树
  • 元素是pair
• multimap
  • 操作：

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

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

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

bitset s;

• 操作：

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