之前已經(jīng)完成了STL中容器的梳理凡纳，那么從語言的層面來看：

• 容器是class template
• 算法是function template
• 迭代器是class template
• 適配器是class template
• 分配器是class template

一般STL中的算法都是如下的兩種形式（Algorithm代表一種泛指窃植，可以替代其他的函數(shù)名稱）

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

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

對于Algorithms來說，是不能直接看到Container的荐糜，對他的情況可謂一無所知巷怜。那么，他所需要的一切信息就必須要通過他們之間橋梁Iterators來獲得了暴氏。然而Iterators（是由Container所提供的）必須能夠回答Algorithms所提出的一些問題（比如類型等）延塑，才能夠搭配對應的Algorithm的所有操作。

所謂算法的所提出的問題答渔，其hi就是類型的確認過程关带，通過確認，來獲取他所需要的沼撕，例如標記了五種iterator categories的類型

//5種iterator categories
struct input_iterator_tag{};
//

struct output_iterator_tag{};
//

struct forward_iterator_tag : public input_iterator_tag{};
//forward_list是單向鏈表

struct bidirectional_iterator_tag : public forward_iterator_tag{};
//list宋雏，rb_tree為底層的set，multiset端朵、map好芭、multimap是雙向鏈表，iterator不能隨機跳躍

struct random_access_iterator_tag : public bidirectional_iterator_tag{};
//對于連續(xù)空間的array冲呢、vector舍败、deque
（雖然實際上不連續(xù)，但是iterator構(gòu)造了連續(xù)的假象）
敬拓，這些迭代器可以隨便跳躍的類型

iterator categories的UML

這樣設計的優(yōu)勢是在于邻薯，通過對象的方式就可以調(diào)用不同函數(shù)的重載，例如：

void _display_category(random_access_iterator_tag){
    cout << "random_access_iterator" << endl;
}

void _display_category(bidirectional_iterator_tag){
    cout << "bidirectional_iterator" << endl;
}

void _display_category(forward_iterator_tag){
    cout << "forward_iterator" << endl;
}

void _display_category(input_iterator_tag){
    cout << "input_iterator" << endl;
}

void _display_category(output_iterator_tag){
    cout << "output_iterator" << endl;
}

template<typename I>
void display_category(I iter){
    typename iterator_traits<I>::iterator_category cagy;
    _display_category(cagy);
    //根據(jù)對象類型乘凸，可以調(diào)用不同的函數(shù)重載
}

//.........
{
    //通過iterator的臨時對象來作為參數(shù)調(diào)用
    display_category(set<int>::iterator());
}

• istream_iterator 的iterator_category
  gnu2.9里面的istream_iterator

template <class T,
                 class Distance = ptrdiff_t>
class istream_iterator{
public:
      typedef input_iterator_tag iterator_category;
//      ............
};

gnu 3.3里面的istream_iterator

template<class _Tp,
         class _CharT = char,
         class _Traits = char_traits<_CharT>,
         class _Dist = ptrdiff_t>
class istream_iterator{
public:
    typedef input_iterator_tag iterator_category;
}

Gnu4.9里面的istream_iterator

template<typename _Category,
         typename _Tp,
         typename _Distance = ptrdiff_t,
         typename _Pointer = _Tp*,
         typename _Reference = _Tp&>
struct iterator{
      typedef _Category iterator_category;
      typedef _Tp       value_type;
      typedef _Distance difference_type;
      typedef _Pointer  pointer;
      typedef _Reference reference;
}

template<typename _Tp,
      typename _CharT = char,
      typename _Traits = char_traits<_CharT>,
      typename _Dist = ptrdiff_t>
class istream_iterator: public iterator<input_iterator_tag, _Tp, _Dist, const _*Tp, const _Tp&>
{...........}

• ostream_iterator 的iterator_category
  gnu2.9里面的ostream_iterator

template <class T,
                 class Distance = ptrdiff_t>
class ostream_iterator{
public:
      typedef output_iterator_tag iterator_category;
//      ............
};

gnu 3.3里面的ostream_iterator

template<class _Tp,
         class _CharT = char,
         class _Traits = char_traits<_CharT>,
         class _Dist = ptrdiff_t>
