2. C++標(biāo)準(zhǔn)庫(kù)

2.1 IO庫(kù)

• IO對(duì)象無(wú)拷貝或賦值市埋，進(jìn)行IO操作的函數(shù)通常以引用方式傳遞和返回流。

• IO庫(kù)條件狀態(tài)

  
  
  
  

• 導(dǎo)致緩沖刷新的原因：
  1）程序正常結(jié)束
  2）緩沖區(qū)滿
  3）endl
  4）用unitbuf箩艺。默認(rèn)情況下凉泄，對(duì)cerr是設(shè)置unitbuf，因此寫(xiě)到cerr的內(nèi)容是立即刷新的
  5）一個(gè)輸出流可能被關(guān)聯(lián)到另一個(gè)流劳较，關(guān)聯(lián)到的流的緩沖區(qū)會(huì)被刷新。
• 刷新輸出緩沖區(qū)
  endl
  flush 不輸出任何額外字符
  ends 向緩沖區(qū)插入一個(gè)空字符浩聋，然后刷新緩沖區(qū)
• unitbuf
  如果想在每次輸出操作后都刷新緩沖區(qū)观蜗，使用unitbuf，告訴流每次操作之后進(jìn)行一次flush衣洁。nounitbuf則是重置流墓捻，恢復(fù)正常的系統(tǒng)管理的緩沖區(qū)刷新機(jī)制。

cout << unitbuf;
cout << nounitbuf;

• 如果程序崩潰坊夫，輸出緩沖區(qū)很可能不會(huì)被刷新砖第。
• 標(biāo)準(zhǔn)庫(kù)將cout和cin關(guān)聯(lián)在一起，因此cin >> ival;將導(dǎo)致cout的緩沖區(qū)被刷新环凿。
• tie函數(shù)梧兼，將流關(guān)聯(lián)到輸出流。

• fstream繼承了iostream類型的行為智听，并且還新增了一些新的成員來(lái)管理與流關(guān)聯(lián)的文件羽杰。

  
  
• 當(dāng)一個(gè)fstream對(duì)象唄銷毀時(shí)，close會(huì)自動(dòng)被調(diào)用

• 文件模式

  
  

• 指定文件模式的限制

  
  
  
  

  默認(rèn)情況下到推，與ifstream關(guān)聯(lián)的文件以in模式打開(kāi)考赛；與ofstream關(guān)聯(lián)的文件以out模式打開(kāi)；與fstream關(guān)聯(lián)的文件默認(rèn)以in和out模式打開(kāi)莉测。

• sstream頭文件定義了三個(gè)類型來(lái)支持內(nèi)存IO颜骤。

  
  
• istringstream使用場(chǎng)景：對(duì)整行文本進(jìn)行處理，而其他一些工作是處理行內(nèi)的單個(gè)單詞捣卤。
  ostringstream使用場(chǎng)景：逐步構(gòu)造輸出复哆，最后一起打印欣喧。

• 總結(jié)：
  1）iostream 處理控制臺(tái)IO
  2）fstream處理命名文件IO
  3）stringstream處理內(nèi)存stringIO
  并且fstream和stringstream都繼承自類iostream。

2.2 順序容器

• 與內(nèi)置數(shù)組相比梯找，array是一種更為安全唆阿、更容易使用的數(shù)組類型
• forward_list的設(shè)計(jì)目標(biāo)是達(dá)到與最好的手寫(xiě)的單向鏈表數(shù)據(jù)結(jié)構(gòu)相當(dāng)?shù)男阅?/li>
• 新標(biāo)準(zhǔn)庫(kù)的容器比舊版本快得多，性能幾乎肯定與最精心優(yōu)化過(guò)的同類數(shù)據(jù)結(jié)構(gòu)一樣好（通常會(huì)更好）锈锤。

• 選擇順序容器的基本原則：

  
  

• 容器操作分為三個(gè)層次
  1）某些操作是所有容器都提供的
  2）另外一些操作僅針對(duì)順序容器驯鳖、關(guān)聯(lián)容器或無(wú)序容器
  3）還有一些操作只適用于一小部分容器
• 保存沒(méi)有默認(rèn)構(gòu)造函數(shù)的類型

// noDefault是一個(gè)沒(méi)有默認(rèn)構(gòu)造函數(shù)的類型
vector<noDefault> v1(10, init); //提供元素初始化器
錯(cuò)誤 vector<noDefault> v2(10); 

• 容器的共有操作

  
  
  
  

• 迭代器
  迭代器范圍[begin, end)。這種左閉合區(qū)間久免，使用特定的編程范式：

