C++語言（2：標準庫）

.標準庫

注意

標準庫函數(shù)返回數(shù)值的類型大部分是size_t（unsigned long），不能直接與負數(shù)運算！

.1.標準模板庫（STL）函數(shù)和算法模板

比較和比較類型`less`、`greater`和`equal_to`

比較必須滿足嚴格弱序（《基礎(chǔ)算法3.4.嚴格弱序》）。

在STL中，若比較函數(shù)cmp(x,y)返回true，則認為元素x比元素y小。

比較類型cmptype：

struct cmptype
{
    bool operator () (const Node &x,const Node &y) const
    {
        return /*比較元素x,y的條件*/;
    }
};

比較函數(shù)cmp：

bool cmp(Node x,Node y)
{
    return /*比較元素x,y的條件*/;
}

less<type> cmp;cmp(x,y);：比較類型less<type>定義一個比較函數(shù)cmp，cmp返回命題“元素x小于元素y”的布爾值，元素需有<的定義，O(Compare)。

greater<type> cmp;cmp(x,y);：比較類型greater<type>定義一個比較函數(shù)cmp，cmp返回命題“元素x大于元素y”的布爾值，故常作為反向比較，元素需有>的定義，O(Compare)。

equal_to<type> cmp;cmp(x,y);：比較類型equal_to<type>定義一個比較函數(shù)cmp，cmp返回命題“元素x等于元素y”的布爾值，元素需有==的定義，O(Compare)。

哈希和哈希類型`hash`

哈希必須滿足相等的對象產(chǎn)生相同的哈希值。

哈希類型hashtype：

struct hashtype
{
    size_t operator () (const Node &x) const
    {
        return /*元素x的哈希值計算*/;
    }
};

hash<type> hsh;hsh(x);：哈希類型hash<type>定義一個哈希函數(shù)hsh，hsh返回元素x的哈希值，元素需有哈希函數(shù)的定義，O(Calculate_Hash)。

最小值`min`和最大值`max`

根據(jù)比較函數(shù)cmp來比較大小，當cmp缺省時默認為less<type>()。

min(x,y,cmp)：返回元素x和元素y的最小值，O(Compare)。

max(x,y,cmp)：返回元素x和元素y的最大值，O(Compare)。

交換`swap`

swap(x,y)：交換兩個元素x,y，O(1)。

翻轉(zhuǎn)`reverse`

reverse(bg,ed)：將序列中[bg,ed)翻轉(zhuǎn)，O(n)。

排序`sort`

底層結(jié)構(gòu)：內(nèi)省排序。

sort(bg,ed,cmp)：將序列中[bg,ed)排序。根據(jù)比較函數(shù)cmp（注意嚴格弱序）來比較大小，當cmp缺省時默認為less<type>()。較小的元素排在前面。每個元素最壞參與O(log n)次比較，O((log n)*n*Compare)。

bool cmp(type x,type y)
{
    return /*若返回true，則x排在y前面。注意嚴格弱序。*/;
}

//sort(a+l,a+r+1);//將a[l]~a[r]按從小到大排序。需有小于號的定義。
//sort(a+l,a+r+1,greater<type>());//將a[l]~a[r]按從大到小排序。需有大于號的定義。
sort(a+l,a+r+1,cmp);//將a[l]~a[r]按cmp排序。

穩(wěn)定排序`stable_sort`

底層結(jié)構(gòu)：歸并排序。

與sort用法相同。穩(wěn)定排序，相同元素的相對順序保持不變。效率比sort低。

去重`unique`

unique(bg,ed,cmp)：若比較函數(shù)cmp(x,y)返回true，則認為元素x和元素y重復(fù)，當cmp缺省時默認為equal_to<type>()。將滿足重復(fù)元素相鄰排列（通常配合sort使用）的序列中[bg,ed)去重，返回去重之后末尾元素的下一個位置的迭代器。去重之后末尾元素后面保留最初的序列的部分。O(n*Compare)。

第n小元素`nth_element`

根據(jù)比較函數(shù)cmp來排序元素和比較大小，當cmp缺省時默認為less<type>()。

