玩命加载中 . . .

3-迭代器概念与traits编程技法

STL
C++
发布日期:   2022-06-12

3.4 Traits编程技法

比如想要获取迭代器指向的元素的类型作为返回值类型，可以这样写

template<class T>
struct MyIter {
    typedef T value_type;	// 声明内嵌型别
    T* ptr;
    MyIter(T *p = 0) : ptr(p) {}
    T& operator*() const { return *ptr; }
};

template<class I>
typename I::value_type func(I ite) {
    return *ite;
}

int main() {
    MyIter<int> ite1(new int(8));
    cout << func(ite1) << endl;	// 8
    return 0;
}

这样函数func就可以通过I::value_type获取到迭代器指向的元素的类型，并作为返回值的类型

关键字typename的用意在于告知编译器这是一个型别

如果迭代器是一个原生指针，那我们希望获取到指针所指对象的类型，这里就不能直接用了，需要使用traits机制

template<class I>
struct iterator_traits {
    typedef typename I::value_type value_type;
};

// 使用iterator_traits获取迭代器的value_type
template<class I>
typename iterator_traits<I>::value_type func(I ite) {
    iterator_traits<I>::info();
    return *ite;
}

这样中间加了一层iterator_traits，好处就是可以针对原生指针定义偏特化版本

如果迭代器是一个pointer-to-const，应该令其value_type为一个non_const型别

// 原生指针版本
template<class I>
struct iterator_traits<I*> {
    typedef I value_type;
};

// pointer-to-const指针版本
template<class I>
struct iterator_traits<const I*> {
    typedef I value_type;
};

int main() {
    MyIter<int> ite1(new int(8));
    cout << func(ite1) << endl;	// 8

    int a = 10;
    cout << func(&a) << endl;	// 10

    const int b = 10;
    cout << func(&b) << endl;	// 10
    return 0;
}

这样不论面对的迭代器MyIter，或是原生指针int*或const int*，都可以通过traits取出正确的value_type

这样也要求要使用traits的迭代器需要定义内嵌型别value_type，不然就用不了了

常见的迭代器相应型别有五种：

  • value_type：表示迭代器所指对象的型别
  • difference_type：表示两个迭代器之间的距离
  • pointer
  • reference
  • iterator_category：迭代器的种类

3.4.5 迭代器相应型别之五：iterator_category

迭代器的分类

  • Input Iterator：迭代器所指对象，不允许外界改变（read only）
  • Output Iterator：唯写（write only）
  • Forward Iterator：可以向前移动
  • Bidirectional Iterator：可以双向移动
  • Random Access Iterator：可以随机访问

可以这样定义迭代器类型

struct input_iterator_tag {};
struct output_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 {};

template <class T, class Distance> struct input_iterator {
    typedef input_iterator_tag  iterator_category;
    typedef T                   value_type;
    typedef Distance            difference_type;
    typedef T*                  pointer;
    typedef T&                  reference;
};
struct output_iterator {
    typedef output_iterator_tag iterator_category;
    typedef void                value_type;
    typedef void                difference_type;
    typedef void                pointer;
    typedef void                reference;
};
template <class T, class Distance> struct forward_iterator {
    typedef forward_iterator_tag    iterator_category;
    typedef T                       value_type;
    typedef Distance                difference_type;
    typedef T*                      pointer;
    typedef T&                      reference;
};
template <class T, class Distance> struct bidirectional_iterator {
    typedef bidirectional_iterator_tag  iterator_category;
    typedef T                           value_type;
    typedef Distance                    difference_type;
    typedef T*                          pointer;
    typedef T&                          reference;
};
template <class T, class Distance> struct random_access_iterator {
    typedef random_access_iterator_tag  iterator_category;
    typedef T                           value_type;
    typedef Distance                    difference_type;
    typedef T*                          pointer;
    typedef T&                          reference;
};

下面这个可以被自定义的迭代器继承，提供了默认参数

template<class Category, class T, class Distance = ptrdiff_t, class Pointer = T*, class Reference = T&>
struct iterator {
    typedef Category    iterator_category;
    typedef T           value_type;
    typedef Distance    difference_type;
    typedef Pointer     pointer;
    typedef Reference   reference;
};

可以这样写

template<class Item>
struct ListIter : public std::iterator<std::forward_iterator_tag, Item> {...};

同时定义了三个函数用于获取迭代器的这几个属性