while (begin != end) {
    *begin = val;
    ++begin;
}

• 容器定義和初始化

  
  
  
  

  當(dāng)將一個(gè)容器初始化為另一個(gè)容器的拷貝時(shí)浅辙，兩個(gè)容器的容器類型和元素類型必須相同。
  使用迭代器范圍時(shí)阎姥，只要能將要拷貝的元素轉(zhuǎn)換為要初始化的容器的元素類型即可记舆。

• array的大小也是類型的一部分。

array<int, 42>
array<string, 10>

• 內(nèi)置數(shù)組不能進(jìn)行拷貝或?qū)ο筚x值呼巴，但是array可以

array<int, 10> digits = {0, 1,2 ,3, 4, 5, 6, 7, 8, 9};
array<int, 10> copy = digits;

• 容器賦值運(yùn)算

  
  
  
  

  除array外泽腮，swap不對(duì)任何元素進(jìn)行拷貝、刪除或插入操作衣赶，因此可以保證在常數(shù)時(shí)間內(nèi)完成诊赊。swap兩個(gè)array會(huì)真正交換它們的元素。
  非成員版本的swap在范型編程中是非常重要的府瞄，統(tǒng)一使用成員版本的swap是一個(gè)好習(xí)慣碧磅。

• 順序容器添加元素操作

  
  
• 容器元素是拷貝
• 使用insert的返回值，insert返回指向所有新加入元素的第一個(gè)的迭代器遵馆。

list<string> lst;
auto iter = lst.begin();
while (cin >> word) {
    iter = lst.insert(iter, word); //等價(jià)于調(diào)用push_front
}

• emplace_front鲸郊、emplace、emplace_back這些操作構(gòu)造而不是拷貝元素货邓。當(dāng)調(diào)用push严望、insert成員函數(shù)時(shí)，將對(duì)象拷貝到容器中逻恐。當(dāng)調(diào)用emplace時(shí)像吻，則是將參數(shù)傳遞給元素類型的構(gòu)造函數(shù)。
  調(diào)用emplace_back复隆，會(huì)在容器管理的內(nèi)存空間中直接創(chuàng)建對(duì)象拨匆。而調(diào)用push_back則會(huì)創(chuàng)建一個(gè)臨時(shí)對(duì)象，并將其壓入容器中挽拂。
  因此傳遞給emplace函數(shù)的參數(shù)必須與元素類型的構(gòu)造函數(shù)相匹配惭每。

正確：c.emplace_back("874-13498901850", 24, 14.88);
錯(cuò)誤：c.push_back("874-13498901850", 24, 14.88);
正確：c.push_back(Sales_data("874-13498901850", 24, 14.88));

• 順序容器的訪問(wèn)操作

  
  

• 順序容器的刪除操作

  
  
  
  

  刪除元素的成員函數(shù)并不檢查其參數(shù)，在刪除元素之前，程序員必須確保它們是存在台腥。

• forward_list中插入或刪除元素的操作

  
  

• 改變?nèi)萜鞔笮?/p>
  

• 管理迭代器
  使用迭代器時(shí)宏赘，必須保證每次改變?nèi)萜鞯牟僮髦螅ㄌ砑印h除）都正確地重新定位迭代器黎侈。
  如果在一個(gè)循環(huán)中插入/刪除deque察署、string或vector中的元素，不要緩存end返回的迭代器峻汉。

• vecotr的元素是連續(xù)存儲(chǔ)的贴汪。

  
  
  
  

  size是指容器已經(jīng)保存的元素的數(shù)量
  capacity是在不分配新的內(nèi)存空間的前提下最多可以保存多少元素。

• string的其他方法

  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  

• 三個(gè)順序容器適配器
  stack
  queue
  priority_queue
• 適配器是標(biāo)準(zhǔn)庫(kù)中的一個(gè)通用概念休吠。容器扳埂、迭代器和函數(shù)都有適配器，本質(zhì)上瘤礁，一個(gè)適配器是一種機(jī)制阳懂，能使某種事物的行為看起來(lái)像另外一種事物。

• 素有容器適配器都支持的操作和類型

  
  
• 默認(rèn)情況下柜思，stack和queue是基于deque實(shí)現(xiàn)的岩调，priority_queue是在vector上實(shí)現(xiàn)的≡脱眩可以在創(chuàng)建一個(gè)適配器時(shí)將一個(gè)命名的順序容器作為第二個(gè)類型參數(shù)，來(lái)重載默認(rèn)容器類型矾湃。