nth_element(bg,nth,ed,cmp)：將序列中[bg,ed)重新分配順序，順序位于nth的元素x分配在nth，小于或者等于x的元素分配在[bg,nth)，大于或者等于x的元素分配在(nth,ed)，O(n*Compare)。

nth_element(a+l,a+l+k-1,a+r+1,cmp);//將a[l]~a[r]重新分配順序，第k小的元素分配在l+k-1，小于或者等于第k小的元素的元素分配在[l,l+k-1)，大于或者等于第k小的元素的元素分配在(l+k-1,r]

二分`lower_bound`和`upper_bound`

在按照比較函數(shù)cmp（當cmp缺省時默認為less<type>()）排序后的序列中：

根據(jù)cmp來比較大小，根據(jù)cmp的等價傳遞性來判斷相等。

lower_bound(bg,ed,x,cmp)：在序列中[bg,ed)二分查找最前一個大于或者等于x的元素，并且返回指向該元素的迭代器，若不存在則返回ed。

upper_bound(bg,ed,x,cmp)：在序列中[bg,ed)二分查找最前一個大于x的元素，并且返回指向該元素的迭代器，若不存在則返回ed。

通過將返回的迭代器減去bg，得到找到的元素的位置。

O((log n)*Compare)，需要容器支持O(1)隨機訪問（例如 []），否則復(fù)雜度無法保證。

上、下一個排列`prev_permutation`、`next_permutation`

next_permutation(bg,ed)：整數(shù)序列中[bg,ed)是一個排列，若它已經(jīng)是全排列中字典序排在最后一個的排列（元素完全從大到小排列），則將它更改為全排列中字典序排在第一個的排列（元素完全從小到大排列）并且返回false；否則，將它更改為全排列中字典序排在下一個的排列并且返回 true。O(n)。

prev_permutation(bg,ed)同理。

.2.標準模板庫（STL）容器

迭代器

conttype::iterator it：聲明一個訪問容器類型為conttype的迭代器it，O(1)。

conttype::reverse_iterator it：聲明一個訪問容器類型為conttype的反向迭代器it，O(1)。

*：返回迭代器指向的元素。迭代器不可是end()，反向迭代器不可是rend()。O(1)。

->：返回迭代器指向的元素的成員。迭代器不可是end()，反向迭代器不可是rend()。O(1)。

容器

時空復(fù)雜度與當前存儲元素數(shù)量n相關(guān)。

當使用刪除元素類或查詢元素類操作時，需要保證容器非空。

=：拷貝賦值，O(n*Copy)。

<=>：按照字典序比較兩個容器，O(min(n_1,n_2)*Compare)。

map相當于set<pair<key,value>>。

無序容器僅支持==和!=，O(n*Hash*Compare)，最壞O((n^2)*Compare)。

begin()：返回首迭代器，O(1)。

end()：返回尾迭代器，O(1)。

rbegin()：返回反向首迭代器，O(1)。

rend()：返回反向尾迭代器，O(1)。

empty()：返回命題“是否為空”的布爾值，O(1)。

size()：返回當前存儲的元素的個數(shù)，O(1)。

swap(b)：和容器b交換，O(1)。

徹底釋放容器空間，O(n)：type().swap(a)。

clear()：清空，O(n)。

.2.1.向量`vector`

底層結(jié)構(gòu)：動態(tài)數(shù)組。

支持O(1)隨機訪問。

聲明

vector<type> a：聲明一個a，O(1)。

vector<type> a(n,x)：聲明一個大小為n的a，并且所有元素都為x，當x缺省時默認為zero，O(n*New)。

vector<vector<type>> a(n,vector<type>(m,x))：聲明一個大小為n*m的a，并且所有元素都為x，當x缺省時默認為zero，O(nm*New)。

迭代器

++、--：迭代器遞增（變?yōu)橹赶蚝笠粋€元素的迭代器）、遞減（變?yōu)橹赶蚯耙粋€元素的迭代器）。迭代器分別不可是end()、begin()，反向迭代器分別不可是rend()、rbegin()。O(1)。

+、-：迭代器是隨機訪問迭代器，和指針一樣支持加減運算，O(1)。

