補(bǔ)充bitset+容器使用建議

bitset（可當(dāng)作一個(gè)bool類型的集合）

bitset類相當(dāng)于一個(gè)二進(jìn)制集合，并且能處理超過long long類型大小的位集合。

bitset可以與string和整型相互轉(zhuǎn)化。

1.bitset對象的定義和初始化方法（n是一個(gè)大于0的整形字面值常量）

※ bitset<n> b(u);等價(jià)于bitset<n> b=u;

以string賦值bitset的例子：

2.bitset支持的操作（bitset可當(dāng)作一個(gè)bool類型的集合）

※ 需要特別注意bitset的下標(biāo)是從最右邊開始的?。。ㄈ鏱itset<4> b=2;(此時(shí)b是0010)中b[1]為1而不是0）

3.bitset實(shí)現(xiàn)整數(shù)十進(jìn)制與二進(jìn)制的相互表示

1）十進(jìn)制到二進(jìn)制：cin>>n;cout<<bitset<8>(n);（此處n為十進(jìn)制數(shù)；bitset長度為8，但可按需改變）

2）二進(jìn)制到十進(jìn)制：cin>>b;cout<<b.to_ulong();（此處b為一個(gè)bitset）

function類型和函數(shù)式編程

1.function類型

function<T>可以看作是一個(gè)函數(shù)的“容器”。創(chuàng)建其時(shí)，需要額外提供能夠表示函數(shù)的類型信息，即需要向function類型提供想讓它封裝的函數(shù)的【返回類型以及參數(shù)列表】。如下定義了一個(gè)接受兩個(gè)char類型參數(shù)，返回一個(gè)int類型參數(shù)的函數(shù)的function類型對象：

因此對f賦值時(shí)，應(yīng)賦予其一個(gè)函數(shù)對象，且該函數(shù)對象的參數(shù)列表和返回類型都應(yīng)與f封裝的函數(shù)對象的參數(shù)列表和返回類型相匹配。例如：

2.函數(shù)式編程

函數(shù)式編程就是把函數(shù)當(dāng)作普通的變量一樣使用。同樣的，可以定義一個(gè)函數(shù)，讓它以另一個(gè)函數(shù)對象為參數(shù)。如下展示了find_if算法的簡單實(shí)現(xiàn)：

命名沖突

在定義的函數(shù)名已經(jīng)存在在C++標(biāo)準(zhǔn)庫中時(shí)，會造成編譯錯誤，稱其為命名沖突。

錯誤提示通常是：error:reference to '###' is ambiguous，'###'表示發(fā)生命名沖突的名字。

出現(xiàn)這種錯誤提示后，將原來命名的函數(shù)改為首字母大寫或換名即可。

容器的關(guān)系運(yùn)算

1.前面章節(jié)所敘述的所有容器均支持==與!=運(yùn)算符；除無序關(guān)聯(lián)容器以外的所有容器均支持比較運(yùn)算符（<、<=、>、>=）。

2.由于容器支持關(guān)系運(yùn)算，所以容器之間不僅可使用關(guān)系運(yùn)算符直接比較，還可以將容器作為參數(shù)傳遞給max、min等函數(shù)。

容器選擇建議（根據(jù)順序容器、關(guān)聯(lián)容器、容器適配器的性質(zhì)（見4、6、7章））

①除非有更好的理由選擇其他容器，否則應(yīng)使用vector（默認(rèn)首選vector）。

②程序要求在容器中間插入或刪除元素，使用list（雙向鏈表任何位置增刪都快，但沒法隨機(jī)訪問）。

③程序不會在中間插入刪除，但可能在頭尾插入刪除元素，分以下情況（結(jié)合數(shù)據(jù)結(jié)構(gòu)即可，不用刻意記）：

1）在尾部插入刪除，若不要求隨機(jī)訪問，使用stack棧（LIFO），否則使用vector。（容器適配器不支持隨機(jī)訪問，vector也可作為stack的底層實(shí)現(xiàn)）

2）在頭部插入刪除，若不要求隨機(jī)訪問，使用queue隊(duì)列（FIFO），否則使用deque。（容器適配器不支持隨機(jī)訪問，deque一般作為queue的底層實(shí)現(xiàn)）

3）頭尾都有插入刪除，使用deque（雙端隊(duì)列頭尾增刪都快）。

④使用string存儲字符串，棄用字符數(shù)組（內(nèi)置數(shù)組等同array，不可增刪元素不便于操作）。

⑤使用pair或tuple時(shí)，若持有的元素類型都相同（假設(shè)為T），應(yīng)用array<T,2>代替pair<T,T>，用array<T,n>代替tuple<T,T,...,T>（n為tuple的元素個(gè)數(shù)）。因?yàn)閍rray支持下標(biāo)運(yùn)算符，訪問元素更方便。

⑥程序要求對序列去重，可以直接使用set或unordered_set（關(guān)鍵字不可重復(fù)，故會自動去重），而不要使用unique，因?yàn)閡nique去重只針對相鄰的元素，要對整個(gè)序列去重還要先排序，效率低下。

⑦要求建立兩種數(shù)據(jù)之間的映射關(guān)系，可以使用unordered_map或map。

⑧vector+sort與set、map（即靜態(tài)用前者、實(shí)時(shí)用后者）：若要求一邊保持元素有序，一邊還要插入新的元素或刪除元素，使用set、map（若元素不會重復(fù)，用set；否則用map，鍵表示元素，值表示該元素出現(xiàn)的次數(shù)），否則使用vector+sort。

⑨程序不要求元素有序，但要求每次找出容器中某種規(guī)則下最優(yōu)的元素，使用priority_queue，其在類似的復(fù)雜情景模擬題中特別好用。

泛型算法使用建議

①容器適配器不支持迭代器，因此不能使用泛型算法。且一般只對順序容器使用泛型算法。

②對同個(gè)算法，若有泛型算法和容器的成員函數(shù)版本，優(yōu)先使用容器的成員函數(shù)版本。例如list的成員函數(shù)版本的remove和unique。

③若使用可以接收函數(shù)對象的泛型算法，應(yīng)盡可能地傳遞lambda表達(dá)式作參數(shù)。

④lambda表達(dá)式的參數(shù)最好都設(shè)置為常引用類型，即lambda表達(dá)式內(nèi)的代碼不應(yīng)該改變參數(shù)的值。lambda表達(dá)式中代碼邏輯也應(yīng)盡量簡單，一般在1~5行為宜。