stack<string, vector<string>> str_stk; // 在vector上實(shí)現(xiàn)棧

• 棧適配器

  
  

• 隊(duì)列適配器

  
  
  
  

2.3 泛型算法

• 標(biāo)準(zhǔn)庫(kù)并未給每個(gè)容器添加大量功能亡脑，而是提供了一組算法，這些算法中的大多數(shù)都獨(dú)立于任何特定的容器邀跃。
• 大多數(shù)算法定義在algorithm中霉咨，numeric定義了一組數(shù)值范型算法。
• 一般情況下拍屑，這些算法并不直接操作容器途戒，而是遍歷由兩個(gè)迭代器指定的一個(gè)元素范圍進(jìn)行操作。
  算法永遠(yuǎn)不改變底層容器的大小僵驰，可能改變?cè)氐闹蹬缯苿?dòng)元素。
• find——在一個(gè)未排序的元素列表中查找一個(gè)特定元素
  find操作不依賴于容器所保存的元素類型蒜茴。
• 迭代器令算法不依賴于容器星爪，但算法依賴于元素類型的操作，例如==等比較運(yùn)算符粉私。
• 理解算法的最基本方法就是了解它們是否讀取元素顽腾、改變?cè)鼗蚴侵嘏脑仨樞颉?br> 1）只讀算法——通常使用cbegin()和cend()
  find count accumulate
  equal 假定第二個(gè)序列至少與第一個(gè)序列一樣長(zhǎng)。
  那些只接受一個(gè)單一迭代器表示第二個(gè)序列的算法诺核，都假定第二個(gè)序列至少與第一個(gè)序列一樣長(zhǎng)抄肖。
  2）寫(xiě)算法
  fill fill_n copy replace replace_copy
  向目的位置迭代器寫(xiě)入數(shù)據(jù)的算法假定目的位置足夠大久信，能容納要寫(xiě)入的元素。
  一種保證算法有足夠元素空間來(lái)容納輸出數(shù)據(jù)的方法是使用插入迭代器漓摩。
  back_inserter接受一個(gè)指向容器的引用裙士，返回一個(gè)與該容器綁定的插入迭代器。當(dāng)我們通過(guò)此迭代器賦值時(shí)幌甘，賦值運(yùn)算符會(huì)調(diào)用push_back將一個(gè)具有給定值的元素添加到容器中潮售。
  3）重排算法
  sort unique

vector<int> vec;
auto it = back_inserter(vec);
*it = 42;

vector<int> vec;
fill_n(back_inserter(vec), 10, 0);

• 定制操作——謂詞
  sort stable_sort find_if for_each
  可調(diào)用對(duì)象：函數(shù)、函數(shù)指針锅风、重載了函數(shù)調(diào)用運(yùn)算符的類酥诽、lambda表達(dá)式
  lambda表達(dá)式：
  [capture list] (parameter list) -> return type {function body}
  capture list是一個(gè)lambda所在函數(shù)中定義的局部變量的列表。捕獲列表只用于局部非static變量皱埠，lambda可以直接使用局部static變量和在它所在函數(shù)之外聲明的名字肮帐。
  當(dāng)定義一個(gè)lambda時(shí)，編譯器生成一個(gè)與lambda對(duì)應(yīng)的新的（未命名的）類類型边器。
  值捕獲：與參數(shù)不同训枢，被捕獲的變量的值是在lambda創(chuàng)建時(shí)拷貝，而不是調(diào)用時(shí)拷貝忘巧。
  引用捕獲：保證被引用的對(duì)象在lambd
  a執(zhí)行的時(shí)候是存在恒界，比如IO對(duì)象的引用。
  隱式捕獲：為了指示編譯器推斷捕獲列表砚嘴，應(yīng)在捕獲列表中寫(xiě)一個(gè)&或=十酣。&告訴編譯器采用引用捕獲方式，=表示采用值捕獲方式际长。

  
  

