1.C++標(biāo)準(zhǔn)庫的算法，是什么東西？
從語言的層面講，STL的算法都長(zhǎng)下面兩個(gè)樣子：

template<typename Iterator>
Algorithm(Iterator itr1, Iterator itr2)
{
  //...
}
template<typename Iterator, typename Cmp>
Algorithm(Iterator itr1, Iterator itr2, Cmp comp)
{ 
  //...
}

上面這兩個(gè)東西是Function template（函數(shù)模板），一般情況算法都有兩個(gè)版本，一個(gè)是兩個(gè)參數(shù)的，一個(gè)是有三個(gè)參數(shù)的版本。前面兩個(gè)參數(shù)是兩個(gè)迭代器，用來讓算法知道需要操作的對(duì)象的范圍，第三個(gè)參數(shù)是為了增加算法的彈性，用戶可以在其中加上自己的準(zhǔn)則，比如：sort函數(shù)，默認(rèn)是從小到大排序，如果加上第三個(gè)參數(shù)（指定從大到?。敲磗ort就會(huì)將數(shù)據(jù)按照指定的方式操作。
算法是看不見容器的，對(duì)其一無所知，一切信息都是從iterator中得到。iterator就是算法和容器之間的橋梁。

1.1各種容器的iterators的iterator_category
STL中有五中iterator_category分別是：

struct input_iterator_tag{};
struct output_iterator_tag{};
struct forward_iterator_tag: public input_iterator_tag{};
struct bidirectional_iterator_tag: public forward_iterator_tag{};
struct random_access_iterator_tag: public bidirectional_iterator_tag{};

Array，Vector，Deque這三種容器支持隨機(jī)訪問，是連續(xù)空間（deque模仿出連續(xù)的假象），使用的是random_access_iterator_tag
list，set，map，multiset，multimap，都是關(guān)聯(lián)性容器，不支持隨機(jī)訪問，使用的是bidirectional_iterator_tag
forward_list，unordered_set，unordered_map，unordered_multiset，unordered_multimap是單向連續(xù)性空間，不支持隨機(jī)訪問，使用的是forward_iterator_tag
istream，ostream分別使用的是input_iterator_tag，output_inerator_tag
注：typeid(iter).name()，可以直接得到對(duì)象的類型名稱

1.2iterator_category對(duì)算法的影響
使用distance函數(shù)求得一個(gè)容器begin和end之間的距離

template<typename InputIterator>
inline iterator_traits<InputIterator>::difference_type
distance(InputIterator first, InputIterator last)
{ 
  typedef typename iterator_traits<InputIterator>::iterator_category category;
  return __distance(first, last, category);
}

當(dāng)傳入vector.begin()和vector.end()函數(shù)，通過萃取機(jī)iterator_traits得到他的iterator_category類型，然后去調(diào)用：

template<typename RandomAccessIterator>
inline iterator_traits<RandomAccessIterator>::difference_type
__distance(RandomAccessIterator first, RandomAccessIterator last, input_iterator_tag)
{ 
  return last - first;
}

因?yàn)檫B續(xù)空間的容器，所以直接首尾相減，就能得到距離，速度非?？?br> 當(dāng)傳入的是list.begin()和list.end()函數(shù)，通過萃取機(jī)iterator_traits得到他的iterator_category類型，然后去調(diào)用：

template<typename InputIterator>
inline iterator_traits<InputIterator>::difference_type
__distance(InputIterator first, InputIterator last, input_iterator_tag)
{ 
  iterator_traits<InputIterator>::difference_type n = 0; 
    while(first != last) 
    { 
      ++first; 
      ++n; 
    } 
  return n;
}

因?yàn)槭欠沁B續(xù)空間容器，所以只能通過迭代的方式，一個(gè)一個(gè)向后偏移得到距離。速度很慢。
由此可以想象，不同的iterator_category對(duì)算法的影響是非常大的。在算法中，會(huì)做非常多的檢查，讓算法使用正確的最快的迭代器分類去操作容器，使用STL其實(shí)是一件非常幸福的事情（想想c程序員。。。）

2.仿函數(shù)
仿函數(shù)其實(shí)是一個(gè)類重載了()運(yùn)算符，在STL中如下：

