当前位置: 首页 > 工具软件 > SGI STL > 使用案例 >

SGI STL迭代器概念与traits编程技法

邵鸿福
2023-12-01

1. 迭代器设计思维 ---- STL 关键所在:

《Design Patterns》一书提供有23个设计模式的完整描述,其中 iterator模式定义如下:

提供一种方法,使之能够依序巡访某个聚合物(容器)所含的各个元素,而有无需暴露该聚合物的内部表达方式。

也就是说,迭代器可用于遍历访问容器中的元素,而又无需关注容器中的元素的类型。

STL的中心思想在于:

将数据容器(containers)和算法(algorithms)分开,彼此独立设计,最后再以一帖胶着剂将它们撮合在一起。

STL核心拆分成“容器、算法、迭代器”这三部分。

“容器”“算法” 的泛型化,从技术角度来看并不难,C++的 “类模板”“函数模板” 可分别达成目标。
如何设计出两者之间的良好胶着剂,才是大难题。


2. 迭代器是一种智能指针(也是一个类):

  1. 迭代器也是一个类,是对原生指针的封装,原生指针也可以看做是一种特殊的迭代器
  2. 指针的各种行为中,最常见也最重要的便是“解引用”(*iter)和 “成员访问”(->),因此迭代器对这两种运算符在类内都做了重载;
  3. 迭代器为了支持STL中通用的算法,无可避免的会暴露过多的迭代器所指对象的内部实现细节。换句话说,要想实现针对某种容器的迭代器,就必须首先对容器内部的实现细节有非常丰富的了解。因此,在STL的实现中,每一种STL容器都提供有专属的迭代器,封装了容器的实现细节。

3. Traits编程技法 ---- STL源代码门钥:

3.1 typename关键字:

  1. 用于声明模板中的一个类型,此时用法与class完全相同,可互为替代:
template <class T>
class A { ... }

template <typename T>
class B { ... }
  1. 用于声明一个类型名称:
    typename的作用就是告诉C++编译器,typename后面的字符串是一个 “类型名称”,而不是成员函数或者成员变量,这个时候如果前面没有typename,编译器没有任何办法知道 T::LengthType 是一个类型还是一个成员名称(静态数据成员或者静态函数),所有编译不能通过。这种使用场景下,typename是不能用class替代的。 例如:
template <class T>
typename iteartor_trais<I>::value_type
func(I ite) 
{ return *ite; }

3.2 模板偏特化:

template partial specialization:模板偏特化:

大致的意义是:
如果一个类模板拥有一个及以上的模板参数时,则可以针对其中某个(或数个,但非全部)模板参数进行特化工作。

换句话说,我们可以在泛化设计中提供一个特化版本(也就是将泛化版本中的某些模板参数赋予明确的指定)。

其实从 “template partial specialization” 字面意思也可以理解“模板偏特化”的含义:

partital: adj. 部分的、不完全的、偏颇、偏袒
specialization: n. 专业化,特化,专门化

直译过来就是“将模板的一部分进行特化”。

例如,假设有如下一个类模板::

template <typename T>
class C { ... };	//这个泛化模板允许(接受)T为任何型别

它的一个特化版本可以是:

template <typename T>
class C<T*> { ... };
//这个特化版本仅适用于“T为原生指针”的情况
//“T为原生指针”便是“T为任何型别”的一个更进一步的条件限制

“T为原生指针”便是“T为任何型别”的一个更进一步的条件限制。

3.2.1 模板为什么要有偏特化:

因为编译器认为,对于特定的类型,如果你能对某一个功能有更好的实现,那么就该听你的。

3.2.2 “模板偏特化”这一模板特性的作用是:

借助“模板偏特化”,可以实现iterator_traits类的多种“特化版本”,用以支持原生指针、const原生指针等多种特殊迭代器的情况。

3.3 使用traits实现的迭代器:

核心思想:

在“算法函数func()”与“迭代器iter”之间,引入“中间层”萃取类 iterator_traits,进而通过 iterator_traits 模板类的“泛化<T>” 与“偏特化<T*>”两种版本,实现分别对“class type”类类型的迭代器 和 “原生指针”类型的迭代器的支持。

实现示例:

#include <iostream>
using namespace std;

template <typename T>
class ListItem {
public:
	ListItem(T val = 0, ListItem* nex = NULL) : _value(val), _next(nex) {}
	T value() const { return _value; }
	ListItem* next() const { return _next; }
private:
	T  _value;
	ListItem* _next;
};

template <typename T>
struct MyIter {
	typedef T value_type;			//iter迭代器类中必须要定义一个value_type,用于返回类型T,这是规定
	T* ptr;
	MyIter(T* p = 0) : ptr(p) {}

	T& operator*() const { return *ptr; }
};

template <class I>
struct iterator_traits_my {			//泛化版模板,用于支持class type类型的迭代器
	typedef typename I::value_type value_type;
};
template <class I>
struct iterator_traits_my<I*> {		//特例化版的模板,用于支持原生指针类型的迭代器
	typedef I value_type;
};

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


int main() {
	ListItem<int> item(42);
	MyIter<ListItem<int> > iter(&item);

	ListItem<int> _i = func(iter);
	cout << _i.value() << endl;

	int* _p = new int(43);
	cout << func(_p) << endl;

	return 0;
}

------
42
43

4. 五种最常用到的迭代器型别:

  1. value type
  2. difference type
  3. pointer
  4. reference
  5. iterator catagoly

5. SGI STL的私房菜:__type_traits

STL只对迭代器加以规范,制定出 iterator_traits 这样的东西。
SGI把这种技法进一步扩大到迭代器以外的世界,于是有了所谓的 __type_traits
双下划线表示这是 SGI STL 内部所用的东西,不是STL标准规范之内。

 类似资料: