本文主要總結(jié)了常見的STL容器用法，備忘。詳細請見STL用法。

1.vector

• 變長數(shù)組，倍增思想，系統(tǒng)為某一程序分配空間，所需時間與空間大小無關(guān)，與申請次數(shù)有關(guān)

• a.size()

• a.empty()

• clear()

• front()/back()

• push_back()/pop_back()

• begin()/end()

• []隨機取址

• 支持比較運算 按照字典序比較

• erase 復雜度

#include<vector>

vector<int> a(10,3)

//3種遍歷方式
for(int i=0;i<a.size();i++)cout<<a[i]<<" ";

for(vector<int>::iterator i= a.begin();i<a.end();i++)cout<<*i<<" ";

for(auto it:a)cout<<it<<" ";

2 pair

• 可以存儲二元組，類型任意
• p.first p.second
• 支持比較運算，以first為第一關(guān)鍵字，以second為第二關(guān)鍵字
• 多種屬性 pair<int,pair<int,int>>
• 應(yīng)用場景：
  • 某個對象擁有兩種屬性，且需要排序
  • 可以看成實現(xiàn)了一個二元結(jié)構(gòu)體，并實現(xiàn)了比較函數(shù)

3 string

• 字符串加減操作
• substr(start,length)
• printf("%s\n",a.c_str()) //a.c_str() 返回起始地址

4 queue 隊列

• size()
• empty()
• push()/pop()
• front()/back()
• 清空queue，重新構(gòu)造 q=queue<int>()

5 priority_queue 優(yōu)先隊列

• 默認大根堆
  • priority_queue<int> heap
• 如何構(gòu)建小根堆
  • 黑科技，負數(shù)大法
  • priority_queue<int,vector<int>,greater<int>> heap

6 stack 棧

• push/pop
• empty
• top
• size()

7 deque

• size
• empty
• clear
• front/back
• push_back/pop_back
• push_front/pop_front
• begin/end
• []

8 set、multiset,

• 時間復雜度
• 基于平衡二叉樹（紅黑樹），動態(tài)維護有序序列
• size()、empty()、clear()
• insert 函數(shù)
• find 查找函數(shù) 不存在返回end迭代器
• count()
• begin()/end() 支持++,--操作，返回前驅(qū)和后繼
• erase
  • 輸入一個數(shù)，刪除x 復雜度
  • 輸入一個迭代器，刪除這個迭代器
• lower_bound() 大于等于x最小的數(shù)
• upper_bound 大于x最小的數(shù)

9 map、multimap

• insert() 插入的是一個pair

• erase() 輸入的參數(shù)是pair 或者迭代器

• find

• [] 時間復雜度為

  #include<set>
  
  map<string,int> a;
  a["abc"]=1;
  

10 其他

• unordered_set, unordered_map, unordered_multiset, unordered_multimap, 哈希表
• 和上面類似，增刪改查的時間復雜度都是
• 不支持基于排序的操作lower_bound() upper_bound()、++ --

11 bitset

• 經(jīng)典應(yīng)用場景
• 支持操作
  • ~ & | ^
  • >> <<
  • == !=
  • []
  • count() 返回有多少個1
  • any()判斷是否至少有一個1
  • none() 判斷是否全為0
  • set() 把所有位置1
  • set(k,v)把第k位置v
  • reset()把所有位置0
  • flip() 等價于 ~
  • flip(k) 將第k位取反