stable_sort(words.begin(), words.end(), [] (const string &a, const string &b) {return a.size() < b.size()} ）;

auto wc = find_if(words.begin(), words.end(), [sz](const string &a) {return a.size() >= sz;});

for_each(wc, word.end(), [](const string &s){cout << s << " ";} );

• 對(duì)于一個(gè)值拷貝的變量耸采，lambda不會(huì)改變其值，如果希望改變一個(gè)被捕獲的變量的值工育，就必須在參數(shù)列表首加上關(guān)鍵字mutable虾宇。
• 如果一個(gè)lambda體包含return之外的任何語(yǔ)句，則編譯器假定此lambda返回void如绸。此時(shí)嘱朽，必須使用尾置返回類型：

transform(vi.begin(), vi.end(), vi.begin(), 
                                       [](int i) -> int
                                       {if (i < 0) return -i; else return i;} );

• 如果lambda的捕獲列表為空，通痴樱可以用函數(shù)來(lái)代替它燥翅；對(duì)于捕獲局部變量的lambda，用函數(shù)來(lái)替代它就不那么容易了蜕提。
• functional中的bind函數(shù)森书，看作一個(gè)通用的函數(shù)適配器，它接受一個(gè)可調(diào)用對(duì)象，生成一個(gè)新的可調(diào)用對(duì)象來(lái)適應(yīng)原對(duì)象的參數(shù)列表凛膏。
  auto newCallable = bind(callable, arg_list);
  當(dāng)調(diào)用newCallable時(shí)杨名，會(huì)調(diào)用callable，并傳遞給它arg_list參數(shù)猖毫。_n表示占位符台谍，表示newCallable的參數(shù)，占據(jù)了傳遞給newCallable的參數(shù)位置吁断，n表示生成可調(diào)用對(duì)象中參數(shù)的位置：_1為newCallable的第一個(gè)參數(shù)趁蕊，_2第二個(gè)，依此類推仔役。
• ref和cref定義在頭文件functional中

bool check_size(const string &s, string::size_type sz) {
    return s.size() >= sz;
}
auto check6 = bind(check_size, _1, 6); // bind調(diào)用只有一個(gè)占位符掷伙，表示check6
//只接受單一string參數(shù)，6賦值給了check_size的sz又兵。
auto wc = find_if(words.begin(), words.end(),
                           bind(check_size, _1, sz));

sort(words.begin(), words.end(), isShorter); // 由短到長(zhǎng)排序
sort(words.begin(), words.end(), bind(isShorter, _2, _1); //由長(zhǎng)到短排序

for_each(words.begin(), words.end(), 
               bind(print, ref(os), _1, ' ')); //對(duì)于ostream任柜，只能返回一個(gè)引用，此對(duì)象可拷貝

• 名字_n都定義在placeholders的命名空間中沛厨，而這個(gè)命名空間本身定義在std命名空間中宙地。placeholders定義在functional頭文件中。

• 除了為每個(gè)容器定義的迭代器之外逆皮，標(biāo)準(zhǔn)庫(kù)在iterator頭文件中還定義了其他迭代器
  1）插入迭代器：這些迭代器被綁定到一個(gè)容器上宅粥，可以用來(lái)向容器插入元素
  2）流迭代器：這些迭代器被綁定到輸入或輸出流上，可用來(lái)遍歷所關(guān)聯(lián)的IO流
  3）反向迭代器：這些迭代器向后面不是向前移動(dòng)电谣，除了forward_list之外的標(biāo)準(zhǔn)庫(kù)容器都有反向迭代器
  4）移動(dòng)迭代器：這些專用的迭代器不是拷貝其中的元素秽梅，而是移動(dòng)它們。

• 插入迭代器

  
  
  
  

  back_inserter創(chuàng)建一個(gè)使用push_back的迭代器辰企；
  front_inserter創(chuàng)建一個(gè)使用push_front的迭代器
  inserter創(chuàng)建一個(gè)使用insert的迭代器风纠。此函數(shù)接受第二個(gè)參數(shù)况鸣，這個(gè)參數(shù)必須是一個(gè)指向給定容器的迭代器牢贸。元素被插入到給定迭代器之前。
  front_inserter和inserter迭代器的行為截然相反：

    list<int> lst = { 1, 2, 3, 4 };
    list<int> lst2, lst3;
    copy(lst.cbegin(), lst.cend(), front_inserter(lst2));
    copy(lst.cbegin(), lst.cend(), inserter(lst3, lst3.begin()));
    for_each(lst2.cbegin(), lst2.cend(), [](const int s){cout << s << " "; });
    cout << endl; // 4 3 2 1
    for_each(lst3.cbegin(), lst3.cend(), [](const int s){cout << s << " "; });
    cout << endl; // 1 2 3 4

• iosream迭代器
  istream_iterator和ostream_iterator將對(duì)應(yīng)的流當(dāng)作一個(gè)特定類型的元素序列來(lái)處理镐捧。
  1）istream_iterator
  一個(gè)istream_iterator使用>>來(lái)讀取流潜索，因此要讀取的類型必須定義了輸入運(yùn)算符。

  
  
  
  

  2）ostream_iterator
  ostream_iterator可以提供第二參數(shù)懂酱，它是一個(gè)字符串竹习，在輸出每個(gè)元素后都會(huì)打印此字符串。
  ostream_iterator不允許空的或表示尾后位置的ostream_iterator.

  
  

istream_iterator<int> in_iter(cin);
istream_iterator<int> eof;
while (in_iter != eof) {
    vec.push_back(*in_iter++);
}

等價(jià)于：
istream_iterator<int> in_iter(cin), eof;
vector<int> vec(in_iter, eof);

//////////////////////////////////////////////////////////////////////////
ostream_iterator<int> out_iter(cout, " ");
for (auto e:vec) {
    *out_iter++ = e; //運(yùn)算符*和++實(shí)際上對(duì)ostream_iterator對(duì)象不做任何事情
}
cout << endl;

• 反向迭代器
  不能從forward_list或流迭代器創(chuàng)建反向迭代器列牺，因?yàn)椴恢С诌f減運(yùn)算符整陌。
  reverse_iterator的base成員函數(shù)可以將反向迭代器轉(zhuǎn)換成一個(gè)普通迭代器。

  
  

auto rcomma = find(line.crbegin(), line.crend(), ',');
cout << string(rcomma.base(), line.cend()) << endl;

• 五類迭代器
  
  
  1）輸入迭代器必須支持：
  用于比較兩個(gè)迭代器的相等和不相等運(yùn)算符（==、!=）泌辫；
  用于推進(jìn)迭代器的前置和后置遞增運(yùn)算符（++）随夸；
  用于讀取元素的解引用運(yùn)算符（），解引用只會(huì)出現(xiàn)在賦值運(yùn)算符的右側(cè)震放；
  ->等價(jià)于(*it).member宾毒。
  輸入迭代器只用于順序訪問(wèn)，不能保證輸入迭代器的狀態(tài)可以保存下來(lái)并訪問(wèn)元素殿遂。因此诈铛，輸入迭代器只能用于單遍掃描算法。
  find accumulate要求輸入迭代器墨礁，istream_iterator是一種輸入迭代器幢竹。
  2）輸出迭代器必須支持：
  用于推進(jìn)迭代器的前置和后置遞增運(yùn)算符（++）；
  用于寫(xiě)入元素的解引用運(yùn)算符（）饵溅，解引用只會(huì)出現(xiàn)在賦值運(yùn)算符的左側(cè)妨退。
  只能向一個(gè)輸出迭代器賦值一次。只能用于單遍掃描算法蜕企。
  copy函數(shù)的第三個(gè)參數(shù)就是輸出迭代器咬荷。ostream_iterator是輸出迭代器。
  3）前向迭代器
  只能在序列中沿一個(gè)方向移動(dòng)轻掩，支持輸入和輸出迭代器的操作幸乒，可以多次讀寫(xiě)同一個(gè)元素〈侥粒可以保存前向迭代器的狀態(tài)罕扎，可以進(jìn)行多遍掃描。
  replace要求前向迭代器丐重。forward_list上的迭代器時(shí)前向迭代器腔召。
  4）雙向迭代器
  支持所有前向迭代器操作，還支持前置和后置遞減運(yùn)算符（--）扮惦。
  reverse要求雙向迭代器臀蛛，除forward_list外其他標(biāo)準(zhǔn)庫(kù)都提供符合雙向迭代器要求的迭代器。
  5）隨機(jī)訪問(wèn)迭代器
  支持雙向迭代器的操作崖蜜，還支持：
  用于比較兩個(gè)迭代器相對(duì)位置關(guān)系運(yùn)算符（<浊仆、<=、>和>=）豫领；
  迭代器和一個(gè)整數(shù)值的加減運(yùn)算（+抡柿、+=、-和-=）等恐，計(jì)算結(jié)果是迭代器在序列中前進(jìn)（或后退）給定整數(shù)個(gè)元素后的位置洲劣；
  用于兩個(gè)迭代器上減法運(yùn)算符（-）备蚓，得到兩個(gè)迭代器的距離；
  下標(biāo)運(yùn)算符（iter[n]）囱稽，與*(iter[n])等價(jià)星著。
  sort要去隨機(jī)訪問(wèn)迭代器，array粗悯、deque虚循、string和vector的跌大氣都是隨機(jī)訪問(wèn)迭代器，用于訪問(wèn)內(nèi)置數(shù)組元素的指針也是样傍。
• 算法形參模式横缔，四種形式：
  alg(beg, end, other args);
  alg(beg, end, dest, other args);
  alg(beg, end, beg2, other args);
  alg(beg, end, beg2, end2,other args);
  1）dest
  向輸出迭代器寫(xiě)入數(shù)據(jù)的算法都假定目標(biāo)空間足夠容納寫(xiě)入的數(shù)據(jù)。
  dest一般綁定到一個(gè)插入迭代器或是一個(gè)ostream_iterator衫哥。
  2）beg2或beg2,end2
  接受beg2的算法假定從beg2開(kāi)始的序列與beg和end所表示的范圍至少一樣大茎刚。
• 算法命名規(guī)范
  一些算法使用重載形式傳遞一個(gè)謂詞。unique(beg, end, comp);
  接受謂詞參數(shù)的算法都附加有_if前綴撤逢。find find_if
  區(qū)分拷貝和不拷貝版本膛锭。 reverse reverse_copy

• 特定容器算法——list、forward_list
  對(duì)于list和forward_list蚊荣，應(yīng)該優(yōu)先使用成員函數(shù)版本的算法而不是通用算法初狰。

  
  
  
  
  
  
  
  

  鏈表特有版本與通用版本間的一個(gè)至關(guān)重要的區(qū)別是鏈表版本會(huì)改變底層容器。

2.4關(guān)聯(lián)容器

• 關(guān)聯(lián)容器中的元素是按關(guān)鍵字來(lái)保存和訪問(wèn)的互例。與之相對(duì)奢入，順序容器中的元素是按它們?cè)谌萜髦械奈恢脕?lái)順序保存和訪問(wèn)的。