template <typename T>
struct plus: public binary_function<T,T,T>
{ 
  T operator () (const T& x, const T& y) 
  { 
    return x+y; 
  }
}

在使用STL的算法時(shí)，可以使用函數(shù)來指定第三參數(shù)，也可以用仿函數(shù)指定，例如：

// 使用函數(shù)指定
bool myfunc(int i, int j)
{ 
  return i < j;
}
sort(myvec.begin(), myvec.end(), myfunc);

// 使用仿函數(shù)指定
template <typename T>
struct less: public binary_function<T, T, bool>
{ 
  bool operator () (const T& x, const T& y) const 
  { 
    return x < y; 
  }
}
sort(myvec.begin(), myvec.end(), less<int>());

less<int>()是一個(gè)臨時(shí)對(duì)象，將其傳入sort之后，sort會(huì)自動(dòng)調(diào)用class less里頭的operator ()，就像調(diào)用函數(shù)一樣（仿函數(shù)比函數(shù)更有彈性），因?yàn)榉潞瘮?shù)可以被適配器修改。
如果我們自己寫了一個(gè)仿函數(shù)，需要繼承STL的兩個(gè)類：

// 一個(gè)操作數(shù)繼承
unary_functiontemplate <class Arg, class Result>
struct unary_function
{ 
  typedef Arg argument_type; 
  typedef Result result_type;
};

// 兩個(gè)操作數(shù)繼承
binary_functiontemplate <class Arg1, class Arg2, class Result>
struct binary_function
{ 
  typedef Arg1 fist_argument_type; 
  typedef Arg2 second_argument_type; 
  typedef Result result_type;
};

STL規(guī)定每一個(gè)Adaptable Function都要挑選適當(dāng)?shù)膩砝^承，因?yàn)镕unction Adapter將會(huì)提問問題，例如：

template <class Operation>
class binder2nd: public unary_function<typename Operation::fist_argument_type,typename Operation::result_type>
{
protected: Operation op; 
// 這里就是function adapter在問問題
  typename Operation::second_argument_type value; 

public: 
// ....
};

typename Operation::second_argument_type value;
這一句就是在問仿函數(shù)問題，你的第二個(gè)參數(shù)類型是什么，如果這一句可以編譯通過，那么函數(shù)適配器就得到了仿函數(shù)的第二個(gè)參數(shù)類型，仿函數(shù)就可以被改造。
一個(gè)仿函數(shù)想要能被STL中的適配器改造，就需要繼承適當(dāng)?shù)念惾谌隨TL。

3. Adapter
STL的算法可以讓用戶提供第三參數(shù)，用于給用戶自定義算法處理數(shù)據(jù)的方式，上面講述了可以使用仿函數(shù)作為第三參數(shù)，仿函數(shù)可以被適配器改造，下面就來看一下適配器是如何改造仿函數(shù)的。

3.1 bind2nd
以泛型算法count_if為例：

template <class InputIterator, class Predicate>
typename iterator_traits<InputIterator>::difference_type
count_if(InputIterator first, InputIterator last, Predicate pred)
{
  typename iterator_traits<InputIterator>::difference_type n = 0; 
  for(; first != last; ++first) 
  { 
    if(pred(*first)) 
      { 
        ++n; 
      } 
  } return n;
}

在使用count_if時(shí)如下：

count_if(vi.begin(), vi.end(), bind2nd(less<int>(), 40));

bind2nd就是一個(gè)適配器，用于將仿函數(shù)less的第二參數(shù)綁定為40。
bind2nd源碼如下：

template <class Operation, class T>
inline binder2nd<Operation> bind2nd(const Operation& op, const T& x)
{ 
  typedef typename Operation::second_argument_type arg2_type; 
  return binder2nd<Operation>(op, arg2_type(x));
}

在bind2nd中返回的是一個(gè)binder2nd類型的臨時(shí)對(duì)象，bind2nd函數(shù)其實(shí)是一個(gè)中間層，因?yàn)閎inder2nd類模板不可以自動(dòng)推導(dǎo)類型參數(shù)，只有模板函數(shù)可以，所以使用中間層給類模板指定模板參數(shù)Operation。
class binder2nd源碼如下：

