STL与泛型编程第二周

本页内容是 Boolan C++ 开发工程师培训系列的笔记。
因个人水平有限，我撰写的笔记不免出现纰漏。如果您发现错误，请留言提出，谢谢！

面向对象 V.S 泛型编程

面向对象编程与泛型编程的区别主要在于两点：

面向对象编程强调数据和方法的整合性，而泛型编程强调数据和方法的独立性。
面向对象编程和泛型编程实现抽象的手段不同。

组合上的区别

首先我们来看看面向对象编程组织数据的特点：

数据成员 + 成员方法（封装）
实例化（类型特定）

上述的特点造成了一个结果：面向对象编程整合了数据和方法；也就是说，特定的方法只能对特定的成员使用。

再来看看通过泛型编程实现的功能有什么样的特点：

数据和方法独立（Container 和 Algorithm）
类型泛化

很显然，泛型编程希望将数据和方法分离开。

抽象上的区别

STL 的的整体设计思路是基于泛型 * 普通列表项目编程的思想。泛型编程，所谓的泛，指的是类型的泛化，这一点可以通过其语言实现机制：模板很好的体现出来。很容易看出来的是，泛型编程的核心思想是抽象，即将特定于某些类型的算法中那些与类型无关的共性抽象出来。比如，Array 和 Vector 都可以抽象为容器；函数和自定义类都可以抽象为可调用的对象（仿函数）。通过这样一层一层的抽象，最终抽象出来的一个最大公约数，就是我们现在看到的标准库。

面向对象编程也是一种抽象。但不同的是，面向对象是通过多态来实现抽象的；我们需要使用一些共通的功能，只能通过继承这样的间接调用的手段来实现；而在继承以后，我们一定会从具体化的子类中得到一个类型，这个类型是特指的，不是泛化的。

泛型编程和迭代器

你一定很好奇，既然在标准库中，容器和算法都是独立的，那标准库是如何把他们联系起来的？

大致步骤是这样的：

对于标准库中所有的部分，C++ 统一了接口。
这个接口是通过迭代器来实现的，即前闭后开的区间。
这个区间是通过两个迭代器维护（begin(), end()）。
既然容器的范围可以用区间表示，那么算法只需要围绕着两个迭代器来实现就可以了。

面向对象和迭代器

有一个和特殊的例子可以说明面向对象编程和泛型编程的区别：标准库的中的 List，不能使用泛型算法的 sort() 排序。

在标准库的 sort() 中有这么一段代码：

RandomAccessIterator cut = __unguarded_partition
    (first, last, T(__median(*first, *(first + (last - first) / 2), *(last - 1))));

对于可以进行“跳跃” 的这些迭代器，比如可以做 last - first 这样操作的迭代器，我们一般称之为 Random Access Iterator。这样的迭代器要求元素在内存里是连续的。反观 List 中的迭代器，因为 List 是通过链表实现的，这就注定了在 List 中，迭代器是不能跳转的。因此 List 容器不得不使用自己的成员函数 sort()。

从上面的例子我们可以看出，泛型算法也是有局限性的；特定的情况下我们必须使用面向对象编程来解决特定的问题。

泛型算法的作用

泛型算法是一个标准库独立的部分，它只需要考虑对元素本身的操作。这些操作从本质上来说就是比较元素的大小。元素大小的定义并不由算法决定，而是由容器决定；因此我们可以通过自定义大小规则实现不同功能的算法。

比如我们即将比较两个 string 的大小：默认的比较方法是按位比较，即首字母大的 string 比较大。我们通过算法按默认的规则比较 zoo 和 hello：

template<class T>
inline const T& max(const T& a, const T& b) {
    return a < b ? b : a;
}
// "zoo" is greater than "hello"
cout << max(string("zoo"), string("hello") << endl;
}

很显然这里 zoo 是比 hello 大的。如果希望按照 string 的大小来比较的话，我们可以把 max() 的定义改写一下：

temlate<class T, class Compare>
inline const T&max(const T&a, const T&b, Compare comp) {
    return comp(a, b) ? b : a;
}

我们在这里实际添加了一个谓词，用于接收一个自定义规则；这个规则可以以函数的方式表现出来：

bool strLonger(const string& s1, const string& s2) {
    return s1.size() < s2.size();
}

于是我们就可以在新的 max() 函数调用的时候使用这个规则了：

