Iterator
迭代器是STL特有的一个概念,翻译的比较绕口,更加通俗的翻译可以翻译成游标. 它提供一种统一和抽象的方式,使用迭代器可以用于访问和修改STL容器的每一个元素,而无需暴露STL容器的内部实现.
迭代器提供和指针一样的dereference和member access的功能,所有的迭代器都重载了*和->运算符,使他们工作的更像指针. 事实上,一般的STL实现里,vector容器的iterator就是T*.
在这里推荐一篇博客带你深入理解STL之迭代器和Traits技法.
Iterator与重载决议
下面讲一个工程问题,如何利用迭代器特性来帮助重载决议.
//construct 1
iterator insert( const_iterator pos, size_type n, const value_type &value )
//construct 2
template<typename InputIterator>
iterator insert( const_iterator pos, InputIterator first, InputIterator last )
当出现这样两个构造函数时,很明显,可以看到,当出现insert(pos,5,10)这样的函数调用时,InputIterator将会被构造成int,从而调用第二个构造函数,这是错误的.我们应该在构造函数中引入判断是否是InputIterator的代码.
template <typename Iter>
using isInputIterator = typename std::enable_if<
std::is_convertible<typename iterator_traits<Iter>::iterator_category,
input_iterator_tag>::value>;
注意,这里代码里的iterator_traits<Iter>自己实现的话,容易触发编译期错误.接下来看
一个朴素的iterator_traits<Iter>的实现
template <typename Iter>
struct iterator_traits
{
typedef typename Iter::iterator_category iterator_category;
typedef typename Iter::value_type value_type;
typedef typename Iter::difference_type difference_type;
typedef typename Iter::pointer pointer;
typedef typename Iter::reference reference;
};
联想到之前谈到的,insert(pos,5,10)中,InputIter被推断成int,为了避免调用错误的函数,我们引入了Iterator_traits<Iter>来检验InputIter是否是迭代器.错误出现在这里,当我们传入Iterator_traits<int>,妄图获得它是不是一个迭代器的结果时,我们触发了编译期错误,因为在Iterator_traits<int>的内部,我们定义了
typedef typename int::iterator_category iterator_category,
而int并不具备iterator_category成员.我们会获得int is not a class,struct or an union的错误.
Iterator_helper和SFINAE
SFINAE是一个简写的术语,Substitution Failure Is Not An Error.当模版参数在重载决议的实例化时候无效,该模版实例被移除重载决议,而不是抛出错误.
简单的来说
注:这一节主要参考于
C++模板技术之SFINAE与enable_if的使用
struct test
{
typedef int bar;
};
template <typename T>
void foo(typeame T::bar){}
template <typename T>
void foo(T){}
foo<test>(10);
foo<double>(10.0); //will not throw an error
当double被构造的时候,不会因为没有定义double::bar而抛出编译错误.
由此,我们可以写一个helper函数,用于探测T是否含有nested type.
struct false_type{const static bool bool_flag = false;};
struct true_type{const static bool bool_flag = true;};
template <typename U>
struct iterator_help {
typedef void iterator;
};
template <typename T, typename = void>
struct has_typedef_iterator : false_type {}; //fallback
template <typename T>
struct has_typedef_iterator<T, typename iterator_help<typename T::iterator>::iterator > : true_type {};
struct foo {
typedef float iterator;
};
has_typedef_iterator<foo>::bool_flag //true
has_typedef_iterator<int>::bool_flag //false
原理:当编译器在重载决议时, 当T::iterator成员存在时,模版2的匹配程度更高,而当T::iterator不存在时,模版2被编译器排除出重载决议,回到模版1.通过两个不同的继承,带上了不同的bool_flag.
现在通过帮助函数可以探测到T::iterator的存在了,所以回到最开始的问题,如果检测T是否是一个iterator,如果是,则萃取它的iterator_category,如果不是这个模版匹配失败,排除出重载决议.
接着上面的has_typedef_iterator的代码,我们可以利用模版的偏特化(partial specialization)来完善我们的iterator traits.
template <class Iter,bool>
struct iterator_traits_helper {};
template <class Iter>
struct iterator_traits_helper<Iter,true>
{
typedef typename Iter::iterator_category iterator_category;
typedef typename Iter::value_type value_type;
typedef typename Iter::difference_type difference_type;
typedef typename Iter::pointer pointer;
typedef typename Iter::reference reference;
};
template <typename Iter>
struct iterator_traits : public iterator_traits_helper<Iter,has_typedef_iterator<Iter>::bool_flag>{};
我们定义一个默认的空的iterator_traits_helper,再偏特化一个真正的萃取器iterator_traits_helper.当我们调用iterator_traits时,我们利用has_typedef_iterator来检验它是否包含iterator这个nested type,如果是int,iterator_traits将继承一个空的traits table,从而在重载决议条件中的enable_if中失败,被排除出重载决议.
Written with StackEdit.