九、STL模板库

1.C++函数模板

• 函数模板是一个独立于类型的函数，可产生函数特定类型的版本。通过对参数类型进行参数化，获取有相同形式的函数体。

• 它是一个通用函数，它可适应一定范围内的不同类型对象的操作。

• 函数模板将代表着不同类型的一组函数，它们都使用相同的代码，这样可以实现代码重用，避免重复劳动，又可增强程序的安全性。

  函数模板的定义格式：

template < 模板形参表 > 类型 函数名(参数表)

{

//函数体

}

模板形参表又称参数化类型名表，多个表项用逗号分隔。

每个项称为一个模板参数（模板形参）。

格式如下：

class <参数名>

或typename<参数名>

或<非类型形参> <参数名> // int , double ,char

//函数模板实例-t1.cpp
template <typename T> // template <class T>
T Max(const T &a, const T &b)
{
    return a > b ? a : b;
}
-  < > 括起部分就是模板的形参表，T是一个虚拟类型参数。注意，可以用多个虚拟参数构成模板形参表。
-  不但普通函数可以声明为函数模板，类的成员函数也可以声明为函数模板
int main()
{
    cout <<“Max(15, 60) = ” << Max<double>(15.1, 60) << endl;
    cout << "Max('a','b') = " << Max('a','b') << endl;
    cout << "Max(1.2, 16.2) = " << Max(1.2, 16.2) << endl;
    
    return 0;
}

2.泛型编程

• 那么，代码中的 T 是什么呢？很明显，这是一个占位符，更确切的说是一个类型占位符。也就是说，将来在 T 这个位置上的是一个真实、具体的数据类型，至于到底是哪个类型，完全取决于用户的需求。

• 当然，如果硬要给 T 这种类型占位符也叫做一种数据类型，提供这种想法的发明者称它为泛型（**generic type），而使用这种类型占位符的编程方式就被称为泛型编程。

• 值得一提的是，既然泛型并不是真实的数据类型，那么使用泛型编写的代码也就不是真正的程序实体，只能算是一个程序实体的样板。故此，通常形象的将这种使用了泛型的代码称为模板，由模板生成实际代码的过程称为模板的具体实现。

• 总之一句话，泛型也是一种数据类型，只不过它是一种用来代替所有类型的“通用类型” 。在 C++ 中，用以支持泛型应用的就是标准模板库 STL，它提供了 C++ 泛型设计常用的类模板和函数模板。

3.模板形参

• 类型形参

类型形参跟在关键字class或typename之后定义，如class T 是名为T的类型形参。

template

int compare(const T &v1, const T &v2);

• 非类型形参

在调用函数时非类型形参将用值代替，值的类型在模板形参表中指定。非类型形参通常定义为模板内部的常量值。

template <class T,  int rows >
​
void sum(T data[],T &result)
​
{
​
    result = 0;
​
    for(int i=0; i < rows;i++}
​
    result+=data[i];
​
}

1)模板形参限制（一）

• 模板形参作用域

模板形参的名字可以在声明为模板形参之后直到模板声明或定义的末尾处使用。

typedef double T;
​
template <typename T>
T fun(const T &a, const T &b)
{
    T tmp = a;
……
    return tmp;
}
​
template <typename T>
T cacl(const T &a)
{
……
}

2)模板形参限制（二）

• 使用模板形参名字的限制模板形参的名字在同一模板形参表中只能使用一次，并且不能在模板内部重定义。

注意：不能出现如下定义

template <typename T>
T fun(const T &a, const T &b)
{
typedef double T; //Error!
T tmp = a;
……
return tmp;
}
template <typename T, typename T>
T cacl(const T &a, const T &b){……}

3)模板形参限制（三）

• 模板声明

模板可以像其他函数一样只声明而不定义。

template <typename T> void fun(const T &);
​
//在同一模板的声明和定义中，模板形参名称可以不同。
​
template <typename T> void fun(const T &);
template <typename U> void fun(const U &);
​
template <typename V>
void fun(const V &a)
{
……
}

4.函数模板实例化 – 模板函数

• 函数模板是模板函数的一个样板，它可以生成多个重载的模板函数，这些模板函数重用函数体代码。模板函数是函数模板的一个实例。

• 编译系统将依据每一次对模板函数调用时实际所使用的数据类型生成适当的调用代码，并生成相应的函数版本。编译系统生成函数模板的某个具体函数版本的过程称为函数模板的实例化（instantiation），每一个实例就是一个函数定义。