迭代器失效：在容量變動后，所有迭代器可能失效。

運算符

[pos]：返回下標為pos的元素的引用，O(1)。

函數(shù)

capacity()：返回實際使用內(nèi)存（單位是元素個數(shù)），O(1)。

front()：返回最前一個元素，O(1)。

back()：返回最后一個元素，O(1)。

push_back(x)：向最后插入一個元素x，O(1)。

pop_back()：刪除最后一個元素，O(1)。

resize(m,x)：調(diào)整大小至m，調(diào)大則在新增的位置填充元素x，調(diào)小則在刪減的位置刪除元素，當x缺省時默認為zero，O(max(|m-n|*New,m))。

shrink_to_fit()：釋放多余的內(nèi)存，O(n)。

注意：只有該函數(shù)才會釋放內(nèi)存。clear()和resize()等不會釋放內(nèi)存。

遍歷

O(n)。

//方法一
for(type x : a) cout<<x<<" ";//type可以寫為auto

//方法二
for(size_t i=0;i<a.size();i++) cout<<a[i]<<" ";

//方法三
for(vector<type>::iterator it=a.begin();it!=a.end();it++) cout<<*it<<" ";//vector<type>::iterator可以寫為auto

注意

錯誤的寫法：~~vector<int> a;a.push_back(6);auto it=lower_bound(a.begin(),a.end(),6);a.push_back(8);cout<<*it;~~：vector在插入元素后，所有迭代器可能失效。

.2.2.雙端隊列`deque`

底層結(jié)構(gòu)：分塊數(shù)組。

支持O(1)隨機訪問。性能比vector差。

聲明

deque<type> a：聲明一個a，O(1)。

迭代器

+、-：迭代器是隨機訪問迭代器，和指針一樣支持加減運算，O(1)。

迭代器失效：在容量變動后，所有迭代器可能失效。

運算符

[pos]：返回下標為pos的元素的引用，O(1)。

最前一個元素的下標始終保持是0。

函數(shù)

front()：返回最前一個元素，O(1)。

back()：返回最后一個元素，O(1)。

push_front(x)：向最前插入一個元素x，O(1)。

push_back(x)：向最后插入一個元素x，O(1)。

pop_front()：刪除最前一個元素，O(1)。

pop_back()：刪除最后一個元素，O(1)。

遍歷

和vector同理。

注意

deque基于分塊數(shù)組，因此deque即使是空的或者只存儲少量元素，也會至少占用一個完整的塊的空間（e.g.512字節(jié)）。

.2.3.有序集合`set`和有序多重集合`multiset`

底層結(jié)構(gòu)：紅黑樹。

不支持隨機訪問。

set元素自動去重，multiset元素可以重復(fù)。

聲明

set<type,cmptype> a，multiset<type,cmptype> a：聲明一個存儲元素類型是type、比較類型是cmptype的a，當cmptype缺省時默認為less<type>，O(1)。

根據(jù)cmptype來排序元素和比較大小，較小的元素排在前面，根據(jù)cmptype的等價傳遞性來判斷兩個元素是否相等。

迭代器

++、--：迭代器遞增（變?yōu)橹赶蚝笠粋€元素的迭代器）、遞減（變?yōu)橹赶蚯耙粋€元素的迭代器）。迭代器分別不可是end()、begin()，反向迭代器分別不可是rend()、rbegin()。單次O(log n)，當單向遍歷全集時均攤O(1)。

迭代器失效：在刪除元素后，只有被刪除元素的迭代器失效。

函數(shù)

insert(x)：插入一個元素x，并且set返回pair<iterator,bool>，first是指向插入元素或已存在元素的迭代器，second是表示插入是否成功（set若元素已存在，則不會插入重復(fù)元素）；multiset返回指向插入元素的迭代器。O((log n)*Compare)。

erase(x)：刪除所有等于x的元素，并且返回被刪除的元素數(shù)量，x可以不存在，O((log n)*Compare+Cnt)。

erase(it)：刪除迭代器it指向的元素，并且返回被刪除元素的后繼元素的迭代器，it不可以為end()，O(log n)。

