ACM基础——STL详解

[TOC]

---

本内容参考北大基础训练PPT《C++模板与STL库介绍（单栋栋）》

概论

C++中有两个方面体现重用：

1. 面向对象的思想：继承、多态、标准类库
2. 泛型程序设计（Generic Programming）的思想：模板机制、标准模板库STL

模板机制的介绍

上面讲了，C++的重用体现在两个方面，下面从泛型程序设计入手，着重讲解有关STL的相关内容。

泛型程序设计

泛型程序设计，简单的讲就是使用模板的程序设计法，主要是将一些常用的数据结构和算法写成模板，以后则不论数据结构里放的是什么对象，算法针对什么样的对象，都不必重新实现数据结构，重新编写算法。其中，标准模板库（Standard Template Library）就是一些常用数据结构和算法的模板集合。有了STL，不必再重复造轮子便可获得非常高的性能。

模板的概念

假如设计一个求两参数最大值的函数，在实际中我们可能需要定义如下四个函数：

int max ( int a , int b ) { return ( a > b ) ? a , b ; }
long max ( long a , long b ) { return ( a > b ) ? a , b ;}
double max ( double a , double  b ) { return ( a >b)? a , b ; }
char max ( char a , char b ) { return ( a > b ) ? a , b ;}

尽管这些函数几乎相同，唯一的区别就是形参类型不同，但是需要事先知道有哪些类型会使用这些函数，否则都必须要写。

那么——

所谓模板，就是一种使用无类型参数来产生一系列函数或类的机制。

若一个程序的功能是对某种特定的数据类型进行处理，则可以将所处理的数据类型说明为参数，以便在其他数据类型的情况下使用，这就是模板的由来。模板是以一种完全通用的方法来设计函数或类而不必预先说明将被使用的每个对象的类型。通过模板可以产生类或函数的集合，使它们操作不同的数据类型，从而避免需要为每一种数据类型产生一个单独的类或函数。

模板分类

• 函数模板（function template）

独立于类型的函数，可产生函数的特定版本

• 类模板（class template）

跟类相关的模板，例如vector；
可产生类对特定类型的版本，例如vector<int>

---

下面我们来看个例子：
求两个数最大值

template < class T > 
T max(T a , T b){
    return ( a > b ) ? a , b;
}

这里即使用了模板——

template < 模板形参表>
<返回值类型> <函数名>（模板函数形参表）
{
      //函数定义体
}

模板的工作方式

函数模板只是说明，不能直接执行，需要实例化为模板函数后才能执行。在说明了一个函数模板后，当编译系统发现有一个对应的函数调用时，将根据实参中的类型来确认是否匹配函数模板中对应的形参，然后生成一个重载函数。该重载函数的定义体与函数模板的函数定义体相同，它称之为模板函数。

编写一个对具有n个元素的数组a[ ]求最小值的程序，要求将求最小值的函数设计成函数模板。

#include <iostream>
template <class T>
T min(T a[],int n)
{
    int i;
    T minv=a[0];
    for( i = 1;i < n ; i++){
            if(minv>a[i])
              minv=a[i];
    }
    return minv;
}
void main()
{ ina a[]={1,3,0,2,7,6,4,5,2};
   double b[]={1.2,-3.4,6.8,9,8};
   cout<<”a数组的最小值为：”
          <<min(a,9)<< endl;
   cout<<”b数组的最小值为：”
          <<min(b,4)<<endl;   
}

此程序的运行结果为：
a数组的最小值为：0
b数组的最小值为：-3.4

模板的优缺点

优点：

• 函数模板方法克服了C语言解决上述问题时用大量不同函数名表示相似功能的坏习惯
• 克服了宏定义不能进行参数类型检查的弊端
• 克服了C++函数重载用相同函数名字重写几个函数的繁琐
  缺点：
• 调试比较困难（一般先写一个特殊版本的函数，运行正确后改成模板函数）

STL中的几个基本概念

• 容器：可容纳各种数据类型的数据结构
• 迭代器：可依次存取容器中元素的东西
• 算法：用来操作容器中的元素的函数模板。

例如，STL用sort()来对一个vector中的数据进行排序；用find()来搜索一个list中的对象。

容器

容器是一种可以用于存放各种类型的数据（基本类型的变量，对象等）的数据结构。共分为3大类：

1. 顺序容器

• vector：后部插入/删除，直接访问
• deque：前/后部插入/删除，直接访问
• list：双向链表，任意位置插入/删除

2. 关联容器

• set：快速查找，无重复元素
• multiset：快速查找，可有重复元素

前二者合称为第一类容器

• map：一对一映射，无重复元素，基于关键字查找
• multimap：一对一映射，可有重复元素，基于关键字查找

3. 容器适配器

• stack：LIFO
• queue：FIFO
• prionity_queue：优先级高的元素先出

注意以下两点：

1. 对象被插入容器中时，被插入的是对象的一个复制品。

2. 许多算法，比如排序，查找，要求对容器中的元素进行比较，所以放入容器的对象所属的类，还应该实现==和<运算符。

顺序容器简介

1. vector 头文件<vector>
   实际上就是个动态数组。随机存取任何元素都能在常数时间完成。在尾端增删元素具有较佳的性能。
2. deque 头文件 <deque>
   是个动态数组，随机存取任何元素都能在常数时间完成(但性能次于vector)。在两端增删元素具有较佳的性能。
3. list 头文件 <list>
   双向链表，在任何位置增删元素都能在常数时间完成。不支持随机存取。

上述三种容器称为顺序容器，是因为元素的插入位置同元素的值无关。

关联容器简介