3.1 指針的算術(shù)運算

容器
Vector - 連續(xù)的存儲塊
List - 雙向鏈表構(gòu)成的存儲塊

考慮要實現(xiàn)一種通用的查找容器的方法find

3.1.1 Step 1 我們要實現(xiàn)一個vector<int>容器的元素查找

很容易實現(xiàn)，find 函數(shù)中輪詢vector里面所有元素，找到就返回

int* find(const vector<int> &vec, int value)
{
    for( int ix = 0 ; ix < vec.size(); ++ix)
    {
        if (vec[ ix ] == value)
        {
            return &vex[ ix ];
        }
    }

    return std::nullptr;
}

3.1.2 Step 2 實現(xiàn)任意類型的vector元素的查找

這個時候我們引入了模板函數(shù)

template<typename elemType>
elemType* find(const vector<elemType> &vec, 
                const elemType& value)
{
    for( int ix = 0 ; ix < vec.size() ; ++ix)
    {
        if ( vec[ix] == value)
        {
            return &vec[ix];
        }
    }

    return std::nullptr
}

你可以用這個函數(shù)查找任何諸如vector<float>之類的容器了

3.1.3 Step 3 我要用同一個函數(shù)來實現(xiàn)數(shù)組的查找，可行么？

這個時候vector要在find函數(shù)里面不可見，所以我們想到了指針

template<typename elemType>
elemType* find(const elemType *array, int size,
                const elemType& value)
{
    if ( ! array || size < 1 )
    {
        return 0;
    }

    for ( int ix = 0 ; ix < size ; ++ix )
    {
        if ( vec[ix] == value )
        {
            return &vec[ix]
        }
    }

    return std::nullptr;
}

如果是數(shù)組，我們只要傳遞數(shù)組的首地址即可；如果是vector，只要傳遞容器中數(shù)據(jù)的首地址也能做到

3.1.4 Step 4 如果我現(xiàn)在還要是先list的查找呢

那就有點困難了，因為list底層是一個鏈表結(jié)構(gòu)，不是連續(xù)內(nèi)存，find函數(shù)這個時候就失效了。

3.2 了解Iterator

簡單來說Iterator也是一組類，但是卻可以實現(xiàn)和指針相同的語法，也提供內(nèi)置的運算符操作(*, !=, ++ )。
那么我們怎么樣來定義這樣的一個迭代器類型呢？我們可能有vector<xxx>，有l(wèi)ist<xxx>，怎么來進行區(qū)分？
標(biāo)準(zhǔn)庫中是這么來定義的，

std::vector<std::string> svec;
std::vector<std::string>::iterator iter = svec.begin();

這里的iter指向vector<string>容器的第一個元素，我們前面說了你可以把它當(dāng)成指針來用，比如說取第一個string的內(nèi)容：*iter；指向下一個元素；iter++
這樣，看來我們就能解決前一節(jié)中的最后一個問題了

template<typename IteratorType, typename elemType >
IteratorType find(IteratorType first, IteratorType last, 
                const elemtType &value)
{
    for (; first != last; ++first)
    {
        if(*first == value)
        {
            return first;
        }
    }
    return last;
}

這個時候，如果你要查找的是一個數(shù)組你可以這么寫

    const inst asize = 8;
    int ia[ asize ] = { 1, 1, 2, 3, 5, 8, 13, 21};

    int* pia = find( ia, ia+asize, 1024);

vector可以這樣

    vector<int> ivec;
    vector<int>::iterator it(ia, ia + asize); 
    it = find(ivec.begin, ivec.end(), 1024);

list可以這樣

    list<int> ilist;
    list<int>::iterator iter(ia, ia + asize);
    iter = find(ilist.begin(), ilist.end(), 1024);

看樣子大功告成了。

常用的泛型算法

• 搜索算法： find(), count(), etc;
• 排序及次序整理算法：merge(), sort(), reverse(), etc;
• 賦值、刪除、替換算法：copy(), remove(), swap(), etc；
• 關(guān)系算法：equal(), include();
• 生成（generation）與質(zhì)變（mutation）算法： fill(), for_each(), generate(), transform();
• 數(shù)值算法：accumulate(), partial_sum();
• 集合算法：set_union(), set_difference()

3.3 順序型容器

3.5 設(shè)計一個泛型算法（Generic Algorithm）

3.5.1 從問題開始

Step1， 我需要設(shè)計一個算法，輸入是一個vector<int>，輸出是一個新的vector，包含了原vector中所有小于10的值。
很容易做到，