multiset刪除一個等于x的元素，O((log n)*Compare)：

auto it=a.find(x);
if(it!=a.end()) a.erase(it);

find(x)：查找最前一個等于x的元素，并且返回對應(yīng)的迭代器，若不存在則返回end()，O((log n)*Compare)。

count(x)：返回等于x的元素的數(shù)量，O((log n)*Compare+Cnt)。

lower_bound(x)：二分查找最前一個滿足大于或者等于x的元素，并且返回指向該元素的迭代器，若不存在則返回end()，O((log n)*Compare)。

upper_bound(x)：二分查找最前一個滿足大于x的元素，并且返回指向該元素的迭代器，若不存在則返回end()，O((log n)*Compare)。

有序插入

insert(it,x)：使用提示迭代器it插入一個元素x。若提示正確（it指向的元素小于等于x并且后繼元素大于等于x），則在it后插入x，當有序插入全集時均攤O(1)；否則，重新查找正確位置插入x，O(log n)。并且若插入成功，則返回指向x的迭代器；否則，返回指向已存在元素的迭代器。

利用提示迭代器插入一個有序序列b的復(fù)雜度為O(n)。

set<int>::iterator it=a.begin();//set<int>::iterator可以寫為auto
for(auto x : b) it=a.insert(it,x);

//multiset同理

遍歷

遍歷的復(fù)雜度為O(n)。

//方法一
for(type x : a) cout<<x<<" ";//type可以寫為auto

//方法二
for(set<type>::iterator it=a.begin();it!=a.end();it++) cout<<*it<<" ";//set<type>::iterator可以寫為auto

//multiset同理

注意

錯誤的寫法：~~auto it=lower_bound(s.begin(),s.end(),x);~~：因為不支持隨機訪問，所以這種寫法的時間復(fù)雜度為O(n)。

.2.4.有序映射`map`

底層結(jié)構(gòu)：紅黑樹。

map相當于set<pair<type1,type2>>，因此下文只寫map的優(yōu)勢部分。

聲明

map<type1,type2,cmptype> a;：聲明一個存儲鍵元素類型是type1、值元素類型是type2、針對type1的比較類型是cmptype的a，當cmptype缺省時默認為less<type>，O(1)。

根據(jù)cmptype來排序元素，根據(jù)cmptype的等價傳遞性來判斷兩個鍵元素是否相等。

運算符

[x]：查找等于x的鍵，并且返回x映射到的值y的引用，若不存在則先自動插入映射元素{x,y=zero}再返回y的引用，O((log n)*Compare)。

可以在使用[x]之前使用find()檢查x的存在性，以避免自動插入過多的{x,zero}。

函數(shù)

erase(x)：刪除等于x的鍵和對應(yīng)的映射元素，并且返回被刪除的映射元素數(shù)量，x可以不存在，O((log n)*Compare)。

find(x)：查找等于x的鍵，并且返回指向?qū)?yīng)的映射元素的迭代器，若不存在則返回end()，O((log n)*Compare)。

.2.5.無序映射`unordered_map`

底層結(jié)構(gòu)：哈希表。

聲明

unordered_map<type1,type2,hashtype,cmptype> a;：聲明一個存儲鍵元素類型是type1、值元素類型是type2、針對鍵元素的哈希類型是hashtype、針對鍵元素的比較類型cmptype的a，當hashtype、cmptype缺省時分別默認為hash<type>、equal_to<type>，O(1)。

若hash(x)等于hash(y)并且cmp(x,y)返回true，則認為兩個鍵元素x,y相等。

運算符

[x]：查找等于x的鍵，并且返回x映射到的值y的引用，若不存在則先自動插入映射元素{x,y=zero}再返回y的引用，O(Hash*Compare)，最壞O(n*Compare)。

可以在使用[x]之前使用find()檢查x的存在性，以避免自動插入過多的{x,zero}。

函數(shù)

erase(x)：刪除等于x的鍵和對應(yīng)的映射元素，并且返回被刪除的映射元素數(shù)量，x可以不存在，O(Hash*Compare)，最壞O(n*Compare)。