template <class Operation>
class binder2nd
    : public unary_function<typename Operation::first_argument_type,
                            typename Operation::result_type>
{
protected:
    Operation op;
    typename Operation::second_argument_type value;
public:
    binder2nd(const Operation& x, const typename Operation::second_argument_type& y)
        :op(x), value(y)
    { }
    typename Operation::result_type
    operator () (const typename Operation::first_argument_type& x) const
    {
        return op(x, value);
    }
}

當(dāng)在count_if中傳入第三參數(shù)bind2nd(less<int>(), 40)后，先會(huì)調(diào)用bind2nd函數(shù)，函數(shù)確定Operation 和 T的類型函數(shù)變成如下：

inline binder2nd<less<int>> bind2nd(const less<int>& op, const int& x)
{
    typedef less<int>::second_argument_type arg2_type;
    return binder2nd<less<int>>(op, arg2_type(x));
}

然后先讓class binder2nd確定模板參數(shù)

class binder2nd
    : public unary_function<less<int>::fist_argument_type, less<int>::result_type>
{
protected:
    less<int> op;
    less<int>::second_argument_type value;
public:
    binder2nd(const less<int>& x, const less<int>::second_argument_type& y)
        :op(x), value(y)
    { }
    less<int>::result_type operator () (const less<int>::first_argument_type& x) const
    {
        return op(x, value);
    }
}

再在函數(shù)內(nèi)部調(diào)用class binder2nd的構(gòu)造函數(shù)，實(shí)例化一個(gè)binder2nd類型的臨時(shí)對(duì)象，將less<int>()和40分別記錄在op和value里頭。
最后count_if的第三個(gè)參數(shù)就得到一個(gè)binder2nd類型的臨時(shí)對(duì)象，其中包涵了less<int>和40，count_if函數(shù)變成如下：

// 加上vi是容器list的實(shí)例化
ptrdiff_t count_if(list<int>::iterator first, list<int>::iterator last, binder2nd pred)
{
    ptrdiff_t n = 0;
    for(; first != last; ++first)
    {
        if(pred(*first))
        {
            ++n;
        }
    }
    return n;
}

在count_if中調(diào)用pred這個(gè)仿函數(shù)時(shí)（pred就是binder2nd類型的臨時(shí)對(duì)象的別名），會(huì)觸發(fā)class binder2nd中的 operator()，在operator()中

op(x, 40)；

40就被綁定到less<int>()的第二參數(shù)上
這就是仿函數(shù)適配器的工作原理（真的非常的巧妙）。
3.2 inserter
當(dāng)我們想用copy函數(shù)進(jìn)行容器間的拷貝動(dòng)作時(shí)，一種是提前將空間預(yù)留

int myints[] = {10, 20, 30, 40, 50, 60, 70};
vector<int> myvec(7);
copy(myints, myints+7, myvec.begin());

提前預(yù)留空間是因?yàn)閏opy函數(shù)只是單純的移動(dòng)迭代器，向迭代器所指的地方插入數(shù)據(jù)，源碼如下：

template <class InputIterator, class OutputIterator>
OutputIterator copy(InputIterator first, InputIterator last, OutputIterator result)
{
    while(first != last)
    {
        result = *first;
        ++result;
        ++first;
    }
    return result;
}

假設(shè)我們的容器其中本來就有數(shù)據(jù)，沒有預(yù)留空間，那么直接使用copy函數(shù)會(huì)造成一顆定時(shí)炸彈（越界訪問），在這種時(shí)候就需要使用適配器來改造拷貝動(dòng)作。
將copy的第三參數(shù)改寫成迭代適配器：

copy(myints, myints+7, inserter(myvec, iter)); //iter為迭代器，指向容器內(nèi)任意地方

inserter源碼如下：

template <class Container, class iterator>
inline insert_iterator<Container>
insert(Container& x, Iterator i)
{
    typedef typename Container::iterator iter;
    return insert_iterator<Container>(x, iter(i));
}

inserter與bind2nd一樣，也是一個(gè)輔助函數(shù)，幫助class insert_iterator確定模板參數(shù)。
class insert_iterator源碼如下：

