Take a simple advance as example, you might design:

template
    
     void advance(II& i, D n){    while( n-- ) ++i;}
    

However it have O(n) complexity, which is not acceptable when you have a random_access_iterator. So you may change your design like this:

template
    
     void advance_II(II& i, D n){    while( n-- ) ++i;}template
     
      void advance_RAI(RAI& i, D n){    i += n;}template
      
       void advance(II& i, D n){    if(is_random_access_iterator(i)) // not yet designed        advance_RAI(i, n);    else        advance_II(i, n);}
      
     
    

However the version of function to use is decided at run-time, so we try to let compiler decided which method to choose at compile-time. So we give iterators tags. There are five tags:

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

Now you can do this:

template
    
     void __advance(II& i, D n, input_iterator_tag){    while( n-- ) ++i;}template
     
      void __advance(RAI& i, D n, random_access_iterator_tag){    i += n;}template
      
       void advance(II& i, D n){    __advance(i, n, iterator_traits
       
        ::iterator_category());}