find(x)：查找等于x的鍵，并且返回指向?qū)?yīng)的映射元素的迭代器，若不存在則返回end()，O(Hash*Compare)，最壞O(n*Compare)。

.3.標準模板庫（STL）容器適配器

時空復(fù)雜度與當前存儲元素數(shù)量n相關(guān)。

不支持隨機訪問和迭代器。

當使用刪除元素類或查詢元素類操作時，需要保證容器非空。

=：拷貝賦值，O(n*Copy)。

empty()：返回命題“是否為空”的布爾值，O(1)。

size()：返回當前存儲元素個數(shù)，O(1)。

swap(b)：和容器b交換，O(1)。

徹底釋放容器空間，O(n)：type().swap(a)。

.3.1.棧`stack`和隊列`queue`

底層結(jié)構(gòu)：基于底層容器（默認deque）。

聲明

stack<type,conttype> a、queue<type,conttype> a：聲明一個存儲元素類型是type、底層容器類型是conttype的a，當conttype缺省時默認為deque<type>，O(1)。

運算符

<=>：按照字典序比較兩個容器，O(min(n_1,n_2)*Compare)。

函數(shù)

push(x)：向最后插入一個元素x，O(1)。

pop()：

stack：刪除最后一個元素，O(1)。

queue：刪除最前一個元素，O(1)。

top()：stack：返回最后一個元素，O(1)。

front()：queue：返回最前一個元素，O(1)。

back()：queue：返回最后一個元素，O(1)。

注意

stack和queue默認基于deque，因此也會有deque的空間注意事項，可以令conttype為list<type>來解決。

.3.2.優(yōu)先隊列`priority_queue`

底層結(jié)構(gòu)：基于底層容器（默認vector），并使用大根堆算法。

聲明

priority_queue<type,conttype,cmptype> a：聲明一個存儲元素類型是type、底層容器類型是conttype、比較類型是cmptype的a，當conttype缺省時默認為vector<type>，當cmptype缺省時默認為less<type>，O(1)。

根據(jù)cmptype來排序元素和比較大小，最大的元素排在堆頂top()。

函數(shù)

push(x)：插入一個元素x，O(log n*Compare)。

pop()：刪除一個最大的元素，O(log n*Compare)。

top()：返回最大的元素，O(1)。

技巧

懶惰刪除法

priority_queue不支持隨機刪除操作。當遇到刪除操作時，可以使用其他的數(shù)據(jù)結(jié)構(gòu)維護一些信息（e.g.數(shù)組記錄元素的最新值），用于后面在使用最大的元素時檢查是否已被刪除。
結(jié)構(gòu)體小于號的定義：

struct Node
{
    bool operator < (const Node & that) const
    {
        return ;//返回false的排在堆頂top
    }
};
priority_queue<Node> q;

.4.其他常用內(nèi)容

.4.1.字符串`string`

底層結(jié)構(gòu)：類似vector<char>。

支持O(1)隨機訪問。

時空復(fù)雜度與當前字符串長度n相關(guān)。

string相當于vector<char>，因此下文只寫string的優(yōu)勢部分。

聲明

string a：聲明一個a，O(1)。

讀入和輸出

cin、cout：和字符數(shù)組一樣。cin讀入空白字符停止。

getline(cin,a)：整行讀入至字符串a(chǎn)。

運算符

[pos]：返回下標為pos的字符的引用，O(1)。

=：拷貝賦值，O(n)。

<=>：按照字典序比較兩個字符串，O(min(n_1,n_2))。

對n個字符串執(zhí)行sort，這個n個字符串的總長度是m，復(fù)雜度是O((log n)*m)。

+：返回兩個字符串的拼接字符串，O(n_1+n_2)。

+=：在本字符串后拼接（長度為m的）字符串，O(m)。

函數(shù)

size()、length()：返回當前字符串長度，O(1)。

c_str()：返回C風(fēng)格字符串const char*，O(1)。

find(str,pos)：查找并返回從下標pos開始（含pos）最前出現(xiàn)（長度為m的）字符串str的首字符下標，若不存在則返回string::npos（被定義為-1的size_t），當pos缺省時默認為0，O(nm)。