• 实例化的过程或结果通常是不可见的，编译系统会根据函数调用的具体情况自动传递相应的模板实参，生成相应的函数实例。

模板实参推断

• 从函数实参确定模板实参类型和值的过程叫做模板实参推断（template argument deduction）。

• 实参推断过程中可能出现的问题

  • 从模板函数实参表获得的信息有矛盾。

  • 需要获得特定类型的返回值，而不管参数的类型如何。

  • 函数模板含有常规形参

1)模板实参推断（一）

• 模板函数实参表获得的信息有矛盾

template<typename T> T add(T a, T b){return a+b;}

int main()

{

double a = 5.3;

add(a, 100); //error: no matching add(double, int)

return 0;

}

• 解决办法

  • 当实参表中有多个类型时，保证实参类型完全匹配。

  • 指定显示模板实参

add<int>(a, 100); // add(int, int)

2)模板实参推断（二）

• 获得特定类型的返回值

  引入新的模板形参表示返回值，并由调用者显示指定

template<typename T1, typename T2, typename T3>

T1 add(T2 a, T3 b)

{

return a + b;

}

long v1 = add<long>(452.8, 100);

由于显示模板实参从左至右依次匹配，第一个模板实参与第一个模板形参相匹配，因此好的设计是将返回值类型设置为第一个模板形参

template<typename T1, typename T2, typename T3>

T3 add(T2 a, T1 b);

long v2 = add<int, double, long>(45.2, 100);

3)模板实参推断（三）

• 函数模板含有常规形参

  • 当模板含有常规形参时，如果常规参数的信息无法从模板函数的实参表中获得，则在调用时必须显式的给出对应于常规参数的模板实参

template <class T,int rows>
void sum(T data[],T &result)
{
    result=0;
    for(int i=0;i<rows;i++)
    result += data[i];
}
​
int main()
{
    int d[3]={1,2,3};
    int r;
    sum<int,3>(d,r);
    cout<<"sum="<<r<<endl;
    
    return 0;
}

5.函数模板的重载例子

// 函数模板与函数模板、普通函数之间可以重载
template<class T>
T Func(T t)
{
    cout << “Func(T)”<<endl;
    return t;
}
​
template<class T>
T Func(int i,T t)
{
    cout << “Func(int, T)”<<endl;
    return i*t;
}
    int Func(int t)
{
    cout << “Func(int)”<<endl;
    return t;
}
​
int main()
{
    cout << Func(2.3);
    cout << Func(5);
    cout << Func(2.5, 5.3);
    cout << Func(2, 42.4);
    
    return 0;
}

6.C++类模板

• 为何要引进类模板？

  • 按不同的方式重用相同的代码

  • 使代码参数化（通用化），即不受类型和操作的影响

• 使用类模板所定义的一种类类型，类中的某些数据成员和某些成员函数的参数及返回值可以选取一定范围内的多种类型，从而实现代码重用。

• 是一种参数化类型的类，是类的生成器

1)引入类模板的优势

template <class T>     //可以存放任何对象的栈
class Stack
{
public:
    Stack(int = 10);
    ~Stack()
    {
        delete [] stackPtr;
    }
    int push(const T&);
    int pop(T&);
    int isEmpty() { return top == -1; }
    int isFull() { return top == size - 1; }
private:
    int size;
    int top;
    T* stackPtr;
};

2)类模板的定义

• 类模板的定义

template<模板参数表>

class 类名

{ //类的实现部分 };

• 模板参数表

  class /typename 标识符

• 用类模板定义对象的格式是：

  类名<模板实参表> 对象名(构造函数实参表)；

Stack<int> sk;

Stack<string> stk(10);

3)类模版成员

• 类模板成员函数的定义

template<模板参数表>
类型 类名<模板形参>：：函数名（参数列表）
{
//实现部分
}
​
template<class T>
Stack<T>::Stack(int size){}
​
template <class T>
int Stack<T>::push(const T &i){}
​
template <class T>
int Stack<T>::pop(T &i){}

4)类模版的派生与继承

• 继承与派生方式

  • 公有继承

  • 私有继承

  • 保护继承

• 访问控制与一般的类一致

• 常见继承与派生情况

  • 普通类继承类模板

  • 模板类继承普通类

  • 模板类继承模板类

  • 模板类继承模板参数给出的基类

5)普通类继承类模板

• 普通类继承类模板

  通过继承类模板的一个实例来声明一个类

template<class T>
class A
{
public:
    A(){}
private:
    T data;
……
};
​
class B:public A<int>
{
    ……
};

6)模板类继承普通类

