常用STL总结（详细 全）

/*目录
vector

pair

string

queue

priority_queue

stack

dequeue

set

map

multiset,multimap

unordered_______map,set,multimap, multiset //基于哈希表实现
*/




#include <vector>
int main(){
  //vector定义：倍增思想。系统为某一程序分空间时，所需的时间与空间大小无关，与申请次数有关
  //所以尽量减少申请空间的次数。
  //实现思想：每一次空间不够的时候，就会开一个成倍的空间，将原来的数据copy过来，这样很费时间的
  vector<int> a;
  vector<int> a(maxn);//长度为maxn的vector
  vector<int> a(maxn, -1)//全部初始化为特定的数 
  vector<int> a[10];//数组
  
  a.size();//返回a的大小         //这个是所有STL的都有的，通用的函数。时间复杂度是O(1)
  a.empty();//返回是否非空
  a.clear();//清空
  a.front();//返回第一个数
  a.back();//返回最后一个数
  a.push_back();//压栈
  a.pop_back();//删除最后一个数
  a.begin();//第一个数
  a.end();//最后一个数的下一个位置 
  a[];  //数组访问下标也是支持的
  //vector还支持比较运算
  vector<int> a(3, 4), b(4, 3);
  if(a > b) cout << "a > b" << endl;//按照字典序来比较
  
}





//pair<int, int>
int main(){
  pair<int, string>p;//前后两个可以不一致 
  p.first;//第一个元素
  p.second;//第二个元素
  //pair支持比较运算 ，按照字典序来比较。
  //以first为第一关键字，second第二关键字
  //要排序的内容放在first里面，不需要排序的属性放在second
  
  p = make_pair(10, "yesda");
  p = {20, "absc"};
  
  //当有三种属性的时候可以用pair<int , pair<int , string>>来存
  pair<int, pair<int , string>>;
  
  //和结构体相比，pair能省一些代码，并自带一个排序函数
}







//string
int main(){
  string 
  string.size();//string.length();//两个作用一样
  string.empty();
  string.clear();
  
  string a = "fads";
  a += "def";
  a += 'c';//都支持
  
  a.substr(int sp, int len);//两个参数，一个是0开始的下标位置，第二个是长度
  a.substr(1, 3);//a[1]---a[3]//len是包含a[1]本身的
  //也可以：substr(int sp)//直接返回从1开始到end的字符串
  
  printf("%s", a.c_str());//返回的是首地址
  printf("%s", a);//也行
  
}





//queue
#include <queue>
int main(){
  queue<int> q;
  //没有clear，怎么刷新队列？
  q = queue<int>();//刷新队列，重新指向一片新的区域
  
  
  queue.push();//队尾插入元素
         front() //返回队头元素
         back() //返回队尾元素
         pop() //弹出队头元素、//注意是弹出队头，先进先出
         size() 
         //没有clear()
  
  
}



//priority_queue优先队列
//priority_queue
//priority_queue
//priority_queue
//priority_queue
#include <queue>
int main(){
  priority_queue<int> heap; //优先队列//默认是大根堆
  push()//插入一个元素
  top()//返回堆顶元素
  pop()//弹出堆顶元素
  //没有clear()
  
  //小根堆
  //如何定义小根堆？
  priority_queue<int, vector<int>, greater<int>> heap;//这就是小根堆的定义
      //也可以在插入的时候插入负数
  queue.push(-x);//这样顺序也是小根堆
}








//stack栈        和队列基本差不多
int main(){
  push(); // 栈顶插入元素
  top(); //top是返回栈顶元素
  pop(); // 弹出栈顶元素
  //没有clear
  size();//O(1)
  empty();
}









#include <deque>
//deque双端队列         加强版的vector
int main(){
  deque<int> q;
  clear();
  size();
  empty();
  front()//返回第一个元素
  back();//返回最后一个元素
  push_back();//最后插入元素
  pop_back();//弹出最后元素
  
  push_front();//队首插入元素
  pop_front();//队首弹出元素
}










