「BUAA-C++」Lec7:C++类模版和STL简介

Class Template

首先我们可以用类来实现一个int型数据的栈，代码如下

class Stack {
    int pool[100];
    int top;
public:
    Stack() : top(0) {}
    void push(int i) {
        this->pool[top++] = i;
    }
    int pop() {
        return this->pool[top--];
    }
};

此时，如果我们想要实现一个储存double类型的栈怎么办呢？

当然，我们可以使用程序员传统艺能——“ctrl C + ctrl V”，这在栈的类型较少时是比较适用的，顶多就是代码多了一些；但是如果需要的栈的类型比较多（比如我们需要一个存储“苹果”类对象的栈），这种方法显然是不行的。

类模板可以帮助我们解决这个问题。所谓类模板，实际上是建立一个通用类，其数据成员、成员函数的返回值类型和形参类型不具体指定，用一个虚拟的类型来代表。 在该类创建对象的时候，我们需要指定一个确定的类型，然后编译器就会用我们指定的类型来代替前面定义类模板时适用的虚拟类型。模板类的定义方法为——

template <class T>
class ClassName {
    //...
};

在用类模板来创建对象时，需要用<>指定一下具体类型

ClassName<type_name> obj_name;

下面我们使用类模板来重新定义一下Stack类，并使用这个类模板分别创建int类型和double类型的Stack

template <class T>
class Stack {
    T pool[100];
    T top;
public:
    Stack() : top(0) {}
    void push(T i) {
        this->pool[top++] = i;
    }
    int pop() {
        return this->pool[--top];
    }
};

int main() {
    Stack<int> intStack;
    Stack<double> intStack;
}

STL

像上面Stack这种数据结构（或者称为容器），我们在编程时会大量使用。但是，如果每次使用都定义一次Stack，显然是非常费力的，而且这种重复造轮子的工作也没有什么意义。

这让我们不禁会想——如果C++能够为我们提供一个写好Stack模板就好了

幸运的是，C++摸透了我们的小心思，提供了STL（标准模板库）供我们使用。STL中有大量的动态增长的万能容器，像list、vector、queue、stack等等，同时还为我们提供了容器操作（增删改查）的相关操作。

list&vector

我们先简单介绍一下两个常用的容器——list和vector，这两种容器都是线性存储容器，其定义和操作也很相似

list<int> a;
a.push_back(0); //insert element

vector<int> b;
b.push_back(1); //insert element

我们需要关注的是这两者的底层实现原理——

• vector类似于我们在c语言中使用的数组，强于随机访问，弱于增删改
• list类似于我们学过的链表，强于增删改，弱于随机访问

问题来了，前面提到STL中的容器大多都是可以动态增长的，那么vector和list是如何实现动态增长的呢？

• list比较好理解，毕竟是链表嘛，当需要插入一个新的数据时，直接申请一个新的空间来容纳新的链表项就行。

• 而vector实现方式是，在vector创建时先在内存空间中开辟了一大块连续的空间用来存储，当发现这一块连续的空间不够用了，他会在内存中找到一个更大的连续的空间，然后将之前的数据全部都复制到新的内存空间，从而实现动态增长。

为了证明这一点，我们可以做一个小的实验，我们先定义一个vector<int>类型的对象a，然后a中插入10000个数字，每次插入后看一下a[0]的地址又没有改变，如果改变了则证明我刚才的解释是正确的。实验代码如下

int main() {
    vector<int> a;
    int* last_addr = 0x0;
    for (int i = 0; i < 10000; i++) {
        a.push_back(i);
        if ((int *)(&a[0]) != last_addr) {
            cout << &a[0] << endl;
            last_addr = (int *)(&a[0]);
        }
    }
}

实验结果为——

0x6c2520
0x6c2540
0x6c2520
0x6c2540
0x6c38a0
0x6c38f0
0x6c3980
0x6c3a90
0x6a6300
0x6a6710
0x6a6f20
0x6a7f30
0x6a9f40
0x6c38a0
0x6cb8b0

Iterator

如果想要访问vector中的某一个数据，直接可以使用下标a[i]访问；但是，如果想要访问list中的一个元素呢？我们需要先翻一下STL手册，查一下有没有和访问相关的函数。同样，对于不同的容器，同一访问操作（增、删、改、查）可能会有不同的函数定义。如果要把所有容器的相关函数都记住，显然是不可能的，查STL手册同样也费事费力。

所以，那么多STL容器就没有一个统一的访问方法么???

答案当然是有的，那就是使用迭代器。迭代器实际上是每个STL容器中都定义的一个数据类型，通过这个数据类型我们可以访问容器中所有的元素。此外，基本每个STL容器中也都提供了begin()和end()函数，这两个函数分别返回容器开头和末尾的迭代器，这样我们就可以很容易的遍历容器中的元素了——

int main() {
    vector<int> a;
    for (vector<int>::iterator it = a.begin(); it != a.end(); it++) {
        cout << *it << endl;
    }
}

可以发现迭代器的操作和指针是非常像的，这是因为，STL的开发者对迭代器进行了运算符重载，从而方便用户使用迭代器。

实际上，迭代器有不同的类型，包括输入迭代器、输出迭代器、正向迭代器、双向迭代器和随机访问迭代器，而且不同类型的迭代器操作方法也不完全相同。关于迭代器的类型和相关操作，可以参考这篇博客。