C++ STL 一般總結(jié)

以下內(nèi)容來源網(wǎng)上 經(jīng)過整合而成

一、一般介紹

      STL（Standard Template Library），即標(biāo)準(zhǔn)模板庫，是一個具有工業(yè)強(qiáng)度的，高效的C++程序庫。它被容納于C++標(biāo)準(zhǔn)程序庫（C++ Standard Library）中，是ANSI/ISO C++標(biāo)準(zhǔn)中最新的也是極具革命性的一部分。該庫包含了諸多在計(jì)算機(jī)科學(xué)領(lǐng)域里所常用的基本數(shù)據(jù)結(jié)構(gòu)和基本算法。為廣大C++程序員們提供了一個可擴(kuò)展的應(yīng)用框架，高度體現(xiàn)了軟件的可復(fù)用性。

      從邏輯層次來看，在STL中體現(xiàn)了泛型化程序設(shè)計(jì)的思想（generic PRogramming），引入了諸多新的名詞，比如像需求（requirements），概念（concept），模型（model），容器（container），算法（algorithmn），迭代子（iterator）等。與OOP（object-oriented programming）中的多態(tài)（polymorphism）一樣，泛型也是一種軟件的復(fù)用技術(shù)；

       從實(shí)現(xiàn)層次看，整個STL是以一種類型參數(shù)化（type parameterized）的方式實(shí)現(xiàn)的，這種方式基于一個在早先C++標(biāo)準(zhǔn)中沒有出現(xiàn)的語言特性--模板（template）。如果查閱任何一個版本的STL源代碼，你就會發(fā)現(xiàn)，模板作為構(gòu)成整個STL的基石是一件千真萬確的事情。除此之外，還有許多C++的新特性為STL的實(shí)現(xiàn)提供了方便；

二、STL的六大組件

以下主要討論：容器，迭代器，算法，適配器。如欲詳加了解 參見C++ Primer 

1.STL容器

1）序列式容器（Sequence containers），每個元素都有固定位置－－取決于插入時機(jī)和地點(diǎn)，和元素值無關(guān)，vector、deque、list；

   Vectors：將元素置于一個動態(tài)數(shù)組中加以管理，可以隨機(jī)存取元素（用索引直接存取），數(shù)組尾部添加或移除元素非常快速。但是在中部或頭部安插元素比較費(fèi)時；

   Deques：是“double-ended queue”的縮寫，可以隨機(jī)存取元素（用索引直接存取），數(shù)組頭部和尾部添加或移除元素都非常快速。但是在中部或頭部安插元素比較費(fèi)時；

   Lists：雙向鏈表，不提供隨機(jī)存取（按順序走到需存取的元素，O(n)），在任何位置上執(zhí)行插入或刪除動作都非常迅速，內(nèi)部只需調(diào)整一下指針；

