小結C++中一些自帶的好用東西

?

STL部分

<set>/<multiset>

支持插入一個元素，刪除指定key值的元素，查找指定key值的元素，返回最大/小值，找前驅，找后繼，返回指定key值的相同元素個數。

部分代替平衡樹中一些操作。不能updata或push_down之類的操作，也不能找第K大等。

set的cmp可以自己寫，這給我們帶來了不少方便。

*如果在set中按key1比較是有序的，且key2也是有序的。此時我們要找指定key2時就可以在cmp函數中人工設置一個開關來解決。也就是說set中的查找要保證key是有序的。如NOI2007cash一題。

?

<map>/<multimap>

與set不同之處在于map是一個映射，可以知道指定key值的一個映射（數據）。

在時間要求不是很苛刻的情況下，可以代替Hash。如記憶化搜索。

可以代替鏈表，即動態開空間。如AC自動機中son。

可以嵌套數據結構。如map套set。

<stack>棧

<queue>隊列

<deque>雙端隊列

<vector>/<list>

類似于線性表一樣的東西。

很大一個好處是內存是動態的。

?

?

一些線性表基本操作

?

??? 如果數據是線性有序的，就可以二分。???

???? Lower_bound(S,T,key)：找第一個大于等于key的。

???? upper_bound(S,T,key)：找第一個大于key的。

??? 當然也可以這么干

??? upper_bound(S,T,key)-1：找第一個小于等于key的。

??? Lower_bound(S,T,key)-1：找第一個小于key的。

??? binary_search(S,T,key)：判斷關鍵字為key的是否存在。

?

Reverse(S,T)：翻轉

Unique(S,T)：去重

min_element:返回最大

max_element：返回最小

next_permutation：下一個排列

prev_permutation:上一個排列

random_shuffle:隨機生成一個元素的排列

?

其他

<complex>

?????? 虛數的使用。

?