class A
{
    ……
};
​
template<class T>
class B:public A
{
public:
    B(){}
private:
    T data;
……
};

7)模板类继承模板类

• 模板类继承模板类

template<class T>
class Base
{
    T data1;
    ……
};
​
template<class T1,class T2>
class Derived:public Base<T1>
{
    T2 data2;
    ……
};

8)模板类继承模板参数给出的基类

#include<iostream>
using namespace std;
class BaseA
{
public:
    BaseA(){cout<<"BaseA found"<<endl;}
};
​
class BaseB
{
public:
    BaseB(){cout<<"BaseB found"<<endl;}
};
​
template<typename T,int value>
class BaseC
{
private:
    T data;
public:
    BaseC(T n=value):data(n){
    cout<<"BaseC found "<<data<<endl;}
};
​
template<class T>
class Derived:public T
{
public:
    Derived():T(){cout<<"Derived found"<<endl;}
};
​
int main()
{
    Derived<BaseA> x; // BaseA作为基类
    Derived<BaseB> y; // BaseB作为基类
    Derived<BaseC<int,3> > z;// BaseC<int,3>作为基类
}

9)类的模板成员

• 类的模板成员在类内部与一般模板函数实现方法一致

template<class T>
class Base
{
public:
template <typename V> void fun(const V&);
};

• 类的模板成员函数，在类外部实现时必须包含所有模板的形参表

template <class T> template <typename V>
void Base<T>::fun(const V &t)
{
}

7.STL概述

• STL是C++标准程序库的核心，深刻影响了标准程序库的整体结构，是泛型(generic）程序库，利用先进、高效的算法来管理数据。

• STL 的特点是数据结构和算法的分离。尽管这是个简单的概念，但这种分离确实使得 STL 变得非常通用。

1)STL六大组件

2)STL的作用

在 C++ 支持模板功能，引入了泛型编程思想的基础上，C++程序员们想编写出很多通用的针对不同数据类型的算法，其中 STL 脱颖而出成为 C++ 标准，并被引入 C++ 标准程序库。

STL 是一个具有高度可用性、高效的模板库，该库包含了诸多在计算机科学领域中常用的基础数据结构和算法，掌握了STL 标准，很多功能就无需自己费心费力的去实现了（不用重复的造轮子），直接拿来用即可。

STL 模板库是 C++ 标准程序库的重要组成部分，为 C++ 程序员提供了大量的可扩展的程序框架，高度实现了代码的可重用性，并且它是内置的，不需要额外安装，使用非常方便。

3)STL 容器种类和功能

4)STL容器的共通能力

• 所有容器中存放的都是值而非引用，即容器进行安插操作时内部实施的是拷贝操作。因此容器的每个元素必须能够被拷贝。如果希望存放的不是副本，容器元素只能是指针。

• 所有元素都形成一个次序（order），可以按相同的次序一次或多次遍历每个元素

• 各项操作并非绝对安全，调用者必须确保传给操作函数的参数符合需求，否则会导致未定义的行为

5)STL容器元素的条件

• 必须能够通过拷贝构造函数进行复制

• 必须可以通过赋值运算符完成赋值操作

• 必须可以通过析构函数完称销毁动作

• 序列式容器元素的默认构造函数必须可用

• 某些动作必须定义operator == ，例如搜寻操作

• 关联式容器必须定义出排序准则，默认情况是重载

  operator <

对于基本数据类型（int, long, char, double,…）而言，

以上条件总是满足

6)STL容器的共通操作（一）

// 产生一个空容器
    std::list<int> l;
// 以另一个容器元素为初值完成初始化
    std::list<int> l;
    …
    std::vector<float> c(l.begin(),l.end());
// 以数组元素为初值完成初始化
int array[]={2,4,6,5};
…
std::set<int> c(array, array+sizeof(array)/sizeof(array[0]));

7)STL容器的共通操作（二）

• 与大小相关的操作（size operator）

  • size()－返回当前容器的元素数量

  • empty()－判断容器是否为空

  • max_size()－返回容器能容纳的最大元素数量

• 比较（comparison）

  • == ,!= ,<,<= ,>,>=

  • 比较操作两端的容器必须属于同一类型

  • 如果两个容器内的所有元素按序相等，那么这两个容器相等

  • 采用字典式顺序判断某个容器是否小于另一个容器

• 赋值（assignment）和交换（swap）

  • swap用于提高赋值操作效率

8)STL容器的共通操作（三）