// 获取迭代器的类型（category）
template<class Iterator>
inline typename iterator_traits<Iterator>::iterator_category
iterator_category(const Iterator& It){
    typedef typename iterator_traits<Iterator>::iterator_category category;
    return category();
}

// 获取迭代器的difference_type
template<class Iterator>
inline typename iterator_traits<Iterator>::difference_type*
difference_type(const Iterator& It){
    return static_cast<typename iterator_traits<Iterator>::difference_type*>(0);
}

// 获取迭代器的value_type
template<class Iterator>
inline typename iterator_traits<Iterator>::value_type*
value_type(const Iterator& It){
    return static_cast<typename iterator_traits<Iterator>::value_type*>(0);
}

应用

函数advance()让迭代器移动n步，根据不同的迭代器类型，应该调用不同的函数

template<class InputIterator, class Distance>
void advance(InputIterator i, Distance n) {
    if (is_random_access_iterator(i))
        advance_RAI(i, n);
    else if (is_bidirectional_iterator(i))
        advance_BI(i, n);
    else 
        advance_II(i, n);
}

这样到运行时才知道调用哪个版本，会影响程序效率，最好能够在编译期就选择正确的版本。重载函数机制可以达到这个目标

可以让三个advance_xx同名，形成函数重载，然后加上一个标识类型的参数

这个标识迭代器类型的参数可以通过traits来获取，这个相应型别必须是一个class type，不能只是数值号码类的东西，因为编译器需依赖它来进行重载决议

这样advance()就可以写成

template<class InputIterator, class Distance>
inline void advance(InputIterator, Distance n) {
    __advance(i, n, iterator_traits<InputIterator>::iterator_category());
}

这里iterator_traits<InputIterator>::iterator_category()将产生一个临时对象，根据临时对象类型调用不同重载版本的__advance

同时，iterator_traits里面也需要有这个相应型别

template<class I>
struct iterator_traits {
    typedef typename I::iterator_category iterator_category;
};

可以针对原生指针和指向常量的指针制定偏特化版本

template<class T>
struct iterator_traits<T*> {
    // 原生指针可以随机访问
    typedef random_access_iterator_tag iterator_category;
};

template<class T>
struct iterator_traits<const T*> {
    // 也是随机访问
    typedef random_access_iterator_tag iterator_category;
};

注意到迭代器类型之间有继承关系，这样对于接受不同参数但逻辑相同的函数，就不需要在重复写这个重载函数了，比如__advance的input_iterator_tag版本的逻辑和forward_iterator_tag版本的逻辑是完全一样的，因为后者继承于前者，所以如果没有forward_iterator_tag版本的函数，会调用input_iterator_tag版本的，因为子类可以向上转型为父类

#include <iostream>
using namespace std;

struct B {};    // 模拟 InputIterator
struct D1 : public B {};    // 模拟 ForwardIterator
struct D2 : public D1 {};   // 模拟 BidirectionalIterator

template<class I>
void func(I& p, B) {
    cout << "B version" << endl;
}

template<class I>
void func(I& p, D2) {
    cout << "D2 version" << endl;
}

int main(int argc, char const *argv[]) {
    int* p;
    func(p, B());   // B version
    func(p, D1());  // B version，调用了父类版本的函数
    func(p, D2());  // D2 version
    return 0;
}

三个版本的_advance函数

template<class InputIterator, class Distance>
void __advance(InputIterator& it, Distance n, input_iterator_tag) {
    while (n--) {
        ++it;
    }
}

// 双向移动版本
template<class BidirectionIterator, class Distance>
void __advance(BidirectionIterator& it, Distance n, bidirectional_iterator_tag) {
    if (n < 0) {
        while (n++) {
            --it;
        }
    } else {
        while (n--) {
            ++it;
        }
    }
}

// 随机访问版本
template<class RandomIterator, class Distance>
void __advance(RandomIterator& it, Distance n, random_access_iterator_tag) {
    if (n < 0) {
        it -= (-n);
    } else {
        it += n;
    }
}

template <class InputIterator, class Distance> 
void advance(InputIterator& it, Distance n) {
    typedef typename iterator_traits<InputIterator>::iterator_category iterator_category;
    __advance(it, n, iterator_category());
}

distance也是同理

template<class InputIterator>
typename iterator_traits<InputIterator>::difference_type
__distance(InputIterator first, InputIterator last, input_iterator_tag) {
    typename iterator_traits<InputIterator>::difference_type dist = 0;
    while (first++ != last){
        ++dist;
    }
    return dist;
}

