---
tags: 程式語言
---
C++ Primer 第五版 中
===
# Part II The C++ Library

## Ch 8 The IO Library
C++語言並沒有直接處理輸入與輸出的語法，而是靠定義在標準程式庫中一系列的型別所處理。這些型別支援對裝置的寫入和讀取，例如檔案和主控台視窗。還有額外的型別允許讀寫string的in-memory IO。

### IO 類別
* `iostream`標頭檔
* `istream` 讀取自一個資料流
* `ostream` 寫入到一個資料流
* `iostream` 讀寫一個資料流
* `fstream`標頭檔
* `ifstream` 讀取自一個檔案
* `ofstream` 寫入到一個檔案
* `fstream` 讀寫一個檔案
* `sstream`標頭檔
* `istringstream` 讀取自一個string
* `ostringstream` 寫入到一個string
* `stringstream` 讀寫一個string


因為`ifstream`和`istringstream`類別都繼承自`istream`，所以我們可以把型別為`ifstream`和`istringstream`的物件當成是`istream`物件來使用。

[IO物件不能拷貝和指定]()

因為IO型別無法被拷貝，資料流型別不能當作參數傳入函式，也不能當作回傳型別，但可以透過參考傳入或回傳資料流，且讀寫一個IO物件會改變其狀態，所以這種參考不能是`const`。

std::ofstream out1, out2;
out1 = out2; // error: cannot assign stream objects
std::ofstream print(std::ofstream); // error: can't initialize the ofstream parameter
out2 = print(out2); // error: cannot copy stream objects

[condition state]()

進行IO時，要面對的一個事實是可能會有錯誤發生。有時錯誤是可以復原的，其他的則發生在系統底層，超出程式更正錯誤的能力範圍。IO類別定義了一些函式與flags，讓我們可以存取和操作一個資料流的condition state。
因為一個資料流可能處在錯誤狀態，程式碼一般都應該在試著使用前，檢查一個資料流是否沒有問題。例如：

while (std::cin >> word)
    // ok : 讀取運算成功

上述使用一個資料流做為條件只能告訴我們該資料流是否有效，但不會告訴我們發生了什麼事。有的時候我們也需要知道資料流為何是無效的。舉例來說，碰到檔案結尾時我們要做的事，很有可能和遇到IO裝置錯誤時處置不同。
IO資料庫定義了一個獨立於機器的整數型別，名為`iostate`，用以傳達有關資料流狀態的資訊。這種型別被當作一組位元來使用：

`goodbit`、`failbit`、`eofbit`和`badbit`
上述flags可用`s.good()`、`s.fail()`、`s.eof()`和`s.bad()`來取得。
另外：
* `s.clear()` 將資料流s所有條件值都重置為有效狀態
* `s.clear(flags)` 將s的條件重置為flags，flags的型別為strm::iostate
* `s.setstate(flags)` 將所指定的條件新增到s。flags的型別為strm::iostate
* `s.rdstate()` 將s目前的條件回傳為一個strm::iostate值

範例1：

// remember the current state of cin
auto old_state = std::cin.rdstate(); // remember the current state of cin
std::cin.clear(); // make cin valid
process_input(std::cin); // use cin
std::cin.setstate(old_state); // now reset cin to its old state

範例2：下列程式碼會關閉`failbit`和`badbit`，但不會動到`eofbit`。

// turns off failbit and badbit but all other bits unchanged
std::cin.clear(std::cin.rdstate() & ~std::cin.failbit & ~std::cin.badbit);

[管理 output buffer]()

每個輸出資料流都管理了一個緩衝區(buffer)，用以存放程式要讀寫的資料，有幾個條件會導致緩衝區被flushed：
* 程式正常結束，所有的輸出緩衝區都會在main函式的return動作中被flushed。
* 當緩衝區滿了，也會被flushed。
* 使用`std::endl`強制flushed。
* 我們可以使用`unibuf`來設定資料流內部狀態，讓它在每次輸出運算後flush緩衝區。

std::cout << std::unitbuf;   // 讓所有的寫入都立刻flushed
std::cout << std::nounitbuf; // 回復到正常緩衝

* 當一個輸入資料流被綁到輸出資料流，讀取那個輸入資料流的任何嘗試都會flush該輸出資料流，因為程式庫將`cout`綁到`cin`，所以`std::cin >> ival;`會導致`cout`被flush。我們可以用`tie`函式來綁定輸入資料流和輸出資料流。

cin.tie(&cout); // illustration only: the library ties cin and cout for us
// old_tie points to the stream (if any) currently tied to cin
ostream *old_tie = cin.tie(nullptr); // cin is no longer tied
// ties cin and cerr; not a good idea because cin should be tied to cout
cin.tie(&cerr); // reading cin flushes cerr, not cout
cin.tie(old_tie); // reestablish normal tie between cin and cout

注意：當程式異常結束，輸出緩衝區不會被flushed。

std::cout << "hi" << std::endl;    // 寫入hi以及一個newline，然後flush
std::cout << "hi" << std::flush;   // 寫入hi，然後flush
std::cout << "hi" << std::ends;    // 寫入hi以及一個null，然後flush

### 檔案輸入與輸出
`fstream`標頭檔定義了三個型別來支援檔案IO：`ifstream`用來讀取檔案，`ofstream`則用來寫入檔案，還有`fstream`用來讀寫檔案。因為`ifstream`繼承自`istream`，`ofstream`繼承自`ostream`，所以我們可以將`ifstream`物件傳給接受`istream&`型別的函式：

ifstream input(argv[1]); // open the file of sales transactions
ofstream output(argv[2]); // open the output file
Sales_data total; // variable to hold the running sum
if (read(input, total)) { // read the first transaction
    Sales_data trans; // variable to hold data for the next transaction
    while(read(input, trans)) { // read the remaining transactions
        if (total.isbn() == trans.isbn()) // check isbns
            total.combine(trans); // update the running total
        else {
            print(output, total) << endl; // print the results
            total = trans; // process the next book
        }
    }
    print(output, total) << endl; // print the last transaction
} else // there was no input
    cerr << "No data?!" << endl;

[`open`和`close`成員]()

當我們定義一個空的檔案資料流物件，我們可以在之後呼叫`open`來將檔案關聯至該物件：

ifstream in(ifile);
ofstream out;
out.open(ifile + ".copy");
if (out)
    // open成功，所以我們可以使用該檔案

注意：在已經開啟的一個檔案資料流上呼叫`open`一定會失敗，並設定`failbit`。如要將一個檔案資料流關聯到一個不同的檔案，我們必須先關閉現有的檔案，一旦檔案被關閉，我們就可以開一個新的：

in.close();     // 關閉檔案
in.open(ifile + "2")  // 開啟另一個檔案

[自動建構與解構]()

請思考一個程式，`main`接受一個檔案清單，並逐一開啟檔案：

for (auto p = argv + 1; p != argv + argc; ++p) {
    ifstream input(*p);    // 創建input並開啟該檔案
    if (input) {           // 如果開檔沒問題就處理該檔案
        process(input);
    } else 
        cerr << "couldn't open: " + string(*p);
}  // input 已跑出範疇，並會在每次迭代中被摧毀

注意：當一個`fstream`物件被摧毀，`close`會自動被呼叫。

[檔案模式]()

每個資料流都有一個關聯的檔案模式(file mode)用以代表檔案可以如何被使用：
* in 寫入檔案
* out 讀取檔案
* app 每次寫入都移到尾端
* ate 開啟後立刻移到尾端
* trunc 截斷檔案
* binary 以二進制進行作業

預設情況下，當我們開啟一個`ofstream`，檔案的內容會被捨棄，避免一個`oftream`清空給定檔案的唯一方式是指定`app`：

// file1 is truncated in each of these cases
ofstream out("file1"); // out and trunc are implicit
ofstream out2("file1", ofstream::out); // trunc is implicit
ofstream out3("file1", ofstream::out | ofstream::trunc);
// to preserve the file's contents, we must explicitly specify app mode
ofstream app("file2", ofstream::app); // out is implicit
ofstream app2("file2", ofstream::out | ofstream::app);

