最新消息:想得多,做的少。一天到晚瞎鸡巴搞。

STL迭代器手札

大概数据结构与算法 阿虚 62浏览 0评论

利用模板来推倒函数返回值

template<class T>
typename T::value_type FunName(PatamType var)
{
    return xxxx;
}

.      T是模板参数,编译器不认识T,同时也并不知道T::value_type代表的是什么。typename告诉编译器这是一个行别。

偏特化,对指针和基础类型做处理

偏特化:就是提供另一份模板定义式,本身仍然是模板。
//泛化版本,允许接T为任何类型
temp<typename T>
class ClassName
{
}

//特化版本,允许接受T为指针类型
temp<typename T>
class ClassName&lt;T*&gt;
{
}

//特化版本,允许接受T为const 指针类型
temp<typename T>
class ClassName&lt;const T*&gt;
{
}

STL迭代器类型

.      如果希望兼容STL迭代器,那么类模板都必须定义一下五种类型:

.      值类型:typedef T::value_type      value_type

.      不同类型:typedef T::difference_type           difference_type

.      指针类型:typedef T::pointer                  pointer

.      参考(引用)类型:typedef T::reference reference

.      迭代器类型:typedef T::iterator_category            iterator_category

.      同时iterator_category必须对传入类型point以及const point两者设计特化版本。

value_type

.      值迭代器所指对象的型别。T

difference_type

.      表示两个迭代器之间的距离,也可以用来表示容器的最大容量。针对相应的偏特化,如果是指针类型那么difference_type为:typedef ptrdiff_t             difference_type

pointer

.     迭代器允许修改所指对象的内容那么为T*,如果不允许修改所指向的内容那么为const T*

reference

.      迭代器允许改变所指对象的内容为T&,如果不允许修改指向的内容那么为const T&

iterator_category

.      迭代器有五项分类:

.      Input Iterator:迭代器所指对象不允许外界修改为“只读”

.      Output Iterator:只写

.      Forward Iterator:允许“写入行”,表示所形成区间上进行读写操作

.      Bidirectional Iterator:可双向移动。

.      Random Access Iterator:上一种在加上“++、–”运算符。并且涵盖所有指针算数能力。p+n、p-n、p[n]、p1-p2、p1<p2.。。。。。

.      他们之间的关系并非“继承”而是“强化”的概念,但是下面以C++类型表示

class Input Iterator{}
class Output Iterator{}
class Forward Iterator : poublic Input Iterator, public Output Iterator{}
class Bidirectional Iterator : public Forward Iterator{}
class Random Access Iterator : public Bidirectional Iterator

.      以上为“强化”关系,而非“继承”关系!!!!

迭代器分类,这到底是什么鬼东西?

.      emmmmmm,迭代器分类,用来做“函数重载”的。不同的iterator_category对其typedef为iterator_category。如:typedef Input_Iterator iterator_category或者是typedef Random_Access_Iterator iterator_category。

.      C++函数可以是相同的函数名称,只要保证函数参数不一致就能够实现“函数重载”。同样,不同的iterator_category是由上面几个不同的“迭代器分类”重新typedef定义为iterator_category的。那么不同的iterator_category将他当成函数传递的“参数类型”时就能够实现“函数重载”。

为什么要iterator_category函数重载?

int find1(vector<int&> vec, int pos)
{    
    return vec[pos];
}
int find2(vector<int>& vec, int pos)
{ 
    vector<int>::iterator it = vec.begin();
    for (; pos--; it++)
        ;
    return *it;
}

.      为了迭代器提速。比如vector支持“[]” find1访问这是最快的方式。那么vector同样也可以实现为find2来进行访问。但是明显find1比find2效率要高出很多。同样,对于STL来说在编译前并不知道迭代器的所指向的类型是什么,用什么方式访问元素最快。那么通过定义不同的iterator_category重载到不同的数据遍历的函数中实现最大效率的数据遍历。

型别特性

.      这玩意儿时SGI私有的将iterator_category的特性从迭代器扩展迭代器之外来使用。用于“萃取”型别的特性。型别特性是指具备:构造、拷贝构造、运算符重载、析构。如果不满足那么可以直接调用系统函数memset、memcopy之类的函数来提速执行。而非调用迭代器慢慢悠悠的一个一个memset、memcopy。

.      它的定义和在<type_traits.h>中。__type_traits中的所有typedef都定义为__false_type。然后下面都是对基本类型进行“特化”,将所有的typedef都定义为__true_type。那么当__type_traits的type为class时,所有的typedef都为__false_type。那么对于基础类型和class类型就可以区分开来做一些“提速”处理。

value_type理解

.      这玩意的实现是在<stl_iterator>当中,具体为:

template <class T>
inline T* value_type(const T*) { return (T*)(0); }

这玩意返回一个T*而不是返回T的原因是T*为一个“指针”类型,指针类型用于都只占用4个字节!如果返回T的话那么所占用的栈空间那么就大了。

转载请注明:虚无 » STL迭代器手札

发表我的评论
取消评论

表情

Hi,您需要填写昵称和邮箱!

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址