class ostream_iterator{
public:
    typedef output_iterator_tag iterator_category;
}

Gnu4.9里面的ostream_iterator

template<typename _Category,
         typename _Tp,
         typename _Distance = ptrdiff_t,
         typename _Pointer = _Tp*,
         typename _Reference = _Tp&>
struct iterator{
      typedef _Category iterator_category;
      typedef _Tp       value_type;
      typedef _Distance difference_type;
      typedef _Pointer  pointer;
      typedef _Reference reference;
}

template<typename _Tp,
      typename _CharT = char,
      typename _Traits = char_traits<_CharT>,
      typename _Dist = ptrdiff_t>
class ostream_iterator: public iterator<output_iterator_tag, void, void, void, void>
{...........}

• iterator_category對算法的影響

template<class InputIterator>
inline iterator_trais<InputIterator>::diference_type __distance(InputIterator first, InputIterator last, input_iterator_tag){
//input_iterator_tag是forward_iteator_tag和bidirectional_iterator_tag的父類厕诡，
//所以遇到了會直接進入input_iterator_tag的重載部分
      iterator_trais<InputIterator>::difference_type n = 0;
      //由于不是RandomAccessIterator，所以迭代器不能直接相減营勤，需要遍歷了
      while(first != last){
          ++first;
          ++n;
      }
      return n;
}

template<class RandomAccessIterator>
inline iterator_trais<RandomAccessIterator>::difference_type __distance(RandomAccessIterator first, RandomAccessIterator last, random_access_iterator_tag){
      return last - first;
      //只有連續(xù)空間才能迭代器想減
}

template<class InputIterator>
inline iterator_trais<InputIterator>::difference_type distance(InputIterator first, InputIterator last){
      //根據(jù)trais獲取iterator的category tag灵嫌，如果編譯不通過說明迭代器出問題
      typedef typename iterator_trais<InputIterator>::iterator_category category;
      return __distance(first, last, category());
      //根據(jù)第三參數(shù)調(diào)用了不同的函數(shù)重載
}

以copy()函數(shù)為例壹罚，說明STL算法設計的思路，針對不同的類型的Iterator進行了詳細的區(qū)分和判斷寿羞，選擇最高效的方法來賦值需要復制的內(nèi)容

copy函數(shù)對于不同的類型的判斷流程

destroy函數(shù)對于不同類型的判斷流程

算法的效率與他是否能夠判斷出iterator的分類很重要猖凛。
算法源碼中，對于iterator_category都是采用“暗示”的方式绪穆，因為算法主要為模版函數(shù)辨泳，而模版函數(shù)可以傳入任何的類型，所以只是定義模版的時候定義為需要的迭代器名字玖院，但并不是真正的區(qū)分類型菠红。如果傳入的類型不正確，編譯會不通過难菌，采用這樣的方式來區(qū)分iterator的類型

部分算法源碼剖析

• c語言的算法函數(shù)樣例

qsort(c.data(), ASIZE, sizeof(long), compareLongs);

long* pItem = (long*) bsearsh(&target, (c.data()), ASIZE, sizeof(long), compareLongs);

• C++標準庫的函數(shù)樣例

template<typename Iterator>
std::Algorithm (Iterator itr1, Iterator itr2)
{
    ..........
}

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

• 算法accumulate

template <class InputIterator, class T>
T accumulate(InputIterator first, InputIterator last, T init)
{
      for( ; first != last; ++first)
      {
              //將元素累加至初值init上
              init = init + *first;
      }

      return init;
}

template <class InputIterator, class T, class BinaryOperation>
T accumulate(InputIterator first, InputIterator last, T init, BinaryOperation binary_op)
{
        for( ; first != last; ++first)
        {
              //對元素“累加計算（具體算法可以通過傳入一個函數(shù)指針或者函數(shù)對象來指定）”至初值init上
              init = binary_op(init, *first);
        }
        return init;
}

用例

int myfunc(int x, int y){return x + 2 * y;}//一般的函數(shù)

struct myclass{
      int operator()(int x, int y){return x + 3 * y; }
} myobj;  //函數(shù)對象（仿函數(shù)）