2）關(guān)聯(lián)式容器（Associated containers），元素位置取決于特定的排序準(zhǔn)則，和插入順序無關(guān)，set、multiset、map、multimap；

   Sets/Multisets：內(nèi)部的元素依據(jù)其值自動排序，Set內(nèi)的相同數(shù)值的元素只能出現(xiàn)一次，Multisets內(nèi)可包含多個數(shù)值相同的元素，內(nèi)部由二叉樹實(shí)現(xiàn)（實(shí)際上基于紅黑樹(RB-tree）實(shí)現(xiàn)），便于查找；

   Maps/Multimaps：Map的元素是成對的鍵值/實(shí)值，內(nèi)部的元素依據(jù)其值自動排序，Map內(nèi)的相同數(shù)值的元素只能出現(xiàn)一次，Multimaps內(nèi)可包含多個數(shù)值相同的元素，內(nèi)部由二叉樹實(shí)現(xiàn)（實(shí)際上基于紅黑樹(RB-tree）實(shí)現(xiàn)），便于查找；

另外有其他容器hash_map,hash_set,hash_multiset,hash_multimap。

  容器的比較：

2.STL迭代器 

Iterator（迭代器）模式又稱Cursor（游標(biāo)）模式，用于提供一種方法順序訪問一個聚合對象中各個元素, 而又不需暴露該對象的內(nèi)部表示。或者這樣說可能更容易理解：Iterator模式是運(yùn)用于聚合對象的一種模式，通過運(yùn)用該模式，使得我們可以在不知道對象內(nèi)部表示的情況下，按照一定順序（由iterator提供的方法）訪問聚合對象中的各個元素。

迭代器的作用：能夠讓迭代器與算法不干擾的相互發(fā)展，最后又能無間隙的粘合起來，重載了*，＋＋，＝＝，！＝，＝運(yùn)算符。用以操作復(fù)雜的數(shù)據(jù)結(jié)構(gòu)，容器提供迭代器，算法使用迭代器；

常見的一些迭代器類型：iterator、const_iterator、reverse_iterator和const_reverse_iterator

迭代器一般聲明使用示例

vector<T>::iterator it;list<T>::iterator it;deque<T>::iterator it；
 
            input         output
              /            /  
                forward
                     |
                bidirectional
                     |
               random access                                       
 
要注意，上面這圖表并不是表明它們之間的繼承關(guān)系：而只是描述了迭代器的種類和接口。處于圖表下層的迭代器都是相對于處于圖表上層迭代器的擴(kuò)張集。例如：forward迭代器不但擁有input和output迭代器的所有功能，還擁有更多的功能。
各個迭代器的功能如下：
迭代器類別
說明
輸入
從容器中讀取元素。輸入迭代器只能一次讀入一個元素向前移動，輸入迭代器只支持一遍算法，同一個輸入迭代器不能兩遍遍歷一個序列
輸出
向容器中寫入元素。輸出迭代器只能一次一個元素向前移動。輸出迭代器只支持一遍算法，統(tǒng)一輸出迭代器不能兩次遍歷一個序列
正向
組合輸入迭代器和輸出迭代器的功能，并保留在容器中的位置
雙向
組合正向迭代器和逆向迭代器的功能，支持多遍算法
隨機(jī)訪問
組合雙向迭代器的功能與直接訪問容器中任何元素的功能，即可向前向后跳過任意個元素
迭代器的操作：
每種迭代器均可進(jìn)行包括表中前一種迭代器可進(jìn)行的操作。
迭代器操作
說明
所有迭代器
p++
后置自增迭代器
++p
前置自增迭代器
輸入迭代器
*p
復(fù)引用迭代器，作為右值
p=p1
將一個迭代器賦給另一個迭代器
p==p1
比較迭代器的相等性
p!=p1
比較迭代器的不等性
輸出迭代器
*p
復(fù)引用迭代器，作為左值
p=p1
將一個迭代器賦給另一個迭代器
正向迭代器
提供輸入輸出迭代器的所有功能
雙向迭代器
--p
前置自減迭代器
p--
后置自減迭代器
隨機(jī)迭代器
p+=i
將迭代器遞增i位
p-=i
將迭代器遞減i位
p+i
在p位加i位后的迭代器
p-i
在p位減i位后的迭代器
p[i]
返回p位元素偏離i位的元素引用
p<p1
如果迭代器p的位置在p1前，返回true，否則返回false
p<=p1
p的位置在p1的前面或同一位置時返回true，否則返回false
p>p1
如果迭代器p的位置在p1后，返回true，否則返回false
p>=p1
p的位置在p1的后面或同一位置時返回true，否則返回false
只有順序容器和關(guān)聯(lián)容器支持迭代器遍歷，各容器支持的迭代器的類別如下：
容器
支持的迭代器類別
說明
vector
隨機(jī)訪問
一種隨機(jī)訪問的數(shù)組類型，提供了對數(shù)組元素進(jìn)行快速隨機(jī)訪問以及在序列尾部進(jìn)行快速的插入和刪除操作的功能。可以再需要的時候修改其自身的大小
deque
隨機(jī)訪問
一種隨機(jī)訪問的數(shù)組類型，提供了序列兩端快速進(jìn)行插入和刪除操作的功能。可以再需要的時候修改其自身的大小
list
雙向
一種不支持隨機(jī)訪問的數(shù)組類型，插入和刪除所花費(fèi)的時間是固定的，與位置無關(guān)。
set
雙向
一種隨機(jī)存取的容器，其關(guān)鍵字和數(shù)據(jù)元素是同一個值。所有元素都必須具有惟一值。
multiset
雙向
一種隨機(jī)存取的容器，其關(guān)鍵字和數(shù)據(jù)元素是同一個值。可以包含重復(fù)的元素。
map
雙向
一種包含成對數(shù)值的容器，一個值是實(shí)際數(shù)據(jù)值，另一個是用來尋找數(shù)據(jù)的關(guān)鍵字。一個特定的關(guān)鍵字只能與一個元素關(guān)聯(lián)。
multimap
雙向
一種包含成對數(shù)值的容器，一個值是實(shí)際數(shù)據(jù)值，另一個是用來尋找數(shù)據(jù)的關(guān)鍵字。一個關(guān)鍵字可以與多個數(shù)據(jù)元素關(guān)聯(lián)。
stack
不支持
適配器容器類型，用vector，deque或list對象創(chuàng)建了一個先進(jìn)后出容器
queue
不支持
適配器容器類型，用deque或list對象創(chuàng)建了一個先進(jìn)先出容器
priority_queue
不支持
適配器容器類型，用vector或deque對象創(chuàng)建了一個排序隊(duì)列
 
 3.STL算法
STL算法部分主要由頭文件<algorithm>,<numeric>,<functional>組成。要使用 STL中的算法函數(shù)必須包含頭文件<algorithm>，對于數(shù)值算法須包含<numeric>，<functional>中則定義了一些模板類，用來聲明函數(shù)對象。STL中算法大致分為四類：1）、非可變序列算法：指不直接修改其所操作的容器內(nèi)容的算法。2）、可變序列算法：指可以修改它們所操作的容器內(nèi)容的算法。3）、排序算法：包括對序列進(jìn)行排序和合并的算法、搜索算法以及有序序列上的集合操作。4）、數(shù)值算法：對容器內(nèi)容進(jìn)行數(shù)值計(jì)算。
 
以下對所有算法進(jìn)行細(xì)致分類并標(biāo)明功能：    <一>查找算法(13個)：判斷容器中是否包含某個值    adjacent_find:            在iterator對標(biāo)識元素范圍內(nèi)，查找一對相鄰重復(fù)元素，找到則返回指向這對元素的第一個元素的ForwardIterator。否則返回last。重載版本使用輸入的二元操作符代替相等的判斷。    binary_search:            在有序序列中查找value，找到返回true。重載的版本實(shí)用指定的比較函數(shù)對象或函數(shù)指針來判斷相等。    count:                    利用等于操作符，把標(biāo)志范圍內(nèi)的元素與輸入值比較，返回相等元素個數(shù)。    count_if:                 利用輸入的操作符，對標(biāo)志范圍內(nèi)的元素進(jìn)行操作，返回結(jié)果為true的個數(shù)。    equal_range:              功能類似equal，返回一對iterator，第一個表示lower_bound，第二個表示upper_bound。    find:                     利用底層元素的等于操作符，對指定范圍內(nèi)的元素與輸入值進(jìn)行比較。當(dāng)匹配時，結(jié)束搜索，返回該元素的一個InputIterator。    find_end:                 在指定范圍內(nèi)查找"由輸入的另外一對iterator標(biāo)志的第二個序列"的最后一次出現(xiàn)。找到則返回最后一對的第一個ForwardIterator，否則返回輸入的"另外一對"的第一個ForwardIterator。重載版本使用用戶輸入的操作符代替等于操作。    find_first_of:            在指定范圍內(nèi)查找"由輸入的另外一對iterator標(biāo)志的第二個序列"中任意一個元素的第一次出現(xiàn)。重載版本中使用了用戶自定義操作符。    find_if:                  使用輸入的函數(shù)代替等于操作符執(zhí)行find。    lower_bound:              返回一個ForwardIterator，指向在有序序列范圍內(nèi)的可以插入指定值而不破壞容器順序的第一個位置。重載函數(shù)使用自定義比較操作。    upper_bound:              返回一個ForwardIterator，指向在有序序列范圍內(nèi)插入value而不破壞容器順序的最后一個位置，該位置標(biāo)志一個大于value的值。重載函數(shù)使用自定義比較操作。    search:                   給出兩個范圍，返回一個ForwardIterator，查找成功指向第一個范圍內(nèi)第一次出現(xiàn)子序列(第二個范圍)的位置，查找失敗指向last1。重載版本使用自定義的比較操作。    search_n:                 在指定范圍內(nèi)查找val出現(xiàn)n次的子序列。重載版本使用自定義的比較操作。     <二>排序和通用算法(14個)：提供元素排序策略    inplace_merge:            合并兩個有序序列，結(jié)果序列覆蓋兩端范圍。重載版本使用輸入的操作進(jìn)行排序。    merge:                    合并兩個有序序列，存放到另一個序列。重載版本使用自定義的比較。    nth_element:              將范圍內(nèi)的序列重新排序，使所有小于第n個元素的元素都出現(xiàn)在它前面，而大于它的都出現(xiàn)在后面。重載版本使用自定義的比較操作。    partial_sort:             對序列做部分排序，被排序元素個數(shù)正好可以被放到范圍內(nèi)。重載版本使用自定義的比較操作。    partial_sort_copy:        與partial_sort類似，不過將經(jīng)過排序的序列復(fù)制到另一個容器。    partition:                對指定范圍內(nèi)元素重新排序，使用輸入的函數(shù)，把結(jié)果為true的元素放在結(jié)果為false的元素之前。    random_shuffle:           對指定范圍內(nèi)的元素隨機(jī)調(diào)整次序。重載版本輸入一個隨機(jī)數(shù)產(chǎn)生操作。    reverse:                  將指定范圍內(nèi)元素重新反序排序。    reverse_copy:             與reverse類似，不過將結(jié)果寫入另一個容器。    rotate:                   將指定范圍內(nèi)元素移到容器末尾，由middle指向的元素成為容器第一個元素。    rotate_copy:              與rotate類似，不過將結(jié)果寫入另一個容器。    sort:                     以升序重新排列指定范圍內(nèi)的元素。重載版本使用自定義的比較操作。    stable_sort:              與sort類似，不過保留相等元素之間的順序關(guān)系。    stable_partition:         與partition類似，不過不保證保留容器中的相對順序。     <三>刪除和替換算法(15個)    copy:                     復(fù)制序列    copy_backward:            與copy相同，不過元素是以相反順序被拷貝。    iter_swap:                交換兩個ForwardIterator的值。    remove:                   刪除指定范圍內(nèi)所有等于指定元素的元素。注意，該函數(shù)不是真正刪除函數(shù)。內(nèi)置函數(shù)不適合使用remove和remove_if函數(shù)。    remove_copy:              將所有不匹配元素復(fù)制到一個制定容器，返回OutputIterator指向被拷貝的末元素的下一個位置。    remove_if:                刪除指定范圍內(nèi)輸入操作結(jié)果為true的所有元素。    remove_copy_if:           將所有不匹配元素拷貝到一個指定容器。    replace:                  將指定范圍內(nèi)所有等于vold的元素都用vnew代替。    replace_copy:             與replace類似，不過將結(jié)果寫入另一個容器。    replace_if:               將指定范圍內(nèi)所有操作結(jié)果為true的元素用新值代替。    replace_copy_if:          與replace_if，不過將結(jié)果寫入另一個容器。    swap:                     交換存儲在兩個對象中的值。    swap_range:               將指定范圍內(nèi)的元素與另一個序列元素值進(jìn)行交換。    unique:                   清除序列中重復(fù)元素，和remove類似，它也不能真正刪除元素。重載版本使用自定義比較操作。    unique_copy:              與unique類似，不過把結(jié)果輸出到另一個容器。     <四>排列組合算法(2個)：提供計(jì)算給定集合按一定順序的所有可能排列組合    next_permutation:         取出當(dāng)前范圍內(nèi)的排列，并重新排序?yàn)橄乱粋€排列。重載版本使用自定義的比較操作。    prev_permutation:         取出指定范圍內(nèi)的序列并將它重新排序?yàn)樯弦粋€序列。如果不存在上一個序列則返回false。重載版本使用自定義的比較操作。 
    <五>算術(shù)算法(4個)    accumulate:               iterator對標(biāo)識的序列段元素之和，加到一個由val指定的初始值上。重載版本不再做加法，而是傳進(jìn)來的二元操作符被應(yīng)用到元素上。    partial_sum:              創(chuàng)建一個新序列，其中每個元素值代表指定范圍內(nèi)該位置前所有元素之和。重載版本使用自定義操作代替加法。    inner_product:            對兩個序列做內(nèi)積(對應(yīng)元素相乘，再求和)并將內(nèi)積加到一個輸入的初始值上。重載版本使用用戶定義的操作。    adjacent_difference:      創(chuàng)建一個新序列，新序列中每個新值代表當(dāng)前元素與上一個元素的差。重載版本用指定二元操作計(jì)算相鄰元素的差。     <六>生成和異變算法(6個)    fill:                     將輸入值賦給標(biāo)志范圍內(nèi)的所有元素。    fill_n:                   將輸入值賦給first到first+n范圍內(nèi)的所有元素。    for_each:                 用指定函數(shù)依次對指定范圍內(nèi)所有元素進(jìn)行迭代訪問，返回所指定的函數(shù)類型。該函數(shù)不得修改序列中的元素。    generate:                 連續(xù)調(diào)用輸入的函數(shù)來填充指定的范圍。    generate_n:               與generate函數(shù)類似，填充從指定iterator開始的n個元素。    transform:                將輸入的操作作用與指定范圍內(nèi)的每個元素，并產(chǎn)生一個新的序列。重載版本將操作作用在一對元素上，另外一個元素來自輸入的另外一個序列。結(jié)果輸出到指定容器。 
    <七>關(guān)系算法(8個)    equal:                    如果兩個序列在標(biāo)志范圍內(nèi)元素都相等，返回true。重載版本使用輸入的操作符代替默認(rèn)的等于操作符。    includes:                 判斷第一個指定范圍內(nèi)的所有元素是否都被第二個范圍包含，使用底層元素的<操作符，成功返回true。重載版本使用用戶輸入的函數(shù)。    lexicographical_compare:  比較兩個序列。重載版本使用用戶自定義比較操作。    max:                      返回兩個元素中較大一個。重載版本使用自定義比較操作。    max_element:              返回一個ForwardIterator，指出序列中最大的元素。重載版本使用自定義比較操作。    min:                      返回兩個元素中較小一個。重載版本使用自定義比較操作。    min_element:              返回一個ForwardIterator，指出序列中最小的元素。重載版本使用自定義比較操作。    mismatch:                 并行比較兩個序列，指出第一個不匹配的位置，返回一對iterator，標(biāo)志第一個不匹配元素位置。如果都匹配，返回每個容器的last。重載版本使用自定義的比較操作。 
    <八>集合算法(4個)    set_union:                構(gòu)造一個有序序列，包含兩個序列中所有的不重復(fù)元素。重載版本使用自定義的比較操作。    set_intersection:         構(gòu)造一個有序序列，其中元素在兩個序列中都存在。重載版本使用自定義的比較操作。    set_difference:           構(gòu)造一個有序序列，該序列僅保留第一個序列中存在的而第二個中不存在的元素。重載版本使用自定義的比較操作。    set_symmetric_difference: 構(gòu)造一個有序序列，該序列取兩個序列的對稱差集(并集-交集)。 
   <九>堆算法(4個)    make_heap:                把指定范圍內(nèi)的元素生成一個堆。重載版本使用自定義比較操作。    pop_heap:                 并不真正把最大元素從堆中彈出，而是重新排序堆。它把first和last-1交換，然后重新生成一個堆。可使用容器的back來訪問被"彈出"的元素或者使用pop_back進(jìn)行真正的刪除。重載版本使用自定義的比較操作。    push_heap:                假設(shè)first到last-1是一個有效堆，要被加入到堆的元素存放在位置last-1，重新生成堆。在指向該函數(shù)前，必須先把元素插入容器后。重載版本使用指定的比較操作。    sort_heap:                對指定范圍內(nèi)的序列重新排序，它假設(shè)該序列是個有序堆。重載版本使用自定義比較操作。
 
