迭代器偏移——advance

1. 场景

业务场景使用unordered_map，每次从指定位置n(n不大于unordered_map长度)开始往后遍历。由于unordered_map没有operator+=不能像vector一样通过+=偏移到指定位置。advance可以将迭代器偏移到n个位置。
本文简单探究一下advance不同迭代器实现过程是怎样，由于advance实现依赖迭代器类型，本文还会简单介绍一下iterator_category。

2. advance 用法介绍

http://www.cplusplus.com/reference/iterator/advance/?kw=advance

Advance iterator

template <class InputIterator, class Distance>void advance (InputIterator& it, Distance n);

Advances the iterator it by n element positions.
If it is a random-access iterator, the function uses just once operator+ or operator-. Otherwise, the function uses repeatedly the increase or decrease operator (operator++ or operator–) until n elements have been advanced.

Parameters

it
  Iterator to be advanced.
  InputIterator shall be at least an input iterator.
n
  Number of element positions to advance.
  This shall only be negative for random-access and bidirectional iterators.
  Distance shall be a numerical type able to represent distances between iterators of this type.

Return value

none

3. advance源码分析

3.1 源码查看

  /***  @brief A generalization of pointer arithmetic.*  @param  i  An input iterator.*  @param  n  The "delta" by which to change @p i.*  @return  Nothing.**  This increments @p i by @p n.  For bidirectional and random access*  iterators, @p n may be negative, in which case @p i is decremented.**  For random access iterators, this uses their @c + and @c - operations*  and are constant time.  For other %iterator classes they are linear time.*/template<typename _InputIterator, typename _Distance>inline voidadvance(_InputIterator& __i, _Distance __n){// concept requirements -- taken care of in __advancetypename iterator_traits<_InputIterator>::difference_type __d = __n;std::__advance(__i, __d, std::__iterator_category(__i));}

__advance 有两个特化

  template<typename _InputIterator, typename _Distance>inline void__advance(_InputIterator& __i, _Distance __n, input_iterator_tag){// concept requirements__glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)while (__n--)++__i;}template<typename _BidirectionalIterator, typename _Distance>inline void__advance(_BidirectionalIterator& __i, _Distance __n,bidirectional_iterator_tag){// concept requirements__glibcxx_function_requires(_BidirectionalIteratorConcept<_BidirectionalIterator>)if (__n > 0)while (__n--)++__i;elsewhile (__n++)--__i;}template<typename _RandomAccessIterator, typename _Distance>inline void__advance(_RandomAccessIterator& __i, _Distance __n,random_access_iterator_tag){// concept requirements__glibcxx_function_requires(_RandomAccessIteratorConcept<_RandomAccessIterator>)__i += __n;}

从源码上可知，调用哪一个__advance 取决于 iterator_category 类型。

4. 迭代器类型 iterator_category

一共有5种iterator_category分别为：

1. input_iterator：istream独有的迭代器。
2. output_iterator：ostream独有的迭代器。
3. forward_iterator：继承自input_iterator，单向走的迭代器，只能走一个，不能跳。如forward_list、单向list的hashtable
4. bidirectional_iterator：继承自forward_iterator，双向走的迭代器，只能走一个，不能跳。如list、rb-tree、双向list的hashtable
5. random_access_iterator：继承自bidirectional_iterator，可以跳的迭代器。如array、vector、deque。

使用stl我们一般不需要关系迭代器类型，但在stl源码中有很多地方使用到，这里我们只针在advance中迭代器类型起到的作用。

4.1 迭代器类型定义

  /***  @defgroup iterators Iterators*  These are empty types, used to distinguish different iterators.  The*  distinction is not made by what they contain, but simply by what they*  are.  Different underlying algorithms can then be used based on the*  different operations supported by different iterator types.*///@{ ///  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 { };

4.2 几种容器迭代器类型定义

unorder_map迭代器类型：forward_iterator_tag

map迭代器类型：bidirectional_iterator_tag

vector迭代器类型：bidirectional_iterator_tag

vector 使用的是通用迭代器：random_access_iterator_tag

  /***  This class does nothing but define nested typedefs.  The general*  version simply "forwards" the nested typedefs from the Iterator*  argument.  Specialized versions for pointers and pointers-to-const*  provide tighter, more correct semantics.*/template<typename _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;};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;};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;};

5. 例子

#include <iostream>
#include <unordered_map>
#include <vector>
#include <map>
using namespace std;// g++ advance.cpp  -std=c++0x -o aa
void test_umap()
{unordered_map<int, int> umap;int n1 = 100;for (size_t i = 0; i < n1; i++){umap[i] = i+1000000;}cout <<"test_umap bucket count: "<<umap.bucket_count()<<endl;// 表格重建for (size_t i = n1; i < n1 + 100000; i++){umap[i] = i+1000000;}cout <<"test_umap bucket count: "<<umap.bucket_count()<<endl;auto it = umap.begin();advance(it, 5);for(int i = 0; i < 5; ++i, ++it){cout<<it->first<<", "<<it->second<<endl;}
}void test_map()
{map<int, int> mp;for (size_t i = 0; i < 100; i++){mp[i] = i+1000000;}auto it = mp.begin();advance(it, 5);cout<<"\ntest_map"<<endl;for(int i = 0; i < 5; ++i, ++it){cout<<it->first<<", "<<it->second<<endl;}
}void test_vector()
{vector<int> vt;for (size_t i = 0; i < 100; i++){vt.push_back(i+1000000);}auto it = vt.begin();advance(it, 5);cout<<"\ntest_vector"<<endl;for(int i = 0; i < 5; ++i, ++it){cout<<*it<<endl;}
}int main()
{test_umap();test_map();test_vector();cout <<"\nmain end"<<endl;
}

运行结果

test_umap bucket count: 199
test_umap bucket count: 126271
5, 1000005
6, 1000006
7, 1000007
8, 1000008
9, 1000009test_map
5, 1000005
6, 1000006
7, 1000007
8, 1000008
9, 1000009test_vector
1000005
1000006
1000007
1000008
1000009main end