• 八個(gè)關(guān)聯(lián)容器媳叨，三個(gè)維度：
  1）set or map
  2）關(guān)鍵字是否重復(fù)
  3）是否有序

  
  
• 關(guān)聯(lián)容器的迭代器都是雙向的腥光，關(guān)聯(lián)容器不支持順序容器的位置相關(guān)的操作，如push_front等

• 關(guān)聯(lián)容器的關(guān)鍵字map multimap set multiset必須定義元素比較的方法糊秆。默認(rèn)使用<來(lái)比較兩個(gè)關(guān)鍵字武福。
  定義的比較函數(shù)必須具備如下基本性質(zhì)（嚴(yán)格弱序）：

  
  

• 標(biāo)準(zhǔn)庫(kù)utility中的pair類型

  
  
• map和set的關(guān)鍵字都是const，不能修改

• 關(guān)聯(lián)容器操作

  
  
  
  

  關(guān)聯(lián)容器定義的專用的find成員會(huì)比調(diào)用泛型find快得多痘番。
  如果真要對(duì)一個(gè)關(guān)聯(lián)容器使用算法捉片，要么將它當(dāng)作一個(gè)源序列，要么當(dāng)作一個(gè)目的位置夫偶。

  
  
  
  
  
  
  
  
  
  
  
  

  如果容器中沒(méi)有指定的元素界睁，lower_bound將指向第一個(gè)關(guān)鍵字大于k的元素觉增。lower_bound和upper_bound可以一起指定范圍兵拢。
  lower_bound和upper_bound一起指定范圍等價(jià)于equal_range。