// 随机访问版本
template<class RandomIterator>
typename iterator_traits<RandomIterator>::difference_type
__distance(RandomIterator first, RandomIterator last, random_access_iterator_tag){
    auto dist = last - first;
    return dist;
}

template<class Iterator>
typename iterator_traits<Iterator>::difference_type
distance(Iterator first, Iterator last){
    typedef typename iterator_traits<Iterator>::iterator_category iterator_category;
    return _distance(first, last, iterator_category());
}

3.7 type_traits

iterator_traits负责萃取迭代器的特性，type_traits负责萃取型别的特性，看型别是否具有non-trivial的默认构造函数，如果不是，在对这个型别进行构造、析构、拷贝、赋值等操作时，就可以采用最有效的措施，比如内存直接处理，malloc、memcpy等

类似地，对型别的萃取也要返回一个class object，以便重载函数根据这个对象的类型调用不同的版本，所以就分成两种类型

struct _true_type {};	// 可以高效处理
struct _false_type {};	// 只能一个一个处理

然后用内嵌定义的形式对型别的属性进行判断

template<class T>
struct _type_traits {
    typedef _false_type     has_trivial_default_constructor;
    typedef _false_type     has_trivial_copy_constructor;
    typedef _false_type     has_trivial_assignment_operator;
    typedef _false_type     has_trivial_destructor;
    typedef _false_type     is_POD_type;
};

这里全部定义为_false_type，给的是最保守的判断

如果是POD（Plain Old Data）类型，即char、int、float这些，就可以直接用内存处理，不需要考虑构造析构，所以针对POD类型定义特化版本

template<>
struct _type_traits<char> {
    typedef _true_type      has_trivial_default_constructor;
    typedef _true_type      has_trivial_copy_constructor;
    typedef _true_type      has_trivial_assignment_operator;
    typedef _true_type      has_trivial_destructor;
    typedef _true_type      is_POD_type;
};	
template<>
struct _type_traits<int> {
    typedef _true_type      has_trivial_default_constructor;
    typedef _true_type      has_trivial_copy_constructor;
    typedef _true_type      has_trivial_assignment_operator;
    typedef _true_type      has_trivial_destructor;
    typedef _true_type      is_POD_type;
};
//...

应用

1、uninitialized_fill_n函数需要从迭代器first开始构造n个元素，这样就可以根据元素的类型调用不同版本的处理函数，如果是POD类型，就直接处理，否则就需要逐个调用构造函数

template<class ForwardIterator, class Size, class T>
inline ForwardIterator uninitialized_fill_n(ForwardIterator first, Size n, const T& x){
    typedef typename _type_traits<T>::is_POD_type isPODType;    // 获取POD类型
    return _uninitialized_fill_n_aux(first, n, x, isPODType());
}

template<class ForwardIterator, class Size, class T>
ForwardIterator _uninitialized_fill_n_aux(ForwardIterator first, Size n, const T& x, _true_type){
    return fill_n(first, n, x); // 是POD直接处理
}

template<class ForwardIterator, class Size, class T>
ForwardIterator _uninitialized_fill_n_aux(ForwardIterator first, Size n, const T& x, _false_type){
    int i = 0;
    for (; i != n; ++i) {
        construct((T*)(first + i), x);  // 不是POD要逐个调用构造函数
    }
    return (first + i);
}

对应的fill_n函数，还定义了char和wchat_t的特化版本，可以直接用memset

template<class OutputIterator, class Size, class T>
OutputIterator fill_n(OutputIterator first, Size n, const T& value) {
    for (; n > 0; --n, ++first) {
        *first = value; // 直接赋值
    }
    return first;
}

template<class Size>
char *fill_n(char *first, Size n, const char& value) {
    memset(first, static_cast<unsigned char>(value), n);
    return first + n;
}

template<class Size>
wchar_t *fill_n(wchar_t *first, Size n, const wchar_t& value) {
    memset(first, static_cast<unsigned char>(value), n * sizeof(wchar_t));
    return first + n;
}

对应的construct函数

template<class T1, class T2>
inline void construct(T1 *ptr1, const T2& value) {
    new(ptr1) T1(value);    // 用placement new逐个调用构造函数
}

2、destory函数

如果是POD类型，就什么都不用做，如果不是，就需要调用析构函数

template<class T>
inline void destroy(T *ptr){
    ptr->~T();  // 调用析构函数
}