4.適配器
STL提供了三個容器適配器：queue、priority_queue、stack。這些適配器都是包裝了vector、list、deque中某個順序容器的包裝器。注意：適配器沒有提供迭代器，也不能同時插入或刪除多個元素。下面對各個適配器進(jìn)行概括總結(jié)。
（1）stack用法
#include <stack>template < typename T, typename Container=deque > class stack;
可以使用三個標(biāo)準(zhǔn)順序容器vecotr、deque(默認(rèn))、list中的任何一個作為stack的底層模型。
bool stack<T>::empty()                               //判斷堆棧是否為空void stack<T>::pop()                                 //彈出棧頂數(shù)據(jù)stack<T>::push(T x)                                  //壓入一個數(shù)據(jù)stack<T>::size_type stack<T>::size()                 //返回堆棧長度T stack<T>::top()                                    //得到棧頂數(shù)據(jù)
 代碼示例：
stack<int> intDequeStack;  stack<int,vector<int>> intVectorStack;  stack<int,list<int>> intListStack; 
 
（2）queue用法
#include <queue>template<typename T, typename Container = deque<T> > class  queue;
第一個參數(shù)指定要在queue中存儲的類型，第二個參數(shù)規(guī)定queue適配的底層容器，可供選擇的容器只有dequeue和list。對大多數(shù)用途使用默認(rèn)的dequeue。
queue<T>::push(T x)void queue<T>::pop()T queue<T>::back()T queue<T>::front()queue<T>::size_type queue<T>::size()bool queue<T>::empty()
代碼示例：
queue<int> intDequeQueue;    queue<int,list<int>> intListQueue;
 