substr(pos,len)：返回從下標pos開始（含pos）截取長度為len的字符串，若從pos開始的后綴的長度小于len則返回這個后綴，當len缺省時返回從pos開始的后綴，O(len)。

swap(b)：和字符串b交換，O(1)。

徹底釋放字符串空間，O(n)：string().swap(a)。

遍歷

O(n)。

//方法一
for(char x : a) cout<<x<<" ";//char可以寫為auto

//方法二
for(size_t i=0;i<a.size();i++) cout<<a[i]<<" ";

//方法三
for(string::iterator it=a.begin();it!=a.end();it++) cout<<*it<<" ";//string::iterator可以寫為auto

.4.2.位集合`bitset`

底層結(jié)構(gòu)：固定大小的位數(shù)組。

支持O(1)隨機訪問。

時空復(fù)雜度與聲明的位集合大小N相關(guān)。

聲明

bitset<N> a：聲明一個大小為N的a，初值是false，O(N/w)。

運算符

[pos]：返回第pos位的引用，O(1)。

&、&=、|、|=、^、^=、~、<<、<<=、>>、>>=：N位二進制數(shù)的位運算，O(N/w)。

=：拷貝賦值，O(N/w)。

==、!=：判斷兩個大小為N的位集合是否相等、不相等，O(N/w)。

函數(shù)

size()：返回位集合的大小，O(1)。

count()：返回值為true的位的個數(shù)，O(N/w)。

all()：返回命題“所有位為true”的布爾值，O(N/w)。

any()：返回命題“至少有一位為true”的布爾值，O(N/w)。

none()：返回命題“所有位為false”的布爾值，O(N/w)。

set()：把所有位設(shè)置為true，O(N/w)。

reset()：把所有位設(shè)置為false，O(N/w)。

flip()：把所有位取反，O(N/w)。

遍歷

_Find_first()：查找并返回最前的值為true的位的下標，O(len/w)，其中l(wèi)en是該位的下標。

_Find_next(pos)：查找并返回在第pos位之后（不含pos）最前的值為true的位的下標，O(len/w)，其中l(wèi)en是該位和pos的距離。

遍歷所有值為true的位的下標的復(fù)雜度是O(N/w+m)，其中m是值為true的位的個數(shù)。

for(size_t i=a._Find_first();i<a.size();i=a._Find_next(i))

.4.3.隨機

random_device srd;srd();：隨機數(shù)生成器類型random_device定義一個隨機數(shù)生成器srd，隨機數(shù)函數(shù)srd()返回一個在unsigned int的范圍（[0,2^32-1]）內(nèi)的隨機數(shù)，O(1)。

真隨機數(shù)，來源于操作系統(tǒng)的熵池。但性能慢，故用于生成隨機種子而非隨機數(shù)。

random_device srd;
unsigned int r=srd();

mt19937_64 gen(seed);gen();：隨機數(shù)生成器類型mt19937_64定義一個隨機種子為seed的隨機數(shù)生成器gen，隨機數(shù)函數(shù)gen()返回一個使用seed生成的在unsigned long long的范圍（[0,2^64-1]）內(nèi)的隨機數(shù)，當seed缺省時默認為默認隨機種子，O(1)。

偽隨機數(shù)。注意要先隨機種子，可以利用真隨機數(shù)(random_device()())來隨機種子。

mt19937_64 gen((random_device()()));//注意要先隨機種子
unsigned long long r=gen();

mt19937 gen(seed);gen();：隨機數(shù)生成器類型mt19937定義一個隨機種子為seed的隨機數(shù)生成器gen，隨機數(shù)函數(shù)gen()返回一個使用seed生成的在unsigned int的范圍（[0,2^32-1]）內(nèi)的隨機數(shù)，當seed缺省時默認為默認隨機種子，O(1)。

