(1)從語言層面上講：
容器Container是一個class template
算法Algorithm是一個function template
迭代器Iterator是一個class template
仿函數(shù)Functor是一個class template
適配器Adapter是一個class template
分配器allocator是一個class template
其之間的關(guān)系為：

從上圖中可以看出：Algorithm與Container是沒有直接關(guān)聯(lián)的贸弥，兩者之間是通過Iterator關(guān)聯(lián)徙菠。Algorithm所需要的所有信息都是通過Iterator取得的脸秽，而Iterators（由Containers供應(yīng)）必須能夠回到Algorithm的所有提問挖腰，才能夠搭配該Algorithm的所有操作。
對于算法的基本形式有兩種：
<1>不帶仿函數(shù)

template<typename Iterator>
Algorithm(Iterator itr1,Iterator itr2)
{
  朱浴。。。
}

<2>帶仿函數(shù)

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

(2)迭代器
一共有五種iterator category（也就是種類）,其相互之間存在繼承關(guān)系
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{};

五種迭代器的繼承關(guān)系

各種容器的迭代器類型：

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(output_iterator_tag)
{cout<<"output_iterator"<<endl;}

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

template<typename T>
void display_category(T itr)
{
    typename iteratir_traits<T>::iterator_category cagy;
    _display_category(cagy);
}

主函數(shù)調(diào)用：
display_category(array<int,10>::iterator());        //random_access_iterator
display_category(vector<int>::iterator());              //random_access_iterator
display_category(list<int>::iterator());                    //bidirectional_iterator
display_category(forward_list<int>::iterator());            //forward_iterator
display_category(deque<int>::iterator());               //random_access_iterator
display_category(set<int>::iterator());                 //bidirectional_iterator
display_category(map<int>::iterator());                 //bidirectional_iterator
display_category(multiset<int>::iterator());                //bidirectional_iterator
display_category(multimap<int>::iterator());                //bidirectional_iterator
display_category(unordered_set<int>::iterator());           //forward_iterator
display_category(unordered_map<int>::iterator());           //forward_iterator
display_category(unordered_multiset<int>::iterator());      //forward_iterator
display_category(unordered_multimap<int>::iterator());      //forward_iterator

display_category(istream_iterator<int>::iterator());            //input_iterator
display_category(ostream_iterator<int>::iterator(cout,"")); //output_iterator

獲取各種容器的iterators的iterator_category的typeid:

#include<typeinfo>//typeid

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(output_iterator_tag)
{cout<<"output_iterator"<<endl;}

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

template<typename T>
void display_category(T itr)
{
    typename iteratir_traits<T>::iterator_category cagy;
    _display_category(cagy);
    cout<<"typeid(itr).name()="<<typeid(itr).name()<<endl<<endl;
}

(3)terator_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的父類，
//所以遇到了會直接進(jìn)入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ù)重載
}

通過traits判斷迭代器的類型，判斷是否為random_access_iterator_tag,若為該類型迭代器斧蜕，直接相減；否則根據(jù)步長計算涛舍。
若迭代器類型為forward_iterator_tag，依據(jù)其繼承關(guān)系，將會調(diào)用input_iterator_tag佃牛。
以copy()函數(shù)為例廉沮，說明STL算法設(shè)計的思路豫尽，針對不同的類型的Iterator進(jìn)行了詳細(xì)的區(qū)分和判斷优炬，選擇最高效的方法來賦值需要復(fù)制的內(nèi)容库北。

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

__copy_d()其中使用了copy賦值林说。
Type Traits：其中一個問題就是has trivial op=(有不重要的copy賦值)。
在其析構(gòu)過程中判斷析構(gòu)函數(shù)是否重要：