（3）priority_queue用法
#include <queue>template <typename T, typename Container = vector<T>, typename Compare = less<T> > class priority_queue;
priority_queue也是一個隊(duì)列，其元素按有序順序排列。其不采用嚴(yán)格的FIFO順序，給定時刻位于隊(duì)頭的元素正是有最高優(yōu)先級的元素。如果兩個元素有相同的優(yōu)先級，那么它們在隊(duì)列中的順序就遵循FIFO語義。默認(rèn)適配的底層容器是vector，也可以使用deque，list不能用，因?yàn)閜riority_queue要求能對元素隨機(jī)訪問以便進(jìn)行排序。
priority_queue<T>::push(T x)void priority_queue<T>::pop()T priority_queue<T>::top()priority_queue<T>::size_type priority_queue<T>::size()bool priority_queue<T>::empty()
代碼示例：
priority_queue< int, vector<int>, greater<int> >priority_queue< int, list<int>, greater<int> >
 
標(biāo)準(zhǔn)庫默認(rèn)使用元素類型的<操作符來確定它們之間的優(yōu)先級關(guān)系，用法有三：（下文轉(zhuǎn)自http://m.survivalescaperooms.com/vvilp/articles/1504436.html）
優(yōu)先隊(duì)列第一種用法，通過默認(rèn)使用的<操作符可知在整數(shù)中元素大的優(yōu)先級高。
priority_queue<int> qi; 
示例中輸出結(jié)果為：9 6 5 3 2
優(yōu)先隊(duì)列第二種用法，建立priority_queue時傳入一個比較函數(shù)，使用functional.h函數(shù)對象作為比較函數(shù)。
priority_queue<int, vector<int>, greater<int> >qi2;
示例2中輸出結(jié)果為：2 3 5 6 9
優(yōu)先隊(duì)列第三種用法，是自定義優(yōu)先級。
struct node {     friend bool operator< (node n1, node n2)     {         return n1.priority < n2.priority;     }      int priority;     int value; }; priority_queue<node> qn; 
在示例3中輸出結(jié)果為：
優(yōu)先級  值
9          5
8          2
6          1
2          3
1          4
在該結(jié)構(gòu)中，value為值，priority為優(yōu)先級。通過自定義operator<操作符來比較元素中的優(yōu)先級。注意：必須是自定義<操作符才行，把上述的結(jié)構(gòu)中的<操作符改成>編譯不通過。