std::vector<int> less_than(std::vector<int>& vec, int level)
{
    std::vector<int> nvec;
    for（ int ix = 0; ix < vec.size(); ++ix）
    {
        if(vec[ix] < level)
        {
            nvec.push_back(vec[ix]);
        }
    }
    return nvec;
}

Step 2, 現(xiàn)在我們增加一些難度，允許用戶指定不同的操作，比如說過濾大于一個值的元素，或者過濾等于一個值的元素。
一種解決的辦法就是，增加第三個參數(shù)，一個函數(shù)指針，這第三個入?yún)⒕褪怯脩艨梢灾付ǖ牟僮鳎?/p>

vector<int> filter_ver1(const vector<int>& vec, 
                    int filter_value,
                    bool (*pred)( int, int))
{
    vector<int> nvec;

    for( int ix = 0 ; ix < vec.size(); ix++)
    {
        if(pred(vec[ix], filter_value))
        {
            nvec.push_back(vec[ix]);
        }
    }

    return nvec;
}

這個時候用戶可以自己定義小于操作

bool less_than(int a, int b)
{
  return a < b ? true : false;
}

3.5.2 函數(shù)對象

函數(shù)對象實際上是某種類的實例對象，這種對象對函數(shù)調(diào)用運算符()進行了重載操作，而這個時候運算符()重載函數(shù)通常是inline的，從效率上來說要優(yōu)于函數(shù)指針。
標(biāo)準(zhǔn)庫定義了很多函數(shù)對象

我們來看一個使用這些運算符的例子，加入說我要對一個vector里的元素以降序排序，我們可以這么來寫

#include <functional>
sort( vec.begin(), vec.end(), greater<int>());

• 前兩個參數(shù)標(biāo)記范圍；
• 第三個參數(shù)告知操作；

3.5.3 函數(shù)對象適配器（Function Object Adapter）

我們再回到我們要實現(xiàn)這個泛型算法filter，我們可以使用標(biāo)準(zhǔn)庫中使用的這些函數(shù)對象了，
Step 3， 使用標(biāo)準(zhǔn)庫提供的函數(shù)對象less<int>來作為filter的第三個入?yún)ⅲ?br> 除此之外我們還希望用函數(shù)find_if來替代原來用for循環(huán)遍歷整個vector的方式，但是我們知道find_if的第三個入?yún)ⅲㄓ脕碜鳛椴檎覘l件的）應(yīng)該是一個一元操作函數(shù)對象，只接受一個輸入?yún)?shù)；但我們這里的sort函數(shù)是一個二元操作函數(shù)對象，那我們該怎么實現(xiàn)？

std::vector<int> filter(std::std::vector<int>& vec, int val, less<int>& lt)
{
    std::vector<int> nvec;
    
    std::vector<int>::const_iterator iter = vec.begin();
    while(( iter = 
                find_if(iter, vec.end(), 
                    bind2nd(lt, value)) != vec.end())
    {
        nvec.push_back(*iter);
        iter++;
    }
    return nvec;
}

這個時候就引出了本節(jié)所要介紹的一個新東西了，叫函數(shù)對象適配器，這個適配器會對普通的函數(shù)對象進行修改，來滿足用戶所需。
比如說這個例子里用到的綁定適配器（binder adapter）可以將函數(shù)對象的參數(shù)綁定到一些特定值，這樣我們的二元操作符sort就可以變成我們所需的一元的了。

NOTE: C++11以后引入了std::bind函數(shù)，使得適配器操作起來更加靈活

Step4， 消除filter()與vector的元素類型，讓我們的泛型算法更加通用
使用模板函數(shù)，

template<typename InputIterator, typename OutputIterator
        typename ElemType, typename Comp>
OutputIterator filter(InputIterator first, InputIterator last, 
                OutputIterator at, ElemType& val, Comp pred)
{
    while((first = find_if(first, last, bind2nd(pred,val))) != last)
    {
        *at++ = *first++;
    }
    return at;
}

• 首先，要消除filter的返回值類型vector<int>，如前所述的，我們只能返回迭代器；這里定義了返回值迭代器類型OutputIterator；
• 然后，消除第一個入?yún)⒌念愋蛌ector<int>，也使用迭代器來標(biāo)記過濾的范圍；
• 之后，加一個參數(shù)at，標(biāo)記filter的結(jié)果保存的目的地址；
• 接著是查找對象以及區(qū)別算法的定義。

NOTE: 后面章節(jié)中有另一種解決方法，叫做插入迭代器適配器（insert iterator adapter）

