STL 源码剖析 -- Iterator 迭代器全揭秘
1、iterator_tag
iterator_tag 标记了 iterator 的类型。
/// Marking input iterators.
struct input_iterator_tag { };
/// Marking output iterators.
struct output_iterator_tag { };
/// Forward iterators support a superset of input iterator operations.
struct forward_iterator_tag : public input_iterator_tag { };
/// Bidirectional iterators support a superset of forward iterator
/// operations.
struct bidirectional_iterator_tag : public forward_iterator_tag { };
/// Random-access iterators support a superset of bidirectional
/// iterator operations.
struct random_access_iterator_tag : public bidirectional_iterator_tag { };
2、iterator
每个 iterator 都必须提供以下 5 中数据类型
- iterator_category
- value_type
- difference_type
- pointer
- reference
template<typename _Category, typename _Tp, typename _Distance = ptrdiff_t,
typename _Pointer = _Tp*, typename _Reference = _Tp&>
struct _GLIBCXX17_DEPRECATED iterator
{
/// One of the @link iterator_tags tag types@endlink.
typedef _Category iterator_category;
/// The type "pointed to" by the iterator.
typedef _Tp value_type;
/// Distance between iterators is represented as this type.
typedef _Distance difference_type;
/// This type represents a pointer-to-value_type.
typedef _Pointer pointer;
/// This type represents a reference-to-value_type.
typedef _Reference reference;
};
3、iterator_traits
iterator_traits 是为了兼容原生指针（原生指针没有定义上述 5 中数据类型）
template<typename _Iterator>
struct __iterator_traits<_Iterator,
__void_t<typename _Iterator::iterator_category,
typename _Iterator::value_type,
typename _Iterator::difference_type,
typename _Iterator::pointer,
typename _Iterator::reference>>
{
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;
};
template<typename _Iterator>
struct iterator_traits
: public __iterator_traits<_Iterator> { };
iterator_traits 使用偏特化的方法，对于原生指针，也定义了 Iterator 的 5 中数据类型。
template<typename _Tp>
struct iterator_traits<_Tp*>
{
typedef random_access_iterator_tag iterator_category;
typedef _Tp value_type;
typedef ptrdiff_t difference_type;
typedef _Tp* pointer;
typedef _Tp& reference;
};
/// Partial specialization for const pointer types.
template<typename _Tp>
struct iterator_traits<const _Tp*>
{
typedef random_access_iterator_tag iterator_category;
typedef _Tp value_type;
typedef ptrdiff_t difference_type;
typedef const _Tp* pointer;
typedef const _Tp& reference;
};
4、std::distance()/std::advance()
4.1、std::distance()
std::distance() 计算 first 到 last 的距离。不同的 iterator_tag 支持的操作不同，计算方法也不同。
template<typename _InputIterator>
_GLIBCXX_NODISCARD
inline _GLIBCXX17_CONSTEXPR
typename iterator_traits<_InputIterator>::difference_type
distance(_InputIterator __first, _InputIterator __last)
{
// concept requirements -- taken care of in __distance
return std::__distance(__first, __last,
std::__iterator_category(__first));
}
input_iterator_tag 每次只能移动一步，循环直到 first == last，返回距离。
template<typename _InputIterator>
inline _GLIBCXX14_CONSTEXPR
typename iterator_traits<_InputIterator>::difference_type
__distance(_InputIterator __first, _InputIterator __last,
input_iterator_tag)
{
// concept requirements
__glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
typename iterator_traits<_InputIterator>::difference_type __n = 0;
while (__first != __last)
{
++__first;
++__n;
}
return __n;
}
如果是 random_access_iterator_tag，直接 last - first 返回结果
template<typename _RandomAccessIterator>
inline _GLIBCXX14_CONSTEXPR
typename iterator_traits<_RandomAccessIterator>::difference_type
__distance(_RandomAccessIterator __first, _RandomAccessIterator __last,
random_access_iterator_tag)
{
// concept requirements
__glibcxx_function_requires(_RandomAccessIteratorConcept<
_RandomAccessIterator>)
return __last - __first;
}
output_iterator_tag 是不支持 std::distance() 计算
template<typename _OutputIterator>
void
__distance(_OutputIterator, _OutputIterator, output_iterator_tag) = delete;
4.2、std::advance()
std::advance() 将 first 移动 n 个位置。
template<typename _InputIterator, typename _Distance>
inline _GLIBCXX17_CONSTEXPR void
advance(_InputIterator& __i, _Distance __n)
{
// concept requirements -- taken care of in __advance
typename iterator_traits<_InputIterator>::difference_type __d = __n;
std::__advance(__i, __d, std::__iterator_category(__i));
}
如果是 input_iterator_tag，仅仅支持正向移动，每次移动一步。
template<typename _InputIterator, typename _Distance>
inline _GLIBCXX14_CONSTEXPR void
__advance(_InputIterator& __i, _Distance __n, input_iterator_tag)
{
// concept requirements
__glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
__glibcxx_assert(__n >= 0);
while (__n--)
++__i;
}
bidirectional_iterator_tag 支持正向和反向移动。
template<typename _BidirectionalIterator, typename _Distance>
inline _GLIBCXX14_CONSTEXPR void
__advance(_BidirectionalIterator& __i, _Distance __n,
bidirectional_iterator_tag)
{
// concept requirements
__glibcxx_function_requires(_BidirectionalIteratorConcept<
_BidirectionalIterator>)
if (__n > 0)
while (__n--)
++__i;
else
while (__n++)
--__i;
}
random_access_iterator_tag 直接通过 + 计算
template<typename _RandomAccessIterator, typename _Distance>
inline _GLIBCXX14_CONSTEXPR void
__advance(_RandomAccessIterator& __i, _Distance __n,
random_access_iterator_tag)
{
// concept requirements
__glibcxx_function_requires(_RandomAccessIteratorConcept<
_RandomAccessIterator>)
if (__builtin_constant_p(__n) && __n == 1)
++__i;
else if (__builtin_constant_p(__n) && __n == -1)
--__i;
else
__i += __n;
}
5、insert_iterator
insert_iterator 构造于容器之上，将 iterator 的赋值操作，转换为容器的插入操作。
5.1、back_insert_iterator
back_insert_iterator 的赋值操作，转换为容器末尾的插入。
back_insert_iterator 属于 output_iterator_tag
template<typename _Container>
class back_insert_iterator
: public iterator<output_iterator_tag, void, void, void, void>
{
protected:
_Container* container;
/* ... */
};
operator=() 调用容器 push_back() 函数在末尾插入元素。
_GLIBCXX20_CONSTEXPR
back_insert_iterator&
operator=(const typename _Container::value_type& __value)
{
container->push_back(__value);
return *this;
}
_GLIBCXX20_CONSTEXPR
back_insert_iterator&
operator=(typename _Container::value_type&& __value)
{
container->push_back(std::move(__value));
return *this;
}
函数 back_inserter() 接受一个容器参数，构造一个 back_insert_iterator 对象。
template<typename _Container>
_GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
inline back_insert_iterator<_Container>
back_inserter(_Container& __x)
{ return back_insert_iterator<_Container>(__x); }
5.2、front_insert_iterator
front_insert_iterator 和 back_insert_iterator 类似，也是 output_iterator_tag 类型 iterator。
template<typename _Container>
class front_insert_iterator
: public iterator<output_iterator_tag, void, void, void, void>
{
protected:
_Container* container;
/* ... */
};
operator=() 调用容器 push_front() 函数在首部插入元素。
_GLIBCXX20_CONSTEXPR
front_insert_iterator&
operator=(const typename _Container::value_type& __value)
{
container->push_front(__value);
return *this;
}
_GLIBCXX20_CONSTEXPR
front_insert_iterator&
operator=(typename _Container::value_type&& __value)
{
container->push_front(std::move(__value));
return *this;
}
函数 front_inserter() 接受一个容器参数，构造一个 front_insert_iterator对象。
template<typename _Container>
_GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
inline front_insert_iterator<_Container>
front_inserter(_Container& __x)
{ return front_insert_iterator<_Container>(__x); }
5.3、insert_iterator
insert_iterator 也是 output_iterator_tag 类型迭代器。
template<typename _Container>
class insert_iterator
: public iterator<output_iterator_tag, void, void, void, void>
{
protected:
_Container* container;
_Iter iter;
/* ... */
};
operator=() 调用容器 insert() 函数插入元素。
_GLIBCXX20_CONSTEXPR
insert_iterator&
operator=(const typename _Container::value_type& __value)
{
iter = container->insert(iter, __value);
++iter;
return *this;
}
_GLIBCXX20_CONSTEXPR
insert_iterator&
operator=(typename _Container::value_type&& __value)
{
iter = container->insert(iter, std::move(__value));
++iter;
return *this;
}
函数 inserter() 接受一个容器参数，构造一个 insert_iterator对象。
template<typename _Container>
_GLIBCXX_NODISCARD
inline insert_iterator<_Container>
inserter(_Container& __x, typename _Container::iterator __i)
{ return insert_iterator<_Container>(__x, __i); }
6、iterator adaptor
iterator 适配器将某个 iterator 封装成另一个 iterator，改变了原来 iterator 的行为。
6.1、reverse_iterator
bidirectional_iterator_tag 和 random_access_iterator_tag 都有相应的反向迭代器。
template<typename _Iterator>
class reverse_iterator
: public iterator<typename iterator_traits<_Iterator>::iterator_category,
typename iterator_traits<_Iterator>::value_type,
typename iterator_traits<_Iterator>::difference_type,
typename iterator_traits<_Iterator>::pointer,
typename iterator_traits<_Iterator>::reference>
{
protected:
_Iterator current;
/* ... */
};
如果对 reverse_iterator 执行 ++，则原生 iterator 执行 --，反之亦然。+/- n 也是相同的逻辑。
_GLIBCXX17_CONSTEXPR reverse_iterator&
operator++()
{
--current;
return *this;
}
_GLIBCXX17_CONSTEXPR reverse_iterator
operator++(int)
{
reverse_iterator __tmp = *this;
--current;
return __tmp;
}
_GLIBCXX17_CONSTEXPR reverse_iterator&
operator--()
{
++current;
return *this;
}
_GLIBCXX17_CONSTEXPR reverse_iterator
operator--(int)
{
reverse_iterator __tmp = *this;
++current;
return __tmp;
}
比较反直觉的是 reverse_iterator::operator*()/operator->() 两个函数。返回的 --current 对应的值。因为容器 end() 返回的 iterator 并不是容器的最后一个元素，end() - 1 才是最后一个元素。
_GLIBCXX_NODISCARD
_GLIBCXX17_CONSTEXPR reference
operator*() const
{
_Iterator __tmp = current;
return *--__tmp;
}
_GLIBCXX_NODISCARD
_GLIBCXX17_CONSTEXPR pointer
operator->() const
{
// _GLIBCXX_RESOLVE_LIB_DEFECTS
// 1052. operator-> should also support smart pointers
_Iterator __tmp = current;
--__tmp;
return _S_to_pointer(__tmp);
}
make_reverse_iterator() 函数返回 reverse_iterator 对象。
template<typename _Iterator>
[[__nodiscard__]]
inline _GLIBCXX17_CONSTEXPR reverse_iterator<_Iterator>
make_reverse_iterator(_Iterator __i)
{ return reverse_iterator<_Iterator>(__i); }
6.2、__gnu_cxx::__normal_iterator
__normal_iterator 适配器不会改变底层 iterator 的行为，其目的是将原始指针封装成一个普通的 iterator。
template<typename _Iterator, typename _Container>
class __normal_iterator
{
protected:
_Iterator _M_current;
/* ... */
};
6.3、move_iterator
move_iterator 改变 iterator 解引用返回值类型：返回右值引用类型。
template<typename _Iterator>
class move_iterator
{
_Iterator _M_current;
using __traits_type = iterator_traits<_Iterator>;
#if ! (__cplusplus > 201703L && __cpp_lib_concepts)
using __base_ref = typename __traits_type::reference;
#endif
using reference
= __conditional_t<is_reference<__base_ref>::value,
typename remove_reference<__base_ref>::type&&,
__base_ref>;
/* ... */
};
make_move_iterator() 函数返回一个 move_iterator 对象。
template<typename _Iterator>
[[__nodiscard__]]
inline _GLIBCXX17_CONSTEXPR move_iterator<_Iterator>
make_move_iterator(_Iterator __i)
{ return move_iterator<_Iterator>(std::move(__i)); }
欢迎关注公众号“源知源为”，阅读更多技术干货
#STL##C++零基础学习#C/C++基础 文章被收录于专栏
C/C++ 语言基础
海康威视公司福利 1182人发布