cout << max(string("zoo"), string("hello"), strLonger) << endl;

因为是按 string 的长度比大小，这里的 zoo 是小于 hello 的。

运算符重载，模板，特化

该节内容绝大部分已经于C++面向对象高级编程（下）第一周中讨论过，就不再赘述。

运算符重载规则的参考地址：Operator overloading

分配器

分配器（Allocator）主要与容器配合使用，在容器申请内存空间上起作用。分配器在底层实现上主要通过调用 operator new() 和 operator delete() 来完成内存分配和释放的任务；而从前几周的课程里我们也知道，这两个函数实际上是通过 malloc() 和 free() 在操作。

分配器的效率

分配器的不同设计，是会影响容器的效率的；而效率主要体现在速度和空间占用两个方面。我们可以先看看各大编译器的情况：

<html>

</html>

从上表看出，除了 GCC 2.9 版本没有直接使用 malloc() 和 free()，其他编译器都是直接调用上述两个C语言函数实现的内存分配。那为什么有 GCC 2.9 这个例外？

我们来看看 allocator 的调用是怎么样的：

int* p = allocator<int>().allocate(512, (int*)0);
allocator<int>().deallocate(p, 512);

根据先前的图，我们知道 allocate 是以元素为单位操作的。以 malloc() 为例子，这个函数会对每一个元素都进行空间申请；但申请的空间并不止元素所占用的空间，而会加上一系列的其他信息（比如 Cookies）。那么当元素的大小和这些额外开销（overhead）的大小相近，而元素又特别多的时候，这时的空间浪费是非常恐怖的：每一个元素都带来了额外的开销。对于普通的内存申请来说，这是必须的，因为元素的大小可能不一样；但对于容器来说，因为容器元素的大小是相等的，因此 Cookies 就没有必要添加到每个元素中了。

GCC 2.9 中是定义了自己的 allocator 的，但是没有使用。取而代之的是使用了 SGL STL 中的 alloc。相比之下，该函数更有效的利用了空间：该函数通过一个有16个单元的链表来代替 Cookies 来维护元素的大小，每一个链表的单元代表了一个长度：

单元代表的长度和图示的编号有关，长度可以表示为（编号 + 1）* 字节。当使用 alloc 申请内存的时候，元素的大小不再由 Cookies 维护了，而是由这些链表单元所维护。编译器通过链表单元来查找指定大小的容器。而申请的时候，malloc 只需要负责管理区块总的大小就可以了。当然，为了配合这样的链表，我们需要把容器的大小调整为字节的倍数。

Alloc在GCC 4.9中的使用

alloc 在设计时能节省不少的空间；但很遗憾是在 GCC 4.9 中，默认的 allocator 又开始直接调用 malloc 和 free 了。不过 alloc 并没有被直接删除；我们可以通过如下的方法类接着使用 alloc：

vector<string, __gnu_cxx::__pool_alloc<string>> vec;

需要注意的是，GCC 4.9 中 alloc 已经改名为 __pool_alloc，而该头文件存放于 gnu_cxx 中，而不在 std 里。

容器之间的关系

容器之间的关系可以如下图表示：

<html>

</html>

List详解

List 容器是通过双向环状链表的数据结构来实现的：

<html>

</html>

从上图可以看出，需要实现一个 List 容器，我们需要实现以下几个部分的内容：

节点部分：
- 指向前一个节点的指针 prev。
- 指向后一个节点的指针 next。
- 存放数据的空间 data。
迭代器部分：
- → / * 操作符重载，实现传统指针的功能。
- ++ 迭代器自增操作符重载，实现迭代器移位功能。
结构维护部分：
- 空节点

节点部分的实现

GCC 2.9 中通过了一个结构体模板实现了节点，名称为 list_node，具体代码如下：

<template class T>
struct list_node {
    typedef void* void pointer; 
    void_pointer prev;
    void_pointer next;
    T data;
}

迭代器部分的实现

迭代器部分需要实现的除了运算符重载意外，还有一大堆 typedef 的内容。这部分内容与迭代器的设计标准有关系，请参考第六小节获得具体内容。

迭代器自增的实现

++ 和 – 操作对于迭代器来说是非常重要的；迭代器可以通过对此类的运算符重载来遍历整个链表。以 ++操作为例，可以将迭代器的自增分为两个步骤：