其他地方與mt19937_64相同。
uniform_int_distribution<type> dist(l,r);dist(gen);：隨機數(shù)分布類型uniform_int_distribution<type>定義一個隨機數(shù)類型為type、范圍為[l,r]的隨機數(shù)均勻分布函數(shù)dist，dist返回一個利用隨機數(shù)生成器（e.g.mt19937_64()）gen和均勻分布來生成的在[l,r]內(nèi)的隨機整數(shù)。不可l>r。當l、r缺省時分別默認為0、type的最大值numeric_limits<type>::max()。O(1)。
uniform_real_distribution<type> dist(l,r);dist(gen);：隨機數(shù)分布類型uniform_real_distribution<type>定義一個隨機數(shù)類型為type、范圍為[l,r)的隨機數(shù)均勻分布函數(shù)dist，dist返回一個利用隨機數(shù)生成器（e.g.mt19937_64()）gen和均勻分布來生成的在[l,r)內(nèi)的隨機實數(shù)。當l>r時自動交換邊界。當l、r缺省時分別默認為0.0、1.0。O(1)。

隨機整數(shù)[l,r]

mt19937_64 gen((random_device()()));

type rnd(type l,type r)
{
    uniform_int_distribution<type> dist(l,r);
    return dist(gen);
}

隨機實數(shù)

[l,r)

mt19937_64 gen((random_device()()));

type rnd(type l,type r)
{
    uniform_real_distribution<type> dist(l,r);
    return dist(gen);
}

[l,r]

mt19937_64 gen((random_device()()));

type rnd(type l,type r)
{
    uniform_real_distribution<type> dist(l,nextafter(r,numeric_limits<type>::max()));
    return dist(gen);
}

隨機排列`shuffle`

shuffle(bg,ed,gen)：利用隨機數(shù)生成器（e.g.mt19937_64()）gen來打亂序列中[bg,ed)的順序，當缺省gen時默認為默認隨機種子。O(n)。

posted @ 2025-09-29 17:08 Brilliance_Z 閱讀(230) 評論(0) 收藏舉報

刷新頁面返回頂部

BrillianceZ

C++語言（2：標準庫）

.標準庫

注意

.1.標準模板庫（STL）函數(shù)和算法模板

比較和比較類型less、greater和equal_to

哈希和哈希類型hash

最小值min和最大值max

交換swap

翻轉(zhuǎn)reverse

排序sort

穩(wěn)定排序stable_sort

去重unique

第n小元素nth_element

二分lower_bound和upper_bound

上、下一個排列prev_permutation、next_permutation

.2.標準模板庫（STL）容器

迭代器

容器

.2.1.向量vector

聲明

迭代器

運算符

函數(shù)

遍歷

注意

.2.2.雙端隊列deque

聲明

迭代器

運算符

函數(shù)

遍歷

注意

.2.3.有序集合set和有序多重集合multiset

聲明

迭代器

函數(shù)

有序插入

遍歷

注意

.2.4.有序映射map

聲明

運算符

函數(shù)

.2.5.無序映射unordered_map

聲明

運算符

函數(shù)

.3.標準模板庫（STL）容器適配器

.3.1.棧stack和隊列queue

聲明

運算符

函數(shù)

注意

.3.2.優(yōu)先隊列priority_queue

聲明

函數(shù)

技巧

.4.其他常用內(nèi)容

.4.1.字符串string

聲明

讀入和輸出

運算符

函數(shù)

遍歷

.4.2.位集合bitset

聲明

運算符

函數(shù)

遍歷

.4.3.隨機

隨機整數(shù)[l,r]

隨機實數(shù)

隨機排列shuffle

公告

比較和比較類型`less`、`greater`和`equal_to`

哈希和哈希類型`hash`

最小值`min`和最大值`max`

交換`swap`

翻轉(zhuǎn)`reverse`

排序`sort`

穩(wěn)定排序`stable_sort`

去重`unique`

第n小元素`nth_element`

二分`lower_bound`和`upper_bound`

上、下一個排列`prev_permutation`、`next_permutation`

.2.1.向量`vector`

.2.2.雙端隊列`deque`

.2.3.有序集合`set`和有序多重集合`multiset`

.2.4.有序映射`map`

.2.5.無序映射`unordered_map`

.3.1.棧`stack`和隊列`queue`

.3.2.優(yōu)先隊列`priority_queue`

.4.1.字符串`string`

.4.2.位集合`bitset`

隨機排列`shuffle`