void test
{
    int init = 100;
    int nums[] = {10, 20, 30};
    
    accmulate(nums, num + 3, init);  //160

    accumulate(nums, num + 3, init, minus<int>);    //使用了stl的相減的函數(shù)  40

    accumulate(nums, num + 3, init, myfunc);  //220

    accumulate(nums, num + 3, init, myobj);  //280
}

• 算法for_each

template <class InputIterator, class Function>
Function for_each(InputIterator first, InputIterator last, Function f)
{
      for( ; first != last; ++first)
      {
            f(*first);
      }
      return f;
}

用例

void mufunc(int i){
      cout << ' ' << i;
}

typedef struct myclass{
        void operator() (int i){
              cout << ' ' << i;
        }
}  myobj;

void test()
{
      vector<int> myvec;
      myvec.push_back(10);
      ...........
      for_each(myvec.begin(), myvec.end(), myfunc);//循環(huán)調(diào)用自定義函數(shù)
      for_each(myvec.begin(), myvec.end(), myobj);//循環(huán)調(diào)用仿函數(shù)（函數(shù)對象）
}

• 算法replace试溯，replace_if ， replace_copy

template<class ForwardIterator, class T>
void replace(ForwardIterator first, ForwardIterator last, const T& old_value, const T& new_value)
{
      //范圍內(nèi)所有等同于old_value者都以new_value取代
      for( ; first != last; ++first){
            if(*first == old_value)
                *first = new_value;
      }
}

template<class ForwardIterator, class Predicate, class T>
void replace_if(ForwardIterator first, ForwardIterator last, Predicate pred, const T& new_value)
{
        //范圍內(nèi)所有滿足pred()為true的元素都以new_value取代
        for( ; first != last; ++ first)
            if(pred(*first))
                  *first = new_value;
}

template<class InputIterator, class OutputIterator, class T>
OutputIterator replace_copy(InputIteator first, InputIterator last, OutputIterator result, const T& new_value, const T& old_value)
{
      //范圍內(nèi)所有等同于old_value者扔傅，都以new_value防止新的區(qū)間
      //不符合者原值放入新區(qū)間
      for( ; first != last; ++first, ++ result)
            *result = *first == old_value? new_value: *first;

        return result;
}

• 算法count, count_if

template<class InputIterator, class T>
typename iterator_traits<InputIterator>::difference_type count(InputIterator first, InputIterator last, const T& value){
        //以下定義一個初值為0的計數(shù)器n
        typename iterator_traits<InputIterator>::difference_type n = 0;
      for( ; first != last; ++first)
             if(*first == value)
                    ++n;
      return n;
}

template<class InputIterator, class Predicate>
typename iterator_traits<InputIterator>::difference_type count_if(InputIterator first, InputIterator last, Predicate pred){
      //以下定義一個初值為0的計數(shù)器n
      typename iterator_traits<InputIterator>::difference_type n = 0;
      for( ; first != last; ++first)
            if(pred(*first)
                ++n;
      return n;
}

容器不帶成員數(shù)count()：array耍共、vector烫饼、list猎塞、forward_list、deque
容器帶有*成員函數(shù)count()：set杠纵、multiset荠耽、map、multimap比藻、unordered_set铝量、unordered_multiset、unordered_map银亲、unordered_multimap

容器自帶count的應該使用自己所帶有的count效率較高慢叨，而不在容器內(nèi)的count函數(shù)實際是泛化版本，相對效率較低

因為hashtable 和rb_tree是具有自己嚴謹?shù)慕Y(jié)構(gòu)务蝠，所以有自己的count成員函數(shù)

• 算法find拍谐、find_if

template <class InputIterator, class T>
InputIterator find (InputIterator first, InputIterator last, const T& value)
{
        while(first != last && *first != value)
              ++first;
        return first;
}

template<class InputIterator, class Predicate>
InputIterator find_if(InputIterator first, InputIterator last, Predicate pred)
{
      while(first != last && !pred(*first))
              ++first;
      return firstl
}