访问节点，查看 next 的指针内容
将当前迭代器指向 next 指针的内容

由于当前 next 指针的内容指向下一个节点的地址，因此迭代器就指向了下一个节点，从而从逻辑上完成了 ++ 的操作。

不过这里出现了一个问题：在C++中拥有着两种自增运算的存在：一种是前自增（Prefix） ++i，另一种是后自增（Postfix） i++，因此我们必须对该运算符的重载分别设计。GCC 2.9 用一个 int 参数这个运算符重载成了两个不同的版本：

link_type node; //link_type is the type of node
/* ++i */
self& operator++() { 
    node = (link_tpye) ((*node).next); //move iter to the next
    return *this;
}
/* i++ */
self operator++(int) {
    self tmp = *this;
    ++*this;
    return *tmp;
}

前自增版本通过迭代器自身的拷贝构造函数将迭代器指向的当前地址转换到了指向下一个节点的地址（(*node).next）。

而带参数的版本即为后自增版本，该版本在调用过程中使用了重载的前自增版本：

首先建立了一个迭代器的临时变量，装载原有的值，用于稍后返回，实际上是在调用迭代器的拷贝构造函数。
其次通过调用前自增版本的重载将现有的地址指向下一个节点。
最后返回先前存储的临时变量，此处因为是值传递，所以依然调用了拷贝构造函数。

有几点需要注意的是：

相对于前自增版本，后自增版本并不改变当前迭代器的值；他会记录原来的迭代器值，然后将指向目前节点的指针往下挪一位，然后再返回原来的迭代器值。
第一步和第二步中的 *this 实际上使用了重载后的前自增版本。这里不会使用迭代器 * 操作符重载，因为这里将 *this 解释为了前自增操作的参数。

很显然，后自增的这个逻辑与 C++ 中默认的后自增运算的逻辑是相同的。

除此之外，以上两个版本还有一个很重要的区别：前自增版本返回的是引用，而后自增版本返回的是值。

这也是因为设计者按照 C++ 中默认的自增运算逻辑来设计的。试想一下对整型 i 如果有以下运算：

++(++i);
(i++)++; // error: lvalue required as increment operand

很显然第二个表达式是错误的。C++ 标准（section 5.2.6）说明了默认的后自增版本返回一个右值，右值是不能作为自增的操作对象的。而前自增返回了引用，引用是左值，因此就可以作为第二个前自增操作的操作对象了。因此这里为了匹配默认的自增运算标准，我们在前自增版本的重载实现中，也采用了返回引用。

迭代器*运算和->运算实现

这个已经在以前的课程中讨论过了。实现代码如下：

reference operator*() const { return (*node).data; }
pointer operator->() const { return &(operator*()); }

其中 &(operator*()) 操作实际上是做了 &(*ite)→method(); 这样的操作。这里存在着 → 运算符的转化，用老师的话来说就是：

当你对某个 type 实施 operator →, 而该 type 并非 built-in ptr 时，编译器会做一件很有趣的事：在找出 user-defined operator→ 并将其施行与该 type 后，编译器会对执行结果在此施行 operator→。编译器不断执行这个动作，直到初级 a pointer to a built-in type，然后才进行成员存取。

G4.9版本的改进

GCC 4.9 版本对 GCC 2.9 版本做出了一些改进：

迭代器要求的参数从 <T,T&,T*> 换成了 <_Tp>。新版本中剩下的内容都在结构体中定义，这样更容易理解。
从void* 指针替换成了指向自身的指针（_List_node_base* 类型），从而省去了指针转换的开销；并将这个类型做成了父类，以供继承。
重写了 begin() 和 end() 的实现（因为在G 4.9 版本中，原有的 List 结构被拆分成了一大堆类）。

迭代器的设计规则

迭代器是算法和容器沟通的桥梁。在算法和容器沟通的过程中，算法需要知道迭代器的细节来完成沟通工作。具体的来说，C++ 规定了算法必须获取迭代器的以下五个特征：

iterator_category，即负责沟通的迭代器的种类，比如迭代器是否可以后退，是否是随机访问的等等。
value_type，即迭代器指向的值的类型。
difference_type，即两个迭代器之间的距离，一般用 ptrdiff_t 表示。当距离超过 ptrdiff_t 能表示的上限时，程序可能报错。
pointer，指针，几乎没有使用。
reference，引用，几乎没有使用。