• 無(wú)序容器
  無(wú)序容器使用一個(gè)哈希函數(shù)和關(guān)鍵字類型的==運(yùn)算符逾礁。
  無(wú)序容器組織為一組桶说铃，容器將具有一個(gè)特定哈希值的所有元素都保持在相同的桶中访惜。無(wú)序容器的性能依賴于哈希函數(shù)的質(zhì)量和桶的數(shù)量和大小。

  
  
  
  

  標(biāo)準(zhǔn)庫(kù)為內(nèi)置類型（包括指針）腻扇、string债热、智能指針定義了hash，因此可以定義這些類型的無(wú)序容器幼苛。
  自定義類類型的無(wú)序容器必須提供自己的hash模板版本窒篱。

2.5 動(dòng)態(tài)內(nèi)存

• new delete
• 為了更容易、更安全地使用動(dòng)態(tài)內(nèi)存舶沿，標(biāo)準(zhǔn)庫(kù)頭文件memory提供了兩種智能指針來(lái)管理動(dòng)態(tài)對(duì)象墙杯。智能指針負(fù)責(zé)自動(dòng)釋放所指向的對(duì)象。
  shared_ptr允許多個(gè)指針指向同一個(gè)對(duì)象括荡，weak_ptr是一種弱引用高镐，指向shared_ptr所關(guān)聯(lián)的對(duì)象；unique_ptr獨(dú)占所指向?qū)ο?