容器不帶成員數(shù)find()：array、vector馏段、list轩拨、forward_list、deque
容器帶有*成員函數(shù)count()：set院喜、multiset亡蓉、map、multimap喷舀、unordered_set砍濒、unordered_multiset淋肾、unordered_map、unordered_multimap

容器自帶find的應該使用自己所帶有的find效率較高爸邢，而不在容器內(nèi)的count函數(shù)實際是泛化版本巫员，相對效率較低

因為hashtable 和rb_tree是具有自己嚴謹?shù)慕Y(jié)構(gòu)，所以有自己的find成員函數(shù)

• 算法sort

容器不帶成員函數(shù)sort()：array甲棍、vector简识、deque、set感猛、multiset七扰、map、multimap陪白、unordered_set颈走、unordered_multiset、unordered_map咱士、unordered_multimap

關(guān)聯(lián)式容器本身就已經(jīng)完成了排序的任務立由，所以他沒有sort的成員函數(shù)

容器帶有成員函數(shù)sort
list、forward_list

泛化的sort需要傳入的是RandomAccessIterator才能夠排序序厉，對于list和forward_list的迭代器并不是锐膜，如果他們使用泛化的sort會無法通過編譯

仿函數(shù)functors

//算術(shù)類（Arithmetic）
template<class T>
struct plus:public binary_function<T, T>
{
      T operator()(const T& x, const T& y) const { return x + y; }
};

template<class T>
struct minus: public binary_function<T, T, T>
{
      T operator() (const T& x, const T& y)const
      {
              return x - y;
      }
};

//邏輯運算類（Logical）
template<class T>
struct logical_and : public binary_function<T, T, bool>{
      bool operator() (const T& x, const T& y) const { return x && y; }
};

//相對關(guān)系類（比大小 Relational）
template<class T>
struct equal_to : public binary_function<T, T, bool>{
      bool operator()(const T& x, const T& y) const { return x == y; }
};

template<class T>
struct less: public binary_function<T, T, bool>{
      bool operator() (const T& x, const T& y) const { return x < y; }
}

//GNU 獨有非標準
template<class T>
struct identity: public unary_function<T, T>{
    const T& operator() (const T& x) const {return x;}
};

template<class Pair>
struct select1st: public unary_function<Pair, typename Pair::first_type>{
      const typename Pair::first_type& operator() (const Pair& x) const{
            return x.first;
      }
}

template<class Pair>
struct select2nd: public unary_function<Pair, typename Pair::second_type>{
      const typename Pair::second_type& operator() (const Pair& x) const {
          return x.second;
    }
}

template <class T1, class T2>
struct pair{
      typedef T1 first_type;
      typedef T2 second_type;

      T1 first;
      T2 second;
      pair() : first(T1()), second(T2()){}
      pair(const T1& a, const T2& b):first(a),
 second(b){}    
};

目的是為了將這些操作的方法傳給算法來使用，所以必須是定義函數(shù)或者是定義仿函數(shù)的方式來實現(xiàn)

每個標準庫所提供的仿函數(shù)都有繼承關(guān)系弛房，“binary_function<T, T ,T>”和“unary_function<T, T, T>”如果不繼承道盏，那么標準庫對于functors的要求就么有達到

template<class Arg, class Result>
struct unary_function{
      typedef Arg argument_type;
      typedef Result result_type;
};

template<class Arg1, class Arg2, class Result>
struct binary_function{
      typedef Arg1 first_argument_type;
      typedef Arg2 second_argument_type;
      typedef Result result_type;
}

以上兩個類，理論大小為0文捶，實際應該為1荷逞，但是當他作為父類的時候，他所占的空間的大小為0

stl規(guī)定粹排，每個Adaptable Function都應該挑選上面的兩個類進行繼承种远，如果不繼承，將不具備adaptable的條件顽耳，方便Adapter獲取到其中的typedef的一些類型名稱坠敷，以便獲取到相關(guān)的模版類型。

仿函數(shù)斧抱，實際就是class常拓、struct重載()操作符，實際對象就可以像函數(shù)一樣使用

存在多種Adapter

• 容器適配器 stack辉浦、queue