// POD版本
template<class ForwardIterator>
inline void _destroy(ForwardIterator first, ForwardIterator last, _true_type) {}

// 非POD版本
template<class ForwardIterator>
inline void _destroy(ForwardIterator first, ForwardIterator last, _false_type) {
    for (; first != last; ++first) {
        destroy(&*first);   // 传递迭代器指向元素的地址进行析构
    }
}

// 萃取元素的特性
template<class ForwardIterator>
inline void destroy(ForwardIterator first, ForwardIterator last) {
    typedef typename _type_traits<ForwardIterator>::is_POD_type is_POD_type;
    _destroy(first, last, is_POD_type());
}

3、copy函数负责将迭代器区间[first, last)的元素拷贝到迭代器result的位置

先获取迭代器指向元素的型别，然后萃取型别的特性，根据是否是POD类型调用不同版本的函数

// POD版本
template<class InputIterator, class OutputIterator>
OutputIterator __copy(InputIterator first, InputIterator last, OutputIterator result, _true_type) {
    auto dist = distance(first, last);
    memcpy(result, first, sizeof(*first) * dist);	// 调用效率更高的memcpy
    advance(result, dist);
    return result;
}

// 非POD版本
template<class InputIterator, class OutputIterator>
OutputIterator __copy(InputIterator first, InputIterator last, OutputIterator result, _false_type) {
    while (first != last) {
        *result = *first;   // 只能逐个拷贝
        ++result;
        ++first;
    }
    return result;
}

template<class InputIterator, class OutputIterator, class T>
OutputIterator _copy(InputIterator first, InputIterator last, OutputIterator result, T*) {
    typedef typename TinySTL::_type_traits<T>::is_POD_type is_pod;
    return __copy(first, last, result, is_pod());
}

template <class InputIterator, class OutputIterator>
OutputIterator copy(InputIterator first, InputIterator last, OutputIterator result) {
    return _copy(first, last, result, value_type(first));
}

还可以定义针对char和wchar_t的特化版本

template<>
inline char *copy(char *first, char *last, char *result) {
    auto dist = last - first;
    memcpy(result, first, sizeof(*first) * dist);
    return result + dist;
}
template<>
inline wchar_t *copy(wchar_t *first, wchar_t *last, wchar_t *result) {
    auto dist = last - first;
    memcpy(result, first, sizeof(*first) * dist);
    return result + dist;
}

4、uninitialized_copy函数也是类似

先萃取出迭代器的value_type，再萃取出is_POD_type，写到一起了，根据是否是POD调用不同版本的_uninitialized_copy_aux函数

template<class InputIterator, class ForwardIterator>
ForwardIterator _uninitialized_copy_aux(InputIterator first, InputIterator last, ForwardIterator result, _true_type) {
    memcpy(result, first, (last - first) * sizeof(*first));
    return result + (last - first);
}

template<class InputIterator, class ForwardIterator>
ForwardIterator _uninitialized_copy_aux(InputIterator first, InputIterator last, ForwardIterator result, _false_type) {
    int i = 0;
    for (; first != last; ++first, ++i){
        construct((result + i), *first);
    }
    return (result + i);
}

template<class InputIterator, class ForwardIterator>
ForwardIterator uninitialized_copy(InputIterator first, InputIterator last, ForwardIterator result) {
    typedef typename _type_traits<typename iterator_traits<InputIterator>::value_type>::is_POD_type isPODType;
    return _uninitialized_copy_aux(first, last, result, isPODType());
}

如果自定义了一个类，也可以定义一个特化版本指明这些特性，而不是全部默认为_false_type

template<> struct _type_traits<Shape> {
    typedef _true_type      has_trivial_default_constructor;    // 指出有不重要的默认构造函数
    typedef _false_type     has_trivial_copy_constructor;
    typedef _false_type     has_trivial_assignment_operator;
    typedef _false_type     has_trivial_destructor;
    typedef _false_type     is_POD_type;
};
文章作者: kunpeng
文章链接: http://example.com/2022/06/12/C-STL-3-%E8%BF%AD%E4%BB%A3%E5%99%A8%E6%A6%82%E5%BF%B5%E4%B8%8Etraits%E7%BC%96%E7%A8%8B%E6%8A%80%E6%B3%95/
版权声明: 本博客所有文章除特別声明外，均采用 CC BY 4.0 许可协议。转载请注明来源 kunpeng !
STL
赏
  目录