STL內(nèi)容介紹
1 什么是STL？
STL（Standard Template Library），即標(biāo)準(zhǔn)模板庫(kù)，是一個(gè)具有工業(yè)強(qiáng)度的，高效的C++程序庫(kù)。它被容納于C++標(biāo)準(zhǔn)程序庫(kù)（C++ Standard Library）中，是ANSI/ISO C++標(biāo)準(zhǔn)中最新的也是極具革命性的一部分。該庫(kù)包含了諸多在計(jì)算機(jī)科學(xué)領(lǐng)域里所常用的基本數(shù)據(jù)結(jié)構(gòu)和基本算法。為廣大C++程序員們提供了一個(gè)可擴(kuò)展的應(yīng)用框架，高度體現(xiàn)了軟件的可復(fù)用性。
STL的一個(gè)重要特點(diǎn)是數(shù)據(jù)結(jié)構(gòu)和算法的分離。盡管這是個(gè)簡(jiǎn)單的概念，但這種分離確實(shí)使得STL變得非常通用。例如，由于STL的sort()函數(shù)是完全通用的，你可以用它來(lái)操作幾乎任何數(shù)據(jù)集合，包括鏈表，容器和數(shù)組；
STL另一個(gè)重要特性是它不是面向?qū)ο蟮?。為了具有足夠通用性，STL主要依賴于模板而不是封裝，繼承和虛函數(shù)（多態(tài)性）——OOP的三個(gè)要素。你在STL中找不到任何明顯的類繼承關(guān)系。這好像是一種倒退，但這正好是使得STL的組件具有廣泛通用性的底層特征。另外，由于STL是基于模板，內(nèi)聯(lián)函數(shù)的使用使得生成的代碼短小高效；
從邏輯層次來(lái)看，在STL中體現(xiàn)了泛型化程序設(shè)計(jì)的思想，引入了諸多新的名詞，比如像需求（requirements），概念（concept），模型（model），容器（container），算法（algorithmn），迭代子（iterator）等。與OOP（object-oriented programming）中的多態(tài)（polymorphism）一樣，泛型也是一種軟件的復(fù)用技術(shù)；
從實(shí)現(xiàn)層次看，整個(gè)STL是以一種類型參數(shù)化的方式實(shí)現(xiàn)的，這種方式基于一個(gè)在早先C++標(biāo)準(zhǔn)中沒(méi)有出現(xiàn)的語(yǔ)言特性--模板（template）。
2 STL內(nèi)容介紹
STL中六大組件：
容器（Container），是一種數(shù)據(jù)結(jié)構(gòu)，如list，vector，和deques ，以模板類的方法提供。為了訪問(wèn)容器中的數(shù)據(jù)，可以使用由容器類輸出的迭代器；
迭代器（Iterator），提供了訪問(wèn)容器中對(duì)象的方法。例如，可以使用一對(duì)迭代器指定list或vector中的一定范圍的對(duì)象。迭代器就如同一個(gè)指針。事實(shí)上，C++的指針也是一種迭代器。但是，迭代器也可以是那些定義了operator*()以及其他類似于指針的操作符地方法的類對(duì)象；
算法（Algorithm），是用來(lái)操作容器中的數(shù)據(jù)的模板函數(shù)。例如，STL用sort()來(lái)對(duì)一個(gè)vector中的數(shù)據(jù)進(jìn)行排序，用find()來(lái)搜索一個(gè)list中的對(duì)象，函數(shù)本身與他們操作的數(shù)據(jù)的結(jié)構(gòu)和類型無(wú)關(guān)，因此他們可以在從簡(jiǎn)單數(shù)組到高度復(fù)雜容器的任何數(shù)據(jù)結(jié)構(gòu)上使用；
仿函數(shù)（Functor）
適配器（Adaptor）
分配器（allocator）
2.1 容器
STL中的容器有隊(duì)列容器和關(guān)聯(lián)容器，容器適配器（congtainer adapters：stack,queue，priority queue），位集（bit_set），串包(string_package)等等。
（1）序列式容器（Sequence containers），每個(gè)元素都有固定位置－－取決于插入時(shí)機(jī)和地點(diǎn)，和元素值無(wú)關(guān)，vector、deque、list；
Vector：將元素置于一個(gè)動(dòng)態(tài)數(shù)組中加以管理，可以隨機(jī)存取元素（用索引直接存?。?，數(shù)組尾部添加或移除元素非?？焖?。但是在中部或頭部安插元素比較費(fèi)時(shí)；
Deque：是“double-ended queue”的縮寫(xiě)，可以隨機(jī)存取元素（用索引直接存?。?，數(shù)組頭部和尾部添加或移除元素都非常快速。但是在中部或頭部安插元素比較費(fèi)時(shí)；
List：雙向鏈表，不提供隨機(jī)存?。ò错樞蜃叩叫璐嫒〉脑?，O(n)），在任何位置上執(zhí)行插入或刪除動(dòng)作都非常迅速，內(nèi)部只需調(diào)整一下指針；
（2）關(guān)聯(lián)式容器（Associated containers），元素位置取決于特定的排序準(zhǔn)則，和插入順序無(wú)關(guān)，set、multiset、map、multimap等。
Set/Multiset：內(nèi)部的元素依據(jù)其值自動(dòng)排序，Set內(nèi)的相同數(shù)值的元素只能出現(xiàn)一次，Multisets內(nèi)可包含多個(gè)數(shù)值相同的元素，內(nèi)部由二叉樹(shù)實(shí)現(xiàn)，便于查找；
Map/Multimap：Map的元素是成對(duì)的鍵值/實(shí)值，內(nèi)部的元素依據(jù)其值自動(dòng)排序，Map內(nèi)的相同數(shù)值的元素只能出現(xiàn)一次，Multimaps內(nèi)可包含多個(gè)數(shù)值相同的元素，內(nèi)部由二叉樹(shù)實(shí)現(xiàn)，便于查找；
容器類自動(dòng)申請(qǐng)和釋放內(nèi)存，無(wú)需new和delete操作。
2.2 STL迭代器
Iterator（迭代器）模式又稱Cursor（游標(biāo)）模式，用于提供一種方法順序訪問(wèn)一個(gè)聚合對(duì)象中各個(gè)元素, 而又不需暴露該對(duì)象的內(nèi)部表示。或者這樣說(shuō)可能更容易理解：Iterator模式是運(yùn)用于聚合對(duì)象的一種模式，通過(guò)運(yùn)用該模式，使得我們可以在不知道對(duì)象內(nèi)部表示的情況下，按照一定順序（由iterator提供的方法）訪問(wèn)聚合對(duì)象中的各個(gè)元素。
迭代器的作用：能夠讓迭代器與算法不干擾的相互發(fā)展，最后又能無(wú)間隙的粘合起來(lái)，重載了*，＋＋，＝＝，?。?，＝運(yùn)算符。用以操作復(fù)雜的數(shù)據(jù)結(jié)構(gòu)，容器提供迭代器，算法使用迭代器；常見(jiàn)的一些迭代器類型：iterator、const_iterator、reverse_iterator和const_reverse_iterator.
2.3 算法
函數(shù)庫(kù)對(duì)數(shù)據(jù)類型的選擇對(duì)其可重用性起著至關(guān)重要的作用。舉例來(lái)說(shuō)，一個(gè)求方根的函數(shù)，在使用浮點(diǎn)數(shù)作為其參數(shù)類型的情況下的可重用性肯定比使用整型作為它的參數(shù)類性要高。而C++通過(guò)模板的機(jī)制允許推遲對(duì)某些類型的選擇，直到真正想使用模板或者說(shuō)對(duì)模板進(jìn)行特化的時(shí)候，STL就利用了這一點(diǎn)提供了相當(dāng)多的有用算法。它是在一個(gè)有效的框架中完成這些算法的——你可以將所有的類型劃分為少數(shù)的幾類，然后就可以在模版的參數(shù)中使用一種類型替換掉同一種類中的其他類型。
STL提供了大約100個(gè)實(shí)現(xiàn)算法的模版函數(shù)，比如算法for_each將為指定序列中的每一個(gè)元素調(diào)用指定的函數(shù)，stable_sort以你所指定的規(guī)則對(duì)序列進(jìn)行穩(wěn)定性排序等等。只要我們熟悉了STL之后，許多代碼可以被大大的化簡(jiǎn)，只需要通過(guò)調(diào)用一兩個(gè)算法模板，就可以完成所需要的功能并大大地提升效率。
算法部分主要由頭文件，和組成。
是所有STL頭文件中最大的一個(gè)（盡管它很好理解），它是由一大堆模版函數(shù)組成的，可以認(rèn)為每個(gè)函數(shù)在很大程度上都是獨(dú)立的，其中常用到的功能范圍涉及到比較、交換、查找、遍歷操作、復(fù)制、修改、移除、反轉(zhuǎn)、排序、合并等等。
體積很小，只包括幾個(gè)在序列上面進(jìn)行簡(jiǎn)單數(shù)學(xué)運(yùn)算的模板函數(shù)，包括加法和乘法在序列上的一些操作。
中則定義了一些模板類，用以聲明函數(shù)對(duì)象。
STL中算法大致分為四類：
- 非可變序列算法：指不直接修改其所操作的容器內(nèi)容的算法。
- 可變序列算法：指可以修改它們所操作的容器內(nèi)容的算法。
- 排序算法：對(duì)序列進(jìn)行排序和合并的算法、搜索算法以及有序序列上的集合操作。
- 數(shù)值算法：對(duì)容器內(nèi)容進(jìn)行數(shù)值計(jì)算。
以下對(duì)所有算法進(jìn)行細(xì)致分類并標(biāo)明功能：
<一>查找算法(13個(gè))：判斷容器中是否包含某個(gè)值
adjacent_find: 在iterator對(duì)標(biāo)識(shí)元素范圍內(nèi)，查找一對(duì)相鄰重復(fù)元素，找到則返回指向這對(duì)元素的第一個(gè)元素的 ForwardIterator。否則返回last。重載版本使用輸入的二元操作符代替相等的判斷。
binary_search: 在有序序列中查找value，找到返回true。重載的版本實(shí)用指定的比較函數(shù)對(duì)象或函數(shù)指針來(lái)判斷相等。
count: 利用等于操作符，把標(biāo)志范圍內(nèi)的元素與輸入值比較，返回相等元素個(gè)數(shù)。
count_if: 利用輸入的操作符，對(duì)標(biāo)志范圍內(nèi)的元素進(jìn)行操作，返回結(jié)果為true的個(gè)數(shù)。
equal_range: 功能類似equal，返回一對(duì)iterator，第一個(gè)表示lower_bound，第二個(gè)表示upper_bound。
find: 利用底層元素的等于操作符，對(duì)指定范圍內(nèi)的元素與輸入值進(jìn)行比較。當(dāng)匹配時(shí)，結(jié)束搜索，返回該元素的 一個(gè)InputIterator。
find_end: 在指定范圍內(nèi)查找"由輸入的另外一對(duì)iterator標(biāo)志的第二個(gè)序列"的最后一次出現(xiàn)。找到則返回最后一對(duì)的第一 個(gè)ForwardIterator，否則返回輸入的"另外一對(duì)"的第一個(gè)ForwardIterator。重載版本使用用戶輸入的操作符代 替等于操作。
find_first_of: 在指定范圍內(nèi)查找"由輸入的另外一對(duì)iterator標(biāo)志的第二個(gè)序列"中任意一個(gè)元素的第一次出現(xiàn)。重載版本中使 用了用戶自定義操作符。
find_if: 使用輸入的函數(shù)代替等于操作符執(zhí)行find。
lower_bound: 返回一個(gè)ForwardIterator，指向在有序序列范圍內(nèi)的可以插入指定值而不破壞容器順序的第一個(gè)位置。重載函 數(shù)使用自定義比較操作。
upper_bound: 返回一個(gè)ForwardIterator，指向在有序序列范圍內(nèi)插入value而不破壞容器順序的最后一個(gè)位置，該位置標(biāo)志 一個(gè)大于value的值。重載函數(shù)使用自定義比較操作。
search: 給出兩個(gè)范圍，返回一個(gè)ForwardIterator，查找成功指向第一個(gè)范圍內(nèi)第一次出現(xiàn)子序列(第二個(gè)范圍)的位 置，查找失敗指向last1。重載版本使用自定義的比較操作。
search_n: 在指定范圍內(nèi)查找val出現(xiàn)n次的子序列。重載版本使用自定義的比較操作。
<二>排序和通用算法(14個(gè))：提供元素排序策略
inplace_merge: 合并兩個(gè)有序序列，結(jié)果序列覆蓋兩端范圍。重載版本使用輸入的操作進(jìn)行排序。
merge: 合并兩個(gè)有序序列，存放到另一個(gè)序列。重載版本使用自定義的比較。
nth_element: 將范圍內(nèi)的序列重新排序，使所有小于第n個(gè)元素的元素都出現(xiàn)在它前面，而大于它的都出現(xiàn)在后面。重 載版本使用自定義的比較操作。
partial_sort: 對(duì)序列做部分排序，被排序元素個(gè)數(shù)正好可以被放到范圍內(nèi)。重載版本使用自定義的比較操作。
partial_sort_copy: 與partial_sort類似，不過(guò)將經(jīng)過(guò)排序的序列復(fù)制到另一個(gè)容器。
partition: 對(duì)指定范圍內(nèi)元素重新排序，使用輸入的函數(shù)，把結(jié)果為true的元素放在結(jié)果為false的元素之前。
random_shuffle: 對(duì)指定范圍內(nèi)的元素隨機(jī)調(diào)整次序。重載版本輸入一個(gè)隨機(jī)數(shù)產(chǎn)生操作。
reverse: 將指定范圍內(nèi)元素重新反序排序。
reverse_copy: 與reverse類似，不過(guò)將結(jié)果寫(xiě)入另一個(gè)容器。
rotate: 將指定范圍內(nèi)元素移到容器末尾，由middle指向的元素成為容器第一個(gè)元素。
rotate_copy: 與rotate類似，不過(guò)將結(jié)果寫(xiě)入另一個(gè)容器。
sort: 以升序重新排列指定范圍內(nèi)的元素。重載版本使用自定義的比較操作。
stable_sort: 與sort類似，不過(guò)保留相等元素之間的順序關(guān)系。
stable_partition: 與partition類似，不過(guò)不保證保留容器中的相對(duì)順序。
<三>刪除和替換算法(15個(gè))
copy: 復(fù)制序列
copy_backward: 與copy相同，不過(guò)元素是以相反順序被拷貝。
iter_swap: 交換兩個(gè)ForwardIterator的值。
remove: 刪除指定范圍內(nèi)所有等于指定元素的元素。注意，該函數(shù)不是真正刪除函數(shù)。內(nèi)置函數(shù)不適合使用remove和 remove_if函數(shù)。
remove_copy: 將所有不匹配元素復(fù)制到一個(gè)制定容器，返回OutputIterator指向被拷貝的末元素的下一個(gè)位置。
remove_if: 刪除指定范圍內(nèi)輸入操作結(jié)果為true的所有元素。
remove_copy_if: 將所有不匹配元素拷貝到一個(gè)指定容器。
replace: 將指定范圍內(nèi)所有等于vold的元素都用vnew代替。
replace_copy: 與replace類似，不過(guò)將結(jié)果寫(xiě)入另一個(gè)容器。
replace_if: 將指定范圍內(nèi)所有操作結(jié)果為true的元素用新值代替。
replace_copy_if: 與replace_if，不過(guò)將結(jié)果寫(xiě)入另一個(gè)容器。
swap: 交換存儲(chǔ)在兩個(gè)對(duì)象中的值。
swap_range: 將指定范圍內(nèi)的元素與另一個(gè)序列元素值進(jìn)行交換。
unique: 清除序列中重復(fù)元素，和remove類似，它也不能真正刪除元素。重載版本使用自定義比較操作。
unique_copy: 與unique類似，不過(guò)把結(jié)果輸出到另一個(gè)容器。
<四>排列組合算法(2個(gè))：提供計(jì)算給定集合按一定順序的所有可能排列組合
next_permutation: 取出當(dāng)前范圍內(nèi)的排列，并重新排序?yàn)橄乱粋€(gè)排列。重載版本使用自定義的比較操作。
prev_permutation: 取出指定范圍內(nèi)的序列并將它重新排序?yàn)樯弦粋€(gè)序列。如果不存在上一個(gè)序列則返回false。重載版本使用 自定義的比較操作。
<五>算術(shù)算法(4個(gè))
accumulate: iterator對(duì)標(biāo)識(shí)的序列段元素之和，加到一個(gè)由val指定的初始值上。重載版本不再做加法，而是傳進(jìn)來(lái)的 二元操作符被應(yīng)用到元素上。
partial_sum: 創(chuàng)建一個(gè)新序列，其中每個(gè)元素值代表指定范圍內(nèi)該位置前所有元素之和。重載版本使用自定義操作代 替加法。
inner_product: 對(duì)兩個(gè)序列做內(nèi)積(對(duì)應(yīng)元素相乘，再求和)并將內(nèi)積加到一個(gè)輸入的初始值上。重載版本使用用戶定義 的操作。
adjacent_difference: 創(chuàng)建一個(gè)新序列，新序列中每個(gè)新值代表當(dāng)前元素與上一個(gè)元素的差。重載版本用指定二元操作計(jì)算相 鄰元素的差。
<六>生成和異變算法(6個(gè))
fill: 將輸入值賦給標(biāo)志范圍內(nèi)的所有元素。
fill_n: 將輸入值賦給first到first+n范圍內(nèi)的所有元素。
for_each: 用指定函數(shù)依次對(duì)指定范圍內(nèi)所有元素進(jìn)行迭代訪問(wèn)，返回所指定的函數(shù)類型。該函數(shù)不得修改序列中的元素。
generate: 連續(xù)調(diào)用輸入的函數(shù)來(lái)填充指定的范圍。
generate_n: 與generate函數(shù)類似，填充從指定iterator開(kāi)始的n個(gè)元素。
transform: 將輸入的操作作用與指定范圍內(nèi)的每個(gè)元素，并產(chǎn)生一個(gè)新的序列。重載版本將操作作用在一對(duì)元素上，另外一 個(gè)元素來(lái)自輸入的另外一個(gè)序列。結(jié)果輸出到指定容器。
<七>關(guān)系算法(8個(gè))
equal: 如果兩個(gè)序列在標(biāo)志范圍內(nèi)元素都相等，返回true。重載版本使用輸入的操作符代替默認(rèn)的等于操 作符。
includes: 判斷第一個(gè)指定范圍內(nèi)的所有元素是否都被第二個(gè)范圍包含，使用底層元素的<操作符，成功返回 true。重載版本使用用戶輸入的函數(shù)。
lexicographical_compare: 比較兩個(gè)序列。重載版本使用用戶自定義比較操作。
max: 返回兩個(gè)元素中較大一個(gè)。重載版本使用自定義比較操作。
max_element: 返回一個(gè)ForwardIterator，指出序列中最大的元素。重載版本使用自定義比較操作。
min: 返回兩個(gè)元素中較小一個(gè)。重載版本使用自定義比較操作。
min_element: 返回一個(gè)ForwardIterator，指出序列中最小的元素。重載版本使用自定義比較操作。
mismatch: 并行比較兩個(gè)序列，指出第一個(gè)不匹配的位置，返回一對(duì)iterator，標(biāo)志第一個(gè)不匹配元素位置。 如果都匹配，返回每個(gè)容器的last。重載版本使用自定義的比較操作。
<八>集合算法(4個(gè))
set_union: 構(gòu)造一個(gè)有序序列，包含兩個(gè)序列中所有的不重復(fù)元素。重載版本使用自定義的比較操作。
set_intersection: 構(gòu)造一個(gè)有序序列，其中元素在兩個(gè)序列中都存在。重載版本使用自定義的比較操作。
set_difference: 構(gòu)造一個(gè)有序序列，該序列僅保留第一個(gè)序列中存在的而第二個(gè)中不存在的元素。重載版本使用 自定義的比較操作。
set_symmetric_difference: 構(gòu)造一個(gè)有序序列，該序列取兩個(gè)序列的對(duì)稱差集(并集-交集)。
<九>堆算法(4個(gè))
make_heap: 把指定范圍內(nèi)的元素生成一個(gè)堆。重載版本使用自定義比較操作。
pop_heap: 并不真正把最大元素從堆中彈出，而是重新排序堆。它把first和last-1交換，然后重新生成一個(gè)堆?？墒褂萌萜鞯?back來(lái)訪問(wèn)被"彈出"的元素或者使用pop_back進(jìn)行真正的刪除。重載版本使用自定義的比較操作。
push_heap: 假設(shè)first到last-1是一個(gè)有效堆，要被加入到堆的元素存放在位置last-1，重新生成堆。在指向該函數(shù)前，必須先把 元素插入容器后。重載版本使用指定的比較操作。
sort_heap: 對(duì)指定范圍內(nèi)的序列重新排序，它假設(shè)該序列是個(gè)有序堆。重載版本使用自定義比較操作。
2.4 仿函數(shù)
2.4.1 概述
仿函數(shù)(functor)，就是使一個(gè)類的使用看上去象一個(gè)函數(shù)。其實(shí)現(xiàn)就是類中實(shí)現(xiàn)一個(gè)operator()，這個(gè)類就有了類似函數(shù)的行為，就是一個(gè)仿函數(shù)類了。
有些功能的的代碼，會(huì)在不同的成員函數(shù)中用到，想復(fù)用這些代碼。
1）公共的函數(shù)，可以，這是一個(gè)解決方法，不過(guò)函數(shù)用到的一些變量，就可能成為公共的全局變量，再說(shuō)為了復(fù)用這么一片代碼，就要單立出一個(gè)函數(shù)，也不是很好維護(hù)。
2）仿函數(shù)，寫(xiě)一個(gè)簡(jiǎn)單類，除了那些維護(hù)一個(gè)類的成員函數(shù)外，就只是實(shí)現(xiàn)一個(gè)operator()，在類實(shí)例化時(shí)，就將要用的，非參數(shù)的元素傳入類中。
2.4.2 仿函數(shù)(functor)在編程語(yǔ)言中的應(yīng)用
1）C語(yǔ)言使用函數(shù)指針和回調(diào)函數(shù)來(lái)實(shí)現(xiàn)仿函數(shù)，例如一個(gè)用來(lái)排序的函數(shù)可以這樣使用仿函數(shù)
#include < stdio.h >
#include < stdlib.h >
//int sort_function( const void *a, const void *b);
int sort_function( const void *a, const void *b)
{
return *(int*)a-*(int*)b;
}
int main()
{
int list[5] = { 54, 21, 11, 67, 22 };
qsort((void *)list, 5, sizeof(list[0]), sort_function);//起始地址，個(gè)數(shù)，元素大小，回調(diào)函數(shù)
int x;
for (x = 0; x < 5; x++)
printf("%in", list[x]);
return 0;
}
2）在C++里，我們通過(guò)在一個(gè)類中重載括號(hào)運(yùn)算符的方法使用一個(gè)函數(shù)對(duì)象而不是一個(gè)普通函數(shù)。
#include < iostream >
#include < algorithm >
using namespace std;
template< typename T >
class display
{
public:
void operator()(const T &x)
{
cout < < x < < " ";
}
};
int main()
{
int ia[] = { 1,2,3,4,5 };
for_each(ia, ia + 5, display< int >());
system("pause");
return 0;
}
2.4.3 仿函數(shù)在STL中的定義
要使用STL內(nèi)建的仿函數(shù)，必須包含頭文件。而頭文件中包含的仿函數(shù)分類包括
1）算術(shù)類仿函數(shù)
加：plus
減：minus
乘：multiplies
除：divides
模取：modulus
否定：negate
例子：
#include < iostream >
#include < numeric >
#include < vector >
#include < functional >
using namespace std;
int main()
{
int ia[] = { 1,2,3,4,5 };
vector< int > iv(ia, ia + 5);
//120
cout < < accumulate(iv.begin(), iv.end(), 1, multiplies< int >()) < < endl;
//15
cout < < multiplies< int >()(3, 5) < < endl;
modulus< int > modulusObj;
cout < < modulusObj(3, 5) < < endl; // 3
system("pause");
return 0;
}
2）關(guān)系運(yùn)算類仿函數(shù)
等于：equal_to
不等于：not_equal_to
大于：greater
大于等于：greater_equal
小于：less
小于等于：less_equal
從大到小排序：
#include < iostream >
#include < algorithm >
#include< functional >
#include < vector >
using namespace std;
template < class T >
class display
{
public:
void operator()(const T &x)
{
cout < < x < < " ";
}
};
int main()
{
int ia[] = { 1,5,4,3,2 };
vector< int > iv(ia, ia + 5);
sort(iv.begin(), iv.end(), greater< int >());
for_each(iv.begin(), iv.end(), display< int >());
system("pause");
return 0;
}
3）邏輯運(yùn)算仿函數(shù)
邏輯與：logical_and
邏輯或：logical_or
邏輯否：logical_no
除了使用STL內(nèi)建的仿函數(shù)，還可使用自定義的仿函數(shù)，具體實(shí)例見(jiàn)文章3.4.7.2小結(jié)
2.5 容器適配器
標(biāo)準(zhǔn)庫(kù)提供了三種順序容器適配器：queue(FIFO隊(duì)列)、priority_queue(優(yōu)先級(jí)隊(duì)列)、stack(棧)
什么是容器適配器
適配器是使一種事物的行為類似于另外一種事物行為的一種機(jī)制”，適配器對(duì)容器進(jìn)行包裝，使其表現(xiàn)出另外一種行為。例 如，stack >實(shí)現(xiàn)了棧的功能，但其內(nèi)部使用順序容器vector來(lái)存儲(chǔ)數(shù)據(jù)。（相當(dāng)于是vector表現(xiàn)出 了棧的行為）。
容器適配器
要使用適配器，需要加入一下頭文件：
#include //stack
#include //queue、priority_queue
- 定義適配器
1、初始化
stack stk(dep);
2、覆蓋默認(rèn)容器類型
stack > stk;
- 使用適配器
2.5.1 stack
stack< int > s;
stack< int, vector< int > > stk; //覆蓋基礎(chǔ)容器類型，使用vector實(shí)現(xiàn)stk
s.empty(); //判斷stack是否為空，為空返回true，否則返回false
s.size(); //返回stack中元素的個(gè)數(shù)
s.pop(); //刪除棧頂元素，但不返回其值
s.top(); //返回棧頂元素的值，但不刪除此元素
s.push(item); //在棧頂壓入新元素item
實(shí)例：括號(hào)匹配
#include< iostream >
#include< cstdio >
#include< string >
#include< stack >
using namespace std;
int main()
{
string s;
stack< char > ss;
while (cin > > s)
{
bool flag = true;
for (char c : s) //C++11新標(biāo)準(zhǔn)，即遍歷一次字符串s
{
if (c == '(' || c == '{' || c == '[')
{
ss.push(c);
continue;
}
if (c == '}')
{
if (!ss.empty() && ss.top() == '{')
{
ss.pop();
continue;
}
else
{
flag = false;
break;
}
}
if (!ss.empty() && c == ']')
{
if (ss.top() == '[')
{
ss.pop();
continue;
}
else
{
flag = false;
break;
}
}
if (!ss.empty() && c == ')')
{
if (ss.top() == '(')
{
ss.pop();
continue;
}
else
{
flag = false;
break;
}
}
}
if (flag) cout < < "Match!" < < endl;
else cout < < "Not Match!" < < endl;
}
}
2.5.2 queue & priority_queue
queue< int > q; //priority_queue< int > q;
q.empty(); //判斷隊(duì)列是否為空
q.size(); //返回隊(duì)列長(zhǎng)度
q.push(item); //對(duì)于queue，在隊(duì)尾壓入一個(gè)新元素
//對(duì)于priority_queue，在基于優(yōu)先級(jí)的適當(dāng)位置插入新元素
//queue only:
q.front(); //返回隊(duì)首元素的值，但不刪除該元素
q.back(); //返回隊(duì)尾元素的值，但不刪除該元素
//priority_queue only:
q.top(); //返回具有最高優(yōu)先級(jí)的元素值，但不刪除該元素
3 常用容器用法介紹
3.1 vector
3.1.1 基本函數(shù)實(shí)現(xiàn)
1.構(gòu)造函數(shù)
- vector():創(chuàng)建一個(gè)空vector
- vector(int nSize):創(chuàng)建一個(gè)vector,元素個(gè)數(shù)為nSize
- vector(int nSize,const t& t):創(chuàng)建一個(gè)vector，元素個(gè)數(shù)為nSize,且值均為t
- vector(const vector&):復(fù)制構(gòu)造函數(shù)
- vector(begin,end):復(fù)制[begin,end)區(qū)間內(nèi)另一個(gè)數(shù)組的元素到vector中
2.增加函數(shù)
- void push_back(const T& x):向量尾部增加一個(gè)元素X
- iterator insert(iterator it,const T& x):向量中迭代器指向元素前增加一個(gè)元素x
- iterator insert(iterator it,int n,const T& x):向量中迭代器指向元素前增加n個(gè)相同的元素x
- iterator insert(iterator it,const_iterator first,const_iterator last):向量中迭代器指向元素前插入另一個(gè)相同類型向量的[first,last)間的數(shù)據(jù)
3.刪除函數(shù)
- iterator erase(iterator it):刪除向量中迭代器指向元素
- iterator erase(iterator first,iterator last):刪除向量中[first,last)中元素
- void pop_back():刪除向量中最后一個(gè)元素
- void clear():清空向量中所有元素
4.遍歷函數(shù)
- reference at(int pos):返回pos位置元素的引用
- reference front():返回首元素的引用
- reference back():返回尾元素的引用
- iterator begin():返回向量頭指針，指向第一個(gè)元素
- iterator end():返回向量尾指針，指向向量最后一個(gè)元素的下一個(gè)位置
- reverse_iterator rbegin():反向迭代器，指向最后一個(gè)元素
- reverse_iterator rend():反向迭代器，指向第一個(gè)元素之前的位置
5.判斷函數(shù)
- bool empty() const:判斷向量是否為空，若為空，則向量中無(wú)元素
6.大小函數(shù)
- int size() const:返回向量中元素的個(gè)數(shù)
- int capacity() const:返回當(dāng)前向量張紅所能容納的最大元素值
- int max_size() const:返回最大可允許的vector元素?cái)?shù)量值
7.其他函數(shù)
- void swap(vector&):交換兩個(gè)同類型向量的數(shù)據(jù)
- void assign(int n,const T& x):設(shè)置向量中第n個(gè)元素的值為x
- void assign(const_iterator first,const_iterator last):向量中[first,last)中元素設(shè)置成當(dāng)前向量元素
8.看著清楚
1.push_back 在數(shù)組的最后添加一個(gè)數(shù)據(jù)
2.pop_back 去掉數(shù)組的最后一個(gè)數(shù)據(jù)
.at-Domain Parked 得到編號(hào)位置的數(shù)據(jù)
4.begin 得到數(shù)組頭的指針
5.end 得到數(shù)組的最后一個(gè)單元+1的指針
6．front 得到數(shù)組頭的引用
7.back 得到數(shù)組的最后一個(gè)單元的引用
8.max_size 得到vector最大可以是多大
9.capacity 當(dāng)前vector分配的大小
10.size 當(dāng)前使用數(shù)據(jù)的大小
11.resize 改變當(dāng)前使用數(shù)據(jù)的大小，如果它比當(dāng)前使用的大，者填充默認(rèn)值
12.reserve 改變當(dāng)前vecotr所分配空間的大小
13.erase 刪除指針指向的數(shù)據(jù)項(xiàng)
14.clear 清空當(dāng)前的vector
15.rbegin 將vector反轉(zhuǎn)后的開(kāi)始指針?lè)祷?其實(shí)就是原來(lái)的end-1)
16.rend 將vector反轉(zhuǎn)構(gòu)的結(jié)束指針?lè)祷?其實(shí)就是原來(lái)的begin-1)
17.empty 判斷vector是否為空
18.swap 與另一個(gè)vector交換數(shù)據(jù)
3.1.2 基本用法
#include < vector >
using namespace std;
3.1.3 簡(jiǎn)單介紹
- Vector<類型>標(biāo)識(shí)符
- Vector<類型>標(biāo)識(shí)符(最大容量)
- Vector<類型>標(biāo)識(shí)符(最大容量,初始所有值)
- Int i[5]={1,2,3,4,5}
- Vector<類型>vi(I,i+2);//得到i索引值為3以后的值
- Vector< vector< int> >v; 二維向量//這里最外的<>要有空格。否則在比較舊的編譯器下無(wú)法通過(guò)
3.1.4 實(shí)例
3.1.4.1 pop_back()&push_back(elem)實(shí)例在容器最后移除和插入數(shù)據(jù)
#include < string.h >
#include < vector >
#include < iostream >
using namespace std;
int main()
{
vector< int >obj;//創(chuàng)建一個(gè)向量存儲(chǔ)容器 int
for(int i=0;i< 10;i++) // push_back(elem)在數(shù)組最后添加數(shù)據(jù)
{
obj.push_back(i);
cout<
輸出結(jié)果為：
0,1,2,3,4,5,6,7,8,9,
0,1,2,3,4,
3.1.4.2 clear()清除容器中所有數(shù)據(jù)
#include < string.h >
#include < vector >
#include < iostream >
using namespace std;
int main()
{
vector< int >obj;
for(int i=0;i< 10;i++)//push_back(elem)在數(shù)組最后添加數(shù)據(jù)
{
obj.push_back(i);
cout<
輸出結(jié)果為：
0,1,2,3,4,5,6,7,8,9,
3.1.4.3 排序
#include < string.h >
#include < vector >
#include < iostream >
#include < algorithm >
using namespace std;
int main()
{
vector< int >obj;
obj.push_back(1);
obj.push_back(3);
obj.push_back(0);
sort(obj.begin(),obj.end());//從小到大
cout< "從小到大:"<
輸出結(jié)果為：
從小到大:
0,1,3,
從大到小:
3,1,0,
1.注意 sort 需要頭文件 #include
2.如果想 sort 來(lái)降序，可重寫(xiě) sort
bool compare(int a,int b)
{
return a< b; //升序排列，如果改為return a >b，則為降序
}
int a[20]={2,4,1,23,5,76,0,43,24,65},i;
for(i=0;i< 20;i++)
cout< < a[i]< < endl;
sort(a,a+20,compare);
3.1.4.4 訪問(wèn)（直接數(shù)組訪問(wèn)&迭代器訪問(wèn)）
#include < string.h >
#include < vector >
#include < iostream >
#include < algorithm >
using namespace std;
int main()
{
//順序訪問(wèn)
vector< int >obj;
for(int i=0;i< 10;i++)
{
obj.push_back(i);
}
cout< "直接利用數(shù)組：";
for(int i=0;i< 10;i++)//方法一
{
cout<
輸出結(jié)果為：
直接利用數(shù)組：0 1 2 3 4 5 6 7 8 9
利用迭代器：0 1 2 3 4 5 6 7 8 9
3.1.4.5 二維數(shù)組兩種定義方法（結(jié)果一樣）
方法一
#include < string.h >
#include < vector >
#include < iostream >
#include < algorithm >
using namespace std;
int main()
{
int N=5, M=6;
vector< vector< int > > obj(N); //定義二維動(dòng)態(tài)數(shù)組大小5行
for(int i =0; i< obj.size(); i++)//動(dòng)態(tài)二維數(shù)組為5行6列，值全為0
{
obj[i].resize(M);
}
for(int i=0; i< obj.size(); i++)//輸出二維動(dòng)態(tài)數(shù)組
{
for(int j=0;j< obj[i].size();j++)
{
cout<
方法二
#include < string.h >
#include < vector >
#include < iostream >
#include < algorithm >
using namespace std;
int main()
{
int N=5, M=6;
vector< vector< int > > obj(N, vector< int >(M)); //定義二維動(dòng)態(tài)數(shù)組5行6列
for(int i=0; i< obj.size(); i++)//輸出二維動(dòng)態(tài)數(shù)組
{
for(int j=0;j< obj[i].size();j++)
{
cout<
輸出結(jié)果為：
0 0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 0
3.2 deque
所謂的deque是”double ended queue”的縮寫(xiě)，雙端隊(duì)列不論在尾部或頭部插入元素，都十分迅速。而在中間插入元素則會(huì)比較費(fèi)時(shí)，因?yàn)楸仨氁苿?dòng)中間其他的元素。雙端隊(duì)列是一種隨機(jī)訪問(wèn)的數(shù)據(jù)類型，提供了在序列兩端快速插入和刪除操作的功能，它可以在需要的時(shí)候改變自身大小，完成了標(biāo)準(zhǔn)的C++數(shù)據(jù)結(jié)構(gòu)中隊(duì)列的所有功能。
Vector是單向開(kāi)口的連續(xù)線性空間，deque則是一種雙向開(kāi)口的連續(xù)線性空間。deque對(duì)象在隊(duì)列的兩端放置元素和刪除元素是高效的，而向量vector只是在插入序列的末尾時(shí)操作才是高效的。deque和vector的最大差異，一在于deque允許于常數(shù)時(shí)間內(nèi)對(duì)頭端進(jìn)行元素的插入或移除操作，二在于deque沒(méi)有所謂的capacity觀念，因?yàn)樗莿?dòng)態(tài)地以分段連續(xù)空間組合而成，隨時(shí)可以增加一段新的空間并鏈接起來(lái)。換句話說(shuō)，像vector那樣“因舊空間不足而重新配置一塊更大空間，然后復(fù)制元素，再釋放舊空間”這樣的事情在deque中是不會(huì)發(fā)生的。也因此，deque沒(méi)有必要提供所謂的空間預(yù)留（reserved）功能。
雖然deque也提供Random Access Iterator，但它的迭代器并不是普通指針，其復(fù)雜度和vector不可同日而語(yǔ)，這當(dāng)然涉及到各個(gè)運(yùn)算層面。因此，除非必要，我們應(yīng)盡可能選擇使用vector而非deque。對(duì)deque進(jìn)行的排序操作，為了最高效率，可將deque先完整復(fù)制到一個(gè)vector身上，將vector排序后（利用STL的sort算法），再?gòu)?fù)制回deque。
deque是一種優(yōu)化了的對(duì)序列兩端元素進(jìn)行添加和刪除操作的基本序列容器。通常由一些獨(dú)立的區(qū)塊組成，第一區(qū)塊朝某方向擴(kuò)展，最后一個(gè)區(qū)塊朝另一方向擴(kuò)展。它允許較為快速地隨機(jī)訪問(wèn)但它不像vector一樣把所有對(duì)象保存在一個(gè)連續(xù)的內(nèi)存塊，而是多個(gè)連續(xù)的內(nèi)存塊。并且在一個(gè)映射結(jié)構(gòu)中保存對(duì)這些塊以及順序的跟蹤。
3.2.1 聲明deque容器
#include< deque > // 頭文件
deque< type > deq; // 聲明一個(gè)元素類型為type的雙端隊(duì)列que
deque< type > deq(size); // 聲明一個(gè)類型為type、含有size個(gè)默認(rèn)值初始化元素的的雙端隊(duì)列que
deque< type > deq(size, value); // 聲明一個(gè)元素類型為type、含有size個(gè)value元素的雙端隊(duì)列que
deque< type > deq(mydeque); // deq是mydeque的一個(gè)副本
deque< type > deq(first, last); // 使用迭代器first、last范圍內(nèi)的元素初始化deq
3.2.2 deque的常用成員函數(shù)
deque< int > deq;
- deq[ ]：用來(lái)訪問(wèn)雙向隊(duì)列中單個(gè)的元素。
- deq.front()：返回第一個(gè)元素的引用。
- deq.back()：返回最后一個(gè)元素的引用。
- deq.push_front(x)：把元素x插入到雙向隊(duì)列的頭部。
- deq.pop_front()：彈出雙向隊(duì)列的第一個(gè)元素。
- deq.push_back(x)：把元素x插入到雙向隊(duì)列的尾部。
- deq.pop_back()：彈出雙向隊(duì)列的最后一個(gè)元素。
3.2.3 deque的一些特點(diǎn)
- 支持隨機(jī)訪問(wèn)，即支持[ ]以及at()，但是性能沒(méi)有vector好。
- 可以在內(nèi)部進(jìn)行插入和刪除操作，但性能不及l(fā)ist。
- deque兩端都能夠快速插入和刪除元素，而vector只能在尾端進(jìn)行。
- deque的元素存取和迭代器操作會(huì)稍微慢一些，因?yàn)閐eque的內(nèi)部結(jié)構(gòu)會(huì)多一個(gè)間接過(guò)程。
- deque迭代器是特殊的智能指針，而不是一般指針，它需要在不同的區(qū)塊之間跳轉(zhuǎn)。
- deque可以包含更多的元素，其max_size可能更大，因?yàn)椴恢故褂靡粔K內(nèi)存。
- deque不支持對(duì)容量和內(nèi)存分配時(shí)機(jī)的控制。
- 在除了首尾兩端的其他地方插入和刪除元素，都將會(huì)導(dǎo)致指向deque元素的任何pointers、references、iterators失效。不過(guò)，deque的內(nèi)存重分配優(yōu)于vector，因?yàn)槠鋬?nèi)部結(jié)構(gòu)顯示不需要復(fù)制所有元素。
- deque的內(nèi)存區(qū)塊不再被使用時(shí)，會(huì)被釋放，deque的內(nèi)存大小是可縮減的。不過(guò)，是不是這么做以及怎么做由實(shí)際操作版本定義。
- deque不提供容量操作：capacity()和reverse()，但是vector可以。
3.2.4 實(shí)例
#include< iostream >
#include< stdio.h >
#include< deque >
using namespace std;
int main(void)
{
int i;
int a[10] = { 0,1,2,3,4,5,6,7,8,9 };
deque< int > q;
for (i = 0; i <= 9; i++)
{
if (i % 2 == 0)
q.push_front(a[i]);
else
q.push_back(a[i]);
} /*此時(shí)隊(duì)列里的內(nèi)容是: {8,6,4,2,0,1,3,5,7,9}*/
q.pop_front();
printf("%dn", q.front()); /*清除第一個(gè)元素后輸出第一個(gè)(6)*/
q.pop_back();
printf("%dn", q.back()); /*清除最后一個(gè)元素后輸出最后一個(gè)(7)*/
deque< int >::iterator it;
for (it = q.begin(); it != q.end(); it++) {
cout < < *it < < 't';
}
cout < < endl;
system("pause");
return 0;
}
輸出結(jié)果：
3.3 list
3.3.1 list定義
List是stl實(shí)現(xiàn)的雙向鏈表，與向量(vectors)相比, 它允許快速的插入和刪除，但是隨機(jī)訪問(wèn)卻比較慢。使用時(shí)需要添加頭文件
#include
3.3.2 list定義和初始化
listlst1; //創(chuàng)建空l(shuí)ist
list lst2(5); //創(chuàng)建含有5個(gè)元素的list
listlst3(3,2); //創(chuàng)建含有3個(gè)元素的list
listlst4(lst2); //使用lst2初始化lst4
listlst5(lst2.begin(),lst2.end()); //同lst4
3.3.3 list常用操作函數(shù)
Lst1.assign() 給list賦值
Lst1.back() 返回最后一個(gè)元素
Lst1.begin() 返回指向第一個(gè)元素的迭代器
Lst1.clear() 刪除所有元素
Lst1.empty() 如果list是空的則返回true
Lst1.end() 返回末尾的迭代器
Lst1.erase() 刪除一個(gè)元素
Lst1.front() 返回第一個(gè)元素
Lst1.get_allocator() 返回list的配置器
Lst1.insert() 插入一個(gè)元素到list中
Lst1.max_size() 返回list能容納的最大元素?cái)?shù)量
Lst1.merge() 合并兩個(gè)list
Lst1.pop_back() 刪除最后一個(gè)元素
Lst1.pop_front() 刪除第一個(gè)元素
Lst1.push_back() 在list的末尾添加一個(gè)元素
Lst1.push_front() 在list的頭部添加一個(gè)元素
Lst1.rbegin() 返回指向第一個(gè)元素的逆向迭代器
Lst1.remove() 從list刪除元素
Lst1.remove_if() 按指定條件刪除元素
Lst1.rend() 指向list末尾的逆向迭代器
Lst1.resize() 改變list的大小
Lst1.reverse() 把list的元素倒轉(zhuǎn)
Lst1.size() 返回list中的元素個(gè)數(shù)
Lst1.sort() 給list排序
Lst1.splice() 合并兩個(gè)list
Lst1.swap() 交換兩個(gè)list
Lst1.unique() 刪除list中相鄰重復(fù)的元素
3.3.4 List使用實(shí)例
3.3.4.1 迭代器遍歷list
for(list< int >::const_iteratoriter = lst1.begin();iter != lst1.end();iter++)
{
cout< iter;
}
cout<
3.3.4.2 綜合實(shí)例1
#include < iostream >
#include < list >
#include < numeric >
#include < algorithm >
using namespace std;
typedef list< int > LISTINT;
typedef list< int > LISTCHAR;
void main()
{
//用LISTINT創(chuàng)建一個(gè)list對(duì)象
LISTINT listOne;
//聲明i為迭代器
LISTINT::iterator i;
listOne.push_front(3);
listOne.push_front(2);
listOne.push_front(1);
listOne.push_back(4);
listOne.push_back(5);
listOne.push_back(6);
cout < < "listOne.begin()--- listOne.end():" < < endl;
for (i = listOne.begin(); i != listOne.end(); ++i)
cout < < *i < < " ";
cout < < endl;
LISTINT::reverse_iterator ir;
cout < < "listOne.rbegin()---listOne.rend():" < < endl;
for (ir = listOne.rbegin(); ir != listOne.rend(); ir++) {
cout < < *ir < < " ";
}
cout < < endl;
int result = accumulate(listOne.begin(), listOne.end(), 0);
cout < < "Sum=" < < result < < endl;
cout < < "------------------" < < endl;
//用LISTCHAR創(chuàng)建一個(gè)list對(duì)象
LISTCHAR listTwo;
//聲明i為迭代器
LISTCHAR::iterator j;
listTwo.push_front('C');
listTwo.push_front('B');
listTwo.push_front('A');
listTwo.push_back('D');
listTwo.push_back('E');
listTwo.push_back('F');
cout < < "listTwo.begin()---listTwo.end():" < < endl;
for (j = listTwo.begin(); j != listTwo.end(); ++j)
cout < < char(*j) < < " ";
cout < < endl;
j = max_element(listTwo.begin(), listTwo.end());
cout < < "The maximum element in listTwo is: " < < char(*j) < < endl;
system("pause");
}
輸出結(jié)果
3.3.4.3 綜合實(shí)例2
#include < iostream >
#include < list >
using namespace std;
typedef list< int > INTLIST;
//從前向后顯示list隊(duì)列的全部元素
void put_list(INTLIST list, char *name)
{
INTLIST::iterator plist;
cout < < "The contents of " < < name < < " : ";
for (plist = list.begin(); plist != list.end(); plist++)
cout < < *plist < < " ";
cout < < endl;
}
//測(cè)試list容器的功能
void main(void)
{
//list1對(duì)象初始為空
INTLIST list1;
INTLIST list2(5, 1);
INTLIST list3(list2.begin(), --list2.end());
//聲明一個(gè)名為i的雙向迭代器
INTLIST::iterator i;
put_list(list1, "list1");
put_list(list2, "list2");
put_list(list3, "list3");
list1.push_back(7);
list1.push_back(8);
cout < < "list1.push_back(7) and list1.push_back(8):" < < endl;
put_list(list1, "list1");
list1.push_front(6);
list1.push_front(5);
cout < < "list1.push_front(6) and list1.push_front(5):" < < endl;
put_list(list1, "list1");
list1.insert(++list1.begin(), 3, 9);
cout < < "list1.insert(list1.begin()+1,3,9):" < < endl;
put_list(list1, "list1");
//測(cè)試引用類函數(shù)
cout < < "list1.front()=" < < list1.front() < < endl;
cout < < "list1.back()=" < < list1.back() < < endl;
list1.pop_front();
list1.pop_back();
cout < < "list1.pop_front() and list1.pop_back():" < < endl;
put_list(list1, "list1");
list1.erase(++list1.begin());
cout < < "list1.erase(++list1.begin()):" < < endl;
put_list(list1, "list1");
list2.assign(8, 1);
cout < < "list2.assign(8,1):" < < endl;
put_list(list2, "list2");
cout < < "list1.max_size(): " < < list1.max_size() < < endl;
cout < < "list1.size(): " < < list1.size() < < endl;
cout < < "list1.empty(): " < < list1.empty() < < endl;
put_list(list1, "list1");
put_list(list3, "list3");
cout < < "list1 >list3: " < < (list1 > list3) < < endl;
cout < < "list1< list3: " < < (list1 < list3) < < endl;
list1.sort();
put_list(list1, "list1");
list1.splice(++list1.begin(), list3);
put_list(list1, "list1");
put_list(list3, "list3");
system("pause");
}
輸出結(jié)果：
3.4 map/multimap
map和multimap都需要#include，唯一的不同是，map的鍵值key不可重復(fù)，而multimap可以，也正是由于這種區(qū)別，map支持[ ]運(yùn)算符，multimap不支持[ ]運(yùn)算符。在用法上沒(méi)什么區(qū)別。
C++中map提供的是一種鍵值對(duì)容器，里面的數(shù)據(jù)都是成對(duì)出現(xiàn)的,如下圖：每一對(duì)中的第一個(gè)值稱之為關(guān)鍵字(key)，每個(gè)關(guān)鍵字只能在map中出現(xiàn)一次；第二個(gè)稱之為該關(guān)鍵字的對(duì)應(yīng)值。
Map是STL的一個(gè)關(guān)聯(lián)容器，它提供一對(duì)一（其中第一個(gè)可以稱為關(guān)鍵字，每個(gè)關(guān)鍵字只能在map中出現(xiàn)一次，第二個(gè)可能稱為該關(guān)鍵字的值）的數(shù)據(jù) 處理能力，由于這個(gè)特性，它完成有可能在我們處理一對(duì)一數(shù)據(jù)的時(shí)候，在編程上提供快速通道。這里說(shuō)下map內(nèi)部數(shù)據(jù)的組織，map內(nèi)部自建一顆紅黑樹(shù)(一 種非嚴(yán)格意義上的平衡二叉樹(shù))，這顆樹(shù)具有對(duì)數(shù)據(jù)自動(dòng)排序的功能，所以在map內(nèi)部所有的數(shù)據(jù)都是有序的。
3.4.1 基本操作函數(shù)
begin() 返回指向map頭部的迭代器
clear(） 刪除所有元素
count() 返回指定元素出現(xiàn)的次數(shù)
empty() 如果map為空則返回true
end() 返回指向map末尾的迭代器
equal_range() 返回特殊條目的迭代器對(duì)
erase() 刪除一個(gè)元素
find() 查找一個(gè)元素
get_allocator() 返回map的配置器
insert() 插入元素
key_comp() 返回比較元素key的函數(shù)
lower_bound() 返回鍵值>=給定元素的第一個(gè)位置
max_size() 返回可以容納的最大元素個(gè)數(shù)
rbegin() 返回一個(gè)指向map尾部的逆向迭代器
rend() 返回一個(gè)指向map頭部的逆向迭代器
size() 返回map中元素的個(gè)數(shù)
swap() 交換兩個(gè)map
upper_bound() 返回鍵值>給定元素的第一個(gè)位置
value_comp() 返回比較元素value的函數(shù)
3.4.2 聲明
//頭文件
#include< map >
map< int, string > ID_Name;
// 使用{}賦值是從c++11開(kāi)始的，因此編譯器版本過(guò)低時(shí)會(huì)報(bào)錯(cuò)，如visual studio 2012
map< int, string > ID_Name = {
{ 2015, "Jim" },
{ 2016, "Tom" },
{ 2017, "Bob" } };
3.4.3 迭代器
共有八個(gè)獲取迭代器的函數(shù)：* begin, end, rbegin,rend* 以及對(duì)應(yīng)的 * cbegin, cend, crbegin,crend*。
二者的區(qū)別在于，后者一定返回 const_iterator，而前者則根據(jù)map的類型返回iterator 或者 const_iterator。const情況下，不允許對(duì)值進(jìn)行修改。如下面代碼所示：
map< int,int >::iterator it;
map< int,int > mmap;
const map< int,int > const_mmap;
it = mmap.begin(); //iterator
mmap.cbegin(); //const_iterator
const_mmap.begin(); //const_iterator
const_mmap.cbegin(); //const_iterator
返回的迭代器可以進(jìn)行加減操作，此外，如果map為空，則 begin = end。
3.4.4 插入操作
3.4.4.1 用insert插入pair數(shù)據(jù)
//數(shù)據(jù)的插入--第一種：用insert函數(shù)插入pair數(shù)據(jù)
#include < map >
#include < string >
#include < iostream >
using namespace std;
int main()
{
map< int, string > mapStudent;
mapStudent.insert(pair< int, string >(1, "student_one"));
mapStudent.insert(pair< int, string >(2, "student_two"));
mapStudent.insert(pair< int, string >(3, "student_three"));
map< int, string >::iterator iter;
for(iter = mapStudent.begin(); iter != mapStudent.end(); iter++)
cout<
3.4.4.2 用insert函數(shù)插入value_type數(shù)據(jù)
//第二種：用insert函數(shù)插入value_type數(shù)據(jù)，下面舉例說(shuō)明
#include < map >
#include < string >
#include < iostream >
using namespace std;
int main()
{
map< int, string > mapStudent;
mapStudent.insert(map< int, string >::value_type (1, "student_one"));
mapStudent.insert(map< int, string >::value_type (2, "student_two"));
mapStudent.insert(map< int, string >::value_type (3, "student_three"));
map< int, string >::iterator iter;
for(iter = mapStudent.begin(); iter != mapStudent.end(); iter++)
cout<
3.4.4.3 用insert函數(shù)進(jìn)行多個(gè)插入
insert共有4個(gè)重載函數(shù)：
// 插入單個(gè)鍵值對(duì)，并返回插入位置和成功標(biāo)志，插入位置已經(jīng)存在值時(shí)，插入失敗
pair< iterator,bool > insert (const value_type& val);
//在指定位置插入，在不同位置插入效率是不一樣的，因?yàn)樯婕暗街嘏?/span>
iterator insert (const_iterator position, const value_type& val);
// 插入多個(gè)
void insert (InputIterator first, InputIterator last);
//c++11開(kāi)始支持，使用列表插入多個(gè)
void insert (initializer_list< value_type > il);
下面是具體使用示例：
#include < iostream >
#include < map >
int main()
{
std::map< char, int > mymap;
// 插入單個(gè)值
mymap.insert(std::pair< char, int >('a', 100));
mymap.insert(std::pair< char, int >('z', 200));
//返回插入位置以及是否插入成功
std::pair< std::map< char, int >::iterator, bool > ret;
ret = mymap.insert(std::pair< char, int >('z', 500));
if (ret.second == false) {
std::cout < < "element 'z' already existed";
std::cout < < " with a value of " < < ret.first- >second < < 'n';
}
//指定位置插入
std::map< char, int >::iterator it = mymap.begin();
mymap.insert(it, std::pair< char, int >('b', 300)); //效率更高
mymap.insert(it, std::pair< char, int >('c', 400)); //效率非最高
//范圍多值插入
std::map< char, int > anothermap;
anothermap.insert(mymap.begin(), mymap.find('c'));
// 列表形式插入
anothermap.insert({ { 'd', 100 }, {'e', 200} });
return 0;
}
3.4.4.4 用數(shù)組方式插入數(shù)據(jù)
//第三種：用數(shù)組方式插入數(shù)據(jù)，下面舉例說(shuō)明
#include < map >
#include < string >
#include < iostream >
using namespace std;
int main()
{
map< int, string > mapStudent;
mapStudent[1] = "student_one";
mapStudent[2] = "student_two";
mapStudent[3] = "student_three";
map< int, string >::iterator iter;
for(iter = mapStudent.begin(); iter != mapStudent.end(); iter++)
cout<
以上三種用法，雖然都可以實(shí)現(xiàn)數(shù)據(jù)的插入，但是它們是有區(qū)別的，當(dāng)然了第一種和第二種在效果上是完成一樣的，用insert函數(shù)插入數(shù)據(jù)，在數(shù)據(jù)的 插入上涉及到集合的唯一性這個(gè)概念，即當(dāng)map中有這個(gè)關(guān)鍵字時(shí)，insert操作是插入數(shù)據(jù)不了的，但是用數(shù)組方式就不同了，它可以覆蓋以前該關(guān)鍵字對(duì) 應(yīng)的值，用程序說(shuō)明
mapStudent.insert(map::value_type (1, "student_one"));
mapStudent.insert(map::value_type (1, "student_two"));
上面這兩條語(yǔ)句執(zhí)行后，map中1這個(gè)關(guān)鍵字對(duì)應(yīng)的值是“student_one”，第二條語(yǔ)句并沒(méi)有生效，那么這就涉及到我們?cè)趺粗纈nsert語(yǔ)句是否插入成功的問(wèn)題了，可以用pair來(lái)獲得是否插入成功，程序如下
pair::iterator, bool> Insert_Pair;
Insert_Pair = mapStudent.insert(map::value_type (1, "student_one"));
我們通過(guò)pair的第二個(gè)變量來(lái)知道是否插入成功，它的第一個(gè)變量返回的是一個(gè)map的迭代器，如果插入成功的話Insert_Pair.second應(yīng)該是true的，否則為false。
下面給出完成代碼，演示插入成功與否問(wèn)題
//驗(yàn)證插入函數(shù)的作用效果
#include < map >
#include < string >
#include < iostream >
using namespace std;
int main()
{
map< int, string > mapStudent;
pair< map< int, string >::iterator, bool > Insert_Pair;
Insert_Pair = mapStudent.insert(pair< int, string >(1, "student_one"));
if(Insert_Pair.second == true)
cout< "Insert Successfully"<
大家可以用如下程序，看下用數(shù)組插入在數(shù)據(jù)覆蓋上的效果
//驗(yàn)證數(shù)組形式插入數(shù)據(jù)的效果
#include < map >
#include < string >
#include < iostream >
using namespace std;
int main()
{
map< int, string > mapStudent;
mapStudent[1] = "student_one";
mapStudent[1] = "student_two";
mapStudent[2] = "student_three";
map< int, string >::iterator iter;
for(iter = mapStudent.begin(); iter != mapStudent.end(); iter++)
cout<
3.4.5 查找、刪除、交換
查找
// 關(guān)鍵字查詢，找到則返回指向該關(guān)鍵字的迭代器，否則返回指向end的迭代器
// 根據(jù)map的類型，返回的迭代器為 iterator 或者 const_iterator
iterator find (const key_type& k);
const_iterator find (const key_type& k) const;
刪除
// 刪除迭代器指向位置的鍵值對(duì)，并返回一個(gè)指向下一元素的迭代器
iterator erase( iterator pos )
// 刪除一定范圍內(nèi)的元素，并返回一個(gè)指向下一元素的迭代器
iterator erase( const_iterator first, const_iterator last );
// 根據(jù)Key來(lái)進(jìn)行刪除， 返回刪除的元素?cái)?shù)量，在map里結(jié)果非0即1
size_t erase( const key_type& key );
// 清空map，清空后的size為0
void clear();
交換
// 就是兩個(gè)map的內(nèi)容互換
void swap( map& other );
3.4.6 容量
// 查詢map是否為空
bool empty();
// 查詢map中鍵值對(duì)的數(shù)量
size_t size();
// 查詢map所能包含的最大鍵值對(duì)數(shù)量，和系統(tǒng)和應(yīng)用庫(kù)有關(guān)。
// 此外，這并不意味著用戶一定可以存這么多，很可能還沒(méi)達(dá)到就已經(jīng)開(kāi)辟內(nèi)存失敗了
size_t max_size();
// 查詢關(guān)鍵字為key的元素的個(gè)數(shù)，在map里結(jié)果非0即1
size_t count( const Key& key ) const; //
3.4.7 排序
map中的元素是自動(dòng)按Key升序排序，所以不能對(duì)map用sort函數(shù)；
這里要講的是一點(diǎn)比較高深的用法了,排序問(wèn)題，STL中默認(rèn)是采用小于號(hào)來(lái)排序的，以上代碼在排序上是不存在任何問(wèn)題的，因?yàn)樯厦娴年P(guān)鍵字是int 型，它本身支持小于號(hào)運(yùn)算，在一些特殊情況，比如關(guān)鍵字是一個(gè)結(jié)構(gòu)體或者自定義類，涉及到排序就會(huì)出現(xiàn)問(wèn)題，因?yàn)樗鼪](méi)有小于號(hào)操作，insert等函數(shù)在編譯的時(shí)候過(guò) 不去，下面給出兩個(gè)方法解決這個(gè)問(wèn)題。
3.4.7.1 小于號(hào) < 重載
#include < iostream >
#include < string >
#include < map >
using namespace std;
typedef struct tagStudentinfo
{
int niD;
string strName;
bool operator < (tagStudentinfo const& _A) const
{ //這個(gè)函數(shù)指定排序策略，按niD排序，如果niD相等的話，按strName排序
if (niD < _A.niD) return true;
if (niD == _A.niD)
return strName.compare(_A.strName) < 0;
return false;
}
}Studentinfo, *PStudentinfo; //學(xué)生信息
int main()
{
int nSize; //用學(xué)生信息映射分?jǐn)?shù)
map< Studentinfo, int >mapStudent;
map< Studentinfo, int >::iterator iter;
Studentinfo studentinfo;
studentinfo.niD = 1;
studentinfo.strName = "student_one";
mapStudent.insert(pair< Studentinfo, int >(studentinfo, 90));
studentinfo.niD = 2;
studentinfo.strName = "student_two";
mapStudent.insert(pair< Studentinfo, int >(studentinfo, 80));
for (iter = mapStudent.begin(); iter != mapStudent.end(); iter++)
cout < < iter- >first.niD < < ' ' < < iter- >first.strName < < ' ' < < iter- >second < < endl;
return 0;
}
3.4.7.2 仿函數(shù)的應(yīng)用，這個(gè)時(shí)候結(jié)構(gòu)體中沒(méi)有直接的小于號(hào)重載
//第二種：仿函數(shù)的應(yīng)用，這個(gè)時(shí)候結(jié)構(gòu)體中沒(méi)有直接的小于號(hào)重載，程序說(shuō)明
#include < iostream >
#include < map >
#include < string >
using namespace std;
typedef struct tagStudentinfo
{
int niD;
string strName;
}Studentinfo, *PStudentinfo; //學(xué)生信息
class sort
{
public:
bool operator() (Studentinfo const &_A, Studentinfo const &_B) const
{
if (_A.niD < _B.niD)
return true;
if (_A.niD == _B.niD)
return _A.strName.compare(_B.strName) < 0;
return false;
}
};
int main()
{
//用學(xué)生信息映射分?jǐn)?shù)
map< Studentinfo, int, sort >mapStudent;
map< Studentinfo, int >::iterator iter;
Studentinfo studentinfo;
studentinfo.niD = 1;
studentinfo.strName = "student_one";
mapStudent.insert(pair< Studentinfo, int >(studentinfo, 90));
studentinfo.niD = 2;
studentinfo.strName = "student_two";
mapStudent.insert(pair< Studentinfo, int >(studentinfo, 80));
for (iter = mapStudent.begin(); iter != mapStudent.end(); iter++)
cout < < iter- >first.niD < < ' ' < < iter- >first.strName < < ' ' < < iter- >second < < endl;
system("pause");
}
3.4.8 unordered_map
在c++11標(biāo)準(zhǔn)前，c++標(biāo)準(zhǔn)庫(kù)中只有一種map，但是它的底層實(shí)現(xiàn)并不是適合所有的場(chǎng)景，如果我們需要其他適合的map實(shí)現(xiàn)就不得不使用比如boost庫(kù)等三方的實(shí)現(xiàn)，在c++11中加了一種map unordered_map,unordered_set,他們的實(shí)現(xiàn)有什么不同呢？
map底層采用的是紅黑樹(shù)的實(shí)現(xiàn)查詢的時(shí)間復(fù)雜度為O(logn),看起來(lái)并沒(méi)有unordered_map快，但是也要看實(shí)際的數(shù)據(jù)量，雖然unordered_map的查詢從算法上分析比map快，但是它有一些其它的消耗，比如哈希函數(shù)的構(gòu)造和分析，還有如果出現(xiàn)哈希沖突解決哈希沖突等等都有一定的消耗，因此unordered_map的效率在很大的程度上由它的hash函數(shù)算法決定，而紅黑樹(shù)的效率是一個(gè)穩(wěn)定值。
unordered_map的底層采用哈希表的實(shí)現(xiàn)，查詢的時(shí)間復(fù)雜度為是O(1)。所以u(píng)nordered_map內(nèi)部就是無(wú)序的，數(shù)據(jù)是按散列函數(shù)插入到槽里面去的，數(shù)據(jù)之間無(wú)順序可言，如果我們不需要內(nèi)部有序，這種實(shí)現(xiàn)是沒(méi)有問(wèn)題的。unordered_map屬于關(guān)聯(lián)式容器，采用std::pair保存key-value形式的數(shù)據(jù)。用法與map一致。特別的是，STL中的map因?yàn)槭怯行虻亩鏄?shù)存儲(chǔ)，所以對(duì)key值需要有大小的判斷，當(dāng)使用內(nèi)置類型時(shí)，無(wú)需重載operator < ；但是用用戶自定義類型的話，就需要重載operator < 。 unoredered_map全程使用不需要比較元素的key值的大小，但是，對(duì)于元素的==要有判斷，又因?yàn)樾枰褂胔ash映射，所以，對(duì)于非內(nèi)部類型，需要程序員為其定義這二者的內(nèi)容，對(duì)于內(nèi)部類型，就不需要了。unordered庫(kù)使用“桶”來(lái)存儲(chǔ)元素，散列值相同的被存儲(chǔ)在一個(gè)桶里。當(dāng)散列容器中有大量數(shù)據(jù)時(shí)，同一個(gè)桶里的數(shù)據(jù)也會(huì)增多，造成訪問(wèn)沖突，降低性能。為了提高散列容器的性能，unordered庫(kù)會(huì)在插入元素是自動(dòng)增加桶的數(shù)量，不需要用戶指定。但是，用戶也可以在構(gòu)造函數(shù)或者rehash()函數(shù)中，指定最小的桶的數(shù)量。
還有另外一點(diǎn)從占用內(nèi)存上來(lái)說(shuō)因?yàn)閡nordered_map才用hash結(jié)構(gòu)會(huì)有一定的內(nèi)存損失，它的內(nèi)存占用回高于map。
最后就是她們的場(chǎng)景了，首先如果你需要對(duì)map中的數(shù)據(jù)排序，就首選map，他會(huì)把你的數(shù)據(jù)按照key的自然排序排序（由于它的底層實(shí)現(xiàn)紅黑樹(shù)機(jī)制所以會(huì)排序），如果不需要排序，就看你對(duì)內(nèi)存和cpu的選擇了，不過(guò)一般都會(huì)選擇unordered_map，它的查找效率會(huì)更高。
至于使用方法和函數(shù)，兩者差不多，由于篇幅限制這里不再贅述，unordered_multimap用法亦可類推。
3.5 set/multiset
std::set 是關(guān)聯(lián)容器，含有 Key 類型對(duì)象的已排序集。用比較函數(shù)compare進(jìn)行排序。搜索、移除和插入擁有對(duì)數(shù)復(fù)雜度。 set 通常以紅黑樹(shù)實(shí)現(xiàn)。
set容器內(nèi)的元素會(huì)被自動(dòng)排序，set與map不同，set中的元素即是鍵值又是實(shí)值，set不允許兩個(gè)元素有相同的鍵值。不能通過(guò)set的迭代器去修改set元素，原因是修改元素會(huì)破壞set組織。當(dāng)對(duì)容器中的元素進(jìn)行插入或者刪除時(shí)，操作之前的所有迭代器在操作之后依然有效。
由于set元素是排好序的，且默認(rèn)為升序，因此當(dāng)set集合中的元素為結(jié)構(gòu)體或自定義類時(shí)，該結(jié)構(gòu)體或自定義類必須實(shí)現(xiàn)運(yùn)算符‘<’的重載。
multiset特性及用法和set完全相同，唯一的差別在于它允許鍵值重復(fù)。
set和multiset的底層實(shí)現(xiàn)是一種高效的平衡二叉樹(shù)，即紅黑樹(shù)（Red-Black Tree）。
3.5.1 set常用成員函數(shù)
- begin()--返回指向第一個(gè)元素的迭代器
- clear()--清除所有元素
- count()--返回某個(gè)值元素的個(gè)數(shù)
- empty()--如果集合為空，返回true
- end()--返回指向最后一個(gè)元素的迭代器
- equal_range()--返回集合中與給定值相等的上下限的兩個(gè)迭代器
- erase()--刪除集合中的元素
- find()--返回一個(gè)指向被查找到元素的迭代器
- get_allocator()--返回集合的分配器
- insert()--在集合中插入元素
- lower_bound()--返回指向大于（或等于）某值的第一個(gè)元素的迭代器
- key_comp()--返回一個(gè)用于元素間值比較的函數(shù)
- max_size()--返回集合能容納的元素的最大限值
- rbegin()--返回指向集合中最后一個(gè)元素的反向迭代器
- rend()--返回指向集合中第一個(gè)元素的反向迭代器
- size()--集合中元素的數(shù)目
- swap()--交換兩個(gè)集合變量
- upper_bound()--返回大于某個(gè)值元素的迭代器
- value_comp()--返回一個(gè)用于比較元素間的值的函數(shù)
3.5.2 代碼示例
以下代碼涉及的內(nèi)容：
1、set容器中，元素類型為基本類型，如何讓set按照用戶意愿來(lái)排序？
2、set容器中，如何讓元素類型為自定義類型？
3、set容器的insert函數(shù)的返回值為什么類型？
#include < iostream >
#include < string >
#include < set >
using namespace std;
/* 仿函數(shù)CompareSet，在test02使用 */
class CompareSet
{
public:
//從大到小排序
bool operator()(int v1, int v2)
{
return v1 > v2;
}
//從小到大排序
//bool operator()(int v1, int v2)
//{
// return v1 < v2;
//}
};
/* Person類，用于test03 */
class Person
{
friend ostream &operator< const Person &person);
public:
Person(string name, int age)
{
mName = name;
mAge = age;
}
public:
string mName;
int mAge;
};
ostream &operator< const Person &person)
{
out < < "name:" < < person.mName < < " age:" < < person.mAge < < endl;
return out;
}
/* 仿函數(shù)ComparePerson,用于test03 */
class ComparePerson
{
public:
//名字大的在前面，如果名字相同，年齡大的排前面
bool operator()(const Person &p1, const Person &p2)
{
if (p1.mName == p2.mName)
{
return p1.mAge > p2.mAge;
}
return p1.mName > p2.mName;
}
};
/* 打印set類型的函數(shù)模板 */
template< typename T >
void PrintSet(T &s)
{
for (T::iterator iter = s.begin(); iter != s.end(); ++iter)
cout < < *iter < < " ";
cout < < endl;
}
void test01()
{
//set容器默認(rèn)從小到大排序
set< int > s;
s.insert(10);
s.insert(20);
s.insert(30);
//輸出set
PrintSet(s);
//結(jié)果為:10 20 30
/* set的insert函數(shù)返回值為一個(gè)對(duì)組(pair)。
對(duì)組的第一個(gè)值first為set類型的迭代器：
1、若插入成功，迭代器指向該元素。
2、若插入失敗，迭代器指向之前已經(jīng)存在的元素
對(duì)組的第二個(gè)值seconde為bool類型：
1、若插入成功，bool值為true
2、若插入失敗，bool值為false
*/
pair< set< int >::iterator, bool > ret = s.insert(40);
if (true == ret.second)
cout < < *ret.first < < " 插入成功" < < endl;
else
cout < < *ret.first < < " 插入失敗" < < endl;
}
void test02()
{
/* 如果想讓set容器從大到小排序，需要給set容
器提供一個(gè)仿函數(shù),本例的仿函數(shù)為CompareSet
*/
set< int, CompareSet > s;
s.insert(10);
s.insert(20);
s.insert(30);
//打印set
PrintSet(s);
//結(jié)果為:30,20,10
}
void test03()
{
/* set元素類型為Person，當(dāng)set元素類型為自定義類型的時(shí)候
必須給set提供一個(gè)仿函數(shù)，用于比較自定義類型的大小，
否則無(wú)法通過(guò)編譯
*/
set< Person,ComparePerson > s;
s.insert(Person("John", 22));
s.insert(Person("Peter", 25));
s.insert(Person("Marry", 18));
s.insert(Person("Peter", 36));
//打印set
PrintSet(s);
}
int main(void)
{
//test01();
//test02();
//test03();
return 0;
}
multiset容器的insert函數(shù)返回值為什么？
#include < iostream >
#include < set >
using namespace std;
/* 打印set類型的函數(shù)模板 */
template< typename T >
void PrintSet(T &s)
{
for (T::iterator iter = s.begin(); iter != s.end(); ++iter)
cout < < *iter < < " ";
cout < < endl;
}
void test(void)
{
multiset< int > s;
s.insert(10);
s.insert(20);
s.insert(30);
//打印multiset
PrintSet(s);
/* multiset的insert函數(shù)返回值為multiset類型的迭代器，
指向新插入的元素。multiset允許插入相同的值，因此
插入一定成功，因此不需要返回bool類型。
*/
multiset< int >::iterator iter = s.insert(10);
cout < < *iter < < endl;
}
int main(void)
{
test();
return 0;
}
3.5.3 unordered_set
C++ 11中出現(xiàn)了兩種新的關(guān)聯(lián)容器:unordered_set和unordered_map，其內(nèi)部實(shí)現(xiàn)與set和map大有不同，set和map內(nèi)部實(shí)現(xiàn)是基于RB-Tree，而unordered_set和unordered_map內(nèi)部實(shí)現(xiàn)是基于哈希表(hashtable)，由于unordered_set和unordered_map內(nèi)部實(shí)現(xiàn)的公共接口大致相同，所以本文以u(píng)nordered_set為例。
unordered_set是基于哈希表，因此要了解unordered_set，就必須了解哈希表的機(jī)制。哈希表是根據(jù)關(guān)鍵碼值而進(jìn)行直接訪問(wèn)的數(shù)據(jù)結(jié)構(gòu)，通過(guò)相應(yīng)的哈希函數(shù)(也稱散列函數(shù))處理關(guān)鍵字得到相應(yīng)的關(guān)鍵碼值，關(guān)鍵碼值對(duì)應(yīng)著一個(gè)特定位置，用該位置來(lái)存取相應(yīng)的信息，這樣就能以較快的速度獲取關(guān)鍵字的信息。比如：現(xiàn)有公司員工的個(gè)人信息（包括年齡），需要查詢某個(gè)年齡的員工個(gè)數(shù)。由于人的年齡范圍大約在[0，200]，所以可以開(kāi)一個(gè)200大小的數(shù)組，然后通過(guò)哈希函數(shù)得到key對(duì)應(yīng)的key-value，這樣就能完成統(tǒng)計(jì)某個(gè)年齡的員工個(gè)數(shù)。而在這個(gè)例子中，也存在這樣一個(gè)問(wèn)題，兩個(gè)員工的年齡相同，但其他信息（如：名字、身份證）不同，通過(guò)前面說(shuō)的哈希函數(shù)，會(huì)發(fā)現(xiàn)其都位于數(shù)組的相同位置，這里，就涉及到“沖突”。準(zhǔn)確來(lái)說(shuō)，沖突是不可避免的，而解決沖突的方法常見(jiàn)的有：開(kāi)發(fā)地址法、再散列法、鏈地址法(也稱拉鏈法)。而unordered_set內(nèi)部解決沖突采用的是----鏈地址法，當(dāng)用沖突發(fā)生時(shí)把具有同一關(guān)鍵碼的數(shù)據(jù)組成一個(gè)鏈表。下圖展示了鏈地址法的使用:
使用unordered_set需要包含#include頭文件，同unordered_map類似，用法沒(méi)有什么太大的區(qū)別，參考set/multiset。
除此之外unordered_multiset也是一種可選的容器。
-
C++
+關(guān)注
關(guān)注
22文章
2108瀏覽量
73618 -
STL
+關(guān)注
關(guān)注
0文章
86瀏覽量
18319 -
數(shù)據(jù)結(jié)構(gòu)
+關(guān)注
關(guān)注
3文章
573瀏覽量
40121 -
程序設(shè)計(jì)
+關(guān)注
關(guān)注
3文章
261瀏覽量
30391
發(fā)布評(píng)論請(qǐng)先 登錄
相關(guān)推薦
STL130N6F7 MOS管
STL130N6F7 MOS管
STL130N6F7 MOS管現(xiàn)貨
X-CUBE-STL與ARM的STL的區(qū)別是什么？
effective stl中文版下載pdf
C++ STL的概念及舉例
PLC控制系統(tǒng)設(shè)計(jì)教程： 加熱爐送料系統(tǒng)——仿STL指令的編程方式梯形圖舉例
實(shí)用的西門(mén)子PLC工控機(jī)S7-300STL指令詳解
雙足機(jī)器人STL 3D模型詳細(xì)資料合集免費(fèi)下載
STL的概述
C++之STL庫(kù)中的容器
使用STL函數(shù)控制傳送帶
工商網(wǎng)監(jiān)
評(píng)論