第九章 模 板本章主要内容
1,模板的概念
2,函数模板
3,类模板
4,容器与迭代子
21:17:57
§ 1 模板的概念
模板用于表达逻辑结构相同,但具体数据元素类型不同的数据对象的通用行为,是开发大型软件,建立通用函数库和类库的强有力的工具
类属机制：把函数或类要处理的数据类型参数化，表现为参数的多态性
C++中有两种模板
1,函数模板
2,类模板
21:17:57
模板存在的必要性
int abs(int x){return x>0?x:-x;}
double abs(double x){return x>0?x:-x;}
long abs(long x){return x>0?x:-x;}
int main(){
cout << abs(-10) << ends
<< abs(-10.5) << ends
<< abs(-1000000L) << endl;
return 0;
}
1,函数重载重载的多个函数只是处理的数据的类型不一样,除此之外,
其它操作完全一样,但针对每种数据类型都必须实现一个函数完成相应的操作
21:17:57
解决办法：
把要操作的数据的类型做为函数或类的参数
2,链表类
class LINKLIST{
struct NODE {
int i;
NODE * next;
}*head;
public:
LINKLIST();
LINKLIST(LINKLIST &);
～ LINKLIST();
void Create();
void Insert(int i);
void Remove(int i);
NODE *Find(int i);
};
本链表类中只能保存整型数据,若要保存其它类型的数据,必须另外创建一个类,但类的结构,实现代码几乎一样,只是其中的 int
被相应的数据类型替换问题：
对不同的数据类型,代码存在冗余,不利于代码重用模板：
定义函数或创建类时,把数据的类型做为形式参数,调用函数或定义对象时传以要处理数据的类型做为实际参数
21:17:57
§ 2 函数模板
定义语法,使用关键字 template
template <typename 类型形式参数表 >
返回值类型 函数名 (函数的形式参数表）
{ 函数体； }
例：函数模板
1,abs()函数
template <typename T>
T Tabs(T x)
{
return x>0?x:-x;
}
void main(){
cout<<Tabs(10)<<endl;
cout<<Tabs(-10.5)<<endl;
cout<<Tabs(-1000000)<<endl;
}
21:17:57
2,Max()函数
template <typename T>
T Max(T x,T y)
{
if (x>y)
return x;
else
return y;
}
void main()
{
cout<<Max(10,20)<<endl;
cout<<Max(10.0,20.0)<<endl;
cout<<Max('A','B')<<endl;
}
21:17:57
3,冒泡排序的函数模板
template <typename ElementType>
void SortBubble(ElementType *a,int size){
int i,work;
ElementType temp;
for(int pass =1;pass<size;pass++){
work = 1;
for(i=0;i<size-pass;i++){
if(a[i]>a[i+1]){
temp = a[i];a[i] = a[i+1];a[i+1] = temp;
work = 0;
}
}
if (work) break;
}
}
21:17:57
关于函数模板的说明
函数模板定义中类型形式参数表中的类型在函数模板的定义中至少要使用一次
类型形式参数表中的类型不能是具体的某种类型,只能是
,通用,类型
编译时对函数模板不产生可执行代码 （ 为什么？ ）
函数模板可直接调用例,abs(-100000);
编译时,根据传递给函数的实参的类型,确认是否与函数模板中对应的形参相匹配,若匹配则实参的类型替换函数模板的函数形参列表中出现的类型参数,产生一个重载的函数,该函数称为 模板函数
21:17:57
函数模板可以重载：同一个函数模板得到的模板函数之间是重载关系
template <typename T>
T Max(T a,T b)
{
return a>b?a:b;
}
1,函数模板之间的重载
template <typename T>
T Max(T a,T b,T c)
{
return a>b?(a>c?a:c):(b>c?b:c);
}
void main(){
cout << Max(12,120) << endl;
cout << Max(10.0,100.0) << endl;
cout << Max(12,120,1200) << endl;
cout << Max(10.0,100.0,1000.0) << endl;
}
21:17:57
2,函数模板与普通函数之间的重载
template <typename T> char* Max(char *a,char *b)
T Max(T a,T b) {
{ if (strcmp(a,b)>0) return a;
return a>b?a:b; else return b;
} }
void main(){
cout << Max(12,120) << endl;
cout << Max(12.5,120.5) << endl;
cout << Max("ABCDE","abcde") << endl;
}
21:17:57
函数模板的说明（续）
程序中有同名的函数模板与普通函数时,函数调用的匹配顺序为：
.先检查普通函数,若参数数目,类型都能匹配,则调用该普通函数
.否则检查是否有函数模板,能将实参类型代入后产生模板函数,若有则调用该模板函数
.否则尝试将实参进行类型转换,转换后若能与某个 普通函数 匹配,则调用该普通函数
.否则报错
函数模板不允许进行类型转换例,Max(10,’a’);
21:17:57
§ 3 类模板
定义语法：使用关键字 template
template <typename 类型形参 列 表 >
class 类名
{
//类成员
}；
template <typename T>
class LINKLIST
{
struct NODE{
T i;
NODE * next;
}*head;
public:
LINKLIST();
LINKLIST(LINKLIST &);
～ LINKLIST();
void Create();
void Insert(T i);
void Remove(T i);
NODE *Find(T i);
};
类型形参列表 中的类型在类中必须至少使用一次
21:17:57
类模板成员函数的定义
在类模板中定义与普通类的成员函数在类中定义一样,该函数将自动成为 inline函数
在类模板外定义一般形式为：
template <typename 类型形参 列 表 >
返回值类型 类名 <类型形参列表 >::成员函数名 (形参列表 )
{
//函数体
}
21:17:57
例：数组类模板
template <typename T>
class Array
{
public:
Array(int s);
virtual ～ Array();
virtual const T& Entry(int index) const;
virtual void Enter(int index,const T& value);
protectd:
int size;
T * element;
};
21:17:57
类模板成员函数的实现
template <typename T> Array<T>::Array(int s){
if(s>1) size = s;
else size = 1;
element = new T[size];
}
template <typename T> Array<T>::～ Array()
{delete []element;}
template <typename T>const T& Array<T>::
Entry(int index)const
{return element[index];}
template <typename T> void Array<T>::Enter(int index,
const T& value)
{element[index] = value;}
21:17:57
类模板的使用：创建对象
使用类模板创建对象时,把类模板的类型形参列表用实际的数据类型替换,将会得到一个类,该类称为 模板类,创建的对象是模板类的对象
创建对象的语法类名 <实参类型列表 > 对象名；
void main(){
Array<int> IntAry(5);int i;
for(i=0;i<5;i++) IntAry.Enter(i,i);
cout << "Integer Array:\n";
for(i=0;i<5;i++) cout << IntAry.Entry(i) << '\t';
cout << endl;
Array<double> DouAry(5);
for(i=0;i<5;i++) DouAry.Enter(i,(i+1)*0.35);
cout << "Double Array,\n";
for(i=0;i<5;i++) cout << DouAry.Entry(i) << '\t';
cout << endl;
}
编译时编译器不为类模板生成代码生成模板类时需要类模板的全部信息,
所以类模板的声明与类模板成员函数的定义一般放在同一个文件中类模板是类的类 — 类属类
21:17:57
类模板作为函数参数
一个函数拥有类模板参数时,该函数必为函数模板
调用该函数时,实参是该类模板实例化后得到的模板类的对象
template <typename T>
void Tfun(const Array<T> & x,int index)
{
cout << x.Entry(index) << endl;
}
Array <double> DouAry(5);
TFun(DouAry,3);
21:17:57
类层次中的类模板：类模板可以继承
在类的层次中，类模板既可以是基类，也可以是派生类
普通类做基类，派生出类模板
class CB{
int i;
public:
CB(int ii){i=ii;}
int geti(){return i;}
};
template <typename T>
class CA:public CB{
T t;
public:
void putT(T &tt){t = tt;}
};
21:17:57
类模板作基类，派生出类模板
template <typename T>
class BoundArray:public Array<T>{
int min;
public:
BoundArray(int low=0,int height=1);
virtual const T& Entry(int index)const;
virtual void Enter(int index,const T& value);
};
template <typename T>
BoundArray<T>::BoundArray(int low,int height)
:Array<T>(height-low+1){
if(height - low < 0){
cout << "Beyond the bounds of Array." << endl;
exit(1);
}
min = low;
}
21:17:57
类模板作基类（续）
template <typename T>
const T& BoundArray<T>::Entry(int index) const{
if(index < min || index > min+size-1){
cout << "Beyond the bounds of index." << endl;
exit(1);
}
return Array<T>::Entry(index - min);
}
template <typename T>
void BoundArray<T>::Enter(int index,const T&
value){
if(index < min || index > min+size-1){
cout << "Beyond the bounds of index." << endl;
exit(1);
}
Array<T>::Enter(index - min,value);
}
21:17:57
§ 4 容器、迭代器和算法
C++提供了一个包含许多组件的标准模板库 (STL:Standard
Template Library)
STL中有 3个主要组成部分：容器,迭代器和算法
容器
容器是数据结构,是包含对象的对象
例：数组,队列,栈,树,图等数据结构中的每一个结点都是对象,这些结构按某种特定的逻辑形式把数据对象组装起来,形成一个新的对象 -- 即包含对象的对象
21:17:57
容器分类
1.顺序容器,提供顺序表的表示和操作
vector(向量 ),deque(双向队列 ),list(双向链表 )
2.关联容器,提供集合和映像的表示和操作
set(集合 )：不允许重复值
multiset(集合 )：允许重复值
map(映射 )：一对一映射,不允许重复值
multimap(映射 )：一对多映射,允许重复值
3.容器适配器,特殊顺序表
stack(栈 )：后进先出 (LIFO)表
queue(队列 )：先进先出 (FIFO)表
priority_queue(优先队列 )：优先级高的元素先出列
21:17:57
vector
随机访问序列中的单个元素,在序列尾快速插入和删除元素,能够实现数据结构中的数组,队列和栈的所有功能
常用的成员函数
[],at(int i)：引用向量中的第 i个元素
back(),返回向量中中最后一个元素的引用
front(),返回向量中第一个元素的引用
push_back(const T&val),在向量中最后一个元素后面插入 val引用的元素
pop_back(),删除向量中最后一个元素
insert(iterator pos,const T&val),在向量中 pos位置插入 val引用的元素,返回插入位置
erase(iterator pos）,删除 pos位置处的元素
clear()：删除向量中的所有元素
capacity(),数组长度
empty(),判断向量中是否有元素
21:17:57
例：向量的使用
#include <iostream>
#include <vector>
using namespace std;
int main(){
vector<int> vI;
int i;
//用作数组 —— 动态数组：其长度可调
cout << "using as dynamic array" << endl;
vI.reserve(10);//将数组长度设为 10— vI.resize(1000);
for(i=0;i<8;i++) vI[i]=i;
for(i=0;i<8;i++)cout << vI[i] << " " ;
cout << endl;
cout << vI.capacity() << endl;
21:17:57
例：向量的使用（续）
//用作栈：
cout << "using as stack:" << endl;
vector<double> vD;
for(i=1;i<=100;i++)
vD.push_back(i);
for(;!vD.empty();){
cout << vD.back() << " ";
vD.pop_back();
}
cout << endl;
//用作队列
cout << "using as queue:" <<endl;
vector <float> vF;
for(i=1;i<20;i++)vF.push_back(i);
for(;!vF.empty();){
cout << vF.front() << " ";
vF.erase(vF.begin());
}
cout << endl;
return 0;
}
21:17:57
迭代子,iterator
使用容器类时,有时仅依靠一些成员函数还不能对其中的元素进行灵活的访问
可以定义一个与指针变量类似的对象,让其指向容器对象中的不同元素,并按照指定的偏移量和指定的方式在容器对象中向前或向后移动,指向容器中所有的元素,通过它对所指向的元素进行访问 —— 这种对象称为 迭代子或迭代算子或迭代器
STL容器类预定义了一些迭代器类型类型 ++ 操作的方向 功能
iterator 向前 读／写
const_iterator 向前 读
reverse_iteator 向后 读／写
const_reverse_iterator 向后 读
21:17:57
例：迭代子的使用
#include <iostream>
#include <vector>
#include <iterator>
using namespace std;
int main(){
vector<int> vI;
int i;
for(i=1;i<=20;i++)vI.push_back(i);
//using const_iterator
cout << "using const_iterator:" << endl;
vector<int>::const_iterator icfPos;
icfPos=vI.begin();
for(;icfPos!=vI.end();icfPos++)
cout << *icfPos << " ";
cout << endl;
21:17:57
例：迭代子的使用 (续 )
//using iterator
cout << "using iterator:" << endl;
vector<int>::iterator ifPos;
ifPos=vI.begin();
for(;ifPos!=vI.end();ifPos++){
*ifPos=*ifPos*2;
cout << *ifPos << " ";
}
cout << endl;
//using reverse_iterator
cout << "using reverse_iterator:" << endl;
vector<int>::reverse_iterator irPos;
irPos=vI.rbegin();
for(;irPos!=vI.rend();irPos++){
*irPos=*irPos / 2 ;
cout << *irPos << " ";
}
cout << endl;
return 0;
}
21:17:57
list类：双向链表类
用动态链式结构存入数据,可以从任何位置快速插入和删除元素
list容器不支持随机访问,所以不能使用 opeator[]和 at()
除此之外,list提供 vector的所有功能,并且增加了如下成员函数
merge()
void merge(list& x);
void merge(list& x,greater<T> pr);
sort()
void sort();
template<class Pred>void sort(greater<T> pr);
21:17:57
push_front()
void push_front(const T& x);
pop_front()
void pop_front();
#include <iostream>
#include <list>
#include <iterator>
using namespace std;
int main(){
list<int> lI;
int i;
for(i=1;i<10;i++)lI.push_back(i);
for(i=10;i<20;i++)lI.push_front(i);
list<int>::iterator iPos;
for(iPos=lI.begin();iPos!=lI.end();iPos++)
cout << *iPos << " ";
cout << endl;
lI.sort();
for(iPos=lI.begin();iPos!=lI.end();iPos++)
cout << *iPos << " ";
cout << endl;
return 0;
}
21:17:57
算法,STL中包含了约 70余种算法
查找
1.find():返回容器指定范围中元素值等于给定值的元素的迭代子
template<typename InIt,typename T>
InIt find(InIt first,InIt last,const T& val);
2.find_if():从容器的指定范围内查找,返回第一个满足测试条件的元素的迭代子
template<class InIt,class Pred>
InIt find_if(InIt first,InIt last,Pred pr);
21:17:57
例：查找
#include <iostream>
#include <vector>
#include <iterator>
#include <algorithm>
using namespace std;
bool greaterthan10(int value){return value > 10;}
int main(){
vector<int> vctI;
vector<int>::iterator iPos;
vctI.push_back(1); vctI.push_back(100);
vctI.push_back(25);vctI.push_back(18);
vctI.push_back(56); vctI.push_back(87);
iPos=find(vctI.begin(),vctI.end(),25);
cout << *iPos << endl;
iPos=find_if(vctI.begin(),vctI.end(),greaterthan10);
cout << *iPos << endl;
return 0;
}
21:17:57
排序
sort()
template<typename RanIt>
void sort(RanIt first,RanIt last);
template<typename RanIt,typename Pred>
void sort(RanIt first,RanIt last,Pred pr);
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
bool Descending(int a,int b){ return a>b;}
int main(){
vector<int> vctI;
int i;
for(i=1;i<=10;i++)vctI.push_back(i);
for(i=11;i<=20;i++)vctI.insert(vctI.begin(),i);
21:17:57
例：排序 (续 )
cout << "Not Sorted,";
vector<int>::iterator iPos;
for(iPos=vctI.begin();iPos!=vctI.end();iPos++)
cout << *iPos << " ";
cout << endl;
cout << "Sorted Ascending,";
sort(vctI.begin(),vctI.end());
for(iPos=vctI.begin();iPos!=vctI.end();iPos++)
cout << *iPos << " ";
cout << endl;
cout << "Sorted Descending,";
sort(vctI.begin(),vctI.end(),Descending);
for(iPos=vctI.begin();iPos!=vctI.end();iPos++)
cout << *iPos << " ";
cout << endl;
return 0;
}
21:17:57
折半查找
binary_search()
template<typename FwdIt,typename T>
bool binary_search(FwdIt first,FwdIt last,
const T& val);
template<typename FwdIt,typename T,typename Pred>
bool binary_search(FwdIt first,FwdIt last,
const T& val,Pred pr);
21:17:57
1,模板的概念
2,函数模板
3,类模板
4,容器与迭代子
21:17:57
§ 1 模板的概念
模板用于表达逻辑结构相同,但具体数据元素类型不同的数据对象的通用行为,是开发大型软件,建立通用函数库和类库的强有力的工具
类属机制：把函数或类要处理的数据类型参数化，表现为参数的多态性
C++中有两种模板
1,函数模板
2,类模板
21:17:57
模板存在的必要性
int abs(int x){return x>0?x:-x;}
double abs(double x){return x>0?x:-x;}
long abs(long x){return x>0?x:-x;}
int main(){
cout << abs(-10) << ends
<< abs(-10.5) << ends
<< abs(-1000000L) << endl;
return 0;
}
1,函数重载重载的多个函数只是处理的数据的类型不一样,除此之外,
其它操作完全一样,但针对每种数据类型都必须实现一个函数完成相应的操作
21:17:57
解决办法：
把要操作的数据的类型做为函数或类的参数
2,链表类
class LINKLIST{
struct NODE {
int i;
NODE * next;
}*head;
public:
LINKLIST();
LINKLIST(LINKLIST &);
～ LINKLIST();
void Create();
void Insert(int i);
void Remove(int i);
NODE *Find(int i);
};
本链表类中只能保存整型数据,若要保存其它类型的数据,必须另外创建一个类,但类的结构,实现代码几乎一样,只是其中的 int
被相应的数据类型替换问题：
对不同的数据类型,代码存在冗余,不利于代码重用模板：
定义函数或创建类时,把数据的类型做为形式参数,调用函数或定义对象时传以要处理数据的类型做为实际参数
21:17:57
§ 2 函数模板
定义语法,使用关键字 template
template <typename 类型形式参数表 >
返回值类型 函数名 (函数的形式参数表）
{ 函数体； }
例：函数模板
1,abs()函数
template <typename T>
T Tabs(T x)
{
return x>0?x:-x;
}
void main(){
cout<<Tabs(10)<<endl;
cout<<Tabs(-10.5)<<endl;
cout<<Tabs(-1000000)<<endl;
}
21:17:57
2,Max()函数
template <typename T>
T Max(T x,T y)
{
if (x>y)
return x;
else
return y;
}
void main()
{
cout<<Max(10,20)<<endl;
cout<<Max(10.0,20.0)<<endl;
cout<<Max('A','B')<<endl;
}
21:17:57
3,冒泡排序的函数模板
template <typename ElementType>
void SortBubble(ElementType *a,int size){
int i,work;
ElementType temp;
for(int pass =1;pass<size;pass++){
work = 1;
for(i=0;i<size-pass;i++){
if(a[i]>a[i+1]){
temp = a[i];a[i] = a[i+1];a[i+1] = temp;
work = 0;
}
}
if (work) break;
}
}
21:17:57
关于函数模板的说明
函数模板定义中类型形式参数表中的类型在函数模板的定义中至少要使用一次
类型形式参数表中的类型不能是具体的某种类型,只能是
,通用,类型
编译时对函数模板不产生可执行代码 （ 为什么？ ）
函数模板可直接调用例,abs(-100000);
编译时,根据传递给函数的实参的类型,确认是否与函数模板中对应的形参相匹配,若匹配则实参的类型替换函数模板的函数形参列表中出现的类型参数,产生一个重载的函数,该函数称为 模板函数
21:17:57
函数模板可以重载：同一个函数模板得到的模板函数之间是重载关系
template <typename T>
T Max(T a,T b)
{
return a>b?a:b;
}
1,函数模板之间的重载
template <typename T>
T Max(T a,T b,T c)
{
return a>b?(a>c?a:c):(b>c?b:c);
}
void main(){
cout << Max(12,120) << endl;
cout << Max(10.0,100.0) << endl;
cout << Max(12,120,1200) << endl;
cout << Max(10.0,100.0,1000.0) << endl;
}
21:17:57
2,函数模板与普通函数之间的重载
template <typename T> char* Max(char *a,char *b)
T Max(T a,T b) {
{ if (strcmp(a,b)>0) return a;
return a>b?a:b; else return b;
} }
void main(){
cout << Max(12,120) << endl;
cout << Max(12.5,120.5) << endl;
cout << Max("ABCDE","abcde") << endl;
}
21:17:57
函数模板的说明（续）
程序中有同名的函数模板与普通函数时,函数调用的匹配顺序为：
.先检查普通函数,若参数数目,类型都能匹配,则调用该普通函数
.否则检查是否有函数模板,能将实参类型代入后产生模板函数,若有则调用该模板函数
.否则尝试将实参进行类型转换,转换后若能与某个 普通函数 匹配,则调用该普通函数
.否则报错
函数模板不允许进行类型转换例,Max(10,’a’);
21:17:57
§ 3 类模板
定义语法：使用关键字 template
template <typename 类型形参 列 表 >
class 类名
{
//类成员
}；
template <typename T>
class LINKLIST
{
struct NODE{
T i;
NODE * next;
}*head;
public:
LINKLIST();
LINKLIST(LINKLIST &);
～ LINKLIST();
void Create();
void Insert(T i);
void Remove(T i);
NODE *Find(T i);
};
类型形参列表 中的类型在类中必须至少使用一次
21:17:57
类模板成员函数的定义
在类模板中定义与普通类的成员函数在类中定义一样,该函数将自动成为 inline函数
在类模板外定义一般形式为：
template <typename 类型形参 列 表 >
返回值类型 类名 <类型形参列表 >::成员函数名 (形参列表 )
{
//函数体
}
21:17:57
例：数组类模板
template <typename T>
class Array
{
public:
Array(int s);
virtual ～ Array();
virtual const T& Entry(int index) const;
virtual void Enter(int index,const T& value);
protectd:
int size;
T * element;
};
21:17:57
类模板成员函数的实现
template <typename T> Array<T>::Array(int s){
if(s>1) size = s;
else size = 1;
element = new T[size];
}
template <typename T> Array<T>::～ Array()
{delete []element;}
template <typename T>const T& Array<T>::
Entry(int index)const
{return element[index];}
template <typename T> void Array<T>::Enter(int index,
const T& value)
{element[index] = value;}
21:17:57
类模板的使用：创建对象
使用类模板创建对象时,把类模板的类型形参列表用实际的数据类型替换,将会得到一个类,该类称为 模板类,创建的对象是模板类的对象
创建对象的语法类名 <实参类型列表 > 对象名；
void main(){
Array<int> IntAry(5);int i;
for(i=0;i<5;i++) IntAry.Enter(i,i);
cout << "Integer Array:\n";
for(i=0;i<5;i++) cout << IntAry.Entry(i) << '\t';
cout << endl;
Array<double> DouAry(5);
for(i=0;i<5;i++) DouAry.Enter(i,(i+1)*0.35);
cout << "Double Array,\n";
for(i=0;i<5;i++) cout << DouAry.Entry(i) << '\t';
cout << endl;
}
编译时编译器不为类模板生成代码生成模板类时需要类模板的全部信息,
所以类模板的声明与类模板成员函数的定义一般放在同一个文件中类模板是类的类 — 类属类
21:17:57
类模板作为函数参数
一个函数拥有类模板参数时,该函数必为函数模板
调用该函数时,实参是该类模板实例化后得到的模板类的对象
template <typename T>
void Tfun(const Array<T> & x,int index)
{
cout << x.Entry(index) << endl;
}
Array <double> DouAry(5);
TFun(DouAry,3);
21:17:57
类层次中的类模板：类模板可以继承
在类的层次中，类模板既可以是基类，也可以是派生类
普通类做基类，派生出类模板
class CB{
int i;
public:
CB(int ii){i=ii;}
int geti(){return i;}
};
template <typename T>
class CA:public CB{
T t;
public:
void putT(T &tt){t = tt;}
};
21:17:57
类模板作基类，派生出类模板
template <typename T>
class BoundArray:public Array<T>{
int min;
public:
BoundArray(int low=0,int height=1);
virtual const T& Entry(int index)const;
virtual void Enter(int index,const T& value);
};
template <typename T>
BoundArray<T>::BoundArray(int low,int height)
:Array<T>(height-low+1){
if(height - low < 0){
cout << "Beyond the bounds of Array." << endl;
exit(1);
}
min = low;
}
21:17:57
类模板作基类（续）
template <typename T>
const T& BoundArray<T>::Entry(int index) const{
if(index < min || index > min+size-1){
cout << "Beyond the bounds of index." << endl;
exit(1);
}
return Array<T>::Entry(index - min);
}
template <typename T>
void BoundArray<T>::Enter(int index,const T&
value){
if(index < min || index > min+size-1){
cout << "Beyond the bounds of index." << endl;
exit(1);
}
Array<T>::Enter(index - min,value);
}
21:17:57
§ 4 容器、迭代器和算法
C++提供了一个包含许多组件的标准模板库 (STL:Standard
Template Library)
STL中有 3个主要组成部分：容器,迭代器和算法
容器
容器是数据结构,是包含对象的对象
例：数组,队列,栈,树,图等数据结构中的每一个结点都是对象,这些结构按某种特定的逻辑形式把数据对象组装起来,形成一个新的对象 -- 即包含对象的对象
21:17:57
容器分类
1.顺序容器,提供顺序表的表示和操作
vector(向量 ),deque(双向队列 ),list(双向链表 )
2.关联容器,提供集合和映像的表示和操作
set(集合 )：不允许重复值
multiset(集合 )：允许重复值
map(映射 )：一对一映射,不允许重复值
multimap(映射 )：一对多映射,允许重复值
3.容器适配器,特殊顺序表
stack(栈 )：后进先出 (LIFO)表
queue(队列 )：先进先出 (FIFO)表
priority_queue(优先队列 )：优先级高的元素先出列
21:17:57
vector
随机访问序列中的单个元素,在序列尾快速插入和删除元素,能够实现数据结构中的数组,队列和栈的所有功能
常用的成员函数
[],at(int i)：引用向量中的第 i个元素
back(),返回向量中中最后一个元素的引用
front(),返回向量中第一个元素的引用
push_back(const T&val),在向量中最后一个元素后面插入 val引用的元素
pop_back(),删除向量中最后一个元素
insert(iterator pos,const T&val),在向量中 pos位置插入 val引用的元素,返回插入位置
erase(iterator pos）,删除 pos位置处的元素
clear()：删除向量中的所有元素
capacity(),数组长度
empty(),判断向量中是否有元素
21:17:57
例：向量的使用
#include <iostream>
#include <vector>
using namespace std;
int main(){
vector<int> vI;
int i;
//用作数组 —— 动态数组：其长度可调
cout << "using as dynamic array" << endl;
vI.reserve(10);//将数组长度设为 10— vI.resize(1000);
for(i=0;i<8;i++) vI[i]=i;
for(i=0;i<8;i++)cout << vI[i] << " " ;
cout << endl;
cout << vI.capacity() << endl;
21:17:57
例：向量的使用（续）
//用作栈：
cout << "using as stack:" << endl;
vector<double> vD;
for(i=1;i<=100;i++)
vD.push_back(i);
for(;!vD.empty();){
cout << vD.back() << " ";
vD.pop_back();
}
cout << endl;
//用作队列
cout << "using as queue:" <<endl;
vector <float> vF;
for(i=1;i<20;i++)vF.push_back(i);
for(;!vF.empty();){
cout << vF.front() << " ";
vF.erase(vF.begin());
}
cout << endl;
return 0;
}
21:17:57
迭代子,iterator
使用容器类时,有时仅依靠一些成员函数还不能对其中的元素进行灵活的访问
可以定义一个与指针变量类似的对象,让其指向容器对象中的不同元素,并按照指定的偏移量和指定的方式在容器对象中向前或向后移动,指向容器中所有的元素,通过它对所指向的元素进行访问 —— 这种对象称为 迭代子或迭代算子或迭代器
STL容器类预定义了一些迭代器类型类型 ++ 操作的方向 功能
iterator 向前 读／写
const_iterator 向前 读
reverse_iteator 向后 读／写
const_reverse_iterator 向后 读
21:17:57
例：迭代子的使用
#include <iostream>
#include <vector>
#include <iterator>
using namespace std;
int main(){
vector<int> vI;
int i;
for(i=1;i<=20;i++)vI.push_back(i);
//using const_iterator
cout << "using const_iterator:" << endl;
vector<int>::const_iterator icfPos;
icfPos=vI.begin();
for(;icfPos!=vI.end();icfPos++)
cout << *icfPos << " ";
cout << endl;
21:17:57
例：迭代子的使用 (续 )
//using iterator
cout << "using iterator:" << endl;
vector<int>::iterator ifPos;
ifPos=vI.begin();
for(;ifPos!=vI.end();ifPos++){
*ifPos=*ifPos*2;
cout << *ifPos << " ";
}
cout << endl;
//using reverse_iterator
cout << "using reverse_iterator:" << endl;
vector<int>::reverse_iterator irPos;
irPos=vI.rbegin();
for(;irPos!=vI.rend();irPos++){
*irPos=*irPos / 2 ;
cout << *irPos << " ";
}
cout << endl;
return 0;
}
21:17:57
list类：双向链表类
用动态链式结构存入数据,可以从任何位置快速插入和删除元素
list容器不支持随机访问,所以不能使用 opeator[]和 at()
除此之外,list提供 vector的所有功能,并且增加了如下成员函数
merge()
void merge(list& x);
void merge(list& x,greater<T> pr);
sort()
void sort();
template<class Pred>void sort(greater<T> pr);
21:17:57
push_front()
void push_front(const T& x);
pop_front()
void pop_front();
#include <iostream>
#include <list>
#include <iterator>
using namespace std;
int main(){
list<int> lI;
int i;
for(i=1;i<10;i++)lI.push_back(i);
for(i=10;i<20;i++)lI.push_front(i);
list<int>::iterator iPos;
for(iPos=lI.begin();iPos!=lI.end();iPos++)
cout << *iPos << " ";
cout << endl;
lI.sort();
for(iPos=lI.begin();iPos!=lI.end();iPos++)
cout << *iPos << " ";
cout << endl;
return 0;
}
21:17:57
算法,STL中包含了约 70余种算法
查找
1.find():返回容器指定范围中元素值等于给定值的元素的迭代子
template<typename InIt,typename T>
InIt find(InIt first,InIt last,const T& val);
2.find_if():从容器的指定范围内查找,返回第一个满足测试条件的元素的迭代子
template<class InIt,class Pred>
InIt find_if(InIt first,InIt last,Pred pr);
21:17:57
例：查找
#include <iostream>
#include <vector>
#include <iterator>
#include <algorithm>
using namespace std;
bool greaterthan10(int value){return value > 10;}
int main(){
vector<int> vctI;
vector<int>::iterator iPos;
vctI.push_back(1); vctI.push_back(100);
vctI.push_back(25);vctI.push_back(18);
vctI.push_back(56); vctI.push_back(87);
iPos=find(vctI.begin(),vctI.end(),25);
cout << *iPos << endl;
iPos=find_if(vctI.begin(),vctI.end(),greaterthan10);
cout << *iPos << endl;
return 0;
}
21:17:57
排序
sort()
template<typename RanIt>
void sort(RanIt first,RanIt last);
template<typename RanIt,typename Pred>
void sort(RanIt first,RanIt last,Pred pr);
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
bool Descending(int a,int b){ return a>b;}
int main(){
vector<int> vctI;
int i;
for(i=1;i<=10;i++)vctI.push_back(i);
for(i=11;i<=20;i++)vctI.insert(vctI.begin(),i);
21:17:57
例：排序 (续 )
cout << "Not Sorted,";
vector<int>::iterator iPos;
for(iPos=vctI.begin();iPos!=vctI.end();iPos++)
cout << *iPos << " ";
cout << endl;
cout << "Sorted Ascending,";
sort(vctI.begin(),vctI.end());
for(iPos=vctI.begin();iPos!=vctI.end();iPos++)
cout << *iPos << " ";
cout << endl;
cout << "Sorted Descending,";
sort(vctI.begin(),vctI.end(),Descending);
for(iPos=vctI.begin();iPos!=vctI.end();iPos++)
cout << *iPos << " ";
cout << endl;
return 0;
}
21:17:57
折半查找
binary_search()
template<typename FwdIt,typename T>
bool binary_search(FwdIt first,FwdIt last,
const T& val);
template<typename FwdIt,typename T,typename Pred>
bool binary_search(FwdIt first,FwdIt last,
const T& val,Pred pr);
21:17:57