算法源碼中浓瞪，對于iterator_category都是采用“暗示”的方式，因?yàn)樗惴ㄖ饕獮槟０婧瘮?shù)漾唉，而模版函數(shù)可以傳入任何的類型空闲，所以只是定義模版的時候定義為需要的迭代器名字，但并不是真正的區(qū)分類型碴倾。如果傳入的類型不正確逗噩，編譯會不通過悔常，采用這樣的方式來區(qū)分iterator的類型。
(4)部分算法的剖析
<1>累加

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;
}

<2>for_each

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

<3>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;
}

<4>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的應(yīng)該使用自己所帶有的count效率較高坝咐，而不在容器內(nèi)的count函數(shù)實(shí)際是泛化版本，相對效率較低析恢。
因?yàn)閔ashtable 和rb_tree是具有自己嚴(yán)謹(jǐn)?shù)慕Y(jié)構(gòu)墨坚，所以有自己的count成員函數(shù)。
<5>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的應(yīng)該使用自己所帶有的find效率較高吮旅，而不在容器內(nèi)的count函數(shù)實(shí)際是泛化版本溪烤，相對效率較低味咳。
因?yàn)閔ashtable 和rb_tree是具有自己嚴(yán)謹(jǐn)?shù)慕Y(jié)構(gòu)，所以有自己的find成員函數(shù)檬嘀。
<6>sort
不帶成員函數(shù)sort()的容器：array槽驶、vector、deque鸳兽、set掂铐、multiset、map揍异、multimap全陨、unordered_set、unordered_multiset衷掷、unordered_map辱姨、unordered_multimap。
關(guān)聯(lián)式容器本身就已經(jīng)完成了排序的任務(wù)戚嗅，所以沒有sort的成員函數(shù)雨涛。
帶有成員函數(shù)sort的容器list、forward_list懦胞。
泛化的sort需要傳入的是RandomAccessIterator才能夠排序镜悉，對于list和forward_list的迭代器并不是，如果他們使用泛化的sort會無法通過編譯医瘫。
(5)仿函數(shù)
仿函數(shù)實(shí)現(xiàn)了對operator()的重載侣肄。
仿函數(shù)包括：算術(shù)類、邏輯運(yùn)算類醇份、相對關(guān)系類三種形式稼锅。
為了能夠融入STL，仿函數(shù)在定義時應(yīng)當(dāng)存在繼承關(guān)系：
如：

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

仿函數(shù)的父類包括binary_function與unary_function僚纷，分別表示雙參數(shù)與單參數(shù)矩距。
在使用時，若不進(jìn)行繼承怖竭，雖然所創(chuàng)建的仿函數(shù)能夠滿足需求锥债，但是該仿函數(shù)是無法融入STL，無法進(jìn)行更深入的操作痊臭。

STL規(guī)定每一個Adaptable（可適配的）仿函數(shù)必須挑選適當(dāng)者進(jìn)行繼承哮肚。這是因?yàn)镕unction Adapter（仿函數(shù)的適配器）將會進(jìn)行提問。

(6)適配器
存在多種適配器（Adapters）：

<1>容器適配器 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();}
}

<2>函數(shù)適配器：binder2nd

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

上述功能實(shí)現(xiàn)對容器中不大于40的元素的計數(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  
            //實(shí)際
            ++n;
}

輔助函數(shù)bind2nd能夠使使用者可以方便地使用binder2nd<Op>。
輔助函數(shù)not1能夠使用者可以方便地使用unary_negate<Pred>鸦致。
在C++11中定義了新型適配器bind,std::bind能夠?qū)崿F(xiàn)對functions潮剪、function objects涣楷、member functions、data functions的綁定抗碰。
<3>迭代器適配器：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());

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實(shí)際就是insert_iterator對象弧蝇，這個對象中重載了=操作符碳褒。在result指向=時，就會調(diào)用重載的操作符捍壤，以實(shí)現(xiàn)拷貝的同時還在移動原集合的內(nèi)容骤视。
<4>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;
}

內(nèi)部實(shí)現(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; }
};

<5>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;
}

內(nèi)部實(shí)現(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;
  }
};