template<class T, class Sequence = deque<T> >
class stack{
//.......
public:
      typedef typename Squence::value_type value_type;
      typedef typename Squence::size_type size_type;
      typedef typename Squence::reference reference;
      typedef typename Squence::const_reference const_reference;
protected:
      Sequence c;  //底層容器
public:
      bool empty() const {return c.empty();}
      size_type size() const {return c.size();}
      reference top() {return c.back();}
      const_reference top() const {return c.back();}
      void push (const value_type& x) { c.push_back(x);}
      void pop() {c.pop_back();}
}

template <class T, class Sequence = deque<T> >
class queue{
//.............
public:
      typedef typename Squence::value_type value_type;
      typedef typename Squence::size_type size_type;
      typedef typename Squence::reference reference;
      typedef typename Squence::const_reference const_reference;
protected:
      Sequence c;  //底層容器
public:
      bool empty() const {return c.empty();}
      size_type size() const {return c.size();}
      reference front() {return c.front();}
      const_reference front() const {return c.front();}
      reference back() {return c.back();}
      const_reference back() const {return c.back();}
      void push (const value_type& x) { c.push_back(x);}
      void pop() {c.pop_front();}
}

• 函數(shù)適配器（Function Adapter）binder2nd

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

//輔助函數(shù)弄抬，讓使用者方便使用binder2nd<Op>
//編譯器自動推到Op的type
template<class Operation, class T>
inline binder2nd<Opertion> bind2nd(const Operation& op, const T& x){
        typedef typename Operation::second_argument_type arg2_type;//封裝模版?zhèn)魅氲念愋?        return binder2nd<Operation>(op, arg2_type(x));//通過return-by-value的形式，返回了binder2nd值
}

//將夠格Adaptable Binary Function 轉(zhuǎn)換為Unary Function 
template<class Operation>
class binder2nd: public unary_function<typename Operation::first_argument, typename Operation::result_type{
protected:
      Operator op;
      typename Operator::second argument_type value;
public:
 //constructor
      binder2nd(const Operation& x, const typename Operation::second_argument_type& y):op(x), value(y){}  //將算式和第二參數(shù)記錄在成員中
      typename Operation::result_type operator()(const typename Operation::first_argument_type& x) const{
            return op(x, value);//實際調(diào)用算式并取value為第二參數(shù)
      }
};

//count_if的代碼
template <class InputIterator, class Predicate>
typename iterator_traits<InputIterator>::difference_type count_if(InputIterator first, InputIterator last, Predicate pred){
      //以下定義一個取初值為0的計數(shù)器
      typename iterator_traits<InputIterator>::differece_type n = 0;
      for( ; first != last; ++first)  //遍歷
            if(pred(*first))  //如果元素帶入pred的結(jié)果為true  
            //實際
                ++n;
}

注：模版參數(shù)Operation宪郊，其中定義有類型為
typename Operation::second_argment_type value;
掂恕，對于示例中的操作傳入的是是less<int>的拖陆，其中，如果查看之前的所寫的內(nèi)容懊亡，可以看到less的代碼依啰，less繼承了binary_function，而在binary_function中僅僅定義了幾個typedef而已店枣，正好方便確認模版參數(shù)的類型

//less的代碼
template<class T>
struct less: public binary_function<T, T, bool>{  //繼承了binary_function
      bool operator() (const T& x, const T& y) const { return x < y; }
}

//binary_function和unary_function的代碼
template<class Arg, class Result>
struct unary_function{
      typedef Arg argument_type;
      typedef Result result_type;
};
>
template<class Arg1, class Arg2, class Result>
struct binary_function{
      typedef Arg1 first_argument_type;
      typedef Arg2 second_argument_type;
      typedef Result result_type;
}

隨著發(fā)展速警，現(xiàn)在的stl也發(fā)生了一些變化，接下來我們來看看變化的情況：

