# 關於STL容器的簡單總結 ## 1、結構體中重載運算符的示例 ``` //結構體小於符號的重載 struct buf { int a,b; bool operator queuea; //定義 a.push(x); //壓入 a.pop(); //彈出 a.size(); //取大小 a.fro ...
關於STL容器的簡單總結
1、結構體中重載運算符的示例
//結構體小於符號的重載
struct buf {
int a,b;
bool operator < (const buf& c1) const { //註意：第二個const一定不能少
return a<c1.a;
}
};
//或
struct foo {
int a,b;
};
bool operator < (const foo &x, const foo &y)
{return x.a < y.a;}
2、隊列（queue）
#include <queue>
queue<int>a; //定義
a.push(x); //壓入
a.pop(); //彈出
a.size(); //取大小
a.front(); //訪問隊首元素
a.back(); //訪問隊尾元素
a.empty(); //判斷隊列是否為空
3、優先隊列（priority_queue）
#include <queue>
priority_queue<int,vector<int>,greater<int> > c; //定義從小到大的int類型的優先隊列
priority_queue<int> c; //定義從大到小的int類型的優先隊列
c.push(); //壓入
c.pop(); //彈出隊首元素
c.top(); //訪問隊首元素
c.empty(); //判斷隊列是否為空
//如是結構體必須重載'<'
4、雙端隊列（deque）
#include <deque>
deque <int> b; //定義雙端隊列
b.push_front(x); //在隊首壓入元素
b.push_back(x); //在隊尾壓入元素
b.pop_front(); //彈出隊首元素
b.pop_back(); //彈出隊尾元素
b.size(); //取大小
b.back(); //訪問隊尾元素
b.front(); //訪問隊首元素
b.empty(); //判斷隊列是否為空
//可用[]訪問
5、棧（stack）
#include <stack>
stack<int> d; //定義
d.push(x); //壓入元素
d.pop(); //彈出棧頂元素
d.top(); //訪問棧頂元素
d.size(); //取大小
d.empty(); //判斷棧是否為空
6、 集合（set）
#include <set>
set<int> e;
e.insert(i); //插入元素
e.erase(i); //刪除值為i的元素
e.count(i); //查看值為i的元素是否存在
e.empty(); //判斷set是否為空
set<int>:: iterator rit; //定義迭代器
rit = (e.insert(j)).first //返回插入後元素對應的迭代器
rit=e.find(i); //返回值為i的元素的迭代器，如果沒找到返回的是e.end()
rit=e.lower_bound(i) //返回值大於等於i的第一個元素的迭代器， 如果沒有大於等於i的元素返回e.end()
rit=e.upper_bound(i) //返回值大於i的第一個元素的迭代器， 如果沒有大於i的元素返回e.end()
for(rit=e.begin();rit!=e.end();rit++) //正序遍歷，值為*rit
set<int>::reverse_iterator rit; //反向遍歷的迭代器
for(rit=e.rbegin();rit!=e.rend();rit++) //反向遍歷必須這麼寫
註： 不能直接寫e.erase(e.rbegin());
//如使用結構體，必須重載< 或寫仿函數
7、可重集（multiset）
#include <set>
multiset<int> e;
e.insert(i); //插入元素
e.erase(i); //刪除所有值為i的元素
e.erase(e.find(i)) //刪除一個值為i的元素
e.count(i); //統計值為i的元素的數量
e.empty(); //判斷multiset是否為空
multiset<int>:: iterator rit; //定義迭代器
rit = (e.insert(j)).first //返回插入後元素對應的迭代器
rit=e.find(i); //返回第一個值為i的元素的迭代器，如果沒找到返回的是e.end()
rit=e.lower_bound(i) //返回值大於等於i的第一個元素的迭代器， 如果沒有大於等於i的元素返回e.end()
rit=e.upper_bound(i) //返回值大於i的第一個元素的迭代器， 如果沒有大於i的元素返回e.end()
for(rit=e.begin();rit!=e.end();rit++) //正序遍歷，值為*rit
set<int>::reverse_iterator rit; //反向遍歷的迭代器
for(rit=e.rbegin();rit!=e.rend();rit++) //反向遍歷必須這麼寫
//如使用結構體，必須重載< 或寫仿函數
註： 如希望用多種不同排序方式對set/multiset內元素進行排序， 則應該重載運算符， 寫成仿函數形式：
struct t {
int a, b, c;
};
struct cmp1
{
bool operator () (const t &x, const t &y)
{return x.a < y.a;}
};
struct cmp2
{
bool operator () (const t &x, const t &y)
{return x.b < y.b;}
};
struct cmp3
{
bool operator () (const t &x, const t &y)
{return x.c < y.c;}
};
set <t, cmp1> st;
set <t, cmp2> st2;
set <t, cmp3> st3;
8、map
#include <map>
map<string,int> f; //定義一個map，其中string是鍵值（就像一個人的名字一樣）的類型，int是值的類型，可以隨便換。 鍵值需要重載 <。
f[s]=d; //把一個鍵值為s，值為d的元素 插入到此map中或覆蓋原有映射（因為map重載了[]所以可以直接這樣寫）
f.count(s); //統計鍵值為s的元素的個數，因為在map中鍵值是排好序的集合，所以count()的返回值不是1就是0
f.erase(s); //刪掉鍵值是s的元素
f.size(); //取大小
f.empty(); //判斷map是否為空
map<string,int>:: iterator rit; //定義map的迭代器 ，遍歷的時候可能會用到
rit=f.find(s); //返回鍵值為s的元素的迭代器
rit->second; //迭代器為s映射的值，如把second改成first則是s
//查詢可以直接用[]
//map就像一個完美的哈希表，但內部由紅黑樹實現， 因此操作複雜度均為O(log(n))，有了map媽媽再也不用擔心查找數據了！
9、vector
#include <vector>
vector <int> vec; //定義一個vector， 內部元素類型為int。
vector <int>::iterator it; //定義vector<int> 的迭代器
vec.push_back(i) //向vec後面加入元素i
vec.push_front(i) //向vec前面加入元素i
vec.begin() //返回vec的第一個元素對應的迭代器， 如果為空返回vec.end()
vec.size() //返回vector內的元素個數
vec.erase(it) //刪除it對應元素， 同時後面的元素整體前移一位。 註： 複雜度為O(N)
vec.clear() //清空vec， 但不釋放記憶體
vector <int>().swap(vec) //清空vec並釋放記憶體（若卡記憶體，多組數據的題推薦這樣清零）
10、sort()
#include <algorithm>
vector <int> vec;
sort(vec.begin(), vec.end());//vector的sort方式
int a[105];
sort(a, a + 105);//將整個a數組從小到大排序
double b[1005];
bool cmp (double c, double d)//自定義排序方法
{return c > d;}
sort(b + 1, b + 1 + 1000, cmp)//將b[1] ~ b[1000]的元素從大到小排序
11、二分查找
註：lower_bound和upper_bound 使用前提均為原序列有序！
#include <algorithm>
int a[1005], pos;
int *b;
b = lower_bound(a + 1, a + 1001, i) //返回a[1] ~ a[1000]第一個大於等於i的元素的指針， 若沒有則返回a[1001]的指針
b = upper_bound(a + 1, a + 1001, i) //返回a[1] ~ a[1000]第一個大於i的元素的指針， 若沒有則返回a[1001]的指針
pos = b - a; //得到其下標
vector <int> vec;
vector <int>::iterator it;
it = lower_bound(vec.begin(), vec.end(), i) //返回vec中第一個大於等於i的元素的迭代器， 若沒有則返回vec.end()
it = upper_bound(vec.begin(), vec.end(), i) //返回vec中第一個大於i的元素的迭代器， 若沒有則返回vec.end()
set <int> st;
set <int>::iterator it;
it = st.lower_bound(st.begin(), st.end(), i) //返回st中第一個大於等於i的元素的迭代器， 若沒有則返回st.end()
it = st.lower_bound(st.begin(), st.end(), i) //返回st中第一個大於i的元素的迭代器， 若沒有則返回st.end()
12、reverse()
#include <algorithm>
int a[105];
reverse(a + 1, a + 1 + 100); //將a[1] ~ a[100]及其之間的元素前後翻轉
vector <int> vec;
reverse(vec.begin(), vec.end()) //前後翻轉整個vec裡面的元素
13、bitset
//bitset可以當bool數組用， 但其內部為unsigned int壓位而成， 支持左右移， 賦值， 清零等操作。 01背包用bitset優化可以做到O(N^2/32)
#include <bitset>
bitset <1005> bt; //聲明一個大小為1005的bitset
bt[0] = 1; //將bt[0]設為1
int a;
a = bt.count(); //返回bt中1的個數
bt.reset(); //將bt所有位清零
bt.set(); //將bt所有位設為1
bt.flip(); //將bt所有位異或1
bt.flip(i); //將bt第i位翻轉
bt = bt | (bt << 1) //將bt的第i位與第i + 1位取或， 複雜度為O(N/32)
bt = bt ^ (bt >> 2) //將bt的第i位和第i - 2位異或， 複雜度為O(N/32)
14、__builtin_系列
//以下函數複雜度均為O(1)
int a = __builtin_popcount(233) //返回233二進位位上1的個數
int b = __builtin_ffs(666) //返回666二進位位從低向高第一個1的位置
int c = __builtin_ctz(19260817) //返回19260817二進位位尾碼0的個數
//註： 以上函數所傳變數預設均為unsigned int， 若要傳long long 請在後面加上"ll"。
例如： int d = __builtin_popcountll(1000000000000ll);
