關于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);
轉自http://ybt.ssoier.cn:8087
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/553631.html
標籤：其他
下一篇：返回列表