Iterator mode, also known as Cursor mode. GOF defines it as providing a way to access elements of a container object without exposing the internal details of the object.
The core idea of STL is to decouple data containers and algorithms, so that containers and algorithms have good generic ability, while iterator plays a glue role between them, suitable for the close combination of the two.
iterator type in STL
According to the classification in STL, iterator includes:
- Input Iterator: Elements can only be iterated forward one step, and elements referenced by such iterators are not allowed to be modified.
- Output Iterator: This kind of iterator is very similar to Input Iterator and can only iterate elements forward in one step. The difference is that this kind of iterator has only write power to elements.
- Forward Iterator: This type of iterator can read and write in the correct interval, and it has Input
All the features of Iterator, and some of the features of Output Iterator, and the ability to iterate elements forward in one step. - Bidirectional Iterator: This type of iterator is based on Forward Iterator and provides the ability to iterate back elements in one step.
- Random Access Iterator: This kind of iterator can accomplish all the above iterators. Its unique feature is that it can perform arithmetic calculation like a pointer, rather than just one step forward or backward iteration.
The inheritance relationship is as follows
Definition of iterator in STL
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 {};
/*
*As a marker for implementing overload mechanism, it only serves to distinguish different types of iterator s.
*At the same time, it will not occupy any resources.
*/
template <class T, class Distance> struct input_iterator {
typedef input_iterator_tag iterator_category;
typedef T value_type;
typedef Distance difference_type;
typedef T* pointer;
typedef T& reference;
};
struct output_iterator {
typedef output_iterator_tag iterator_category;
typedef void value_type;
typedef void difference_type;
typedef void pointer;
typedef void reference;
};
template <class T, class Distance> struct forward_iterator {
typedef forward_iterator_tag iterator_category;
typedef T value_type;
typedef Distance difference_type;
typedef T* pointer;
typedef T& reference;
};
template <class T, class Distance> struct bidirectional_iterator {
typedef bidirectional_iterator_tag iterator_category;
typedef T value_type;
typedef Distance difference_type;
typedef T* pointer;
typedef T& reference;
};
template <class T, class Distance> struct random_access_iterator {
typedef random_access_iterator_tag iterator_category;
typedef T value_type;
typedef Distance difference_type;
typedef T* pointer;
typedef T& reference;
};
/*
*Iterators define five types, which any iterator that conforms to the STL specification needs to define
*/
template <class Category, class T, class Distance = ptrdiff_t, class Pointer = T*, class Reference = T&>
struct iterator {
typedef Category iterator_category;
typedef T value_type;
typedef Distance difference_type;
typedef Pointer pointer;
typedef Reference reference;
};
Iterator_traits
Any iterator passed in to iterator_traits can easily get iterator types and attributes
Trats programming techniques are widely used in STL implementation. The ability of type authentication that C++ fails to provide is enhanced by using built-in type and template parameter derivation function of compiler.
template <class Iterator>
struct iterator_traits {
typedef typename Iterator::iterator_category iterator_category;
typedef typename Iterator::value_type value_type;
typedef typename Iterator::difference_type difference_type;
typedef typename Iterator::pointer pointer;
typedef typename Iterator::reference reference;
};
/*
*Specification templates with T* or const T* for incoming native pointers
*/
template <class T>
struct iterator_traits<T*> {
typedef random_access_iterator_tag iterator_category;
typedef T value_type;
typedef ptrdiff_t difference_type;
typedef T* pointer;
typedef T& reference;
};
template <class T>
struct iterator_traits<const T*> {
typedef random_access_iterator_tag iterator_category;
typedef T value_type;
typedef ptrdiff_t difference_type;
typedef const T* pointer;
typedef const T& reference;
};
//Lots of overloaded functions implemented by different types of iterators
template <class Iterator>
inline typename iterator_traits<Iterator>::iterator_category
iterator_category(const Iterator&) {
typedef typename iterator_traits<Iterator>::iterator_category category;
return category();
}
template <class Iterator>
inline typename iterator_traits<Iterator>::difference_type*
distance_type(const Iterator&) {
return static_cast<typename iterator_traits<Iterator>::difference_type*>(0);
}
template <class Iterator>
inline typename iterator_traits<Iterator>::value_type*
value_type(const Iterator&) {
return static_cast<typename iterator_traits<Iterator>::value_type*>(0);
}
template <class T, class Distance>
inline input_iterator_tag
iterator_category(const input_iterator<T, Distance>&) {
return input_iterator_tag();
}
inline output_iterator_tag iterator_category(const output_iterator&) {
return output_iterator_tag();
}
template <class T, class Distance>
inline forward_iterator_tag
iterator_category(const forward_iterator<T, Distance>&) {
return forward_iterator_tag();
}
template <class T, class Distance>
inline bidirectional_iterator_tag
iterator_category(const bidirectional_iterator<T, Distance>&) {
return bidirectional_iterator_tag();
}
template <class T, class Distance>
inline random_access_iterator_tag
iterator_category(const random_access_iterator<T, Distance>&) {
return random_access_iterator_tag();
}
template <class T>
inline random_access_iterator_tag iterator_category(const T*) {
return random_access_iterator_tag();
}
template <class T, class Distance>
inline T* value_type(const input_iterator<T, Distance>&) {
return (T*)(0);
}
template <class T, class Distance>
inline T* value_type(const forward_iterator<T, Distance>&) {
return (T*)(0);
}
template <class T, class Distance>
inline T* value_type(const bidirectional_iterator<T, Distance>&) {
return (T*)(0);
}
template <class T, class Distance>
inline T* value_type(const random_access_iterator<T, Distance>&) {
return (T*)(0);
}
template <class T>
inline T* value_type(const T*) { return (T*)(0); }
template <class T, class Distance>
inline Distance* distance_type(const input_iterator<T, Distance>&) {
return (Distance*)(0);
}
template <class T, class Distance>
inline Distance* distance_type(const forward_iterator<T, Distance>&) {
return (Distance*)(0);
}
template <class T, class Distance>
inline Distance*
distance_type(const bidirectional_iterator<T, Distance>&) {
return (Distance*)(0);
}
template <class T, class Distance>
inline Distance*
distance_type(const random_access_iterator<T, Distance>&) {
return (Distance*)(0);
}
template <class T>
inline ptrdiff_t* distance_type(const T*) { return (ptrdiff_t*)(0); }
template <class T, class Distance>
inline Distance* distance_type(const forward_iterator<T, Distance>&) {
return (Distance*)(0);
}
template <class T, class Distance>
inline Distance*
distance_type(const bidirectional_iterator<T, Distance>&) {
return (Distance*)(0);
}
template <class T, class Distance>
inline Distance*
distance_type(const random_access_iterator<T, Distance>&) {
return (Distance*)(0);
}
template <class T>
inline ptrdiff_t* distance_type(const T*) { return (ptrdiff_t*)(0); }
template <class InputIterator, class Distance>
inline void __distance(InputIterator first, InputIterator last, Distance& n,
input_iterator_tag) {
while (first != last) { ++first; ++n; }
}
template <class RandomAccessIterator, class Distance>
inline void __distance(RandomAccessIterator first, RandomAccessIterator last,
Distance& n, random_access_iterator_tag) {
n += last - first;
}
template <class InputIterator, class Distance>
inline void distance(InputIterator first, InputIterator last, Distance& n) {
__distance(first, last, n, iterator_category(first));
}
template <class 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;
}
template <class RandomAccessIterator>
inline iterator_traits<RandomAccessIterator>::difference_type
__distance(RandomAccessIterator first, RandomAccessIterator last,
random_access_iterator_tag) {
return last - first;
}
template <class 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());
}
template <class 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;
}
template <class RandomAccessIterator>
inline iterator_traits<RandomAccessIterator>::difference_type
__distance(RandomAccessIterator first, RandomAccessIterator last,
random_access_iterator_tag) {
return last - first;
}
template <class 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());
}
template <class InputIterator, class Distance>
inline void __advance(InputIterator& i, Distance n, input_iterator_tag) {
while (n--) ++i;
}
template <class BidirectionalIterator, class Distance>
inline void __advance(BidirectionalIterator& i, Distance n,
bidirectional_iterator_tag) {
if (n >= 0)
while (n--) ++i;
else
while (n++) --i;
}
template <class RandomAccessIterator, class Distance>
inline void __advance(RandomAccessIterator& i, Distance n,
random_access_iterator_tag) {
i += n;
}
template <class InputIterator, class Distance>
inline void advance(InputIterator& i, Distance n) {
__advance(i, n, iterator_category(i));
}