下面的例子就是一个典型迭代器类中声明这些需要传递的信息：

template<class T, class Ref, class Ptr>
struct _List_iterator {
    typedef bidirectional_iterator_tag iterator_category; // List need a iterator that can go both forward and backward
    typedef T value_type;
    typedef Ptr pointer;
    typedef Ref reference;
    typedef ptrdiff_t difference_type;
}

而算法通过以下的方法就可以访问这些信息了：

template<typename I> // I is the type of iterator
algorithm(I first, I last) {
    I::iterator_category;
    ....
}

我们把以上这些算法需要知道的特征类型，称为 Associated Types。

Iterator Traits

上节说到 C++ 要求迭代器必须带有五个基本特征信息。但有时候我们遇到的迭代器并不是以类的形式表现的，比如指针；这个时候我们就没有办法通过指针来携带这些信息了。怎么办呢？这时候就需要使用萃取机 （Traits）。我们可以把 Traits 想象为一个中介层，算法通过 Traits 来判断传递过来的迭代器是不是退化的迭代器（指针）。如果不是，就通过普通的办法来调用；如果是，就通过 Traits 层补全信息后，再进行调用。

不难判断的是， Traits 必须有能力分辨得到的迭代器是否是类。实际上， Traits 通过了模板的偏特化 来实现了这个分辨的能力。下面是一个 Traits 的实现（使用 value_type 作为例子）：

/* if iterator is a normal class */
template <class I>
struct iterator_traits {
    typedef typename I::value_type value_type;
}
/* if iterator is a pointer */
template <class T>
struct iterator_traits<T*> {
    typedef T value_type;
};
/* if iterator is a pointer that point to a const */
template <class T>
struct iterator_traits<const T*> {
    typedef T value_type;
};

上面的代码实现了对不同类型的迭代器的分别处理。当我们需要使用迭代器的 value_type 的时候，我们就可以这么写：

template<typename I, ...>
void algorithm(...) {
    typename iterator_traits<I>::value_type v1;
}

有一点需要注意的是，上面的例子中，无论是指针还是常量指针，定义的类型都是 T*，这是因为如果迭代器定义为 const T*,那么该指针指向的值就没有办法更改了；这显然是没意义的。

Traits的种类

Traits 大致可以分为下面几类：

<html>

</html>

Vector详解

Vector 容器可以被看作是一种可以动态增长的数组。我们先来看看 Vector 在内存中的结构：

<html>

</html>

由上图所示，Vector 实际上由三个指针 start、finish 和 end_of_storage 来维护的。start、finish 的距离代表了 Vector 的元素个数多少，即 size()； start、end_of_storage 之间的距离则代表了 Vector 可以最多容纳多少元素，即 capacity()。

通过以上这三个指针，我们可以实现 Vector 中的一部分访问功能函数：

template<class T, class Alloc = alloc>
class vector {
public:
    typedef T value_type;
    typedef value_type* iterator;
    typedef size_t size_type;    
    ....
protected:
    iterator start;
    iterator finish;
    iterator end_of_storage;
public:
    iterator begin() { return start; }
    iterator end() { return finish; }
    iterator size() const { return size_type(end() - begin()); }
    iterator capacity() const { return end_of_storage - begin()); }
    bool empty() const { return begin() == end(); }
    reference operator [] (size_type n) { return *(begin() +  n); }
    ....

需要注意的是，在这些实现中，不直接使用指针，而使用其访问函数实现，是为了更好的统一接口设计。

Vector的增长

Vector 的增长发生在添加元素的时候。Vector 的增长策略是翻倍增长；但需要注意的是，该翻倍策略并不是原地扩充，而是会新申请一片正好是当前 Vector 两倍大小的内存空间，然后把现有 Vector 中的元素拷贝过去。如果按本章开头的 Vector 例子再添加三个元素，下图则可以清楚的描述增长前和增长后的对比：

<html>

</html>

Vector 增长的实现

我们来看一看这种扩充是怎么实现的（以 push_back() 举例说明）。

Vector 在做 push_back() 操作的时候，push_back() 会先检查 Vector 是否还有足够的空间：

if(finish != end_of_storage) {
    construct(finish, x);
    ++finish;
} else { //no enough space
    insert_aux(end(), x);
}

如果没有足够的空间，push_back() 会调用 insert_aux() 函数。该函数会对当前 Vector 做两个步骤的操作：

