(1)从语言层面上讲：
容器Container是一个class template
算法Algorithm是一个function template
迭代器Iterator是一个class template
仿函数Functor是一个class template
适配器Adapter是一个class template
分配器allocator是一个class template
其之间的关系为：

从上图中可以看出：Algorithm与Container是没有直接关联的，两者之间是通过Iterator关联。Algorithm所需要的所有信息都是通过Iterator取得的，而Iterators（由Containers供应）必须能够回到Algorithm的所有提问，才能够搭配该Algorithm的所有操作。
对于算法的基本形式有两种：
<1>不带仿函数

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

<2>带仿函数

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

(2)迭代器
一共有五种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{};

五种迭代器的继承关系

各种容器的迭代器类型：

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

主函数调用：
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的父类，
//所以遇到了会直接进入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;
      //只有连续空间才能迭代器想减
}

template<class InputIterator>
inline iterator_trais<InputIterator>::difference_type distance(InputIterator first, InputIterator last){
      //根据trais获取iterator的category tag，如果编译不通过说明迭代器出问题
      typedef typename iterator_trais<InputIterator>::iterator_category category;
      return __distance(first, last, category());
      //根据第三参数调用了不同的函数重载
}

通过traits判断迭代器的类型，判断是否为random_access_iterator_tag,若为该类型迭代器，直接相减；否则根据步长计算。
若迭代器类型为forward_iterator_tag，依据其继承关系，将会调用input_iterator_tag。
以copy()函数为例，说明STL算法设计的思路，针对不同的类型的Iterator进行了详细的区分和判断，选择最高效的方法来赋值需要复制的内容。

copy函数对于不同的类型的判断流程如下图：

__copy_d()其中使用了copy赋值。
Type Traits：其中一个问题就是has trivial op=(有不重要的copy赋值)。
在其析构过程中判断析构函数是否重要：

算法源码中，对于iterator_category都是采用“暗示”的方式，因为算法主要为模版函数，而模版函数可以传入任何的类型，所以只是定义模版的时候定义为需要的迭代器名字，但并不是真正的区分类型。如果传入的类型不正确，编译会不通过，采用这样的方式来区分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)
        {
              //对元素“累加计算（具体算法可以通过传入一个函数指针或者函数对象来指定）”至初值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)
{
      //范围内所有等同于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)
{
        //范围内所有满足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)
{
      //范围内所有等同于old_value者，都以new_value防止新的区间
      //不符合者原值放入新区间
      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的计数器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的计数器n
      typename iterator_traits<InputIterator>::difference_type n = 0;
      for( ; first != last; ++first)
            if(pred(*first)
                ++n;
      return n;
}

不带成员数count()的容器：array、vector、list、forward_list、deque。
带有成员函数count()的容器：set、multiset、map、multimap、unordered_set、unordered_multiset、unordered_map、unordered_multimap。
容器自带count的应该使用自己所带有的count效率较高，而不在容器内的count函数实际是泛化版本，相对效率较低。
因为hashtable 和rb_tree是具有自己严谨的结构，所以有自己的count成员函数。
<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
}

不带成员函数find()的容器：array、vector、list、forward_list、deque。
带有成员函数count()的容器：set、multiset、map、multimap、unordered_set、unordered_multiset、unordered_map、unordered_multimap。
容器自带find的应该使用自己所带有的find效率较高，而不在容器内的count函数实际是泛化版本，相对效率较低。
因为hashtable 和rb_tree是具有自己严谨的结构，所以有自己的find成员函数。
<6>sort
不带成员函数sort()的容器：array、vector、deque、set、multiset、map、multimap、unordered_set、unordered_multiset、unordered_map、unordered_multimap。
关联式容器本身就已经完成了排序的任务，所以没有sort的成员函数。
带有成员函数sort的容器list、forward_list。
泛化的sort需要传入的是RandomAccessIterator才能够排序，对于list和forward_list的迭代器并不是，如果他们使用泛化的sort会无法通过编译。
(5)仿函数
仿函数实现了对operator()的重载。
仿函数包括：算术类、逻辑运算类、相对关系类三种形式。
为了能够融入STL，仿函数在定义时应当存在继承关系：
如：

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

仿函数的父类包括binary_function与unary_function，分别表示双参数与单参数。
在使用时，若不进行继承，虽然所创建的仿函数能够满足需求，但是该仿函数是无法融入STL，无法进行更深入的操作。

STL规定每一个Adaptable（可适配的）仿函数必须挑选适当者进行继承。这是因为Function Adapter（仿函数的适配器）将会进行提问。

(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>函数适配器：binder2nd

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

上述功能实现对容器中不大于40的元素的计数。
count_if的定义如下：

template <class InputIterator, class Predicate>
typename iterator_traits<InputIterator>::difference_type count_if(InputIterator first, InputIterator last, Predicate pred){
      //以下定义一个取初值为0的计数器
      typename iterator_traits<InputIterator>::differece_type n = 0;
      for( ; first != last; ++first)  //遍历
            if(pred(*first))  //如果元素带入pred的结果为true  
            //实际
            ++n;
}

辅助函数bind2nd能够使使用者可以方便地使用binder2nd<Op>。
辅助函数not1能够使用者可以方便地使用unary_negate<Pred>。
在C++11中定义了新型适配器bind,std::bind能够实现对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中，第三参数传入了一个inserter函数的执行结果后，*result = *first;的代码的result实际就是insert_iterator对象，这个对象中重载了=操作符。在result指向=时，就会调用重载的操作符，以实现拷贝的同时还在移动原集合的内容。
<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;
}

内部实现：

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

内部实现：

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