准备知识
什么是迭代器?
迭代器是链接容器和算法的桥梁, 所有的算法都通过迭代器操作容器中的数据
迭代器是一种智能指针, 最重要的操作符重载就是 operator*,operator->
迭代器的实现需要知道容器的具体细节, 因此每一种容器都对应自己特有的迭代器, 但是迭代器的接口是一致的
Traits 编程技巧
目的: 提取出容器中存放的数据类型
核心是使用模板技术, 在编译期就确认需要调用的函数
嵌套从属名称:
- template <typename T>
- class Data
- {
- typedef T value_type;
- };
- template <typename T>
- class Type
- {
- // typename T::value_type 就是一个嵌套从属名称, 其中的 typename 不能掉
- // 理解模板类型中使用模板类型
- typedef typename T::value_type value_type;
- };
- int main()
- {
- Type<Data<int>>::value_type a(); // a() 表示一个类型为 int 的变量
- }
占位参数实现函数重载
占位参数是函数参数, 只是这种参数只有参数类型, 没有参数名
占位参数同样属于参数列表, 可以实现重载
- // int 是占位参数
- void print(int)
- {
- cout <<"void print(int)" << endl;
- }
- void print()
- {
- cout << "void print()" << endl;
- }
- int main()
- {
- print(1); // 调用 void print(int)
- print(); // 调用 void print()
- }
源码
常用的迭代器相应类型
一般在迭代器中常用的容器类型一共 5 种
- template <class I>
- struct iterator_traits
- {
- typedef typename I::iterator_category iterator_category;
- typedef typename I::value_type value_type;
- typedef typename I::difference_type difference_type;
- typedef typename I::pointer pointer;
- typedef typename I::reference reference
- };
- /*
- value_type: 迭代器所指数据类型
- difference_type: 表示两个迭代器之间距离的类型
- reference: 数据内容本身类型
- pointer: 与 reference 对应的指针类型
- iterator_category:
- Input Iterator: 只读
- Output Iterator: 只写
- Forward Iterator: 可读可写, 只能前进, 每次前进一个单位
- Bidirectional Iterator: 可读可写, 双向移动, 每次移动一个单位
- Random Access Iterator: 可读可写, 双向移动, 每次移动多个单位
- */
由于原生的指针类型并没有提供者 5 种类型的定义, 因此进行特化处理
- // 实现原生指针的类型提取
- template <class T>
- struct iterator_traits<T*>
- {
- ...
- typedef T* pointer;
- typedef T& reference;
- };
- // 实现 const 指针的类型提取, 去掉 const 属性, 因为会通过迭代器操作容器中的数据
- template <class T>
- struct iterator_traits<const T*>
- {
- ...
- typedef const T* pointer;
- typedef const T& reference;
- };
5 种 iterator_category 的类型定义, 都只是类型定义, 没有任何成员
- 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 {
- };
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 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 Iterator>
- struct iterator_traits {
- typedef typename Iterator::iterator_category iterator_category;
- typedef typename Iterator::value_type
- typedef typename Iterator::difference_type
- typedef typename Iterator::pointer
- typedef typename Iterator::reference
- };
- // 针对原生指针的特化处理
- template <class T>
- struct iterator_traits<T*> {
- typedef random_access_iterator_tag iterator_category;
- typedef T value_type;
- typedef ptrdiff_t difference_type;
- typedef T* pointer;
- typedef T& reference;
- };
- // 针对 const 指针的特化处理
- template <class T>
- struct iterator_traits<const T*> {
- typedef random_access_iterator_tag iterator_category;
- typedef T value_type;
- typedef ptrdiff_t difference_type;
- typedef const T* pointer;
- typedef const T& reference;
- };
- // 该函数非常方便的提取某个迭代器的类型 iterator_category
- template <class Iterator>
- inline typename iterator_traits<Iterator>::iterator_category iterator_category(const Iterator&)
- {
- typedef typename iterator_traits<Iterator>::iterator_category category;
- return category();
- }
- // 该函数非常方便的提取某个迭代器的类型 difference_type
- template <class Iterator>
- inline typename iterator_traits<Iterator>::difference_type* distance_type(const Iterator&)
- {
- 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&)
- {
- return static_cast<typename iterator_traits<Iterator>::value_type*>(0);
- }
advance 函数
- // 迭代器前进
- template <class InputIterator, class Distance>
- inline void advance(InputIterator& i, Distance n)
- {
- __advance(i, n, iterator_category(i));
- }
- // radom 迭代器前进
- template <class RandomAccessIterator, class Distance>
- inline void __advance(RandomAccessIterator& i, Distance n, random_access_iterator_tag)
- {
- i += n;
- }
- // bidirectional 迭代器前进
- template <class BidirectionalIterator, class Distance>
- inline void __advance(BidirectionalIterator& i, Distance n, bidirectional_iterator_tag)
- {
- if (n>= 0)
- while (n--) ++i;
- else
- while (n++) --i;
- }
- // input 迭代器前进
- template <class InputIterator, class Distance>
- inline void __advance(InputIterator& i, Distance n, input_iterator_tag)
- {
- while (n--) ++i;
- }
distance 函数
- // 计算迭代器之间的距离
- template <class InputIterator>
- inline iterator_traits<InputIterator>::difference_type distance(InputIterator first, InputIterator last)
- {
- typedef typename iterator_traits<InputIterator>::iterator_category category;
- return __distance(first, last, category());
- }
- // 计算 random 迭代器之间的距离
- template <class RandomAccessIterator>
- inline iterator_traits<RandomAccessIterator>::difference_type __distance(RandomAccessIterator first, RandomAccessIterator last,
- random_access_iterator_tag)
- {
- return last - first;
- }
- // 计算 Input 迭代器的距离
- template <class InputIterator>
- inline iterator_traits<InputIterator>::difference_type __distance(InputIterator first, InputIterator last, input_iterator_tag)
- {
- iterator_traits<InputIterator>::difference_type n = 0;
- while (first != last)
- {
- ++first;
- ++n;
- }
- return n;
- }
__type_traits 技术
不属于标准的 STL, 属于 SGI STL 的私有代码
技术和 iterator_traits 技术相同, 只是定义的类型不同, 作用场合不同
如 POD 就是__type_traits 中定义的一种类型
部分代码如下:
- struct __true_type { };
- struct __false_type { };
- template <class type>
- struct __type_traits
- {
- typedef __true_type this_dummy_member_must_be_first;
- 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; // 是否是 POD 类型
- };
- __STL_TEMPLATE_NULL 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;
- };
- __STL_TEMPLATE_NULL struct __type_traits<signed 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;
- };
- __STL_TEMPLATE_NULL struct __type_traits<unsigned 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;
- };
- __STL_TEMPLATE_NULL struct __type_traits<short>
- {
- 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 <class T>
- struct __type_traits<T*>
- {
- 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;
- };
来源: http://www.bubuko.com/infodetail-3210152.html