template <class Container>
class insert_iterator
{
protected:
    Container* container;
    typename Container::iterator iter;
public:
    typedef output_iterator_tag iterator_category;

    insert_iterator(Container& x, typename Container::iterator i)
        :container(&x), iter(i)
    { }

    insert_iterator<Container>&
    operator = (const typename Container::value_type& value)
    {
        iter = container->insert(iter, value);
        return *this;
    }

    typename Container::iterator& operator ++ ()
    {
        return ++iter;
    }
};

inserter函數(shù)返回一個(gè)insert_iterator類型的臨時(shí)對(duì)象，在這個(gè)臨時(shí)對(duì)象中，容器myvec被記錄到了容器指針container中，myvec的迭代器iter被記錄到了臨時(shí)對(duì)象中的的iter里，當(dāng)copy函數(shù)在執(zhí)行：

result = *first;
++result;

以上兩個(gè)操作的時(shí)候，會(huì)觸發(fā)class insert_iterator里的兩個(gè)操作符重載函數(shù)。
這樣copy函數(shù)從原來一個(gè)傻傻的，只會(huì)一個(gè)一個(gè)拷貝的底層函數(shù)，搖身一變成了一個(gè)智能的插入拷貝函數(shù)（C++技術(shù)相當(dāng)奇妙，這就是操作符重載的好處）。
4. iostream iterator
標(biāo)準(zhǔn)庫定義有提供給輸入輸出使用的 iostream iterator，稱為istream_iterator 和 ostream_iterator，他們分別支持單個(gè)元素的讀取和寫入。
使用這兩個(gè)迭代器需要包涵#include <iterator>
4.1 ostream_iterator
ostream_iterator的使用方法如下：

// 將out_it綁定到cout輸出設(shè)備
ostream_iterator<int> out_it(cout);
// 將out_it綁定到cout輸出設(shè)備，并且在輸出元素后加上一個(gè)字符串
ostream_iterator<int> out_it(cout, ",");

#include <iostream>
#include <vector>
#include <algorithm>
#include <iterator>
using namespace std;

int main()
{
    vector<int> vec;
    for(int i = 0; i < 10; ++i)
    {
        vec.push_back(i);
    }
    ostream_iterator<int> outit(cout, ",");
    copy(vec.begin(), vec.end(), outit);
    return 0;
}

4.2 istream_iterator
使用方法如下：

// 定義一個(gè)指向輸入流結(jié)束位置的迭代器
istream_iterator<double> eos;
// 定義一個(gè)指向標(biāo)準(zhǔn)輸入的迭代器
istream_iterator<double> iit(cin)

當(dāng) iit = eos時(shí)，說明流中的數(shù)據(jù)已經(jīng)全部讀取結(jié)束，操作iit讓其加一，可以讓迭代器指向下一個(gè)流中的數(shù)據(jù)

#include <iostream>
#include <iterator>
using namespace std;

int main()
{
    double value1, value2;
    cout << "please insert two value: ";
    istream_iterator<double> eos;
    istream_iterator<double> iit(cin);

    if(iit != eos)
    {
        value1 = *iit;
    }
    ++iit;
    if(iit != eos)
    {
        value2 = *iit;
    }
    
    cout << value1 << ' ' << value2 << endl;
    return 0;
}

這里值得注意的是，當(dāng)我們把

cout << "please insert two value: ";

寫到

istream_iterator<double> iit(cin);

后面
在執(zhí)行程序的時(shí)候，我們發(fā)現(xiàn)，當(dāng)輸入第一個(gè)數(shù)字之后，cout這句輸出才會(huì)被打印出來，造成這樣的原因是，當(dāng)定義了iit之后，其構(gòu)造函數(shù)已經(jīng)對(duì)iit加一，讀取已經(jīng)開始，所以cout的輸出被放在后面。
注：

ifstream infile("./test/01.cpp");
istream_iterator<string> eos;
istream_iterator<string> iit(infile);

ofstream outfile("./2.cpp");
ostream_iterator<string> out_it(outfile, " ")

這周先參考一篇知乎專欄