STL源码剖析：2.iterator迭代器以及traits技法
2021/6/10 1:20:54
本文主要是介绍STL源码剖析：2.iterator迭代器以及traits技法，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！
1.简介
在STL的设计中，我们最常使用到的就是算法和容器，最为两个独立的个体，我们需要用一个独特的设计来使得二者能够有效的结合，以此来达到我们使用的目的。因此，迭代器便产生了，它的作用是作为一种胶合剂，使得容器以及算法能够有效的结合在一起，以达到我们使用的目的，其中还涉及到了一种巧妙的设计技法traits。每一部分都是按照侯捷老师的《STL源码剖析》的内容以及顺序进行的，如果发现错误欢迎指正。
2.迭代器
迭代器一共有五种分类：
struct input_iterator_tag {};
struct output_iterator_tag {};
struct forward_iterator_tag: public input_iterator_tag {};
struct bidirectional_iterator_tag: public input_iterator_tag {};
struct random_access_iterator_tag: public bidirectional_iterator_tag {};
这里有一些简单的继承关系，从功能上看，forward_iterator以及bidirectional_iterator都是属于input_iterator的一种，他们的行为都是基于input_iterator实现的，是一种is a的关系。（参考侯捷老师对象模型的视频教程），至于为什么会将其设计为struct，在本文之后，我们可以看到其相应的作用。
对于迭代器而言，我们的一共要为其设计五种不同的属性：
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 Pointer pointer;
typedef Reference reference;
typedef Distance difference_type;
};
首先解释这五种属性分别代表的意义：
Category 代表的是迭代器自身的类型；
T 代表的是迭代器所指向的元素的类型;
Pointer 代表的是迭代器所指向元素的指针类型;
Reference 代表的是迭代器所指向元素的引用类型;
Distance 代表两个迭代器之间的距离，也可以表示所指容器的最大容量;
可能会有疑惑为什么是以这样的形式来设计呢？
首先解释typedef用法的意义，对于传入的变量，假如我们要使用的话，我们自然是有很多的办法来对其进行处理，但是假若我们需要使用的是传入的变量的类型呢？我们此时肯定想到的是模板，使用模板的参数推导机制，我们必然可以很自然的使用这个变量的类型了,这个时候我又有一个新的想法，那就是这时候我想使用传入的参数类型作为返回值，此时上述的方法有局限性，那么此时我们采用的办法就是声明内嵌类型，也就是typedef的方法。
那又是为什么需要这些属性呢？
首先明确一个概念，迭代器的作用，是作为算法以及容器的粘合剂，是二者沟通的桥梁，可以抽象的认为，算法在作用的时候，会向迭代器提问，询问一些他在使用的过程中，可能会用到的属性等，那么作为迭代器而言，它本身作为一个桥梁，是无法回答这些问题的，因为从广义的角度来看，连接迭代器的仅仅也就只有算法以及容器，但是算法的作用需要通过获取一些的元素属性，这些元素又是存储在容器中的，因此很自然的，迭代器就向容器索要这些属性，并将这些重要属性进行存储以用于日后能够作为对于算法的回应，因此就有了上述这五个重要的属性。也就是说，当算法在作用的时候，迭代器必须能够给我提供对应容器的上述五个属性，这也就是为什么我们会使用这些属性。
至此，迭代器的基本内容也就讲解结束了。
3.iterator traits技法
在上述的讲解中，我们提到，算法通过迭代器向容器进行提问，以此来完成算法的相应的功能，这个时候我们通过iterator traits技法来解决上述的问题。
通俗点讲，我们通过iterator traits技法来获取迭代器之前所提到的那几个重要的属性。
//萃取器traits
template <class 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;
};
当我们传入的是一个迭代器的时候，我们通过typename来获取迭代器的那几个重要的属性，以此来完成算法对于容器的提问。
如上的设计对于我们作为类存在的迭代器而言当然是没问题的，但是假如迭代器并不是一个class type呢？比如当一个原生指针传入的时候，它并不是一个类自然也就没有这些属性，此时，我们通过模板偏特化来解决上述问题，即针对模板参数更进一步的条件限制所设计出来的一个特化版本，这便能解决我们上述的困惑：
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 T类型的变量，如果按照之前泛化的版本，就会获得一个const T类型的变量，没有什么意义。那么此时，我们就针对这种类型再设计一个特化的版本：
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;
};
到了此时，我们相关的概念也就基本讲述完了，接下来我们开始讲解其使用。
对于许多算法而言，经常会用到一个函数advance函数，作用是讲传入的迭代器累进n个步数。对于迭代器而言，不同的迭代器在累进的过程中，可以采用不同的做法，对于STL的实现而言，为了能够将其效率达到最大化，我们也就理应对于不同版本设计出不同的累进方法。
1.对于前向迭代器，我们只能前进，因此就需要设计出特化的版本。
2.对于双向迭代器，只能前进一步或者是后退一步，因此也需要设计出特化的版本。
3.对于随机访问迭代器，我们可以跳跃访问，因此还需要设计出不同的版本。
template <class InputIterator, class Distance>
inline void __advance(InputIterator& i, Distance n, ) {
while (n--) i++;
}
template <class BidirectionalIterator, class Distance>
inline void __advance(BidirectionalIterator& i, Distance n, ) {
if (n >= 0) {
while (n--) i++;
}
else {
while (n++) i--;
}
}
template <class RandomAccessIterator, class Distance>
inline void __advance(RandomAccessIterator& i, Distance n, ) {
i += n;
}
此时我们可以使用条件判断的方法来决定在不同的情况下访问不同的函数，但是对于函数的效率而言，我们最好避免在执行的时候才确定使用哪一个版本。因此，假如我们可以讲不同的版本作为参数传入让编译器自己去识别，那就是最好不过的了。
这个时候，我们讲这个相应的型别作为一个class type传入，而不是数值号码类的东西，因为编译器需要依赖它来进行重载决议，这也是为啥我们在开始的时候选择讲不同的迭代器设计为类的原因。
也就是下面的版本：
template <class InputIterator, class Distance>
inline void __advance(InputIterator& i, Distance n, input_iterator_tag) {
while (n--) i++;
}
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--;
}
}
template <class RandomAccessIterator, class Distance>
inline void __advance(RandomAccessIterator& i, Distance n, random_access_iterator_tag) {
i += n;
}
template <class InputIterator, class Distance>
inline void advance(InputIterator& i, Distance n) {
//注：iterator_category是通过萃取机制来讲属性提取出来的函数，机制的原理
//已经讲解过了，具体实现放在最后了，通过名字我们可以判别他的功能。
__advance(i, n, iterator_category(i));
}
同理，对于一个常用的函数distance来说，我们以此来计算两个迭代器之间的距离，针对不同的迭代器我们有不同的计算方式，选择于上述一样的实现方式：
template <class InputIterator>
inline typename 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;
}
template <class RandomAccessIterator>
inline typename iterator_traits<RandomAccessIterator>::difference_type
__distance(RandomAccessIterator first, RandomAccessIterator last, random_access_iterator_tag) {
return last - first;
}
template <class InputIterator>
inline typename iterator_traits<InputIterator>::difference_type
distance(InputIterator first, InputIterator last) {
typedef typename iterator_traits<InputIterator>::iterator_category category;
return __distance(first,last,category);
}
下面给出iterator的完整代码：
struct input_iterator_tag {};
struct output_iterator_tag {};
struct forward_iterator_tag: public input_iterator_tag {};
struct bidirectional_iterator_tag: public input_iterator_tag {};
struct random_access_iterator_tag: public bidirectional_iterator_tag {};
//划定了五种typedef，以此来用于之后算法向容器的提问
//哪种迭代器、元素的类型、两个迭代器的距离、元素的指针类型、元素的引用类型(按照template模板的参数顺序)
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 Pointer pointer;
typedef Reference reference;
typedef Distance difference_type;
};
//萃取器traits
template <class 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;
};
//针对原生指针的偏特化版本
//T*, const T*,
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;
};
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;
};
// 决定迭代器的 category
template <class Iterator>
typename iterator_traits<Iterator>::iterator_category
iterator_category(const Iterator&)
{
typedef typename iterator_traits<Iterator>::iterator_category category;
return category();
}
// 决定迭代器的distance type
template <class Iterator>
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>
typename iterator_traits<Iterator>::value_type*
value_type(const Iterator&)
{
return static_cast<typename iterator_traits<Iterator>::value_type*>(0);
}
// 求distance的函数组
template <class InputIterator>
inline typename 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;
}
template <class RandomAccessIterator>
inline typename iterator_traits<RandomAccessIterator>::difference_type
__distance(RandomAccessIterator first, RandomAccessIterator last, random_access_iterator_tag) {
return last - first;
}
template <class InputIterator>
inline typename iterator_traits<InputIterator>::difference_type
distance(InputIterator first, InputIterator last) {
typedef typename iterator_traits<InputIterator>::iterator_category category;
return __distance(first,last,category);
}
//advance函数组
template <class InputIterator, class Distance>
inline void __advance(InputIterator& i, Distance n, input_iterator_tag) {
while (n--) i++;
}
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--;
}
}
template <class RandomAccessIterator, class Distance>
inline void __advance(RandomAccessIterator& i, Distance n, random_access_iterator_tag) {
i += n;
}
template <class InputIterator, class Distance>
inline void advance(InputIterator& i, Distance n) {
__advance(i, n, iterator_category(i));
}
4. type traits技法
相应的，既然我们已经能过通过iterator 来获取一些重要的属性，那么对于一个类而言，我们是否可以获取其相应的属性呢？
这个时候type traits技法就出现了。我们通过这个来获取一个类的那些属性呢？例如，我们想知道这个类的构造函数重要吗？这个类的拷贝赋值函数重要吗？这个类的析构函数重要吗？等等类似的问题，其实也就是询问，类这些函数，是否需要考虑深浅拷贝的问题，是否使用编译器默认的版本即可呢，如果是不重要的，直接使用编译器提供的默认版本就可以的，那我们就认为他是不重要的。
在实现中，我们使用的是has_trivial_xxxx形式的询问，对于默认的类别而言，我们都认为他的这些属性是重要的，也就是从最复杂的情况来考虑。
上述的属性的描述中，我们不使用一个简单的bool值来进行描述，而是使用一个有着真假性质的类，因此我们可以写两个空类，这样又不会造成额外负担，而且还能标志真假以及参与参数推导的过程中去。
struct __true_type
{
};
struct __false_type
{
};
template <class type>
struct __type_traits
{
// 不要移除这个成员，它通知能自动特化__type_traits的编译器, 现在这个__type_traits template是特化的
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;//是否是传统C结构体类型的 或者是编译器提供的构造析构即可的class
};
在SGI STL中，对于内置类型都进行了相应的特化版本：
__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;
};
__STL_TEMPLATE_NULL struct __type_traits<unsigned 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;
};
__STL_TEMPLATE_NULL 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;
};
__STL_TEMPLATE_NULL struct __type_traits<unsigned 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;
};
__STL_TEMPLATE_NULL struct __type_traits<long>
{
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 long>
{
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<float>
{
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<double>
{
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<long double>
{
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的很多设计中都体现出来了，此时，我们以书中展现的例子作为展示（我这里直接使用库函数提供的is_trivially_copy_assignable，在使用中，我们通过is_trivially_copy_assignable{}返回一个true_type或者是false_type，这两个是一个 integral_constant<bool, _Val>类型的变量）：
template <class ForwardIterator, class Size, class T>
ForwardIterator
_uninit_fill_n(ForwardIterator first, Size n, const T& value, std::true_type)
{
return ministl::fill_n(first, n, value);
}
template <class ForwardIterator, class Size, class T>
ForwardIterator
_uninit_fill_n(ForwardIterator first, Size n, const T& value, std::false_type)
{
auto cur = first;
for (; n > 0; --n, ++cur)
{
minitl::construct(&*cur, value);
}
return cur;
}
template <class ForwardIterator, class Size, class T>
ForwardIterator uninitialized_fill_n(ForwardIterator first, Size n, const T& value)
{
return ministl::_uninit_fill_n(first, n, value,
std::is_trivially_copy_assignable<
typename iterator_traits<ForwardIterator>::
value_type>{});
}
第二个例子就用算法库中的uninitialized_copy():
template <class InputInterator, class ForwardInterator>
inline ForwardInterator _uninitialized_copy(InputInterator first, InputInterator last,
ForwardInterator result,std::false_type) {
auto cur = result;
for (; first != last; ++first, ++cur)
{
mystl::construct(&*cur, *first);
}
return cur;
}
template <class InputInterator, class ForwardInterator>
inline ForwardInterator _uninitialized_copy(InputInterator first, InputInterator last,
ForwardInterator result, std::true_type) {
return mystl::copy(first, last, result);
}
template <class InputInterator, class ForwardInterator>
inline ForwardInterator uninitialized_copy(InputInterator first, InputInterator last, ForwardInterator result) {
return _uninitialized_copy(first, last, result, std::is_trivially_copy_assignable<
typename iterator_traits<InputIter>::value_type>{}));
}
template<>
inline char* uninitialized_copy<const char*, char*>(const char* first, const char* last, char* result) {
std::memmove(result, first, last - first);
return result + (last - first);
}
template<>
inline wchar_t* uninitialized_copy<const wchar_t*, wchar_t*>(const wchar_t* first,
const wchar_t* last, wchar_t* result) {
std::memmove(result, first, last - first);
return result + (last - first);
}
参考：
侯捷老师《STL源码剖析》
Github:TinySTL
这篇关于STL源码剖析：2.iterator迭代器以及traits技法的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！
- 2024-05-29蓝桥杯大赛单片机比赛经验总结
- 2024-05-29AI 一键生成高清短视频，视频 UP 主们卷起来...
- 2024-05-29打造 AI “看牙”新体验，当 Serverless 遇上口腔医疗
- 2024-05-27取代或转型？人工智能对软件测试的影响（内附工具推荐）
- 2024-05-14让创意在幻觉中肆虐: 认识Illusion Diffusion AI
- 2024-05-08Sora从入门到入门-白话版1
- 2024-05-082024年github开源top100中文
- 2024-05-083、最大池化maxinmum pooling
- 2024-05-08动态规划基础思想
- 2024-05-08Kimi：文本解析利器，你相信光么？