這里還要介紹另外一種迭代器，交租哦negator，它會對函數(shù)對象的true/false值取反。

3.9 如何使用Iterator Inserter

3.9.1 笨一點的調(diào)用泛型算法filter的方法

我們再回到3.5節(jié)中最后實現(xiàn)的filter函數(shù)，用戶使用這個函數(shù)的時候，可以這么來做,

void main()
{
    int ia[5] = {1, 4, 2, 0, 9, 8};
    std::vector<int> ivec( ia, ia+5 );

    std::vector<int> ovec(5);

    filter(ivec.begin(), ivec.end(), ovec.begin(), 3, greater<int>());
}

上述的程序中，由于filter函數(shù)內(nèi)部是直接給目標(biāo)容器的迭代器進行賦值操作，所以調(diào)用的時候，需要滿足如下的這些條件

• 預(yù)先定義目標(biāo)容器必須足夠大，這樣才足以填充filter函數(shù)中的每個過濾出來的結(jié)果；
  也就是說我們可能需要定義一個和源容器一樣大的目的容器，預(yù)留足夠的空間，這個顯然是會帶來內(nèi)存空間的浪費的。

那么我們可不可以定義一個空的容器呢？我們知道，進行賦值操作（assignment）的時候，容器并不會自動擴容，也就是空的容器會一直保持為空，這樣調(diào)用的時候必然會報錯；
那么我們可不可以使用類似push_back這樣的操作來替換賦值操作呢？這樣的話，我們就不需要定義一個固定大小的目標(biāo)容器了，答案是有的，這就是所謂的迭代器插入適配器（insertion adapter）,

3.9.2 借助Iterator Inserter之后的聰明方法

借助back_inserter，

filter(ivec.begin(), ivec.end(), back_inserter(ovec), 3, greater<int>());

3.10 使用iostream iterator

這節(jié)首先我們考慮要實現(xiàn)一個新的問題，

• 從標(biāo)準(zhǔn)輸入讀取字符，保存到一個vector容器中；
• 然后進行排序；
• 然后通過標(biāo)準(zhǔn)輸出到設(shè)備上；

3.10.1 首先還是笨點的辦法

很容易理解，標(biāo)準(zhǔn)輸入都進來，寫入text，然后排序，然后寫出去，

int main()
{
    std::string word;
    std::vector<std::string> text;

    while (std::cin >> word)
    {
        text.push_back(word);
    }

    std::sort(text.begin(), text.end());

    for (int ix = 0; ix < text.size(); ix++)
    {
        std::cout << text[ix] << std::endl;
    }
}

3.10.2 借助標(biāo)準(zhǔn)庫的iostream迭代器的聰明方法

這里用到了iostream迭代器

• 首先我們考慮使用copy算法，源是cin，目的是text；
• copy算法也有三個入?yún)?，前兩個是源的范圍（類似指針的范圍）；最后一個是text，這里我們借助back_inserter來把copy內(nèi)部的賦值操作轉(zhuǎn)換成了push_back操作；
• 然后是輸出，定義一個ostream_iterator，用于作為copy的目的；

int main()
{
    std::istream_iterator<std::string> is(std::cin);
    std::istream_iterator<std::string> eof;

    std::vector<std::string> text;
    std::copy(is, eof, std::back_inserter(text));

    std::sort(text.begin(), text.end());

    std::ostream_iterator<std::string> os(std::cout, " ");
    std::copy(text.begin(), text.end(), os);
}

3.10.3 來看看上述第二種方法帶來的妙用吧

假如說這個時候我又有新的需求，不再從標(biāo)準(zhǔn)輸入讀入，從標(biāo)準(zhǔn)輸出寫出；而是要從文件讀入，文件寫出，該怎么做？
很簡單，只要做到如下兩點

• istream_iterator綁定到ifstream對象
• ostream_iterator綁定到ofstream對象
  這就大功告成了

int main()
{
    std::ifstream in_file("in.txt");           // 新建ifstream和ofstream
    std::ofstream out_file("out.txt");

    std::istream_iterator<std::string> is(in_file);   // in_file替換std::cin
    std::istream_iterator<std::string> eof;

    std::vector<std::string> text;
    std::copy(is, eof, std::back_inserter(text));

    std::sort(text.begin(), text.end());

    std::ostream_iterator<std::string> os(out_file, " ");  // out_file替換std::cout
    std::copy(text.begin(), text.end(), os);
}

這就是泛型帶來的優(yōu)勢，一套代碼，滿足你各種需求。