| 最新 | 以前 |
| ------------- |: -----:|
| <sstream>, basic_stringbuf| <strstream>, strstreambuf|
| <sstream>, basic_istringstream| <strstream>, istrstream|
|<sstream>, basic_ostringstream | <strstream>, ostrstream|
|<sstream>, basic_stringstream|<strstream>, strstream|
| <unordered_set, unordered_set |<ext/hash_set>, hash_set|
|<unordered_set>, unordered_multiset| <ext/hash_set>, hash_multiset|
|<unordered_map>, unordered_map| <ext/hash_map>, hash_map|
|<unordered_map>, unordered_multimap| <ext/hash_map>, hash_multimap|
|<functional>, bind| <functional>, binder1st|
|<functional>, bind| <functional>, binder2nd|
|<functional>, bind| <functional>, bind1st|
|<functional>, bind| <functional>, bind2nd|
|<memory>, unique_ptr| <memory>, auto_ptr|

• not1

//使用
cout << count_if(vi.begin(), vi.end(), not1(bind2nd(less<int>(), 40); 

template<class Predicate>
inline unary_negate<Predicate>not1(const Predicate& pred){
      return unary_negate<Predicate>(pred);
}

template<class Predicate>
class unary_negate:public unary_function<typename Predicate::argument_type, bool>{
protected:
    Predicate pred;    //內(nèi)部成員
public:
    explicit unary)negate(const Predicate& x): pred(x){}
    bool operator()(const typename Predicate::argument_type& x) const{
        return !pred(x);
    }
}

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

• bind

std::bind可以綁定：
1 functions
2 function objects
3 member functions: 必須是某個object地址
4 data members：必須是某個object的弟子鸯两，返回一個Function object ret闷旧， 調(diào)用ret相當于上述1 2 3 或相當于取出4

#include <iostream>     // std::cout
#include <functional>   // std::bind

// a function: (also works with function object: std::divides<double> my_divide;)
double my_divide (double x, double y) {return x/y;}

struct MyPair {
  double a,b;
  double multiply() {return a*b;}
};

int main () {
  using namespace std::placeholders;    // adds visibility of _1, _2, _3,...

  // binding functions:
  auto fn_five = std::bind (my_divide,10,2);               // returns 10/2
  std::cout << fn_five() << '\n';                          // 5

  auto fn_half = std::bind (my_divide,_1,2);               // returns x/2
  std::cout << fn_half(10) << '\n';                        // 5

  auto fn_invert = std::bind (my_divide,_2,_1);            // returns y/x
  std::cout << fn_invert(10,2) << '\n';                    // 0.2

  auto fn_rounding = std::bind<int> (my_divide,_1,_2);     // returns int(x/y)
  std::cout << fn_rounding(10,3) << '\n';                  // 3

  MyPair ten_two {10,2};

  // binding members:
  auto bound_member_fn = std::bind (&MyPair::multiply,_1); // returns x.multiply()
  std::cout << bound_member_fn(ten_two) << '\n';           // 20

  auto bound_member_data = std::bind (&MyPair::a,ten_two); // returns ten_two.a
  std::cout << bound_member_data() << '\n';                // 10

  return 0;
}

關(guān)于bind的原理較為復雜，在這里就不做詳細的分析了钧唐，但是可以給出兩個參考文章忙灼，來說明bind的實現(xiàn)原理
std::bind技術(shù)內(nèi)幕
std bind 原理簡單圖解

• reverse_iterator

template<class Iterator>
class reverse_iterator{
protected:
    Iterator current;
public:
    typedef typename iterator_traits<Iterator>::iterator_category iterator_category;
    typedef typename iterator_traits<Iterator>::iterator_type iterator_type;
//.........
    typedef Iterator iterator_type;
    typedef reverse_iterator<Iterator> self;
public:
    explicit reverse_iterator(iterator_type x):current(x){}
    reverse_iterator(const self& x):current(x.current){}
    iterator_type base() const{return current;}
    reference operator*() const {Iterator tmp = current; return *--tmp;}
    pointer operator->() const {return &(operator*();}
    self& operator++() {--current; return *this;}
    self& operator--(){ ++current; return *this;}
    self operator+(difference_type n) const {return self(current - n); }
    self operator-(difference_type n) const {return self(current + n); }
}

• 迭代器適配器：inserter

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

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

copy

希望copy的結(jié)果

list<int> foo, bar;
for(int i = 1; i <= 5; i++){
    foo.push_back(i);
    bar.push_back(i * 10);
}
list<int>::iterator it = foo.begin();
advance (it, 3);

copy(bar.begin(), bar.end(), insert(foo, it));

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):container(&x), iter(i){}
      insert_iterator<Container>& operator= (const typename Container::value_type& value){
            iter = container->insert(iter, value);
            ++iter;
            return *this;
      }
};

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

