首页 > 代码库 > STL 笔记(四) 迭代器

STL 笔记(四) 迭代器

stl 中迭代器可以理解为面向对象版本的广义指针,提供了对容器中的对象的访问方法,可以遍历容器所有元素,也可以访问任意元素。stl 迭代器有以下五种:
  • Input iterators   只读,输入迭代器,支持如:istream
  • Output iterators  只写,输出迭代器,支持如:ostream、inserter
  • Forward iterators 读写,前向迭代器,只能前向移动
  • Bidirectional iterators 读写,双向迭代器,能够双向移动,支持如: list、set、map
  • Random access iterators 读写,随机迭代器,可以随机访问,支持如:vector、deque、string

从功能上看,输入和输出迭代器并列,然后前向迭代器、双向迭代器和随机迭代器之间的关系就类似于类的继承关系。比如,可以将随机访问迭代器作为双向迭代器或前向迭代器来使用。

举例:

stl 中的 find 函数需要输入迭代器:

template <class _InputIter, class _Tp>
inline _InputIter find(_InputIter __first, _InputIter __last,
                       const _Tp& __val,
                       input_iterator_tag)
{
  while (__first != __last && !(*__first == __val))
    ++__first;
  return __first;
}

stl 中 的 generate_n 函数需要输出迭代器:

/* The generate_n algorithm traverses the range [first, first + n)
   assigning to each element the value returned by gen. Note that generate
   modifies  the elements in the specified range.  */
template <class _OutputIter, class _Size, class _Generator>
_OutputIter generate_n(_OutputIter __first, _Size __n, _Generator __gen) {
  __STL_REQUIRES(_OutputIter, _OutputIterator);
  for ( ; __n > 0; --__n, ++__first)
    *__first = __gen();
  return __first;
}

stl 中 replace 函数要求前向迭代器:

template <class _ForwardIter, class _Tp>
void replace(_ForwardIter __first, _ForwardIter __last,
             const _Tp& __old_value, const _Tp& __new_value) {
  __STL_REQUIRES(_ForwardIter, _Mutable_ForwardIterator);
  __STL_REQUIRES_BINARY_OP(_OP_EQUAL, bool,
         typename iterator_traits<_ForwardIter>::value_type, _Tp);
  __STL_CONVERTIBLE(_Tp, typename iterator_traits<_ForwardIter>::value_type);
  for ( ; __first != __last; ++__first)
    if (*__first == __old_value)
      *__first = __new_value;
}

stl 中的 reverse 函数要求双向迭代器:

template <class _BidirectionalIter>
inline void reverse(_BidirectionalIter __first, _BidirectionalIter __last) {
  __STL_REQUIRES(_BidirectionalIter, _Mutable_BidirectionalIterator);
  __reverse(__first, __last, __ITERATOR_CATEGORY(__first));
}

stl 中的 sort 函数要求随机访问迭代器:

template <class _RandomAccessIter>
inline void sort(_RandomAccessIter __first, _RandomAccessIter __last) {
  __STL_REQUIRES(_RandomAccessIter, _Mutable_RandomAccessIterator);
  __STL_REQUIRES(typename iterator_traits<_RandomAccessIter>::value_type,
                 _LessThanComparable);
  if (__first != __last) {
    __introsort_loop(__first, __last,
                     __VALUE_TYPE(__first),
                     __lg(__last - __first) * 2);
    __final_insertion_sort(__first, __last);
  }
}



STL 笔记(四) 迭代器