#include <set>
int main(){
  set<int> s;
  multiset<int> ms;
  
  //set里面不允许有重复元素的，如果插入重复元素，该操作会被忽略掉，count也只有一个
  //multiset里面允许有重复元素
  
  size();
  empty();
  clear();
  begin();
  //++  --  返回前驱后继(复杂度logn)
  set<int> s; 
  s++;//后继
  s--;//前驱
  end();
  
  
  set/multiset
    insert();//插入一个元素
    find();//查找元素，找不到就返回end()
    count();  //返回返回某一个数的个数。这个multiset有多少个就返回多少个。set只有一个
    erase();
      //1.输入是一个数，删除所有x(对于multiset就是有多少个删多少个)  O(k + logn)//k是该数个数
      //2.输入一个迭代器，删除这个迭代器
    //set里面最核心的操作：注意区别和含义理解：
    lower_bound(); //返回大于等于x 的最下的数的迭代器 。如果没有，返回end
    upper_bound(); //返回大于x的最小的数的迭代器。 如果没有，返回end
}









//map/multimap
int main(){

  insert() //插入的数是一个pair
  erase() //输入的参数可以是pair或迭代器
    mp.erase(key)
    参数：该函数接受一个强制性参数 key ，该参数指定要在Map容器中擦除的 key 。
    返回值：如果在映射中找到关键元素，则函数返回1，否则返回0。

  find() //查找元素，找不到就返回end()
  [] //像数组用map//时间复杂度是logn
  lower_bound() / upper_bound(）
  
  
  map<string, int> a;
  
  a["fdsa"] = 1;
  cout << a["fdsa"] << endl;  
}









//哈希表的实现：如果是哈希，unordered的效率比map的效率高
#include <unordered_map> //包含俩：unordered_map 和 unordered_multimap  begin(); end();
#include <unordered_set> //包含俩： unordered_set 和 unordered_multiset
//unordered_set, unordered_map, unordered_multiset, unordered_multimap //都是用哈希表来实现的
  //和上面类似，但是绝大部分操作（增删改查）时间复杂度是O（1）
  //不支持 lower_bound() / upper_bound()

/*unordered_map*/
int main(){
  unordered_map<int, string> unmap = unordered_map<int, string>( {{1, "a"}  ,   {2, "b"}} );
  unordered_map<int, string> unmap( {{1, "a"}  ,   {2, "b"}} );
  unordered_map<string, string> umap2{ {"a", "b"} , {"c" , "d"}};
  
  unordered_map<int, string> umap(umap2);//copy
  
  //迭代器初始化
  unordered_map<int, string> umap5(umap1.begin(), umap1.end());
  
  
  first.empty()
  second.empty()
  
  umap.size() // 当前容量
  
  //元素访问
  first["GOOG"] = "Google";    // new element inserted
  first["AAPL"] = "Apple";    // new element inserted
  first["MSFT"] = "Microsoft";  // new element inserted
  first["BOB"] = "Bob";
  string brand1 = first["GOOG"];  // read
  first["BOB"] = "";        // writen
  for (auto it = first.begin(); it != first.end(); it++){
      cout << " " << it->first << ":" << it->second;
  }
  
  //查找
//  find返回迭代器（指针）

  //count计数
  umap.count(key); //有返回1，无返回0
  
  
  //修改
//  使用操作符map_name [key_name] = value，
//  实现对应key的value值的覆盖，若是key值是原来不存在的key，那么实现了新的元素的插入
  
  
  //insert()
//  insert的插入和emplace的插入类似，只有当键是唯一时，才能进行插入，同时size增加
  
  
  return 0;
}











bitset //压位
  1024bool 1字节
  1024b = 1kb;
  128b //bool是8位1字节，但bitset是1位，省了8倍空间
  
  bitset<10000> s;
  ~, &, |, ^
  >>, <<
  ==, !=
  []
  
  count() //返回有多少个1
  
  any() //判断是否至少有一个1
  
  none() //判断是否全为0

  set() //把所有位置设置成1
  set(int k, bool v) //将第k位变成v  (0或1)
  reset()  把所有位置变成0
  flip()  等价于~
  flip(k) 把第k位取反