SGI STL源码阅读报告

# SGI STL源码阅读报告

[toc]

## SGI STL 简介

* SGI STL是STL(Standard Template Library)代码的经典实现版本，虽然很多编译器不直接使用这个版本，但是很多却在此基础之上进行改进的。
* STL可以划分成六个主要部分分别是`Containers`(容器)、`Iterators`(迭代器)、`Algorithms`(算法)、`Function Objects`(函数对象)、`Memory Allocation`(空间配置器)、`Adaptors`（适配器）。

## SGI STL的软件架构与各部件之间关联

### 空间配置器

* 配置器负责空间配置与管理，考虑到小型区块可能造成内存碎片问题，SGI 采用两级配置器，第一级配置器直接使用 malloc() 和 free() 实现；第二级配置器使用 memory pool 自己进行内存池管理，提高了小型内存分配的效率。第二季配置器由16个管理大小分别为 8， 16， 24， 32，40， 48， 56， 64， 72， 80， 88， 96， 104， 112， 120， 128的小额区块的free-list组成。

### 函数对象

* 函数对象是一种重载了 operator() 的 class 或 class template，可以为算法的某种策略。
* 所有函数对象均为一元函数`unary_function`的派生类或者二元函数`binary_function`的派生类。
* 如果按照类型划分，分为基础函数（加减乘除等）以及其用于修饰的适配器。可以通过修饰组合出多样的函数对象。

### 容器

* 容器分为序列式容器和关联式容器。序列式容器有`deque`,`heap`,`list`,`queue`,`slist`,`stack`,`vector`。关联式容器有`hash_map`,`hash_set`,`map`,`set`,`multimap`,`multiset`。
* 容器通过空间配置器获取储存空间，同时也负责释放和分配空间。每个容器也有对应自己类型的迭代器用于访问容器内的元素。

### 迭代器

* 迭代器是一种泛型指针，一共有五种不同的类型，分别为`InputIterator`,`OutputIterator`,`ForwardIterator`,`BidirectionalIterator`,`RandomAccessIterator`。
* 迭代器通过对`operator*`和`operator->`进行重载实现了对于容器内部元素访问的功能。

### 算法

* STL算法包含了多种常用的算法如`sort`，`swap`，`copy`等。所有算法都是使用前开后闭的区间,并且两端点都是迭代器。
* STL算法部分多次使用到了STL的容器来完成数据储存和操作。
* STL算法部分也使用到了函数对象来完成不同策略的变化，比如升序或者降序。

### 适配器

* 适配器是一种用来修饰容器、仿函数或迭代器接口的类。
* 通过对于原有对象做一层适配而起到新的作用。

## SGI STL相关的设计模式

### 适配器模式

适配器模式可以将原本各异的接口变成统一特定的接口。

* 在函数对象出使用适配器进行了对于一元和二元函数的修饰。如`unary_negate`,`binary_negate`等。
* 容器`stack`和`queue`都是重新`deque`的适配器。

### 迭代器模式

迭代器模式完成了对于特定对象的数据访问和遍历操作。比指针更灵活，并且迭代器之间的复制比直接在元素之间复制的速度更快，减少不必要的开销。

### 装饰模式

这种方式拥有比继承更灵活的扩展对象的功能，使得可以动态的添加对象的功能，并且可以随意的组合这些功能。

* 在函数对象处使用了装饰模式的`unary_negate`可以用于装饰所有一元函数，和所有一元函数一样，都继承于`unary_function`。类似的还有`binary_negate`,`binder1st`等适配器。

## SGI STL算法库工作流程

整个STL算法库十分追求运行效率，使用了如inline、memcpy、memcmp、循环展开等常数优化方法来提升算法运行效率。而且使用模板为主，极少使用继承，这样在保持泛化能力的同时，提高了运行时候的效率。

### stl_numeric

* `stl_numeric.h`定义并实现了一些常见数值运算操作。其中广泛使用模板和函数对象来增加代码泛化能力，通过迭代器来完成对于空间的遍历和读写。
* 这里面实现了对于数值的一些常见操作，比如累加、内积、部分和、求幂、递增填充，并且每一个函数都有良好的泛化能力，能够自定义运算符方法。
* 比如内积部分为例，实现了$a_1 \times b_1 + a_2 \times b_2 + ... + a_n \times b_n $, 其中$+$和$\times$都是函数对象，默认为加法和乘法，可以通过使用函数对象来改变运算。

### stl_algobase

* `stl_algobase.h`定义并实现了一些基本的简单函数，比如交换、交换迭代器、最大值、最小值、复制、逆向复制、多遍复制、填充、重复填充、差异比较、序列相等判断、字典序比较。每个函数都有自己的泛化版本支持广泛运用模板以及函数对象，尤其是复制函数有各种各样的泛化和偏泛化版本。
* 比如`fill`函数为例，实现了基础的挨个遍历并赋值，以及特化的针对`char`或`unsigned char`或`signed char`数组的使用`memset`的更快的版本。

### stl_algo

* `stl_algo.h`中定义并实现了很多更复杂一些的算法，比如求中位数、for_each、find、find_if、adjacent_find、count、count_if、search、search_n、swap_ranges、transform、replace、replace_if、replace_copy、replace_copy_if、generate、generate_n、remove_copy、remove_copy_if等等。
* 不少算法也调用了`stl_algobase.h`中实现的基本函数,如`rotate_copy`调用了`copy`。并且算法的每一个部分都拆开成为一个又一个较短的函数，功能明确可读性高。
* 比如sort为例，`sort`分成了`__introsort_loop`和`__final_insertion_sort`两部分，`__introsort_loop`（插入排序）又调用`__linear_insert`完成插入操作等，每一函数都可以充分泛化，长度也控制在一定范围内，方便后续开发使用。

wuvin

导航

最近发表

友情链接