注:在copy中，第三參數(shù)钝侠，傳入了一個inserter函數(shù)的執(zhí)行結(jié)果后该园，*result = *first;的代碼的result實際就是insert_iterator對象，這個對象中重載了=操作符帅韧，在result指向=時里初，就會調(diào)用重載的操作符，以實現(xiàn)弱匪，拷貝的同時還在移動原集合的內(nèi)容

• ostream_iterator

//用例
#include <iostream>     // std::cout
#include <iterator>     // std::ostream_iterator
#include <vector>       // std::vector
#include <algorithm>    // std::copy

int main () {
  std::vector<int> myvector;
  for (int i=1; i<10; ++i) myvector.push_back(i*10);

  std::ostream_iterator<int> out_it (std::cout,", ");
  std::copy ( myvector.begin(), myvector.end(), out_it );
  return 0;
}

//實現(xiàn)代碼
template <class T, class charT=char, class traits=char_traits<charT> >
  class ostream_iterator :
    public iterator<output_iterator_tag, void, void, void, void>
{
  basic_ostream<charT,traits>* out_stream;
  const charT* delim;

public:
  typedef charT char_type;
  typedef traits traits_type;
  typedef basic_ostream<charT,traits> ostream_type;
  ostream_iterator(ostream_type& s) : out_stream(&s), delim(0) {}
  ostream_iterator(ostream_type& s, const charT* delimiter)
    : out_stream(&s), delim(delimiter) { }
  ostream_iterator(const ostream_iterator<T,charT,traits>& x)
    : out_stream(x.out_stream), delim(x.delim) {}
  ~ostream_iterator() {}

  ostream_iterator<T,charT,traits>& operator= (const T& value) {
    *out_stream << value;
    if (delim!=0) *out_stream << delim;
    return *this;
  }

  ostream_iterator<T,charT,traits>& operator*() { return *this; }
  ostream_iterator<T,charT,traits>& operator++() { return *this; }
  ostream_iterator<T,charT,traits>& operator++(int) { return *this; }
};

• istream_iterator

//用例
#include <iostream>     // std::cin, std::cout
#include <iterator>     // std::istream_iterator

int main () {
  double value1, value2;
  std::cout << "Please, insert two values: ";

  std::istream_iterator<double> eos;              // end-of-stream iterator
  std::istream_iterator<double> iit (std::cin);   // stdin iterator

  if (iit!=eos) value1=*iit;

  ++iit;
  if (iit!=eos) value2=*iit;

  std::cout << value1 << "*" << value2 << "=" << (value1*value2) << '\n';

  return 0;
}

//實現(xiàn)代碼
template <class T, class charT=char, class traits=char_traits<charT>, class Distance=ptrdiff_t>
  class istream_iterator :
    public iterator<input_iterator_tag, T, Distance, const T*, const T&>
{
  basic_istream<charT,traits>* in_stream;
  T value;

public:
  typedef charT char_type;
  typedef traits traits_type;
  typedef basic_istream<charT,traits> istream_type;
  istream_iterator() : in_stream(0) {}
  istream_iterator(istream_type& s) : in_stream(&s) { ++*this; }
  istream_iterator(const istream_iterator<T,charT,traits,Distance>& x)
    : in_stream(x.in_stream), value(x.value) {}
  ~istream_iterator() {}

  const T& operator*() const { return value; }
  const T* operator->() const { return &value; }
  istream_iterator<T,charT,traits,Distance>& operator++() {
    if (in_stream && !(*in_stream >> value)) in_stream=0;
    return *this;
  }
  istream_iterator<T,charT,traits,Distance> operator++(int) {
    istream_iterator<T,charT,traits,Distance> tmp = *this;
    ++*this;
    return tmp;
  }
};