0.目錄
- 簡(jiǎn)介
- 關(guān)系
- 介紹
3.1 容器（Container）
3.2 算法（Algorithm）
3.3 迭代器（Iterator）
3.4 仿函數(shù)（Function object）
3.5 適配器（Adaptor）
3.6 空間配置器（allocator） - 引用
1.簡(jiǎn)介
容器（Container）：各種基本數(shù)據(jù)結(jié)構(gòu)
算法（Algorithm）：各種基本算法
迭代器（Iterator）：提供訪問容器中對(duì)象的方法
仿函數(shù)（Function object）
適配器（Adaptor）
空間配置器（allocator）
2.關(guān)系
3.介紹
3.1 容器（Container）
容器庫(kù)是類模板與算法的匯集专执，允許程序員簡(jiǎn)單地訪問常見數(shù)據(jù)結(jié)構(gòu)，例如隊(duì)列雀费、鏈表和棧君纫。有三類容器——順序容器、關(guān)聯(lián)容器和無(wú)序關(guān)聯(lián)容器——每種都被設(shè)計(jì)為支持不同組的操作歧蕉。
容器管理為其元素分配的存儲(chǔ)空間肘习，并提供直接或間接地通過迭代器（Iterator）訪問它們的函數(shù)近零。
大多數(shù)容器擁有至少幾個(gè)常見的成員函數(shù)珠洗，并共享功能溜歪。特定應(yīng)用的最佳容器不僅依賴于提供的功能，還依賴于對(duì)于不同工作量的效率许蓖。
順序容器
順序容器實(shí)現(xiàn)能按順序訪問的數(shù)據(jù)結(jié)構(gòu)蝴猪。
-
array: 靜態(tài)的連續(xù)數(shù)組 (C++11) -
vector: 動(dòng)態(tài)的連續(xù)數(shù)組 -
deque: 雙端隊(duì)列 -
forward_list: 單鏈表 (C++11) -
list: 雙鏈表
關(guān)聯(lián)容器
關(guān)聯(lián)容器實(shí)現(xiàn)能快速查找（ O(log n) 復(fù)雜度）的數(shù)據(jù)結(jié)構(gòu)调衰。
-
set: 唯一鍵的集合，按照鍵排序 -
map: 鍵值對(duì)的集合自阱，按照鍵排序嚎莉，鍵是唯一的 -
multiset: 鍵的集合，按照鍵排序 -
multimap: 鍵值對(duì)的集合动壤，按照鍵排序
無(wú)序關(guān)聯(lián)容器
無(wú)序關(guān)聯(lián)容器提供能快速查找（均攤 O(1) 萝喘，最壞情況 O(n) 的復(fù)雜度）的無(wú)序（哈希）數(shù)據(jù)結(jié)構(gòu)。
-
unordered_set: 唯一鍵的集合琼懊，按照鍵生成散列 (C++11) -
unordered_map: 鍵值對(duì)的集合，按照鍵生成散列爬早，鍵是唯一的 (C++11) -
unordered_multiset: 鍵的集合哼丈，按照鍵生成散列 (C++11) -
unordered_multimap: 鍵值對(duì)的集合，按照鍵生成散列 (C++11)
3.2 算法（Algorithm）
算法庫(kù)提供大量用途的函數(shù)（例如查找筛严、排序醉旦、計(jì)數(shù)、操作）桨啃，它們?cè)谠胤秶喜僮鞒岛Ｗ⒁夥秶x為 [first, last) ，其中 last 指代要查詢或修改的最后元素的后一個(gè)元素照瘾。
不修改序列的操作 <algorithm>
|
作用 |
|---|---|
all_of (C++11)any_of (C++11)none_of (C++11)
|
檢查謂詞是否對(duì)范圍中所有匈棘、任一或無(wú)元素為true
|
for_eachfor_each_n (C++17)
|
應(yīng)用函數(shù)到范圍中的所有/前n個(gè)元素 |
countcount_if
|
返回滿足指定判別標(biāo)準(zhǔn)的元素?cái)?shù) |
mismatch |
尋找兩個(gè)范圍出現(xiàn)不同的首個(gè)位置 |
findfind_iffind_if_not (C++11)
|
尋找首個(gè)滿足特定判別標(biāo)準(zhǔn)的元素 |
find_end |
在特定范圍中尋找最后出現(xiàn)的元素序列 |
find_first_of |
搜索元素集合中的任意元素 |
adjacent_find |
查找首對(duì)相鄰的相同（或滿足給定謂詞的）元素 |
searchsearch_n
|
搜索一個(gè)元素范圍中的某個(gè)元素/一定量的某個(gè)元素的連續(xù)副本 |
修改序列的操作 <algorithm>
|
作用 |
|---|---|
copycopy_if (C++11)copy_n (C++11)
|
將某一范圍的元素/一定數(shù)目的元素復(fù)制到一個(gè)新的位置 |
copy_backward |
按從后往前的順序復(fù)制一個(gè)范圍內(nèi)的元素 |
move (C++11)
|
將某一范圍的元素移動(dòng)到一個(gè)新的位置 |
move_backward (C++11)
|
按從后往前的順序移動(dòng)某一范圍的元素到新的位置 |
fillfill_n
|
將一個(gè)給定值復(fù)制賦值給一個(gè)范圍內(nèi)的每個(gè)元素/N個(gè)元素 |
transform |
將一個(gè)函數(shù)應(yīng)用于某一范圍的各個(gè)元素，并在目標(biāo)范圍存儲(chǔ)結(jié)果 |
generategenerate_n
|
將相繼的函數(shù)調(diào)用結(jié)果賦值給一個(gè)范圍中的每個(gè)元素/N個(gè)元素 |
removeremove_if
|
移除滿足特定判別標(biāo)準(zhǔn)的元素 |
remove_copyremove_copy_if
|
復(fù)制一個(gè)范圍的元素析命，忽略滿足特定判別標(biāo)準(zhǔn)的元素 |
replacereplace_if
|
將所有滿足特定判別標(biāo)準(zhǔn)的值替換為另一個(gè)值 |
replace_copyreplace_copy_if
|
復(fù)制一個(gè)范圍內(nèi)的元素主卫，并將滿足特定判別標(biāo)準(zhǔn)的元素替換為另一個(gè)值 |
swap |
交換兩個(gè)對(duì)象的值 |
swap_ranges |
交換兩個(gè)范圍的元素 |
iter_swap |
交換兩個(gè)迭代器所指向的元素 |
reverse |
逆轉(zhuǎn)范圍中的元素順序 |
reverse_copy |
創(chuàng)建一個(gè)范圍的逆向副本 |
shift_leftshift_right (C++20)
|
遷移范圍中的元素 |
rotate |
旋轉(zhuǎn)范圍中的元素順序 |
rotate_copy |
復(fù)制并旋轉(zhuǎn)元素范圍 |
random_shuffle(C++17 前)shuffle (C++11)
|
隨機(jī)重排范圍中的元素 |
sample (C++17)
|
從一個(gè)序列中隨機(jī)選擇 n 個(gè)元素 |
unique |
移除范圍內(nèi)的連續(xù)重復(fù)元素 |
unique_copy |
創(chuàng)建某范圍的不含連續(xù)重復(fù)元素的副本 |
劃分操作 <algorithm>
|
作用 |
|---|---|
is_partitioned (C++11)
|
判斷范圍是否已按給定的謂詞劃分 |
partition |
將范圍中的元素分為兩組 |
partition_copy (C++11)
|
復(fù)制一個(gè)范圍，將各元素分為兩組 |
stable_partition |
將元素分為兩組鹃愤，同時(shí)保留其相對(duì)順序 |
partition_point (C++11)
|
定位已劃分范圍的劃分點(diǎn) |
排序操作 <algorithm>
|
作用 |
|---|---|
is_sorted (C++11)
|
檢查范圍是否已按升序排列 |
is_sorted_until (C++11)
|
找出最大的已排序子范圍 |
sort |
將范圍按升序排序 |
partial_sort |
排序一個(gè)范圍的前 N 個(gè)元素 |
partial_sort_copy |
對(duì)范圍內(nèi)的元素進(jìn)行復(fù)制并部分排序 |
stable_sort |
將范圍內(nèi)的元素排序簇搅，同時(shí)保持相等的元素之間的順序 |
nth_element |
將給定的范圍部分排序，確保其按給定元素劃分 |
二分搜索操作（在已排序范圍上） <algorithm>
|
作用 |
|---|---|
lower_bound |
返回指向第一個(gè)不小于給定值的元素的迭代器 |
upper_bound |
返回指向第一個(gè)大于給定值的元素的迭代器 |
binary_search |
確定元素是否存在于某范圍中 |
equal_range |
返回匹配特定鍵值的元素范圍 |
集合操作（在已排序范圍上） <algorithm>
|
作用 |
|---|---|
merge |
歸并兩個(gè)已排序的范圍 |
inplace_merge |
就地歸并兩個(gè)有序范圍 |
includes |
若一個(gè)集合是另一個(gè)的子集則返回 true |
set_difference |
計(jì)算兩個(gè)集合的差集 |
set_intersection |
計(jì)算兩個(gè)集合的交集 |
set_symmetric_difference |
計(jì)算兩個(gè)集合的對(duì)稱差 |
set_union |
計(jì)算兩個(gè)集合的并集 |
堆操作 <algorithm>
|
作用 |
|---|---|
is_heap |
檢查給定范圍是否為一個(gè)最大堆 |
is_heap_until (C++11)
|
查找能成為最大堆的最大子范圍 |
make_heap |
從一個(gè)元素范圍創(chuàng)建出一個(gè)最大堆 |
push_heap |
將一個(gè)元素加入到一個(gè)最大堆 |
pop_heap |
從最大堆中移除最大元素 |
sort_heap |
將一個(gè)最大堆變成一個(gè)按升序排序的元素范圍 |
最小/最大操作 <algorithm>
|
作用 |
|---|---|
max |
返回各給定值中的較大者 |
max_element |
返回范圍內(nèi)的最大元素 |
min |
返回各給定值中的較小者 |
min_element |
返回范圍內(nèi)的最小元素 |
minmax (C++11)
|
返回兩個(gè)元素的較小和較大者 |
minmax_element (C++11)
|
返回范圍內(nèi)的最小元素和最大元素 |
clamp (C++17)
|
在一對(duì)邊界值間夾逼一個(gè)值 |
比較操作 <algorithm>
|
作用 |
|---|---|
equal |
確定兩個(gè)元素集合是否是相同的 |
lexicographical_compare |
當(dāng)一個(gè)范圍按字典順序小于另一個(gè)范圍時(shí)软吐，返回 true |
lexicographical_compare_three_way (C++20)
|
用三路比較比較兩個(gè)范圍 |
排列操作 <algorithm>
|
作用 |
|---|---|
is_permutation (C++11)
|
判斷一個(gè)序列是否為另一個(gè)序列的排列 |
next_permutation |
產(chǎn)生某個(gè)元素范圍的按字典順序的下一個(gè)較大的排列 |
prev_permutation |
產(chǎn)生某個(gè)元素范圍的按字典順序的下一個(gè)較小的排列 |
數(shù)值運(yùn)算 <numeric>
|
作用 |
|---|---|
iota (C++11)
|
用從起始值開始連續(xù)遞增的值填充一個(gè)范圍 |
accumulate |
對(duì)一個(gè)范圍內(nèi)的元素求和 |
inner_product |
計(jì)算兩個(gè)范圍的元素的內(nèi)積 |
adjacent_difference |
計(jì)算范圍內(nèi)各相鄰元素之間的差 |
partial_sum |
計(jì)算范圍內(nèi)元素的部分和 |
reduce (C++17)
|
類似std::accumulate瘩将，但不依序執(zhí)行 |
exclusive_scan (C++17)
|
類似std::partial_sum，第 i 個(gè)和中排除第 i 個(gè)輸入 |
inclusive_scan (C++17)
|
類似std::partial_sum凹耙，第 i 個(gè)和中包含第 i 個(gè)輸入 |
transform_reduce (C++17)
|
應(yīng)用一個(gè)函數(shù)對(duì)象姿现，然后以亂序規(guī)約 |
transform_exclusive_scan (C++17)
|
應(yīng)用一個(gè)函數(shù)對(duì)象，然后進(jìn)行排除掃描 |
transform_inclusive_scan (C++17)
|
應(yīng)用一個(gè)函數(shù)對(duì)象使兔，然后進(jìn)行包含掃描 |
未初始化內(nèi)存上的操作 <memory>
|
作用 |
|---|---|
uninitialized_copy |
將范圍內(nèi)的對(duì)象復(fù)制到未初始化的內(nèi)存區(qū)域 |
uninitialized_copy_n (C++11)
|
將指定數(shù)量的對(duì)象復(fù)制到未初始化的內(nèi)存區(qū)域 |
uninitialized_fill |
復(fù)制一個(gè)對(duì)象到以范圍定義的未初始化內(nèi)存區(qū)域 |
uninitialized_fill_n |
復(fù)制一個(gè)對(duì)象到以起點(diǎn)和計(jì)數(shù)定義的未初始化內(nèi)存區(qū)域 |
uninitialized_move (C++17)
|
移動(dòng)一個(gè)范圍的對(duì)象到未初始化的內(nèi)存區(qū)域 |
uninitialized_move_n (C++17)
|
移動(dòng)一定數(shù)量對(duì)象到未初始化內(nèi)存區(qū)域 |
uninitialized_default_construct (C++17)
|
在范圍所定義的未初始化的內(nèi)存區(qū)域以默認(rèn)初始化構(gòu)造對(duì)象 |
uninitialized_default_construct_n (C++17)
|
在起始和計(jì)數(shù)所定義的未初始化內(nèi)存區(qū)域用默認(rèn)初始化構(gòu)造對(duì)象 |
uninitialized_value_construct (C++17)
|
在范圍所定義的未初始化內(nèi)存中用值初始化構(gòu)造對(duì)象 |
uninitialized_value_construct_n (C++17)
|
在起始和計(jì)數(shù)所定義的未初始化內(nèi)存區(qū)域以值初始化構(gòu)造對(duì)象 |
destroy_at (C++17)
|
銷毀在給定地址的對(duì)象 |
destroy (C++17)
|
銷毀一個(gè)范圍中的對(duì)象 |
destroy_n (C++17)
|
銷毀范圍中一定數(shù)量的對(duì)象 |
C 庫(kù) <cstdlib>
|
作用 |
|---|---|
qsort |
對(duì)未指定類型的元素的一個(gè)范圍進(jìn)行排序 |
bsearch |
在未指定類型的數(shù)組中搜索元素 |
3.3 迭代器（Iterator）
迭代器Iterator建钥，用來(lái)在一個(gè)對(duì)象群集（collection of objects）的元素上進(jìn)行遍歷。這個(gè)對(duì)象群集或許是個(gè)容器虐沥，或許是容器的一部分熊经。
迭代器的主要好處是泽艘，為所有容器提供了一組很小的公共接口。迭代器以++進(jìn)行累進(jìn)镐依，以*進(jìn)行提領(lǐng)匹涮，類似于指針，每種容器都提供了自己的迭代器槐壳。
迭代器庫(kù)提供了五種迭代器的定義然低，同時(shí)還提供了迭代器特征、適配器及相關(guān)的工具函數(shù)：
-
Input Iterator：只讀务唐，自增(++)雳攘，單趟 -
Output Iterator：只寫，自增(++)枫笛，單趟 -
Forward Iterator：讀寫吨灭，自增(++) -
Bidirectional Iterator： 讀寫，自增(++)刑巧，自減(--) -
Random Access Iterator：讀寫喧兄，隨機(jī)訪問，增(it+n,it+=n)啊楚，減(it-n,it-=n,it1-it2)
迭代器非法化
只讀方法決不非法化迭代器或引用吠冤。修改容器內(nèi)容的方法可能非法化迭代器和/或引用如下：
| 容器 | 插入 | 刪除 |
|---|---|---|
array |
無(wú) | 無(wú) |
vector |
位于插入元素之前的迭代器合法 位于插入元素及之后的迭代器非法 當(dāng)插入引起內(nèi)存重新分配時(shí)所有迭代器非法 |
位于刪除元素之前的迭代器合法 位于刪除元素及之后的迭代器非法 |
deque |
所有迭代器非法 | 刪除首/尾元素時(shí)除被刪除元素外的迭代器合法 刪除中部元素時(shí)所有迭代器非法 |
listforward_list
|
始終合法 | 僅被刪除元素非法 |
setmultisetmapmultimap
|
始終合法 | 僅被刪除元素非法 |
unordered_setunordered_multiset
|
若插入導(dǎo)致重哈希，所有迭代器非法 否則始終合法 |
僅被刪除元素非法 |
unordered_mapunordered_multimap
|
始終合法 | 僅被刪除元素非法 |
此處插入指代任何添加一或多個(gè)元素到容器的方法恭理，而刪除指代任何從容器移除一或多個(gè)元素的方法拯辙。
- 插入方法的例子是
std::set::insert、std::map::emplace蚯斯、std::vector::push_back和std::deque::push_front薄风。
注意std::unordered_map::operator[]也算，因?yàn)樗赡懿迦朐氐?code>map中拍嵌。 - 擦除方法的例子是
std::set::erase遭赂、std::vector::pop_back、std::deque::pop_front和std::map::clear横辆。
clear非法化所有迭代器和引用撇他。因?yàn)樗脸性兀@在技術(shù)上遵照上述規(guī)則狈蚤。
尾后迭代器需要特別留意困肩。通常像指向未被擦除元素的正常迭代器一般非法化此迭代器。故std::set::end決不被非法化脆侮，std::unordered_set::end僅在重哈希時(shí)被非法化锌畸，std::vector::end始終被非法化（因?yàn)樗冀K出現(xiàn)在被修改元素后），以此類推靖避。
有一個(gè)例外：刪除std::deque末元素的擦除操作會(huì)非法化尾后迭代器潭枣，盡管它不是容器的被擦除元素（或者說(shuō)根本不是元素）比默。與std::deque迭代器的通用規(guī)則結(jié)合后，最終結(jié)果是不非法化std::deque::end的唯一修改操作是刪除首元素盆犁，而非末元素的擦除命咐。
3.4 仿函數(shù)（Function object）
仿函數(shù)具體有什么用？沒找到很好的解釋谐岁。
- 一個(gè)行為類似函數(shù)的對(duì)象醋奠，它可以沒有參數(shù)，也可以帶有若干參數(shù)伊佃。
- 任何重載了調(diào)用運(yùn)算符
operator()的類的對(duì)象都滿足函數(shù)對(duì)象的特征 - 函數(shù)對(duì)象可以把它稱之為
smart function窜司。 - STL中也定義了一些標(biāo)準(zhǔn)的函數(shù)對(duì)象，如果以功能劃分锭魔，可以分為算術(shù)運(yùn)算例证、關(guān)系運(yùn)算、邏輯運(yùn)算三大類迷捧。為了調(diào)用這些標(biāo)準(zhǔn)函數(shù)對(duì)象，需要包含頭文件
<functional>：
| 算術(shù)運(yùn)算 | 功能 |
|---|---|
plus |
實(shí)現(xiàn) x + y 的函數(shù)對(duì)象 |
minus |
實(shí)現(xiàn) x - y 的函數(shù)對(duì)象 |
multiplies |
實(shí)現(xiàn) x * y 的函數(shù)對(duì)象 |
divides |
實(shí)現(xiàn) x / y 的函數(shù)對(duì)象 |
modulus |
實(shí)現(xiàn) x % y 的函數(shù)對(duì)象 |
negate |
實(shí)現(xiàn) -x 的函數(shù)對(duì)象 |
| 比較 | 功能 |
|---|---|
equal_to |
實(shí)現(xiàn) x == y 的函數(shù)對(duì)象 |
not_equal_to |
實(shí)現(xiàn) x != y 的函數(shù)對(duì)象 |
greater |
實(shí)現(xiàn) x > y 的函數(shù)對(duì)象 |
less |
實(shí)現(xiàn) x < y 的函數(shù)對(duì)象 |
greater_equal |
實(shí)現(xiàn) x >= y 的函數(shù)對(duì)象 |
less_equal |
實(shí)現(xiàn) x <= y 的函數(shù)對(duì)象 |
| 邏輯運(yùn)算 | 功能 |
|---|---|
logical_and |
實(shí)現(xiàn) x && y 的函數(shù)對(duì)象 |
logical_or |
實(shí)現(xiàn) x || y 的函數(shù)對(duì)象 |
logical_not |
實(shí)現(xiàn) !x 的函數(shù)對(duì)象 |
| 逐位運(yùn)算 | 功能 |
|---|---|
bit_and |
實(shí)現(xiàn) x & y 的函數(shù)對(duì)象 |
bit_or |
實(shí)現(xiàn) x | y 的函數(shù)對(duì)象 |
bit_xor |
實(shí)現(xiàn) x ^ y 的函數(shù)對(duì)象 |
bit_not (C++14)
|
實(shí)現(xiàn) ~x 的函數(shù)對(duì)象 |
| 取反器 | 功能 |
|---|---|
not_fn (C++17)
|
創(chuàng)建返回其保有的函數(shù)對(duì)象的結(jié)果之補(bǔ)的函數(shù)對(duì)象 |
| 搜索器 | 功能 |
|---|---|
default_searcher(C++17)
|
標(biāo)準(zhǔn) C++ 庫(kù)搜索算法實(shí)現(xiàn) |
boyer_moore_searcher (C++17)
|
Boyer-Moore 搜索算法實(shí)現(xiàn) |
boyer_moore_horspool_searcher (C++17)
|
Boyer-Moore-Horspool 搜索算法實(shí)現(xiàn) |
3.5 適配器（Adaptor）
適配器是一種類胀葱，為已有的類提供新的接口漠秋，目的是簡(jiǎn)化、約束抵屿、使之安全庆锦、隱藏或者改變被修改類提供的服務(wù)集合，適配器對(duì)容器進(jìn)行包裝轧葛，使其表現(xiàn)出另外一種行為搂抒。
容器適配器
用來(lái)擴(kuò)展7種基本容器，它們和順序容器相結(jié)合構(gòu)成棧尿扯、隊(duì)列和優(yōu)先隊(duì)列容器求晶，stack，queue衷笋， priority_queue可以基于vector和deque芳杏，采用最大堆來(lái)實(shí)現(xiàn)，因?yàn)樾枰S機(jī)存取迭代器辟宗，只有這兩個(gè)爵赵；
容器適配器提供順序容器的不同接口。
| 種類 | 默認(rèn)順序容器 | 可用順序容器 | 說(shuō)明 |
|---|---|---|---|
stack |
deque |
vector, list, deque
|
適配一個(gè)容器以提供棧（LIFO 數(shù)據(jù)結(jié)構(gòu)） |
queue |
deque |
list, deque
|
適配一個(gè)容器以提供隊(duì)列（FIFO 數(shù)據(jù)結(jié)構(gòu)） |
priority_queue |
vector |
vector, deque
|
適配一個(gè)容器以提供優(yōu)先級(jí)隊(duì)列 |
迭代器適配器
-
reverse_iterator: 逆序遍歷的迭代器適配器 -
make_reverse_iterator(C++14): 創(chuàng)建擁有從實(shí)參推出的類型的std::reverse_iterator -
move_iterator(C++11): 解引用結(jié)果為右值引用的迭代器適配器 -
move_sentinel(C++20): 用于std::move_iterator的哨位適配器 -
make_move_iterator(C++11): 創(chuàng)建擁有從實(shí)參推出的類型的std::move_iterator -
common_iterator(C++20): 適配一個(gè)迭代器類型及其哨位為一個(gè)公共迭代器類型 -
default_sentinel_t(C++20): 用于知曉其邊界的迭代器的默認(rèn)哨位 -
counted_iterator(C++20): 對(duì)到范圍結(jié)尾距離進(jìn)行跟蹤的迭代器適配器 -
unreachable_sentinel_t(C++20): 始終與任何weakly_incrementable類型比較都不相等的哨位 -
back_insert_iterator: 用于在容器尾部插入的迭代器適配器 -
back_inserter: 創(chuàng)建擁有從實(shí)參推出的類型的std::back_insert_iterator -
front_insert_iterator: 用于在容器頭部插入的迭代器適配器 -
front_inserter: 創(chuàng)建擁有從實(shí)參推出的類型的std::front_insert_iterator -
insert_iterator: 用于插入容器的迭代器適配器 -
inserter: 創(chuàng)建擁有從實(shí)參推出的類型的std::insert_iterator
函數(shù)適配器（函數(shù)對(duì)象適配器泊脐、成員函數(shù)適配器空幻、普通函數(shù)適配器）
3.6 空間配置器（allocator）
負(fù)責(zé)空間配置與管理。從實(shí)現(xiàn)的角度來(lái)看容客，配置器是一個(gè)實(shí)現(xiàn)了動(dòng)態(tài)空間配置秕铛、空間管理约郁、空間釋放的class template。
隱藏在這些容器后的內(nèi)存管理工作是通過STL提供的一個(gè)默認(rèn)的allocator實(shí)現(xiàn)的如捅。當(dāng)然棍现，用戶也可以定制自己的allocator，只要實(shí)現(xiàn)allocator模板所定義的接口方法即可镜遣，然后通過將自定義的allocator作為模板參數(shù)傳遞給STL容器己肮，創(chuàng)建一個(gè)使用自定義allocator的STL容器對(duì)象，如：
stl::vector< int, UserDefinedAllocator> array;
大多數(shù)情況下悲关，STL默認(rèn)的allocator就已經(jīng)足夠了谎僻。這個(gè)allocator是一個(gè)由兩級(jí)分配器構(gòu)成的內(nèi)存管理器，當(dāng)申請(qǐng)的內(nèi)存大小大于128byte時(shí)寓辱，就啟動(dòng)第一級(jí)分配器通過malloc/free直接向系統(tǒng)的堆空間分配艘绍，如果申請(qǐng)的內(nèi)存大小小于128byte時(shí)，就啟動(dòng)第二級(jí)分配器秫筏，從一個(gè)預(yù)先分配好的內(nèi)存池中取一塊內(nèi)存交付給用戶诱鞠，這個(gè)內(nèi)存池由16個(gè)不同大小（8的倍數(shù)这敬，8~128byte）的空閑列表組成航夺，allocator會(huì)根據(jù)申請(qǐng)內(nèi)存的大小（將這個(gè)大小round
up成8的倍數(shù)）從對(duì)應(yīng)的空閑塊列表取表頭塊給用戶崔涂。
這種做法有兩個(gè)優(yōu)點(diǎn)
（1)小對(duì)象的快速分配阳掐。
小對(duì)象是從內(nèi)存池分配的，這個(gè)內(nèi)存池是系統(tǒng)調(diào)用一次malloc分配一塊足夠大的區(qū)域給程序備用冷蚂，當(dāng)內(nèi)存池耗盡時(shí)再向系統(tǒng)申請(qǐng)一塊新的區(qū)域缭保，整個(gè)過程類似于批發(fā)和零售，起先是由allocator向總經(jīng)商批發(fā)一定量的貨物蝙茶，然后零售給用戶艺骂，與每次都總經(jīng)商要一個(gè)貨物再零售給用戶的過程相比，顯然是快捷了尸闸。當(dāng)然彻亲，這里的一個(gè)問題時(shí)，內(nèi)存池會(huì)帶來(lái)一些內(nèi)存的浪費(fèi)吮廉，比如當(dāng)只需分配一個(gè)小對(duì)象時(shí)苞尝，為了這個(gè)小對(duì)象可能要申請(qǐng)一大塊的內(nèi)存池，但這個(gè)浪費(fèi)還是值得的宦芦，況且這種情況在實(shí)際應(yīng)用中也并不多見宙址。
(2)避免了內(nèi)存碎片的生成。
程序中的小對(duì)象的分配極易造成內(nèi)存碎片调卑，給操作系統(tǒng)的內(nèi)存管理帶來(lái)了很大壓力抡砂，系統(tǒng)中碎片的增多不但會(huì)影響內(nèi)存分配的速度大咱，而且會(huì)極大地降低內(nèi)存的利用率。以內(nèi)存池組織小對(duì)象的內(nèi)存注益，從系統(tǒng)的角度看碴巾，只是一大塊內(nèi)存池，看不到小對(duì)象內(nèi)存的分配和釋放丑搔。
