c++标准程序提供了三个辅助函数,分别是advance(), distance(),iter_swap();通过这三个辅助函数可以增强迭代器的能力,比如 list 也具备了向前跳跃 n个元素的能力了。
Advance()
advance()可以将迭代器的位置为增加,增加的幅度由参数决定,即使迭代器一次性前进或后退多个元素。
函数声明如下:
void advance(InputIterator &pos, Dist n);1.对Bidirectional 迭代器 和Random Access迭代器而言, n可以为负值,表示向后跳跃。
2.Dist 是个template型别,通常应该是个整数型别。
3.advance()并不检查迭代器是否超过序列的end(),所以存在一个潜在的危险:如果对序列尾端执行"operator++"操作将会导致未定义的操作行为。
需要特别说明的是,此函数总能根据迭代器类型(category)采用最佳方案,这个归于迭代器特征(iterator traits)的应用。面对Random Access迭代器,此函数只是简单的执行 pos += n。对于其他的类型的迭代器则执行 ++pos n次,后文再介绍iterator traits。
/**************************************************************** *函数名称:AdvanceInstance *功 能:advance函数使用示范 *作 者:Jin *日 期:2016年5月29日 ****************************************************************/ void AdvanceInstance() { typedef list<int> IntList; IntList Collector; //insert 0 1 2 3 4 5 6 7 8 9 for (int i = 0; i < 10; i++) { Collector.push_back(i); } IntList::iterator pos = Collector.begin(); //output: 0 cout << "fist element: " << *pos << endl; //step three element forward advance(pos, 3); //output: 3 cout << "step three element forward: " << *pos << endl; advance(pos, -2); //output: 1 cout << "step two element backward: " << *pos << endl; }
Distance()
函数distance用来处理两个迭代器之间的距离,函数声明如下:
Dist distance(_InIt _First, _InIt _Last);1.传回两个input迭代器_First,_Last之间的距离。
2.两个迭代器都必须是指向同一个迭代器。
3.如果不是Random Access迭代器,则_Last迭代器必须和_First相同或在_First之后,否则会导致未定义行为。
4.返回值的Dist型别由迭代器决定:iterator_traits<InputIterator>::difference_type
和advance函数类似,此函数能根据迭代器类型(category)采用最佳方案,以达到最佳的性能。对于Random Access迭代器该函数传回_Last -_First的值,对于其他迭代器类型需要不断递增_First
直到抵达_Last 。、
/**************************************************************** *函数名称:DistanceInstance *功 能:distance函数应用举例 *作 者:Jin *日 期:2016年5月29日 ****************************************************************/ void DistanceInstance() { typedef list<int> IntList; IntList Collector; //insert -3 -2 -1 0 1 2 3 4 5 6 7 8 9 for (int i = -3; i <= 9; i++) { Collector.push_back(i); } //search element with value 5 IntList::iterator pos; pos = find(Collector.begin(), Collector.end(), 5); if (pos != Collector.end()) { cout << "difference between beginning and element with value 5: " << distance(Collector.begin(), pos) << endl; } else { cout << "can not find element with value 5" << endl; } }
Iter_swap ()
该函数是用来交换两个迭代器所指的元素值,函数原型如下:
void iter_swap(_FwdIt1 pos1, _FwdIt2 pos2);1.迭代器的型别可以不同,但是其所指的两个值必须是可交换的。
/**************************************************************** *函数名称:IterSwapInstance *功 能:iter_swap()函数应用示例 *作 者:Jin *日 期:2016年5月29日 ****************************************************************/ void IterSwapInstance() { typedef vector<int> IntVector; IntVector coll; for (int i = 1; i <= 9; ++i) { coll.push_back(i); } //output:1 2 3 4 5 6 7 8 9 PrintElements(coll,"list1:"); //output:2 1 3 4 5 6 7 8 9 iter_swap(coll.begin(), ++coll.begin()); PrintElements(coll, "list2:"); //output:9 1 3 4 5 6 7 8 2 iter_swap(coll.begin(), --coll.end()); PrintElements(coll, "list3:"); }
迭代器特性
在distance()函数,advance()函数中均提到,这个两个函数能根据迭代器类型采用最佳的实作方案,以达到最加的性能要求。其实现原理:通过迭代器标志(tags)和特性(traits, 由<iterator>提供),将操作行为重载得以实现。
STL为每一种迭代器提供了一个迭代器标志(iterator tag),用来作为迭代器的标签(label):
namespace std { struct output_iterator_tag { }; struct input_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 { }; }如果编写泛型程序代码,我们还需要了解迭代器所指元素的型别。STL提供了一种特殊的template结构来定义迭代器特性(iterator traits),该结构包含了迭代器相关的所有信息,为“迭代器应具备的所有型别定义(包括迭代器类型,元素型别等)”提供一致接口:
namespace std { template <class T> struct iterator_traits { //定义迭代器所指的元素类型 typedef typename T::value_type value_type; //定义两个迭代器距离 typedef typename T::difference_type difference_type; //定义迭代器类型 typedef typename T::iterator_category iterator_category; //定义指针 typedef typename T::pointer pointer; //定义引用 typedef typename T::reference reference; }; }在这个template中,T代表迭代器型别,有了它,就可以编写任何运用“迭代器类型”等特征的泛型程序代码了,例如:
typedef vector<int> IntVector; IntVector coll; for (int i = 1; i <= 9; ++i) { coll.push_back(i); } iterator_traits<IntVector::iterator>::value_type temp(*coll.begin());
这个“迭代器特性”结构有两个优点:
1、能够确保每一个迭代器所提供必要的型别定义。
2、能够针对特性的迭代器进行特化。
上述第二条,运用于”一般指针作“时有:
namespace std { template <class T> struct iterator_traits<T*> { typedef T value_type; //定义距离 typedef ptrdiff_t difference_type; //定义迭代器类型 typedef random_access_iterator_tag iterator_category; //定义指针 typedef T* pointer; //定义引用 typedef T& reference; }; }
运用迭代器类型(iterator_categories)
如果希望针对不同的迭代器类型采用不同的实作方案(采用函数重载技术),需要按照下面两步来进行:1.将迭代器类型作为template函数的附件参数。
2.针对不同的迭代器类型实作出上述所调用的函数。
现在以迭代器辅助函数distance()为例介绍其调用过程,辅助函数advance()实现方法和distance()一样。
template<class Iterator> typename std::iterator_traits<Iterator>::difference_type distance (Iterator pos1, Iterator pos2) { return distance(pos1, pos2, std::iterator_traits<Iterator>::iterator_category); } //distance for random access iterator template<class Raiterator> typename std::iterator_traits<Raiterator>::difference_type distance(Raiterator pos1, Raiterator pos2, std::random_access_iterator_tag) { return pos2 - pos1; } //distance for input, forward, and bidirectional iterator template<class Initerator> typename std::iterator_traits<Initerator>::difference_type distance(Initerator pos1, Initerator pos2, std::input_iterator_tag) { typename std::iterator_traits<Initerator>::difference_type d; for (d = 0; pos1 != pos2; ++pos1, ++d) { ; } return d; }