### string 資料流
`sstream`標頭檔定義了三個型別來支援記憶體內的IO，這些型別會讀取或寫入一個string，好像那個string是一個IO資料流一樣。

`istringstream`型別讀取一個string，`ostringstream`寫入一個string，而`stringstream`則讀寫一個string。

[使用`istringstream`]()

我們經常會在要對一整行做些處理，還要對一行中的個別字詞做其他處理的時候使用一個`istringstream`。舉個例子，假設我們有個檔案：

morgan 2015552368 8625550123
drew 9735550130
lee 6095550132 2015550175 8005550000

這個檔案每筆紀錄以一個名字開頭，後面接一或更多個電話號碼。我們會先定義一個簡單的類別來表示我們的輸入資料：

struct PersonInfo {
    std::string name;
    std::vector<std::string> phones;
};

std::string line, word; // will hold a line and word from input, respectively
std::vector<PersonInfo> people; // will hold all the records from the input
// read the input a line at a time until cin hits end-of-file (or another error)
while (getline(std::cin, line)) {
    PersonInfo info; // create an object to hold this record's data
    std::istringstream record(line); // bind record to the line we just read
    record >> info.name; // read the name
    while (record >> word) // read the phone numbers
        info.phones.push_back(word); // and store them
    people.push_back(info); // append this record to people
}

[使用`ostringstream`]()

當我們想要一點一滴建置出我們的輸出，在之後才印出這些輸出，那`ostringstream`就很實用。

for (const auto &entry : people) { // for each entry in people
    std::ostringstream formatted, badNums; // objects created on each loop
    for (const auto &nums : entry.phones) { // for each number
        if (!valid(nums)) {
            badNums << " " << nums; // string in badNums
        } else
        // ''writes'' to formatted's string
            formatted << " " << format(nums);
    }
    if (badNums.str().empty()) // there were no bad numbers
        os << entry.name << " " // print the name
            << formatted.str() << std::endl; // and reformatted numbers
    else // otherwise, print the name and bad numbers
        std::cerr << "input error: " << entry.name
            << " invalid number(s) " << badNums.str() << std::endl;
}

## Ch 9 Sequential Containers
* vector
* deque
* list
* forward_list
* array
* string

### [Convert a list to a vector](https://www.techiedelight.com/convert-list-to-vector-cpp/)
1. use for loop

#include <iostream>
#include <vector>
#include <list>

int main()
{
    std::list<char> li = {'a', 'b', 'c'};
    std::vector<char> result;
    
    for (const char &c : li) {
        result.push_back(c);
    }
    
    for (const char &c : result) {
        std::cout << c << ' ';
    }
    return 0;
}

2. use range constructor

#include <iostream>
#include <vector>
#include <list>
#include <algorithm>

int main()
{
    std::list<char> li = {'a', 'b', 'c'};
    std::vector<char> result(li.begin(), li.end());
    
    for (const char &c : result) {
        std::cout << c << ' ';
    }
    return 0;
}

3. use move iterator

#include <iostream>
#include <vector>
#include <list>
#include <algorithm>

int main()
{
    std::list<char> li = {'a', 'b', 'c'};
    std::vector<char> result(std::make_move_iterator(li.begin()), 
                             std::make_move_iterator(li.end()));
    
    for (const char &c : result) {
        std::cout << c << ' ';
    }
    return 0;
}

4. use copy

#include <iostream>
#include <vector>
#include <list>
#include <algorithm>

int main()
{
    std::list<char> li = {'a', 'b', 'c'};
    std::vector<char> result(li.size());
    
    std::copy(li.begin(), li.end(), result.begin());
    
    for (const char &c : result) {
        std::cout << c << ' ';
    }
    return 0;
}

5. use assign
`assign`運算會把左邊容器的所有元素取代為它的引數所指定的元素(的拷貝)。

std::list<std::string> names;
std::vector<const char*> oldstyle;
names = oldstyle; // error: container types don't match
// ok: can convert from const char* to string
names.assign(oldstyle.cbegin(), oldstyle.cend());

### [Defining and Initializing a Container]()
1. copy from another container
容器與元素型別必須相同才能拷貝

#include <vector>
#include <string>

int main()
{
    std::vector<std::string> authors = {"Milton", "Shakespeare", "Austen"}; 
    // list initialization
    std::vector<std::string> v2(authors);
    std::vector<std::string> v3(v2.begin(), v2.end());
    return 0;
}

2. size-related constructor

#include <vector>
#include <list>
#incldue <deque>

int main()
{
    std::vector<int> ivec(10, -1);
    std::list<std::string> svec(10, "hi!");
    std::forward_list<int> fvec(10); // default initialized to 0
    std::deque<std::string> dvec(10); // default initialized to empty string
    return 0;
}