• 与迭代器（iterator）相关的操作

  • begin()－返回一个迭代器，指向第一个元素

  • end()－返回一个迭代器，指向最后一个元素之后

  • rbegin()－返回一个逆向迭代器，指向逆向遍历的第一个元素

  • rend()－返回一个逆向迭代器，指向逆向遍历的最后一个元素之后

• 元素操作

  • insert(pos,e)－将元素e的拷贝安插于迭代器pos所指的位置

  • erase(beg,end)－移除[beg，end]区间内的所有元素

  • clear()－移除所有元素

8.序列式容器

1)STL序列式容器

所谓序列式容器，即以线性排列（类似普通数组的存储方式）来存储某一指定类型（例如 int、double 等）的数据，需要特殊说明的是，该类容器并不会自动对存储的元素按照值的大小进行排序。

序列容器只是一类容器的统称，并不指具体的某个容器，序列容器大致包含以下几类容器：

array（数组容器）：表示可以存储 N 个 T 类型的元素，是 C++ 本身提供的一种容器。此类容器一旦建立，其长度就是固定不变的，这意味着不能增加或删除元素，只能改变某个元素的值；

vector（向量容器）：用来存放 T 类型的元素，是一个长度可变的序列容器，即在存储空间不足时，会自动申请更多的内存。使用此容器，在尾部增加或删除元素的效率最高（时间复杂度为 O(1) 常数阶），在其它位置插入或删除元素效率较差（时间复杂度为 O(n) 线性阶，其中 n 为容器中元素的个数）；

deque（双端队列容器）：和 vector 非常相似，区别在于使用该容器不仅尾部插入和删除元素高效，在头部插入或删除元素也同样高效，时间复杂度都是 O(1)常数阶，但是在容器中某一位置处插入或删除元素，时间复杂度为 O(n) 线性阶；

list（链表容器）：是一个长度可变的、由 T 类型元素组成的序列，它以双向

链表的形式组织元素，在这个序列的任何地方都可以高效地增加或删除元素（时间复杂度都为常数阶 O(1)），但访问容器中任意元素的速度要比前三种容器慢，这是因为 list<T> 必须从第一个元素或最后一个元素开始访问，需要沿着链表移动，直到到达想要的元素。

forward_list（正向链表容器）：和 list 容器非常类似，只不过它以单链表的形式组织元素，它内部的元素只能从第一个元素开始访问，是一类比链表容器快、更节省内存的容器。

2)序列式容量

3)vector容器

• vector模拟动态数组

• vector的元素可以是任意类型T，但必须具备赋值和拷贝能力（具有public拷贝构造函数和重载的赋值操作符）

• 必须包含的头文件#include

• vector支持随机存取

• vector的大小（size）和容量（capacity）通常是不同的，size返回实际元素个数，capacity返回vector能容纳的元素最大数量。如果插入元素时，元素个数超过capacity，需要重新配置内部存储器。

• 

4)deque容器

• deque模拟动态数组

• deque的元素可以是任意类型T，但必须具备赋值和拷贝能力（具有public拷贝构造函数和重载的赋值操作符）

• 必须包含的头文件#include

• deque支持随机存取

• deque支持在头部和尾部存储数据

• deque不支持capacity和reserve操作

  

5)list容器

• 使用双向链表管理元素

• list的元素可以是任意类型T，但必须具备赋值和拷贝能力

• 必须包含的头文件#include

• list不支持随机存取，因此不提供下标操作符

• 在任何位置上执行元素的安插和移除都非常快。

• 插入和删除不会导致指向其他元素的指针、引用、iterator失效。

总结：顺序容器

顺序容器类的共同特征：

• 元素既然有顺序就有顺序号（索引号）： 位置Pos，也就是可以通过顺序号（索引号）访问该元素

• 取得已知元素的顺序号

• 在指定位置(顺序号)处插入数据项

• 删除指定项后的Count项，或删除指定范围中的数据项

• front—第一个元素引用

• back—最后一个元素引用

• push_back 在容器尾部插入一个新元素

• pop_back 在容器尾部删除一个元素

9.STL ITERATOR

1)迭代器（iterator）

• 可遍历STL容器内全部或部分元素的对象

• 指出容器中的一个特定位置

• 迭代器的基本操作

• 所有容器都提供获得迭代器的函数

半开区间[beg, end)的好处：

1. 为遍历元素时循环的结束时机提供了简单的判断依据（只要未到达end()，循环就可以继续）

1. 不必对空区间采取特殊处理（空区间的begin()就等于end()）

• 所有容器都提供两种迭代器

  • container::iterator以“读/写”模式遍历元素

  • container::const_iterator以“只读”模式遍历元素