• shared_ptr類

  
  
  
  

  可以認(rèn)為每個(gè)shared_ptr都有一個(gè)關(guān)聯(lián)計(jì)數(shù)器畸冲，稱為引用計(jì)數(shù)嫉髓，拷貝一個(gè)shared_ptr，計(jì)數(shù)器會(huì)遞增邑闲。
  當(dāng)給shared_ptr賦予一個(gè)新值或是shared_ptr被銷毀時(shí)算行，計(jì)數(shù)器會(huì)遞減。
  一旦一個(gè)shared_ptr的計(jì)數(shù)器變?yōu)?苫耸，就會(huì)自動(dòng)釋放自己所管理的對(duì)象纱意。
  由于在最后一個(gè)shared_ptr銷毀前內(nèi)存都不釋放，保證shared_ptr在無(wú)用之后不再保留很重要鲸阔。
  如果shared_ptr存放在一個(gè)容器中偷霉，而后不再需要全部元素，只使用其中的一部分褐筛，要記得用erase刪除不再需要的那些元素类少。

• 使用動(dòng)態(tài)內(nèi)存的三個(gè)原因：
  1）程序不知道自己需要使用多少對(duì)象——容器
  2）程序不知道所需對(duì)象的準(zhǔn)確類型
  3）程序需要在多個(gè)對(duì)象間共享數(shù)據(jù)
• new/delete
  對(duì)動(dòng)態(tài)的對(duì)象進(jìn)行初始化通常是個(gè)好主意。
  內(nèi)存耗盡new會(huì)拋出bad_alloc異常渔扎，可以傳遞給new一個(gè)nothrow對(duì)象硫狞，不拋出異常，此時(shí)返回一個(gè)空指針晃痴。
  返回指向動(dòng)態(tài)內(nèi)存的指針（而不是指針）的函數(shù)給其調(diào)用者增加了一個(gè)額外的負(fù)擔(dān)——調(diào)用者必須記得釋放內(nèi)存残吩。
• new/delete管理動(dòng)態(tài)內(nèi)存存在三個(gè)常見(jiàn)問(wèn)題
  1）內(nèi)存泄漏，忘記delete
  2）使用已經(jīng)釋放掉的對(duì)象
  3）同一塊內(nèi)存釋放兩次
• delete指針后倘核，將指針置為nullptr泣侮；但是這對(duì)其他指向該內(nèi)存的指針沒(méi)有效果。

• 可以使用new返回的指針來(lái)初始化智能指針紧唱，接受指針參數(shù)的智能指針構(gòu)造函數(shù)是explicit活尊，必須使用直接初始化形式隶校，不能使用賦值。
  默認(rèn)情況下蛹锰，一個(gè)用來(lái)初始化智能指針必須指向動(dòng)態(tài)內(nèi)存深胳，智能指針默認(rèn)使用delelte釋放它所關(guān)聯(lián)的對(duì)象⊥可以將智能指針綁定到一個(gè)指向其他類型資源的指針上舞终，此時(shí)必須提供自己的操作來(lái)替代delete。

  
  
  
  

shared_ptr<int> p1(new int(1024));
shared_ptr<int> clone(int p) {
    return shared_ptr<int>(new int(p));
}

• 當(dāng)將一個(gè)shared_ptr綁定到一個(gè)普通指針時(shí)癣猾，就將內(nèi)存的管理責(zé)任交給shared_ptr权埠。一旦這樣做，就不應(yīng)該使用內(nèi)置指針來(lái)訪問(wèn)shared_ptr所指向的內(nèi)存了煎谍。
• 智能指針的get函數(shù)攘蔽，返回內(nèi)置指針，指向智能指針管理的對(duì)象呐粘。
  應(yīng)用情況：需要向不能使用智能指針的代碼傳遞一個(gè)內(nèi)置指針满俗。使用get返回指針的代碼不能delete該指針。特別是作岖，不能將另一個(gè)智能指針綁定到此指針唆垃。
• 改變shared_ptr對(duì)象，如果不是唯一用戶痘儡，需要拷貝一份新的進(jìn)行改變

if(!p.unique()) {
    p.reset(new string(*p));
}
*p += newVal;

• 智能指針可以確保發(fā)生異常之后辕万，資源被正確地釋放。但是直接管理的內(nèi)存時(shí)不會(huì)自動(dòng)釋放的沉删。
  對(duì)于不具良好定義的類渐尿，如果在資源分配和釋放之間發(fā)生了異常，程序會(huì)發(fā)生資源泄漏矾瑰∽┤祝可以使用shared_ptr來(lái)避免資源泄漏。