第一步，计算新的 Vector 需要的空间。这一步又分为以下部分：

存放原来 Vector 的大小。
判断原来 Vector 大小是否为 0，如若为 0，则分配 1 的空间；否则使空间翻倍。

实现代码如下：

const size_type old_size = size();
const size_type len = old_size != 0 ? 2 * old_size : 1; //allocate strategy
iterator new_start = data_allocator::allocate(len);
iterator new_finish = new_start;

第二步，复制所有内容到新的 Vector。这一部分又分为一下部分：

复制旧 Vector 中元素到新的 Vector 中。
为新添加的元素设置初始值，添加到 Vector 中。

实现代码如下：

new_finish = uninitialized_copy(start, position, new_start); //copy elements from old to new
construct(new_finish, x); //setting default value for new elements

需要额外注意的有两点：

insert_aux() 函数中自带判断是否有备用空间的功能和拷贝安插点以后元素到新的 Vector 的功能。这些功能对于 push_back() 可能是不必要的，但必须有，因为这个函数可能被其他函数调用，比如 insert()。
Vector 由于其内存增长策略，在数据规模较大的情况下很容易溢出。因此在此用一个异常捕获是一个不错的保护措施。

Vector的迭代器

因为 Vector 是顺序容器，因此 Vector 的迭代器并不像 List 那样的麻烦，直接使用指针代替就可以。我们通过查看原源代码也可以发现，迭代器的类型实际上就是指针：

value_type* iterator; //T*

而因为是顺序容器，迭代器的种类（category）应该被设置为随机访问的类型，即 random_access_iterator_tag。由于这里使用了指针充当迭代器，我们需要使用 Iterator_traits 对其进行相关的补充。

在 G 4.9 版本中，因为具体实现的复杂化，该迭代器的实现已经从指针转变为对象了，因此会按类的情况来处理。

Array

C++ 11种将 Array 也包装成了容器，使得算法可以直接操作 Array。但和其他容器不同的是，Array 是定长的；因此我们必须在定义 Array 的时候输入一个长度。下面代码是 G 2.9 的实现方式：

template<typename _Tp, std::size_t _Nm>
struct array {
    typedef _Tp;
    typedef _Tp*;
    typedef _value_type* iterator;
value_type _M_instance[_Nm ? _Nm : 1];    
....

我们直接传一个 size_t 类型的参数进去维护数组的长度就可以。当然这里有一个处理：如果这个参数为 0，我们就令其为 1，保证数组不会为空。

因为 Array 是连续的，因此我们也可以使用指针来作为迭代器。而有了这个 _Nm 参数，我们就可以依托数组的基本功能来定义迭代器了：

iterator begin() { return iterator(&_M_instance[0]); }
iterator end() { return iterator(&_M_instance[_Nm]); }

当然，为了匹配算法的查询，我们当然也要对 Array 的迭代器进行特殊处理；这个处理过程和 Vector 类似，也需要用到 Iterator_traits。

注：G 4.9 的内容因侯老师并不推荐学习，我就不针对那些复杂的内容一一分析了。

目录

STL与泛型编程第二周

面向对象 V.S 泛型编程

组合上的区别

抽象上的区别

泛型编程和迭代器

面向对象和迭代器

泛型算法的作用

运算符重载，模板，特化

分配器

分配器的效率

Alloc在GCC 4.9中的使用

相关的技术点

容器之间的关系

List详解

节点部分的实现

迭代器部分的实现

迭代器自增的实现

迭代器*运算和->运算实现

G4.9版本的改进

迭代器的设计规则

Iterator Traits

Traits的种类

Vector详解

Vector的增长

Vector 增长的实现

Vector的迭代器

Array

目录

STL与泛型编程 第二周

面向对象 V.S 泛型编程

组合上的区别

抽象上的区别

泛型编程和迭代器

面向对象和迭代器

泛型算法的作用

运算符重载，模板，特化

分配器

分配器的效率

Alloc在GCC 4.9中的使用

相关的技术点

容器之间的关系

List详解

节点部分的实现

迭代器部分的实现

迭代器自增的实现

迭代器*运算和->运算实现

G4.9版本的改进

迭代器的设计规则

Iterator Traits

Traits的种类

Vector详解

Vector的增长

Vector 增长的实现

Vector的迭代器

Array

STL与泛型编程第二周