C++迭代器详解
迭代器
迭代器是STL库的三大组件之一[1]。其作为容器和算法的连接器，将算法对各种容器的遍历操作与具体的容器类型解耦，即迭代器可用于对相应的容器进行元素遍历。这是STL库的核心技术。迭代器是为了提高编程效率而开发的。
迭代器类型
STL库支持的迭代器类型是所有编程语言中最全面的[2]，共有五种：
InputIterator：输入迭代器。支持对容器元素的逐个遍历，以及对元素的读取（input)；
OutputIterator：输出迭代器。支持对容器元素的逐个遍历，以及对元素的写入（output)。
ForwardIterator：前向迭代器。向前逐个遍历元素。可以对元素读取；
BidirectionalIterator：双向迭代器。支持向前向后逐个遍历元素，可以对元素读取。
RandomAccessIterator：随机访问迭代器。支持O(1)时间复杂度对元素的随机位置访问，支持对元素的读取。
迭代器类型成员
一个迭代器的类型成员包含如下：
template<typename _Category, typename _Tp, typename _Distance = ptrdiff_t,
typename _Pointer = _Tp*, typename _Reference = _Tp&>
struct 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;
};所有容器的迭代器实现必须都包含如上的五个类型成员！这些成员会作为各个算法的类型参数或者用于iterator traits。
由于各个不同的容器其内部实现不同，且元素的数据结构也不同，所以stl并没有一个统一的iterator类实现。即各个不同容器在内部实现其自己的迭代器，同时对迭代器的各个类型成员重定义，以符合struct iterator的定义规范。
该类最初本想所有的迭代器实现类均继承之，但是从一开始就没有使用过！仅仅成为了可选的实现。所以在C++17中将该类废弃了。
iterator traits
迭代器类型萃取可以提取迭代器的各个类型。
template<typename _Iterator, typename = __void_t<>>
struct __iterator_traits { };
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> { };迭代器的基本实现
迭代器在c++实际实现为指针。即使用指针访问对应索引的对象。为了更加直观简便的使用迭代器，各个迭代器均对该指针重载了"->"和"*"解引用操作符。而不需要向某些编程语言一样需要执行如下操作：
itr->value();
itr->next();而c++中则：
itr = container.begin();
itr++;
itr--;
*itr;
itr->...以std::list的迭代器实现为例：
template<typename _Tp>
struct _List_iterator
{
typedef _List_iterator<_Tp> _Self;
typedef _List_node<_Tp> _Node;
typedef ptrdiff_t difference_type;
typedef std::bidirectional_iterator_tag iterator_category;
typedef _Tp value_type;
typedef _Tp* pointer;
typedef _Tp& reference;
_List_iterator() _GLIBCXX_NOEXCEPT
: _M_node() { }
explicit
_List_iterator(__detail::_List_node_base* __x) _GLIBCXX_NOEXCEPT
: _M_node(__x) { }
_Self
_M_const_cast() const _GLIBCXX_NOEXCEPT
{ return *this; }
// Must downcast from _List_node_base to _List_node to get to value.
reference
operator*() const _GLIBCXX_NOEXCEPT
{ return *static_cast<_Node*>(_M_node)->_M_valptr(); }
pointer
operator->() const _GLIBCXX_NOEXCEPT
{ return static_cast<_Node*>(_M_node)->_M_valptr(); }
_Self&
operator++() _GLIBCXX_NOEXCEPT
{
_M_node = _M_node->_M_next;
return *this;
}
_Self
operator++(int) _GLIBCXX_NOEXCEPT
{
_Self __tmp = *this;
_M_node = _M_node->_M_next;
return __tmp;
}
_Self&
operator--() _GLIBCXX_NOEXCEPT
{
_M_node = _M_node->_M_prev;
return *this;
}
_Self
operator--(int) _GLIBCXX_NOEXCEPT
{
_Self __tmp = *this;
_M_node = _M_node->_M_prev;
return __tmp;
}
friend bool
operator==(const _Self& __x, const _Self& __y) _GLIBCXX_NOEXCEPT
{ return __x._M_node == __y._M_node; }
friend bool
operator!=(const _Self& __x, const _Self& __y) _GLIBCXX_NOEXCEPT
{ return __x._M_node != __y._M_node; }
// The only member points to the %list element.
__detail::_List_node_base* _M_node;
};具体使用
迭代器的常见使用方式有三种。
常规遍历方式
std::vector<int> vec;
...
for (std::vector<int>::iterator itr = vec.begin(); itr != vec.end(); ++itr)
{
// 需要对itr执行解引用！
...
}这是最为常用的方式！
c++11遍历方式
std::vector<int> vec;
...
for(int item : vec)
{
// item已经执行了解引用
...
}c++11工具函数
c++11增加了两个工具函数begin()/end()，支持对原生数组的迭代器访问，同时也支持对已有容器的访问。
int eles[10] = {...};
for (auto itr = begin(eles); itr != end(eles); ++itr)
{
...
}容器迭代器的获取
各个容器对象提供了一系列的获取迭代器的方法。
begin()/end()：获取的迭代器的类型是T::iterator，可通过该迭起修改对应元素。即可变。
cbegin()/end()：获取的迭代器的类型是T:const_iterator，仅能读取对应元素，不可修改之。即常量访问。
rbegin()/rend()：获取的迭代器的类型是T::reverse_iterator。反向访问元素，即从最后一个元素向第一个元素遍历。可修改对应元素，即可变。
crbegin()/crend()：获取的迭代器的类型是T::const_reverse_iterator。反向访问元素，即从最后一个元素向第一个元素遍历。不可修改对应元素，即常量访问。
从c++11开始，提供了工具函数begin()/end()。
获取容器迭代器是算法的第一步。获取后即完成了于容器的解耦。
算法的使用
标准库对容器操作提供了丰富的算法，提高开发人员的开发效率。这些算法全是模板函数，传入迭代器。迭代器的类型在类型参数中显示标明，但是实际的类型检查在运行期间才能判断出来。
下面是几个标准库中提供的函数原型：
template< class InputIt, class T >
typename iterator_traits<InputIt>::difference_type
count( InputIt first, InputIt last, const T &value );
template< class BidirIt1, class BidirIt2 >
BidirIt2 copy_backward( BidirIt1 first, BidirIt1 last, BidirIt2 d_last );
template< class ForwardIt, class UnaryPredicate >
ForwardIt partition( ForwardIt first, ForwardIt last, UnaryPredicate p );下面是一个具体的三大组件联合使用的快速排序的实例：
#include <algorithm>
#include <iostream>
#include <iterator>
#include <vector>
#include <forward_list>
template <class ForwardIt>
void quicksort(ForwardIt first, ForwardIt last)
{
if(first == last) return;
auto pivot = *std::next(first, std::distance(first,last)/2);
ForwardIt middle1 = std::partition(first, last,
[pivot](const auto& em){ return em < pivot; });
ForwardIt middle2 = std::partition(middle1, last,
[pivot](const auto& em){ return !(pivot < em); });
quicksort(first, middle1);
quicksort(middle2, last);
}
int main()
{
std::vector<int> v = {0,1,2,3,4,5,6,7,8,9};
std::cout << "Original vector:\n ";
for(int elem : v) std::cout << elem << ' ';
auto it = std::partition(v.begin(), v.end(), [](int i){return i % 2 == 0;});
std::cout << "\nPartitioned vector:\n ";
std::copy(std::begin(v), it, std::ostream_iterator<int>(std::cout, " "));
std::cout << " * " " ";
std::copy(it, std::end(v), std::ostream_iterator<int>(std::cout, " "));
std::forward_list<int> fl = {1, 30, -4, 3, 5, -4, 1, 6, -8, 2, -5, 64, 1, 92};
std::cout << "\nUnsorted list:\n ";
for(int n : fl) std::cout << n << ' ';
std::cout << '\n';
quicksort(std::begin(fl), std::end(fl));
std::cout << "Sorted using quicksort:\n ";
for(int fi : fl) std::cout << fi << ' ';
std::cout << '\n';
}容器对迭代器的支持
并不是所有的stl容器均支持迭代器！
支持迭代器的容器
array:
vector:
deque:双向队列
forward_list:单向（前向）列表
list:双向链表
set:
map:
不支持迭代器的容器
不支持迭代器的均是容器适配器，其提供对其他容器的统一接口的访问。
stack：栈
queue：
priority_queue：优先队列
迭代器失效问题
在对容器元素访问的时候，迭代器可能会失效，即迭代器指向的元素已经失效（内存不可访问）。这个是哪怕老手也很容易忽视的问题，并且一旦出问题，非常难以排查定位！
顺序型容器：在修改元素时迭代器不会失效！而删除和插入时可能导致失效。（空间动态扩增，重新申请内存再迁移了，原本内存就释放了）。
解决方法：在vector中insert后会返回一个新的迭代器 it= vec.insert(5)
关联型容器：在修改/删除/插入时均可能导致迭代器失效