//存在內(nèi)存泄漏風(fēng)險(xiǎn)的代碼
struct destination;
struct conneciton;
connection connect(destination*);
void disconnect(connection);
void f(destination &d) {
    connection c = connect(&d);
}

//使用shared_ptr防止內(nèi)存泄漏
void end_connection(connection *p) {
    disconnect(*p);
}
void f(destination &d) {
    connection c = connect(&d);
    shared_ptr<connection> p(&c, end_connection);
}

• 智能指針必須堅(jiān)持的基本規(guī)范
  1）不適用相同的內(nèi)置指針初始化（或reset）多個(gè)智能指針
  2）不delete get()返回的指針
  3）不適用get() 初始化或reset另一個(gè)智能指針
  4）如果使用get()返回的指針殴穴，記住當(dāng)最后一個(gè)對(duì)應(yīng)的智能指針?shù)N毀后凉夯，你的指針就變?yōu)闊o(wú)效了
  5）如果使用智能指針管理的資源不是new分配的內(nèi)存，記住傳遞給它一個(gè)刪除器采幌。

• unique_ptr
  某個(gè)時(shí)刻只能有一個(gè)unique_ptr指向一個(gè)給定對(duì)象劲够。
  unique_ptr不支持普通的拷貝或賦值操作，可以通過(guò)release或reset將指針的所有權(quán)從一個(gè)（非const）unique_ptr轉(zhuǎn)移到另一個(gè)休傍。

  
  
• 不能拷貝unique_ptr的規(guī)則有一個(gè)例外：可以拷貝或賦值一個(gè)將要銷毀的unique_ptr

unique_ptr<int> clone(int p) {
    return unique_ptr<int>(new int(p));
}

unique_ptr<int> clone(int p) {
    unique_ptr<int> ret(new int (p));
    return ret;
}

• unique_ptr管理刪除器的方式與shared_ptr不同征绎。

void f(destination &d) {
    connection c = connect(&d);
    unique_ptr<connection, decltype(end_connection)*>
                                            p(&c, end_connection);
}

• weak_ptr
  不控制所指向?qū)ο笊嫫诘闹悄苤羔槪赶蛞挥梢粋€(gè)shared_ptr管理的對(duì)象尊残。
  將一個(gè)weak_ptr綁定到一個(gè)shared_ptr不會(huì)改變shared_ptr的引用計(jì)數(shù)炒瘸。

  
  
  
  

  不能使用weak_ptr直接訪問(wèn)對(duì)象，必須調(diào)用lock寝衫。

if (shared_ptr<int> np = wp.lock()) {
}

• 兩種分配對(duì)象數(shù)組的方法
  1）new表達(dá)式語(yǔ)法
  2）allocator類顷扩，將分配和初始化分類，通常會(huì)提供更好的性能和更靈活的內(nèi)存管理能力
• 大多數(shù)應(yīng)用應(yīng)該使用標(biāo)準(zhǔn)庫(kù)容器而不是動(dòng)態(tài)分配的數(shù)組慰毅。使用容器更為簡(jiǎn)單隘截，更不容易出現(xiàn)內(nèi)存管理錯(cuò)誤并且可能有更好的性能。

• 管理new分配數(shù)組的unique_ptr

  
  

unique_ptr<int[]> up(new int[10])
up.release() //自動(dòng)調(diào)用delete[]銷毀其指針

• 與unique_ptr不同汹胃，shared_ptr不直接支持管理動(dòng)態(tài)數(shù)組婶芭，需要提供自定義的刪除器。
  shared_ptr未定義下標(biāo)運(yùn)算着饥，且智能指針不支持指針?biāo)阈g(shù)運(yùn)算铣焊。

• allocator類——頭文件memory
  new將內(nèi)存分配和對(duì)象構(gòu)造組合在一起坯约，同樣，delete將對(duì)象析構(gòu)和內(nèi)存釋放組合在一起。
  當(dāng)分配一大塊內(nèi)存時(shí)涤妒，統(tǒng)計(jì)計(jì)劃在這塊內(nèi)存上按需構(gòu)造對(duì)象，即內(nèi)存分配和對(duì)象構(gòu)造分離裳仆。
  allocator將內(nèi)存分配和對(duì)象構(gòu)造分離開(kāi)敲才，分配的內(nèi)存時(shí)原始的、未構(gòu)造的挪拟。

  
  

• allocator伴隨算法——拷貝和填充未初始化內(nèi)存的算法
  頭文件memory中：