• 迭代器示例：iterator

2)迭代器的分类

• 双向迭代器<reverse_iterator>

  • 可以双向行进,以递增运算前进或以递减运算后退。

  • list、set和map提供双向迭代器

• 随机存取迭代器

  • 除了具备双向迭代器的所有属性，还具备随机访问能力。

  • 可以对迭代器增加或减少一个偏移量、处理迭代器之间的距离或者使用<和>之类的关系运算符比较两个迭代器。

  • vector、deque和string提供随机存取迭代器

10.STL ALGORITHMS

1)STL算法

• STL通过通用的模板函数提供这些算法以及其他很多的算法，可以通过迭代器对容器进行操作。

• STL头文件

  • <algorithm>：STL中的算法函数基本库

  • <numeric>：对于数值算法须包含；

  • <functional>：定义了一些模板类，用来声明函数对象

• STL算法分为：

  • 非变序算法

    • 如计数、搜索、比较

  • 变序算法

    • 如初始化、修改、复制、删除、替换、排序、分区

2)非变序算法

• 一组不破坏操作数据的模板函数，用来对序列数据进行逐个处理、元素查找、子序列搜索、统计和匹配。

• 非变序算法具有极为广泛的适用性，基本上可应用与各种容器。

• 算法简述：

  • 查找容器元素find

  • 条件查找容器元素find_if

  • 统计等于某值的容器元素个数count

  • 条件统计count_if

  • 子序列搜索search

  • …

3)变异算法

• 一组能够修改容器元素数据的模板函数。

  copy(v.begin(),v.end(),l.begin());将v中的元素复制到l中。

• 算法简述：

  • 元素复制copy

  • 元素变换transform改变

  • 替换replace

  • 条件替换replace_if： replace_if(v.begin(),v.end(),odd,100);

  • n次填充fill_n： fill_n(v.begin(),5,-1)；

  • 随机生成n个元素generate： generate_n(v.begin(),5,rand);

  • 条件移除remove_if：remove_if(v.begin(),v.end(),even);

  • …

11.ASSOCIATIVE CONTAINERS

1)关联式容器

• 关联式容器－排列顺序取决于特定准则

2)set/multiset容器

• set 和multiset容器的内部结构通常由平衡二叉树(balancedbinary tree)来实现。

• 平衡二叉检索树使用中序遍历算法，检索效率高于vector、deque和list等容器，另外使用中序遍历可将键值按照从小到大遍历出来。

• 构造set集合主要目的是为了快速检索，不可直接去修改键值。

• 必须包含的头文件#include

3)map/multimap容器

• 使用平衡二叉树管理元素

• 元素包含两部分(key,value)，key和value可以是任意类型

• 必须包含的头文件#include

• 根据元素的key自动对元素排序，因此根据元素的key进行定位很快，但根据元素的value定位很慢

• 不能直接改变元素的key，可以通过operator []直接存取元素值

• map中不允许key相同的元素，multimap允许key相同的元素

• 内部存储结构

12.CONTAINER ADAPTORS

1)容器适配器

• 非第一类容器,其最大特点为不提供存放数据的实际数据结构的实现方法, 而是依赖于三种基础的容器(顺序容器)

• 容器适配器不支持迭代器

• 特别提供了pop, push 成员函数,实现删除和插入的操作

• 有三种容器适配器:

  • stack (后进先出)

  • queue (先进先出)

  • priority_queue(优先级队列)

2)stack容器

• 后进先出（LIFO）

#include <stack>

• 核心接口（API）

  • push(value)－将元素压栈

  • top()－返回栈顶元素，但不移除

  • pop()－从栈中移除栈顶元素，但不返回

• 实例：stack

3)queue容器

• 先进先出（FIFO）

#include <queue>

• 核心接口

  • push(value)－将元素置入队列

  • front()－返回队列头部元素，但不移除

  • back()－返回队列尾部元素，但不移除

  • pop()－从队列中移除元素，但不返回

• 实例：queue

4)priority_queue适配器

• 不管入队顺序如何，每次出队的都是最大值。

• 可以用顺序容器vector, deque实现

• 默认情况下，priority_queue用vector实现

• 常见的成员函数:

  • push() 按照优先顺序将元素插入到合适的位置上(先调用基础容器的push_back, 再用堆排序排列元素)

  • pop() 删除居首位置的最大元素

  • top() 取居首位置的最大元素

  • empty() 判断是否为空(调用基础容器的empty函数)

  • size() 取得元素的个数(调用基础容器的size函数)

• 头文件<queue>