3. [std::array](https://coherence0815.wordpress.com/2015/08/22/stdarray-in-c-11/)
比起C-Style array來說，有以下優缺點：
* 包裝成class，可以避免array被隱式(implicit)轉型成pointer。(e.g. 把array當pointer傳給function)
* performance幾乎沒有差別(C-Style比較好一點點)
* C-Style array可以access超過array的範圍，這將造成undefined behavior；std::array則否。
* std::array知道自己的size；但是如果你透過pointer把一個C-Style array傳給一個function的話，在該function中是無法透過sizeof()來取得該array的size。
* std::array有實作copy constructor和assignment operator，所以他可以方便的被複製。

#include <array>

int main()
{
    std::array<int, 10> arr; // type is: array that holds 10 ints
    std::array<std::string, 10> s; // type is: array that holds 10 strings
    std::array<int, 10>::size_type i; 
    std::array<int, 10> ia = {42}; // ia[0] = 42, remaining elements are 0
    return 0;
}

### [vector](https://mropengate.blogspot.com/2015/07/cc-vector-stl.html)
* 支援隨機存取
* 集合尾端增刪元素很快 : O(1)
* 集合中間增刪元素比較費時 : O(n)
* 以模板(泛型)方式實現，可以儲存任意類型的變數，包括使用者自定義的資料型態。
* 有一些容器提供 [stable iterator](https://edisonx.pixnet.net/blog/post/93629406) 保證，很不幸的 vector 不保證。因此存在一些可能造成 vector iterator 失效的操作。

1. 存取元素的用法

* vec[i] - 存取索引值為 i 的元素值。
* vec.at(i) - 存取索引值為 i 的元素的值，以 at() 存取會做陣列邊界檢查，如果存取越界將會拋出一個例外，這是與operator[]的唯一差異。
* vec.front() - 回傳 vector 第一個元素的值。
* vec.back() - 回傳 vector 最尾元素的值。

2. 新增或移除元素的用法

* vec.push_back() - 新增元素至 vector 的尾端，必要時會進行記憶體配置。
* vec.pop_back() - 刪除 vector 最尾端的元素。
* vec.insert() - 插入一個或多個元素至 vector 內的任意位置。
insert會將元素插入到指定的迭代器前面，並返回指向插入的第一個元素的迭代器
* vec.erase() - 刪除 vector 中一個或多個元素。
erase 會返回「被移除元素之下一個元素」
* vec.clear() - 清空所有元素。

少依賴 push_back() 的自動記憶體配置，不是不要用 push_back，是不要讓 push_back 自己判定記憶體需求，能自己要記憶體的就自己要，善用 reserve()、resize() 或 constructor 引數。

### [stable iterator](https://edisonx.pixnet.net/blog/post/93629406)
vector 裡一些操作，會使得原本之 iterator 失效，必須再重新取得才可，最常見的碼是 erase ，假設要在 vector 裡面刪除某個元素：

int main()
{
    vector<int> v(10);
    vector<int>::iterator it, end;
    const int val = 1;
    // initialize
    for(size_t i=0; i<v.size(); ++i) v[i]=i;
    it = v.begin();
    end = v.end();
    // remove
    while(it!=end){ /* error */
        if(*it == val) 
            v.erase(it);
        ++it; /* error */
    }    
    return 0;
}

(1) erase 會返回「被移除元素之下一個元素」，故至少要寫 it = v.ease(it) ; ++it 略過，但還是錯誤。

正確寫法：

int main()
{
    vector<int> v(10, 1);
    vector<int>::iterator it, end;
    const int val = 1;
    for(it=v.begin(); it!=v.end(); )
        if(*it==val) it = v.erase(it);
        else ++it;
    return 0;
}

或使用find + erase

#include <iostream>
#include <algorithm>
#include <vector>
 
int main()
{
    std::vector<int> vec = {1, 2, 3, 4, 5, 6};
    auto it = find(vec.begin(), vec.end(), 4);
    vec.erase(it);
    for (auto &v : vec)
        std::cout << v << " ";
    std::cout << std::endl;
    return 0;
}

或使用[remove_if](https://www.techiedelight.com/remove-elements-vector-inside-loop-cpp/)。

#include <iostream>
#include <vector>
#include <algorithm>

int main()
{
    std::vector<int> v = {1, 2, 3, 4, 5, 6};
    auto end = std::remove_if(v.begin(), v.end(), [](int const &i){ return i & 1; });
    // remove odd numbers
    v.erase(end, v.end());
    
    for (int const &i : v) {
        std::cout << i << ' ';
    }
    return 0;
}

[push_back vs emplace_back 1](https://blog.csdn.net/yockie/article/details/52674366)

#include <vector>
#include <string>

int main() {


    std::vector<std::string> v;
    int count = 10000000;
    v.reserve(count);       //预分配十万大小，排除掉分配内存的时间

    {
        std::cout << "push_back string";
        for (int i = 0; i < count; i++)
        {
            std::string temp("ceshi");
            v.push_back(temp);// push_back(const string&)，参数是左值引用
        }
    }

    v.clear();
    {
        std::cout << "push_back move(string)";
        for (int i = 0; i < count; i++)
        {
            std::string temp("ceshi");
            v.push_back(std::move(temp));// push_back(string &&), 参数是右值引用
        }
    }

    v.clear();
    {
        std::cout << "push_back(string)";
        for (int i = 0; i < count; i++)
        {
            v.push_back(std::string("ceshi"));// push_back(string &&), 参数是右值引用
        }
    }

    v.clear();
    {
        std::cout << "push_back(c string)";
        for (int i = 0; i < count; i++)
        {
            v.push_back("ceshi");// push_back(string &&), 参数是右值引用
        }
    }

    v.clear();
    {
        std::cout << "emplace_back(c string)";
        for (int i = 0; i < count; i++)
        {
            v.emplace_back("ceshi");// 只有一次构造函数，不调用拷贝构造函数，速度最快
        }
    }
}

第1中方法耗時最長，原因顯而易見，將調用左值參考的push_back，且將會調用一次string的拷貝建構子，比較耗時，這裡的string還算很短的，如果很長的話，差異會更大

第2、3、4中方法耗時基本一樣，參數為右值，將調用右值參考的push_back，故調用string的移動建構子，移動建構子耗時比拷貝建構子少，因為不需要重新分配記憶體空間。

第5中方法耗時最少，因為emplace_back只調用建構子，沒有移動建構子，也沒有拷貝建構子。

[push_back vs emplace_back 2](https://stackoverflow.com/questions/4303513/push-back-vs-emplace-back)
For emplace_back constructor A (int x_arg) will be called. And for push_back A (int x_arg) is called first and move A (A &&rhs) is called afterwards.

#include <iostream>
#include <vector>
class A
{
public:
  A (int x_arg) : x (x_arg) { std::cout << "A (x_arg)\n"; }
  A () { x = 0; std::cout << "A ()\n"; }
  A (const A &rhs) noexcept { x = rhs.x; std::cout << "A (A &)\n"; } // 拷貝建構子
  A (A &&rhs) noexcept { x = std::move(rhs.x); std::cout << "A (A &&)\n"; }  // 移動建構子

private:
  int x;
};

int main ()
{
  {
    std::vector<A> a;
    std::cout << "call emplace_back:\n";
    a.emplace_back (0);
  }
  {
    std::vector<A> a;
    std::cout << "call push_back:\n";
    a.push_back (1);
  }
  return 0;
}

output

call emplace_back:
A (x_arg)

call push_back:
A (x_arg)
A (A &&)

### Sequential Container Operations
除了前面提到的`push_back`和`emplace_back`，我們也可以使用`insert`將元素插入到指定位置：

std::vector<std::string> svec;
std::list<std::string> slist;
slist.insert(iter, "Hello!"); // 在iter前面插入"Hello!"
// 等同於呼叫 slist.push_front("Hello!");
slist.insert(slist.begin(), "Hello!");
// vector沒有push_front運算子，但我們可以在begin()前insert
// warning: 除了在vector尾端，在其他位置插入元素都很慢
svec.insert(svec.begin(), "Hello!");
std::vector<std::string> v = {"quasi", "simba", "frollo", "scar"};
// 在slist的開頭插入v的最後兩個元素
slist.insert(slist.begin(), v.end() - 2, v.end());
slist.insert(slist.end(), {"these", "words", "will", "go", "at", "the", "end"});
// run-time error: 拷貝來源範圍的迭代器不能跟我們要變更的同一個
slist.insert(slist.begin(), slist.begin(), slist.end());

[調整容器的大小]()

我們可以用`resize`來變更容器的大小，如果目前的大小大於請求的大小，元素會從容器的後端刪除；如果目前的大小小於請求的大小，元素會被加到容器的後端：

std::list<int> ilist(10, 42);    // 十個int：每個值都是42
ilist.resize(15);                // 新增五個值為0的元素到ilist的尾端
ilist.resize(25, -1);            // 新增十個-1到ilist的尾端
ilist.resize(5);                 // 從ilist的後端刪除20個元素

注意：如果`resize`縮小容器，那麼迭代器、參考和指標，只要指向的是被刪除的元素，就會無效化。使用無效化的迭代器、參考和指標，會是一種嚴重的執行期錯誤。

### 額外的string運算

## Ch 10 Generic Algorithms
### Overview
大部分的演算法都定義在`algorithm`和`numeric`標頭檔中，一般來說，演算法不會直接作用在整個容器上，而是traverse由兩個迭代器所界定的範圍，對範圍內的元素做些事情。例如：

int val = 42;
auto result = find(vec.cbegin(), vec.cend(), val);
cout << "The value " << val
     << (result == vec.cend() ? " is not present" : " is present") << endl;
int ia[] = {27, 210, 12, 47, 109, 42};
int *result2 = find(begin(ia), end(ia), val);
auto result3 = find(ia + 1, ia + 4, val);

注意：演算法以迭代器運算運作，而非藉由容器運算運作。也就是說，演算法永遠都不會更改底層容器的大小，演算法可以改變儲存在容器中的元素的值，也可以在容器中到處移動元素，但不能直接新增或移除元素。

### A First Look at the Algorithms
除了少數例外，大部分演算法都作用在一個範圍內的元素。我們稱作輸入範圍，接受一個輸入範圍的演算法都會用它們的頭兩個參數來代表這個範圍，這些參數是迭代器，代表要處理的第一個元素和超過最後一個元素的一個位置處。另外，理解這些演算法最基本的方法就是了解它們是否會讀取元素、寫入元素或重新安排元素的順序。

[唯讀演算法]()

有幾個演算法只會讀取它們輸入範圍內的元素，永遠都不會寫入，例如：`find`、`count`、`accumulate`。

* `accumulate`：
accumulate的第三個引數的型別決定要用哪個加法運算子，並且是accumulate回傳的型別。

// 加總vec中的元素，以值0開始加總
int sum = accumulate(vec.cbegin(), vec.cend(), 0);
string sum1 = accumulate(v.cbegin(), v.cend(), string(""));
// error : const char*沒有+運算
string sum2 = accumulate(v.cbegin(), v.cend(), "");

注意：一般來說，最好使用`cbegin()`和`cend()`來搭配讀取但不寫入元素的演算法。

* `equal`：
它讓我們判斷兩個序列是否存放相同的值。

// roster2至少要有與roster1一樣多的元素
equal(roster1.cbegin(), roster1.cend(), roster2.cbegin());

[寫入容器元素的演算法]()

當我們使用會對元素做指定的演算法，我們必須小心確保演算法所寫入的序列之元素數目至少與我們要求演算法寫入的一樣多，畢竟演算法不會進行容器運算，所以它們無法改變容器的大小。

* `fill`

fill(vec.begin(), vec.end(), 0);   // 將每個元素都重置為0

* `fill_n`
fill_n 接受單一個迭代器、一個計數、以及一個值。它會將所給的值指定給該迭代器所代表的元素開始的指定數目個元素。

vector<int> vec;
fill_n(vec.begin(), vec.size(), 0);
fill_n(vec.begin(), 10, 0);   // 災難：試著寫入vec中十個(不存在的)元素，可能引發Segmentation Fault

注意：寫入一個目的地迭代器的演算法假設那個目的地大到足夠容納寫入的元素數。

* `copy`
copy接受三個迭代器，頭兩個代表一個輸入範圍，第三個代表目的地序列的開頭。

int a1[] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
int a2[10];
auto ret = copy(begin(a1), end(a1), a2); // 將a1拷貝到a2中

`copy`回傳的值是目的地迭代器經過遞增後的值，也就是說，`ret`指向剛超過拷貝到`a2`中的最後一個元素的地方。

* `replace` 和 `replace_copy`

#include <iostream>     
#include <algorithm>   
#include <vector>       
 
int main () {
	int myints[] = { 10, 20, 30, 30, 20, 10, 10, 20 };
 
	/*replace*/
	std::vector<int> myvector1 (myints, myints+8);            // 10 20 30 30 20 10 10 20
	std::replace (myvector1.begin(), myvector1.end(), 20, 99); // 10 99 30 30 99 10 10 99
	std::cout << "replace() myvector1:";
	for(const auto i : myvector1)
		std::cout << i << " ";
	std::cout << std::endl;
 
	/*replace_copy*/
	std::vector<int> myvector2 (8);
	std::replace_copy (myints, myints+8, myvector2.begin(), 20, 78);
	std::cout << "replace_copy() myvector2:";
	for(const auto i : myvector2)
		std::cout << i << " ";
	std::cout << std::endl;
 
	return 0;
}

輸出：

replace() myvector1:10 99 30 30 99 10 10 99 
replace_copy() myvector2:10 78 30 30 78 10 10 78 

[改變容器元素順序的演算法]()

* `sort`

#include <iostream>
#include <algorithm>

int main() {
    int arr[6] = {5, 3, 2, 6, 1, 4};

    // 排序 arr 陣列，需指定排序的起始與結束範圍
    sort(arr, arr + 6);

    for (int i = 0; i < 6; i++) {
        std::cout << arr[i] << " ";
    }
    std::cout << std::endl;
    return 0;
}

輸出：

1 2 3 4 5 6

* `unique`
unique演算法會重新安排輸入範圍，來「消除」相鄰的重複項目，並回傳一個迭代器指向範圍的結尾。

#include <iostream>     
#include <algorithm>   
#include <vector>     
#include <string>
 
int main () {
    std::vector<std::string> words = {"the", "quick", "red", "fox", "jumps", 
                                 "over", "the", "slow", "red", "turtle"};
    sort(words.begin(), words.end());
    auto end_unique = unique(words.begin(), words.end());
    words.erase(end_unique, words.end());    // 使用容器運算來移除元素
    for (auto w : words) std::cout << w << std::endl;
	return 0;
}

注意：嚴格來說，`unique`演算法並沒有刪除容器內的元素，而是覆寫相鄰的重複元素，容器的大小則維持不變。

### Customizing Operations
許多演算法都會比較輸入序列中的元素，預設情況下，這種演算法會使用元素型別的`<`或`==`運算子。但我們也可以提供自己的運算來取代預設的運算子。

[傳遞函式給演算法]()

bool isShorter(const string &s1, const string &s2)
{
    return s1.size() < s2.size();
}
// 以字詞長度排序，從最短的到最長的
sort(words.begin(), words.end(), isShorter);
stable_sort(words.begin(), words.end(), isShorter); // 穩定排序會在相等的元素之間保持原有的順序

[Lambda 運算式]()

[capture list](parameter list) -> return type { function body }

* Lambda的捕捉串列
* [] 空的捕捉串列，這個lambda不可以使用來自外圍函式的變數
* [names] names是用逗號分隔的名稱，這些名稱是外圍函式的區域名稱，預設情況下，捕捉的變數會被拷貝，前面接著`&`的名稱會被參考捕捉
* [&] 隱含以參考捕捉
* [=] 隱含以值捕捉
* [&, identifier_list] identifier_list包含的變數以值捕捉，剩下的變數以參考捕捉
* [=, identifier_list] identifier_list包含的變數以參考捕捉，剩下的變數以值捕捉

範例：

// 此函式用來找出words中長度大於等於sz的元素，並移除重複的元素
void biggies(vector<string> &words, vector<string>::size_type sz)
{
    elimDups(words); // 讓words以字母順序排列，並移除重複的元素
    // 以字串長度排序words，但相同長度的字詞間維持原來順序
    stable_sort(words.begin(), words.end(),
        [](const string &a, const string &b) { return a.size() < b.size();});
    // 取得一個迭代器指向size() >= sz的第一個元素
    auto wc = find_if(words.begin(), words.end(),
            [sz](const string &a) { return a.size() >= sz; });
    // 計算大小>=sz的元素數目
    auto count = words.end() - wc;
    // 印出結果
    for_each(wc, words.end(),
            [](const string &s){cout << s << " ";});
    cout << endl;
}

### 再訪迭代器
* 插入迭代器 (insert iterators) 這些迭代器繫結到一個容器，可被用來插入元素
* `back_inserter` 創建使用`push_back`的迭代器

        std::list<int> int_list = {1, 2, 3, 4, 5};
        std::vector<int> int_vector;
        // 因為int_vector為空，複製會造成segmentation fault
	    copy(int_list.begin(), int_list.end(), int_vector.begin()); 
        // 所以要改用
        copy(int_list.begin(), int_list.end(), back_inserter(int_vector)); 

* `front_inserter` 創建使用`push_front`的迭代器

        list<int> lst = {1,2,3,4};
        list<int> lst2, lst3; // empty lists
        // after copy completes, 1st2 contains 4 3 2 1
        copy(lst.cbegin(), lst.cend(), front_inserter(lst2));
        // after copy completes, 1st3 contains 1 2 3 4
        copy(lst.cbegin(), lst.cend(), inserter(lst3, lst3.begin()));

* `inserter` 創建使用`insert`的迭代器

        auto it = inserter(c, iter);
        *it = val;
        // 以上的行為等同：
        auto it = c.insert(iter, val);
        ++it;

* 資料流迭代器 (stream iterators)
* 反向迭代器 (reverse iterators)
* [移動迭代器 (move iterators)](https://www.fluentcpp.com/2017/04/25/move-iterators/)

std::vector<std::string> source = { "Move", "iterators", "in", "C++" };
std::vector<std::string> destination(std::make_move_iterator(begin(source)),
                                     std::make_move_iterator(end(source)));
// Source: "" "" "" "" 
// Destination: "Move" "iterators" "in" "C++"

## Ch 11 Associative Containers
程式庫提供八種associative containers：

元素以鍵值排序
* map : holds key-value pairs
* set : container in which the key is the value
* multimap : `map` in which a key can appear multiple times
* multiset : `set` in which a key can appear multiple times

無序群集
* unordered_map : `map` organized by a hash function
* unordered_set : `set` organized by a hash function
* unordered_multimap : Hashed `map`; keys can appear multiple times
* unordered_multiset : Hashed `set`; keys can appear multiple times

注意：無序群集不能用來排序(sort)，如果要排序無序群集，需要先將無序群集轉換為有序序列再排序。

### [Map (STL) 用法與心得完全攻略](https://mropengate.blogspot.com/2015/12/cc-map-stl.html)

Map 是 C++ 標準程式庫中的一個 class，為眾多容器（container）之一。它提供搜尋和插入友善的資料結構，並具有一對一 mapping 功能：

* 第一個稱為關鍵字 (key)，每個關鍵字只能在 map 中出現一次。
* 第二個稱為該關鍵字的值 (value)。

Map 的特色
* map 內部資料結構為一顆紅黑樹 (red-black tree)，因此：
* 內部是有排序的資料。
* 對於搜尋和插入操作友善( O(logn) )。
* 可以修改 value 值、不能修改 key 值。
* 以模板（泛型）方式實現，可以儲存任意類型的變數，包括使用者自定義的資料型態。

與 map 類似的 STL 結構
* map : 紅黑樹 (查询、插入、删除都是O(logn) )
* unordered_map : hash 結構，C++11 標準函式庫。
* unordered_set : hash 結構，但 value 本身即是 key。

key_type, mapped_type and value_type

#include <iostream>
#include <map>
#include <typeinfo>
 
int main()
{
	using u_map = std::map<char, int>;
	u_map m;
	m.emplace('x', 64);
 
	u_map::key_type key;
	u_map::mapped_type mapped;
	u_map::value_type value;
    
    std::cout << typeid(key).name() << std::endl;
    std::cout << typeid(mapped).name() << std::endl;
    std::cout << typeid(value).name() << std::endl;
 
	return 0;
}

輸出

char 
int
struct std::pair<char const, int>

成員函式簡介與常用程式寫法
1. 宣告

map<string, string> mapStudent;

2. 初始化

std::map<std::string, std::string> authors = {
    {"Joyce", "James"},
    {"Austen", "Jane"},
    {"Dickens", "Charles"}
};

3. 插入 insert()

// 用 insert 函數插入 pair
mapStudent.insert(pair<string, string>("r000", "student_zero"));

//用 "array" 方式插入
mapStudent["r123"] = "student_first";
mapStudent["r456"] = "student_second";

4. 尋找 find()

iter = mapStudent.find("r123");
if(iter != mapStudent.end())
       cout<<"Find, the value is"<<iter->second<<endl;
else
   cout<<"Do not Find"<<endl;

5. 刪除與清空

//迭代器刪除
iter = mapStudent.find("r123");
mapStudent.erase(iter);
//用關鍵字刪除
int n = mapStudent.erase("r123");//如果刪除了會返回1，否則返回0
//用迭代器範圍刪除 : 把整個map清空
mapStudent.erase(mapStudent.begin(), mapStudent.end());
//等同於mapStudent.clear()

6. [equal_range、lower_bound、upper_bound](https://en.cppreference.com/w/cpp/algorithm/equal_range)
* equal_range(key_value)
equal_range是C++ STL中的一種二分查找的演算法，試圖在已排序的[first, end)中尋找value，它返回一對迭代器i和j，其中i是在不破壞次序的前提下，value可插入的第一個位置（亦即lower_bound），j則是在不破壞次序的前提下，value可插入的最後一個位置（亦即upper_bound），因此，[i,j)內的每個元素都等同於value，而且[i,j)是[first, end)之中符合此一性質的最大子區間。

可能的實現方法：

template<class ForwardIt, class T>
std::pair<ForwardIt,ForwardIt> 
    equal_range(ForwardIt first, ForwardIt last,
                const T& value)
{
    return std::make_pair(std::lower_bound(first, last, value),
                          std::upper_bound(first, last, value));
}

例子

#include <algorithm>
#include <vector>
#include <iostream>
 
struct S
{
    int number;
    char name;
    // note: name is ignored by this comparison operator
    bool operator< ( const S& s ) const { return number < s.number; }
};
 
int main()
{
    // note: not ordered, only partitioned w.r.t. S defined below
    const std::vector<S> vec = { {1,'A'}, {2,'B'}, {2,'C'}, {2,'D'}, {4,'G'}, {3,'F'} };
 
    const S value = {2, '?'};
 
    std::cout << "Compare using S::operator<(): ";
    const auto p = std::equal_range(vec.begin(), vec.end(), value);
 
    for ( auto i = p.first; i != p.second; ++i )
        std::cout << i->name << ' ';
 
 
    std::cout << "\n" "Using heterogeneous comparison: ";
    struct Comp
    {
        bool operator() ( const S& s, int i ) const { return s.number < i; }
        bool operator() ( int i, const S& s ) const { return i < s.number; }
    };
 
    const auto p2 = std::equal_range(vec.begin(),vec.end(), 2, Comp{});
 
    for ( auto i = p2.first; i != p2.second; ++i )
        std::cout << i->name << ' ';
}

輸出

Compare using S::operator<(): B C D 
Using heterogeneous comparison: B C D

* lower_bound(key_value) 返回一個iterator，指向键值>=key_value的第一個元素
可能的實現：

template<class ForwardIt, class T>
ForwardIt lower_bound(ForwardIt first, ForwardIt last, const T& value)
{
    ForwardIt it;
    typename std::iterator_traits<ForwardIt>::difference_type count, step;
    count = std::distance(first, last);
 
    while (count > 0) {
        it = first; 
        step = count / 2; 
        std::advance(it, step);
        if (*it < value) {
            first = ++it; 
            count -= step + 1; 
        }
        else
            count = step;
    }
    return first;
}

例子

#include <algorithm>
#include <iostream>
#include <vector>
 
struct PriceInfo { double price; };
 
int main()
{
    const std::vector<int> data = { 1, 2, 4, 5, 5, 6 };
    for (int i = 0; i < 8; ++i) {
        // Search for first element x such that i ≤ x
        auto lower = std::lower_bound(data.begin(), data.end(), i);
 
        std::cout << i << " ≤ ";
        lower != data.end()
            ? std::cout << *lower << " at index " << std::distance(data.begin(), lower)
            : std::cout << "[not found]";
        std::cout << '\n';
    }
 
    std::vector<PriceInfo> prices = { {100.0}, {101.5}, {102.5}, {102.5}, {107.3} };
    for(double to_find: {102.5, 110.2}) {
      auto prc_info = std::lower_bound(prices.begin(), prices.end(), to_find,
          [](const PriceInfo& info, double value){
              return info.price < value;
          });
 
      prc_info != prices.end()
          ? std::cout << prc_info->price << " at index " << prc_info - prices.begin()
          : std::cout << to_find << " not found";
      std::cout << '\n';
    }
}

輸出

0 ≤ 1 at index 0
1 ≤ 1 at index 0
2 ≤ 2 at index 1
3 ≤ 4 at index 2
4 ≤ 4 at index 2
5 ≤ 5 at index 3
6 ≤ 6 at index 5
7 ≤ [not found]
102.5 at index 2
110.2 not found

* upper_bound(key_value) 返回一個iterator，指向键值>key_value的第一個元素

7. [How can I use std::maps with user-defined types as key](https://thispointer.com/stdmap-tutorial-part-3-using-user-defined-class-objects-as-key-in-stdmap/)

* Overloading operator < for sorting of keys

#include <iostream>
#include <map>

using namespace std;

class Person
{
    int id;
public :
    Person(int i) : id(i) {}
    bool operator<(const Person& rhs) const
    {
        return this->id < rhs.id;
    }
};

int main()
{
    map<Person, int> m;
    m.insert(make_pair<Person, int>(Person(1), 1));
    m.insert(make_pair<Person, int>(Person(2), 2));
    
    for (auto i : m) cout << i.second << endl;
    return 0;
}

* Using Comparator for sorting of keys

#include <iostream>
#include <map>

using namespace std;

class Person
{
    int id;
public :
    Person(int i) : id(i) {}
    int getId() const { return id; }
};

struct PersonCompare
{
    bool operator()(const Person& lhs, const Person& rhs) const  
    {
        return lhs.getId() < rhs.getId();
    }
};

int main()
{
    map<Person, int, PersonCompare> m;
    m.insert(make_pair<Person, int>(Person(1), 1));
    m.insert(make_pair<Person, int>(Person(2), 2));
    
    for (auto i : m) cout << i.second << endl;
    return 0;
}

### Using a `map`
使用`map`的經典範例為字詞計數程式：

#include <iostream>
#include <map>

int main()
{
    std::map<std::string, size_t> word_count;
    std::string word;
    while (std::cin >> word) 
        ++word_count[word];
    for (const auto &w : word_count)
        std::cout << w.first << " occurs " << w.second
                  << ((w.second > 1) ? " times" : " time") << std::endl;
    return 0;
}

### Using a `set`
上述程式的邏輯延伸是忽略像是the、and、or之類的字。我們會用一個`set`來存放我們要忽略的字詞，並僅計數沒有在此`set`的那些字詞。

#include <iostream>
#include <map>
#include <set>

int main()
{
    std::map<std::string, size_t> word_count;
    std::set<std::string> exclude = {"The", "But", "And", "Or", "An", "A",
                                     "the", "but", "and", "or", "an", "a"};
    std::string word;
    while (std::cin >> word) 
        if (exclude.find(word) == exclude.end())
        ++word_count[word];
    for (const auto &w : word_count)
        std::cout << w.first << " occurs " << w.second
                  << ((w.second > 1) ? " times" : " time") << std::endl;
    return 0;
}

### [set用法詳解](https://blog.csdn.net/yas12345678/article/details/52601454)
`set`與`map`、`multiset`、`multimap`一樣是使用紅黑樹做為內部結構，在set中每個元素的值都唯一，而且系统能根據元素的值自動進行排序。

關於`set`的相關知識：
1. 為何map和set的插入刪除效率比用其他序列容器高？
因為對於關聯容器來說，不需要做記憶體拷貝和記憶體移動。set容器內所有元素都是以節點的方式來存取，因此插入的時候只需要稍做變換，把節點的指標指向新的節點就可以了。刪除的時候類似，稍做變換後把指向刪除節點的指標指向其他節點也OK了。這裡的一切操作就是指標換來換去，和記憶體移動沒有關係。
2. 為何每次insert之後，以前保存的iterator不會失效？
iterator這裡就相當於指向節點的指標，記憶體沒有變，指向記憶體的指標怎麼會失效呢(當然被刪除的那個元素本身已經失效了)。相對於vector來說，每一次刪除和插入，指標都有可能失效，調用push_back在尾部插入也是如此。因為為了保證內部數據的連續存放，iterator指向的那塊記憶體在刪除和插入過程中可能已經被其他記憶體覆蓋或者記憶體已經被釋放了。另外push_back的時候，容器內部空間可能不夠，需要一塊新的更大的記憶體，只有把以前的記憶體釋放，申請新的更大的記憶體，複製已有的數據元素到新的記憶體，最後把需要插入的元素放到最後，那麼以前的記憶體指標自然就不可用了。特別在和find等算法在一起使用的時候，牢記這個原則：不要使用過期的iterator。
3. 當數據元素增多時，set的插入和搜索速度變化如何？
在set中查找是使用二分查找，也就是說，如果有16個元素，最多需要比較4次就能找到結果，有32個元素，最多比較5次。那麼有10000個呢？最多比較的次數為log10000，最多為14次，如果是20000個元素呢？最多不過15次。看見了吧，當數據量增大一倍的時候，搜索次數只不過多了1次，多了1/14的搜索時間而已。你明白這個道理後，就可以安心往裡面放入元素了。

set中常用的方法
* begin() 　　 返回set容器的第一個元素
* end() 　　　　返回set容器的最後一個元素的下一個
* clear() 　　 刪除set容器中的所有的元素
* empty() 　　 判斷set容器是否為空
* size() 　　　返回當前set容器中的元素個數
* count()
用來查找set中某個鍵值出現的次數。這個函數在set並不是很實用，因為一個鍵值在set只可能出現0或1次，這樣就變成了判斷某一鍵值是否在set出現過了。
* erase(iterator) 刪除iterator指向的值
* erase(first, second) 刪除iterator first和second之間的值
* erase(key_value) 刪除鍵值key_value的值
* find(key_value) 返回給定值的iterator，如果沒找到則返回end()。
* insert(key_value)
將key_value插入到set中，返回值是pair<set<int>::iterator, bool>，
bool標誌著插 入是否成功，而iterator代表插入的位置，若key_value已經在set中，則
iterator指向key_value在set中的位置。
* inset(first, second)
將iterator first到second之間的元素插入到set中，返回值是void。

#### [如果要使用自定義的類別作為set的key，需要](https://www.techiedelight.com/use-object-key-stdset-cpp/)
* 重載`operator<`

#include <iostream>
#include <set>

template<typename T1, typename T2>
class Pair
{
public:
	T1 x;
	T2 y;
	// constructor
	Pair(T1 x, T2 y) {
		this->x = x;
		this->y = y;
	}
	// overload < operator to use a Pair object as a key in a std::set
	bool operator<(Pair const &p) const
	{
		return x < p.x || (x == p.x && y < p.y);
	}
};

int main()
{
	std::set<Pair<std::string,int>> set =
	{
		{"A", 4}, {"B", 4}, {"C", 1}, {"A", 0}, {"B", 3}
	};
	for (auto const &p: set) {
		std::cout << "{" << p.x << ":" << p.y << "}\n";
	}
	return 0;
}

* use a comparator function

#include <iostream>
#include <set>

template<typename T1, typename T2>
class Pair
{
public:
	T1 x;
	T2 y;
	Pair(T1 x, T2 y) {
		this->x = x;
		this->y = y;
	}
};

struct comp
{
	template<typename T>
	bool operator()(const T& lhs, const T& rhs) const
	{
		if (lhs.x == rhs.x)
			return lhs.y < rhs.y;

		return lhs.x < rhs.x;
	}
};

int main()
{
	std::set<Pair<std::string,int>, comp> set =
	{
		{"A", 4}, {"B", 4}, {"C", 1}, {"A", 0}, {"B", 3}
	};
	for (auto const &p: set) {
		std::cout << "{" << p.x << ":" << p.y << "}\n";
	}
	return 0;
}

* [use `std::less`](https://www.fluentcpp.com/2019/10/29/stdless-and-its-modern-evolution/)

#include <iostream>
#include <set>

template<typename T1, typename T2>
class Pair
{
public:
	T1 x;
	T2 y;
	// constructor
	Pair(T1 x, T2 y) {
		this->x = x;
		this->y = y;
	}
};

namespace std
{
	template<typename T1, typename T2>
	struct less<Pair<T1, T2>>
	{
		bool operator()(const Pair<T1, T2> &l,
						const Pair<T1, T2> &r) const
		{
			return l.x < r.x || (l.x == r.x && l.y < r.y);
		}
	};
}

int main()
{
	std::set<Pair<std::string,int>> set =
	{
		{"A", 4}, {"B", 4}, {"C", 1}, {"A", 0}, {"B", 3}
	};
	for (auto const &p: set) {
		std::cout << "{" << p.x << ":" << p.y << "}\n";
	}
	return 0;
}

[C++ unordered_map using a custom class type as the key](https://stackoverflow.com/questions/17016175/c-unordered-map-using-a-custom-class-type-as-the-key)

* 需要定義自己的hash function
* 需要定義`==`運算子

#include <string>
#include <unordered_map>

class Key
{
public :
    Key(std::string f, std::string s, int t) :
        first(f), second(s), third(t) {}

    bool operator==(const Key &other) const
    { 
        return (first == other.first
            && second == other.second
            && third == other.third);
    }
    std::string first;
    std::string second;
    int         third;
};

namespace std {
    template <>
    struct hash<Key>
    {
        std::size_t operator()(const Key& k) const
        {
            using std::size_t;
            using std::hash;
            using std::string;

            // Compute individual hash values for first,
            // second and third and combine them using XOR
            // and bit shifting:

            return ((hash<string>()(k.first)
               ^ (hash<string>()(k.second) << 1)) >> 1)
               ^ (hash<int>()(k.third) << 1);
        }
    };
}
int main()
{
    std::unordered_map<Key, std::string> m6 = {
        { Key("John", "Doe", 12), "example"},
        { Key("Mary", "Sue", 21), "another"}
    };
    return 0;
}

## Ch 12 Dynamic Memory

* 靜態記憶體 (static memory)
用於區域的`static`物件、類別的`static`資料成員、以及在任何函式外定義的變數。
* 堆疊記憶體 (stack memory)
用於在函式內的非`static`物件。

這兩者都是由編譯器自動創建和摧毀的。
* 堆積(heap)或free store
用於動態配置的物件，也就是程式在執行時期配置的物件。程式負責控制動態物件的生命週期。

### Dynamic Memory and Smart Pointers

[`shared_ptr`類別]()

智慧指標是模板(定義在`memory`標頭檔內)，所以在創建一個智慧指標時，我們必須提供額外的資訊：就是該指標可以指的型別。

std::shared_ptr<std::string> p1;     // 可以指向string的shared_ptr
std::shared_ptr<std::list<int>> p2;  // 可以指向由int組成的一個list的shared_ptr

一個預設初始化的智慧指標持有一個`null`指標。

[`make_shared`函式]()

配置並使用動態記憶體最安全的方式是呼叫名為`make_shared`的程式庫函式。這個函式會在動態記憶體中配置並初始化一個物件，然後回傳一個`shared_ptr`指向該物件。

std::shared_ptr<int> p3 = std::make_shared<int>(42);
std::shared_ptr<std::string> p4 = std::make_shared<std::string>(10, '9');
std::shared_ptr<int> p5 = std::make_shared<int>(); // 初始化為0
auto p6 = std::make_shared<std::vector<std::string>>(); 

[拷貝和指定`shared_ptr`]()

當我們拷貝或指定一個`shared_ptr`，每個`shared_ptr`都會追蹤紀錄有多少其他的`shared_ptr`指向相同的物件：

auto p = std::make_shared<int>(42);   // p所指的物件有一個使用者
auto q(p);                            // q和p指向相同的物件
                                      // p所指的物件有兩個使用者

我們可以把一個`shared_ptr`想成它有一個關聯的計數器，每當我們拷貝一個`shared_ptr`，這個計數就會加一，例如用它當作指定運算子的右運算元，或者我們以值將它傳入函式或從函式回傳時。而這個計數器會在我們指定一個新的值給`shared_ptr`和`shared_ptr`本身被摧毀時減一，例如用它當作指定運算子的左運算元和區域性的`shared_ptr`超出範疇的時候。
只要一個`shared_ptr`的計數器降為零，這個`shared_ptr`就會自動釋放它所管理的物件：

auto r = std::make_shared<int>(42);
r = q;    // 增加q所指的物件的使用計數
          // 減少r曾指過的物件的使用計數
          // r曾指過的物件沒有使用者了，那個物件會自動被釋放

[什麼時候會在類別內配置動態記憶體]()

* 其類別不知道需要幾個這種物件
* 其類別不知道所需的物件的確切型別
* 想在不同類別共用資料

例子：容器類別

[定義`StrBlob`類別]()

此類別使用動態記憶體來讓數個物件共用相同的底層資料。

#include <iostream>
#include <string>
#include <vector>
#include <memory>

class StrBlob
{
public:
    typedef std::vector<std::string>::size_type size_type;
    StrBlob();
    StrBlob(std::initializer_list<std::string> il);
    size_type size() const { return data->size(); }
    bool empty() const { return data->empty(); }
    void push_back(const std::string &t) { data->push_back(t); }
    void pop_back();
    std::string &front();
    std::string &back();
private:
    std::shared_ptr<std::vector<std::string>> data;
    void check(size_type i, const std::string &msg) const;
};

StrBlob::StrBlob() : data(std::make_shared<std::vector<std::string>>()) {}
StrBlob::StrBlob(std::initializer_list<std::string> il) : 
            data(std::make_shared<std::vector<std::string>>(il)) {}

void StrBlob::check(size_type i, const std::string &msg) const
{
    if (i >= data->size())
        throw std::out_of_range(msg);
}

std::string &StrBlob::front()
{
    check(0, "front on empty StrBlob");
    return data->front();
}

std::string &StrBlob::back()
{
    check(0, "back on empty StrBlob");
    return data->back();
}

void StrBlob::pop_back()
{
    check(0, "pop_back on empty StrBlob");
    data->pop_back();
}

int main(void)
{
    StrBlob sb = {"hello", "world"};
    StrBlob sb1(sb);   // 使用預設拷貝運算子複製智慧指標
    std::cout << sb.front() << std::endl;
    std::cout << sb1.front() << std::endl;
    return 0;
}

[記憶體耗盡]()

一旦程式用盡它可用的動態記憶體，`new`運算就會失敗。預設情況下，如果`new`沒辦法配置所請求的儲存區，它會擲出型別為`bad_alloc`的一個例外。我們可以使用一種不同形式的`new`來避免`new`擲出一個例外：

int *p1 = new int;    // 如果配置失敗，new會擲出std::bad_alloc
int *p2 = new (std::nothrow) int; // 如果配置失敗，new會回傳一個null指標

[dangling pointer]()

當我們`delete`一個指標後，那個指標就會變得無效。雖然那個指標已經無效，但在許多機器上，該指標仍持有被釋放的動態記憶體的位址。如果我們仍想保留該指標，就應該在使用`delete`後指定`nullptr`給那個指標。

但有可能有數個指標指向相同的記憶體。重置我們用來`delete`那個記憶體的指標能讓我們重新使用該指標，但對仍然指向(已被釋放的)記憶體的其他指標(變為dangling pointers)，沒有任何效果。

int *p(new int(42));
auto q = p;
delete p;
p = nullptr;  // q變成dangling pointer

[Using `shared_ptr` with `new`]()

我們可以用`new`出來的指標初始化`shared_ptr`，但必須用顯式轉換。

std::shared_ptr<double> p1; // shared_ptr that can point at a double
std::shared_ptr<int> p2(new int(42)); // p2 points to an int with value 42
std::shared_ptr<int> p1 = new int(1024); // error:從int*轉型到shared_ptr不能是隱式的
std::shared_ptr<int> clone(int p) {
    return new int(p); // error: implicit conversion to shared_ptr<int>
}
std::shared_ptr<int> clone(int p) {
    // ok: explicitly create a shared_ptr<int> from int*
    return std::shared_ptr<int>(new int(p));
}

[不要混用一般指標與智慧指標]()

// ptr is created and initialized when process is called
void process(std::shared_ptr<int> ptr)
{
    // use ptr
} // ptr goes out of scope and is destroyed

std::shared_ptr<int> p(new int(42)); // reference count is 1
process(p); // copying p increments its count; 
            // in process the reference count is 2
int i = *p; // ok: reference count is 1

int *x(new int(1024)); // dangerous: x is a plain pointer, not a smart pointer
process(x); // error: cannot convert int* to shared_ptr<int>
process(std::shared_ptr<int>(x)); // legal, but the memory will be deleted!
int j = *x; // undefined: x is a dangling pointer!

在最後的例子中，我們將暫時的`shared_ptr`傳給`process`函式，當這個呼叫的運算式結束時，這個暫時的物件就會被摧毀了，這會使得`x`指向的參考計數歸零，導致`x`指向的記憶體被釋放，`x`就變成dangling pointer了。

[其他`shared_ptr`的操作]()

* `p.get()`
回傳`p`保存的指標，主要用來對不能使用智慧指標的程式碼傳遞一個一般指標。
注意：
* `delete`從`get`回傳的指標是個錯誤。
* 雖然編譯器不會報錯，但將智慧指標綁定到`get`返回的指標是會引發問題的。

        std::shared_ptr<int> p(new int(42)); // reference count is 1
        int *q = p.get(); // ok: but don't use q in any way 
                          // that might delete its pointer
        { // new block
        // undefined: two independent shared_ptrs point to the same memory
            std::shared_ptr<int>(q);
        } // block ends, q is destroyed, and the memory to which q points is freed
        int foo = *p; // undefined; the memory to which p points was freed

* `p.reset()`
將p重置為空指標

* `p.reset(new int(1024))`
將p指向一個新記憶體

if (!p.unique())   // 確認p有與別的指標共用記憶體
    p.reset(new string(*p)); // we aren't alone; allocate a new copy
*p += newVal; // now that we know we're the only pointer, 
              // okay to change this object

* `p.use_count()`
返回與`p`共享記憶體的智慧指標數量。

[Smart Pointers and Exceptions]()

如果使用智慧指標，當程式因異常而退出的話，智慧指標會確保不再使用的記憶體被釋放。但如果使用`new`的話，在`delete`前發生異常的話，記憶體不會被釋放。

void f()
{
    std::shared_ptr<int> sp(new int(42)); // allocate a new object
    // code that throws an exception that is not caught inside f
} // shared_ptr freed automatically when the function ends
// 比較 ： delete不會被執行
void f()
{
    int *ip = new int(42); // dynamically allocate a new object
    // code that throws an exception that is not caught inside f
    delete ip; // free the memory before exiting
}

[Using Our Own Deletion Code]()

struct destination; // represents what we are connecting to
struct connection; // information needed to use the connection
connection connect(destination*); // open the connection
void disconnect(connection); // close the given connection
void end_connection(connection *p) { disconnect(*p); }
void f(destination &d /* other parameters */)
{
    connection c = connect(&d);
    std::shared_ptr<connection> p(&c, end_connection);
    // use the connection
    // when f exits, even if by an exception, 
    // the connection will be properly closed
}

[智慧指標使用原則]()

* 不要使用一般指標初始化或`reset`多個智慧指標
這樣所有的智慧指標都指向同個記憶體，但各自的參考計數都為一，只要有一個智慧指標參考計數歸零並釋放記憶體，其他智慧指標都會出錯
* 不要`delete`從`get`返回的指標
* 不要用`get`初始化或`reset`一個智慧指標
* 如果你使用`get`返回的指標，記住當最後一個對應的智慧指標摧毀時，你的指標就變無效了
* 如果你使用的智慧指標管理的資源不是`new`分配的記憶體，記得傳遞給它一個刪除器

### `unique_ptr`
一個`unique_ptr`擁有它指向的物件，與`shared_ptr`不同的是，同時間只能有一個`unique_ptr`指向給定的物件。當`unique_ptr`被摧毀時，它指向的物件也會被摧毀。

std::unique_ptr<double> p1; // unique_ptr that can point at a double
std::unique_ptr<int> p2(new int(42)); // p2 points to int with value 42

由於`unique_ptr`擁有它指向的物件，`unique_ptr`不支援拷貝和指定運算：

std::unique_ptr<std::string> p1(new std::string("Stegosaurus"));
std::unique_ptr<std::string> p2(p1); // error: no copy for unique_ptr
std::unique_ptr<std::string> p3;
p3 = p2; // error: no assign for unique_ptr

雖然我們不能拷貝和指定`unique_ptr`，但我們可以透過呼叫`release`或`reset`來將指標的所有權從一個非`const`的`unique_ptr`轉移到另一個`unique_ptr`。

// transfers ownership from p1 (which points to the string Stegosaurus) to p2
std::unique_ptr<std::string> p2(p1.release()); // release makes p1 null
std::unique_ptr<std::string> p3(new std::string("Trex"));
// transfers ownership from p3 to p2
p2.reset(p3.release()); // 釋放原本p2指向的記憶體，並將p3指向的記憶體傳給p2，
                        // 並將p3變為null

注意：呼叫`release`會切斷`unique_ptr`和它原本管理的物件的關係，`release`返回的指標通常用來初始化另一個智慧指標或指定給另一個智慧型指標，如果我們不用智慧指標來保存`release`返回的指標，我們的程式就要負責資源的釋放。

p2.release(); // WRONG: p2 won't free the memory and we've lost the pointer
auto p = p2.release(); // ok, but we must remember to delete(p)

[傳遞`unique_ptr`和回傳`unique_ptr`]()

不能拷貝`unique_ptr`有一個例外：我們可以拷貝或指定一個將要被摧毀的`unique_ptr`，例如從函式回傳一個`unique_ptr`：

std::unique_ptr<int> clone(int p) {
// ok: explicitly create a unique_ptr<int> from int*
    return std::unique_ptr<int>(new int(p));
}

或可以回傳一個區域物件的拷貝：

std::unique_ptr<int> clone(int p) {
    std::unique_ptr<int> ret(new int (p));
    //...
    return ret;
}

[向`unique_ptr`傳遞刪除器]()

// p points to an object of type objT and 
// uses an object of type delT to free that object
// it will call an object named fcn of type delT
std::unique_ptr<objT, delT> p (new objT, fcn);

void f(destination &d /* other needed parameters */)
{
    connection c = connect(&d); // open the connection
    // when p is destroyed, the connection will be closed
    std::unique_ptr<connection, decltype(end_connection)*> p(&c, end_connection);
    // use the connection
    // when f exits, even if by an exception, the connection will be properly closed
}

### `weak_ptr`

### Dynamic Array

[用`new`動態配置陣列]()

int *pia = new int[get_size()];      // pia points to the first of these ints

我們也可以使用 type alias 來表示陣列型別，以配置一個陣列。

typedef int arrT[42];
int *p = new arrT;      // allocates an array of 42 ints, p points to the first one

注意：動態陣列並不是陣列型別，而是對該陣列第一個元素的一個指標，所以不支援`begin`和`end`函式。

[初始化動態陣列]()

預設情況下，用`new`配置的物件，是預設初始化的。如果我們要值初始化一個陣列中的元素，只要在其大小後接上一對空括弧就行了：

int *pia = new int[10];
int *pia2 = new int[10]();
string *psa = new string[10];
string *psa2 = new string[10]();
int *pia3 = new int[10]{0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
string *psa3 = new string[10]{"a", "an", "the", string(3, 'x')}; // 剩餘元素為值初始化的，即為空string。

注意：`int *p = new int[0];`是合法的，但回傳的指標 p 無法被解參考。

[釋放動態陣列]()

delete p;     // p 必須指向動態配置的物件或null
delete [] pa; // pa 必須指向一個動態配置的陣列或null

[The `allocator` Class]()

`new`有一個面向限制了其彈性，就是`new`結合了記憶體配置和在記憶體中建構物件兩個動作。但有時候我們會想將記憶體配置和建構物件兩個動作分開，比如說：

string *const p = new string[n];       // 建構n個空的string
string s;
string *q = p;
while (cin >> s && q != p + n)
    *q++ = s;
const size_t size = q - p;             // 記住我們讀取了多少個string 

這個`new`運算式配置並初始化了n個string，然而，我們可能不需要n個string。因此我們可能會建立出從未被使用的物件。此外，對於我們確實有用到的物件，我們會即刻指定新的值來蓋過之前初始化的string，所用的元素被寫入兩次；第一次是在預設初始化時，第二次是後續對它指定時。

為了解決這個問題，程式庫提供了`allocator`類別 (定義在`memory`標頭檔)，讓我們可以分離配置與建構。它可配置具有型別的但未經建構的原始記憶體。

allocator<string> alloc;           // 能夠配置string的物件
auto const p = alloc.allocate(n);  // 配置n個未建構的string
auto q = p;
alloc.construct(q++);              // *q是空的string
alloc.construct(q++, 10, 'c');     // *q是"cccccccccc"
alloc.construct(q++, "hi");        // *q是"hi"
while (q != p)
    alloc.destroy(--q);            // 呼叫string物件的解構子
alloc.deallocate(p, n);            // 解除存放n個string物件的記憶體配置

注意：我們必須construct物件才能夠使用allocate所回傳的記憶體。以其它方式使用未經建構的記憶體是未定義行為。

做為`allocator`類別的搭配，程式庫也定義了兩個演算法 (定義在`memory`標頭檔) 用來在未初始化的記憶體中建構物件。
* `uninitialized_copy(b, e, b2)`
從迭代器b和e代表的範圍中拷貝元素到未經建構，由迭代器b2代表的原始記憶體。
* `uninitialized_copy_n(b, n, b2)`
從迭代器b開始，拷貝n個元素到未經建構，由迭代器b2代表的原始記憶體。
* `uninitialized_fill(b, e, t)`
在迭代器b與e所表示的原始記憶體範圍中建構物件為t的拷貝。
* `uninitialized_fill_n(b, n, t)`
在迭代器b開始建構n個物件為t的拷貝。

auto p = alloc.allocate(vi.size() * 2);
auto q = uninitialized_copy(vi.begin(), vi.end(), p);
uninitialized_fill_n(q, vi.size(), 42);