泛型程序设计

泛型程序设计

编写不依赖于具体数据类型的程序
将算法从特定的数据结构中抽象出来，成为通用的
C++的模板为泛型程序设计奠定了关键的基础

概念和模型

概念

概念:
用来界定具备一定功能的数据类型。例如：
将“可以比大小的所有数据类型（有比较运算符）”这一概念记为Comparable
将“具有公有的复制构造函数并可以用”=”赋值的数据类型” 这一概念记为Assignable
将“可以比大小，具有公有的复制构造函数并可以用“=”赋值的所有数据类型 这一概念记作Sortable
对于两个不同概念的A和B ，如果概念A所需求的所有功能也是概念B所需求的功能，那么
就说概念B是概念A的子概念。 例如：
Sortable 既是Comparable的子概念 ，也是Assignable的子概念

模型

模型(model)：符合一个概念的数据类型称为该概念的模型，例如：
int 型是Comparable概念的模型
静态数组类型不是Assignable 概念的模型
（无法用 “=” 给整个静态数组赋值

用概念作模板参数名

为概念赋予一个名称，并使用该名称作为模板参数名
例如：
表示insertionSort这样一个函数模板的原型：

template<class Sortable>
void insertionSort(Sortable a[],int n)

STL

STL 简介
标准模板库，定义了一套概念体系，为泛型程序设计提供了逻辑基础
STL中的各个类模板，函数模板的参数都使用这个体系中的概念来规定的
使用STL的模板时，类型参数既可以是C++标准库中已有的类型，也可以是自定义的类型
只要这些类型是所要求概念的模型

STL基本组件

容器（container)
容纳，包含一组元素的对象。
基本容器类模板
顺序容器
array,vector,deque,forward_list,list
有序关联容器
set,multiset,map,multimap
无序关联容器
unordered_set,unordered_multiset
unordered_map ,unordered_multimap

容器适配器：
stack(栈)
queue（队列）
priority_queue(优先队列)

迭代器（iterator)
提供了顺序访问容器每一个元素的方法
可以使用“++”运算符来获得指向下一个元素的迭代器
可以使用“*”运算符防卫迭代器所指向的元素，如果元素类型是类或结构体，还可以使用
“->”运算符直接访问该元素的一个成员
有些迭代器还支持通过”–”运算符获得指向上一个元素的迭代器
迭代器是泛化的指针： 指针也具有同样的特性，因此指针本身就是一种迭代器
使用独立于STL容器的迭代器 ，需要包含头文件”iterator”

函数对象（function object)
一个行为类似函数的对象，对它可以像调用函数一样调用。
函数对象是泛化的函数：任何普通的函数和任何重载了“（）”运算符的类的对象都可以作为函数对象使用
使用STL的函数对象，需要包含头文件 “functional”

算法(algorithms)
可以广泛用于不同的对象和内置的数据类型
STL包括了70多个算法
例如：排序算法，消除算法，计数算法，比较算法，变换算法，置换算法和容器管理等
使用STL的算法，需要包含头文件“algorithm”

顺序容器

向量

特点：
一个可以扩展的动态数组
随机访问，在尾部插入或删除元素快
在中间或头部插入或删除元素慢

向量的容量：
容量（capacity）：世纪分配空间的大小
s.capacity() ：返回当前容量
s.reserve(n) : 若容量小于n，则对s进行扩展，使其容量至少为n

双端队列(deque)

在两端插入或删除元素快
在中间插入或删除元素慢
随机访问较快，但比向量容器慢

奇偶排序例题：
先按照从大到小顺序输出奇数，再按照从小到达顺序输出偶数
特点：先插入两端元素，速度较快

int main(){
    istream_iterator<int>i1(cin),i2; //建立一对输入流迭代器
    vector <int> s1(i1,i2); //通过输入流迭代器从标准输入流中输入数据
    sort(s1.begin(),s1.end()); //将输入的整数排序
    deque <int> s2; //双端队列
    for (vector <int>::iterator iter = s1.begin();iter!=s1.end();++iter){
        if (*iter%2 ==0)
            s2.push_back(*iter); //偶数放到s2尾部
        else
            s2.push_front(*iter); //奇数放到s2首部
    }
    copy(s2.begin(),s2.end(),ostream_iterator<int>(cout," ")); //将s2的结果输出
    cout<<endl;
    return 0
}

列表

特点：
在任意位置插入和删除都很快
不支持随机访问
接合操作（splice）操作
s1.splice(p,s2,q1,q2):将s2中[q1,q2)移动到s1中p所指向元素之前

单向链表（forward_list)

单向链表每个结点只有指向下个结点的指针，没有简单的方法来获取一个结点的前驱；
未定义insert,emplace,erase操作，而定义了insert_after,emplace_after,erase_after操作，其参数与list的insert,emplace,erase相同，但并不是插入或删除迭代器p1所指的元素，而是对p1所指元素之后的结点进行操作
不支持size操作

数组(array)

array是对内置数组的封装，提供了更安全，更方便的使用数组的方式
array的对象的大小是固定的，定义时除了需要指定元素类型，还需要指定容器大小
不能动态地改变容器大小

顺序容器的比较

STL所提供的顺序容器各有利弊，需要根据自己的需求选择容器
若执行大量的随机访问操作，而且当扩展容器时只需要向容器尾部加入新的元素，就应当选择向量容器vector

如果需要少量的随机访问操作，需要在容器两端插入或删除元素，则应选择双端队列deque

如果不需要对容器进行随机访问，但是需要在中间位置插入或删除元素，就应当选择列表容器list或forward_list

如果需要数组，array相对于内置数组而言，是一种更安全，更容易使用的数组类型

顺序容器的插入迭代器

用于向容器头部，尾部，中间的指定位置插入元素的迭代器
包括前插迭代器(front_inserter),后插迭代器(back_inserter),和任意位置插入迭代器(inserter)

例子：

list <int> s;
back_inserter iter(s);
*(iter++) =5； #通过iter把5插入s尾】

顺序容器的适配器

以顺序容器为基础构建一些常用数据结构，是对顺序容器的封装
栈: 最先压入的元素最后被弹出
队列：最先压入的元素最先被弹出
优先级队列：最”大”的元素最先被弹出

栈和队列模板

栈模板

template<class T,class Sequence = deque<T> >class stack;

队列模板

template<class T,class FrontInsertionSequence = deque<T> >class queue;

栈可以用任何一种顺序容器作为基础容器，而队列只允许用前插顺序容器（双端队列或列表）

栈和队列共同支持的操作

s1 op s2 ，op： ==，！=，<,<=,>,>=
它会对两个容器适配器之间的元素按字典序进行比较

s.size() 返回s的元素个数
s.empty() 返回s是否为空
s.push(t) 将元素t压入到s中
s.pop() 将一个元素从s中弹出 ，对于栈来说，每次弹出的是最后被压入的元素，而对于队列来说，每次被弹出的是最先被压入的元素
不支持迭代器，因为它们不允许对任意元素进行访问

栈和队列不同的操作

栈的操作
s.top() 返回栈顶元素的引用
队列操作
s.front() 获得队头元素的引用
s.back() 获得队尾元素的引用

利用栈反向输出单词
示例：

#include<iostream>
#include<iterator>
#include<stack>
using namespace std;
int main (){
    stack <char> s;
    string str;
    cin >> str; //从键盘输入一个字符串
    // 将字符串的每个元素顺序压入栈中
    for (string::iterator iter = str.begin();iter!=str.end();++iter)
        s.push(*iter);
    // 将栈中的元素弹出
    while(!s.empty()){
        cout<<s.top();
        s.pop();
    }
    cout<<endl;
    return 0;
}

运行结果演示：
congratulations
snoitalutargnoc

优先级队列

优先级队列也像栈队列一样支持元素的压入和弹出，但元素弹出的顺序与元素的大小有关，每次弹出的总是容器中最”最大”的一个元素。

template <class T,class Sequence = vector<T> >class priority_queue;

优先级队列的基础容器必须是支持随机访问的顺序容器
支持栈和队列的size,empty,push,pop几个成员函数，用法与栈和队列相同
优先级队列并不支持比较操作
与栈类似，优先级队列提供一个top函数，可以获得下一个即将被弹出元素（即最”大”的元素）的引用

例10-8 细胞分裂模拟
模拟一种细胞在诞生（即上次分裂）后会在500到20000秒内分裂成两个细胞，每个细胞又按照同样的规律继续分裂

//10_8.cpp
#include <queue>
#include <iostream>
#include <cstdlib> //随机函数
#include <ctime>　//获得当地时间
using namespace std;

const int SPLIT_TIME_MIN = 500;      //细胞分裂最短时间
const int SPLIT_TIME_MAX = 2000;    //细胞分裂最长时间

class Cell; 
priority_queue<Cell> cellQueue;


class Cell {    //细胞类
private:
    static int count;   //细胞总数
    int id;             //细胞编号
    int time;           //细胞分裂时间
public:
    Cell(int birth) : id(count++) { 
        /*产生一定范围随机数的通用表示公式
        要取得 [a,b) 的随机整数，使用 (rand() % (b-a))+ a;

        要取得 [a,b] 的随机整数，使用 (rand() % (b-a+1))+ a;

        要取得 (a,b] 的随机整数，使用 (rand() % (b-a))+ a + 1;

        通用公式: a + rand() % n；其中的 a 是起始值，n 是整数的范围。

        要取得 a 到 b 之间的随机整数，另一种表示：a + (int)b * rand() / (RAND_MAX + 1)
        */
        time = birth + (rand() % (SPLIT_TIME_MAX - SPLIT_TIME_MIN)) + SPLIT_TIME_MIN; //分裂时间在最短时间与最长时间之间
    }
    int getId() const { return id; }            //得到细胞编号
    int getSplitTime() const { return time; }   //得到细胞分裂时间
    bool operator < (const Cell& s) const { return time > s.time; } //重载运算符 

    //细胞分裂
    void split() const {    
        Cell child1(time), child2(time);     //建立两个子细胞
        cout << time << "s: Cell #" << id << " splits to #" 
            << child1.getId() << " and #" << child2.getId() << endl;
        cellQueue.push(child1); //将第一个子细胞压入优先级队列
        cellQueue.push(child2); //将第二个子细胞压入优先级队列
    }
};
int Cell::count = 0;

int main() {
    srand(static_cast<unsigned>(time(0)));
    /*使用当前时钟作为随机数种子
    rand() 产生的随机数在每次运行的时候都是与上一次相同的。若要不同, 用函数 srand() 初始化它。
    可以利用 srand((unsigned int)(time(NULL)) 的方法，产生不同的随机数种子，因为每一次运行程序的时间是不同的。
    */
    //强制转换运算符 static_cast<type> (expr): static_cast 运算符执行非动态转换，没有运行时类检查来保证转换的安全性。例如，它可以用来把一个基类指针转换为派生类指针
    int t;  
    cout << "Simulation time: ";
    cin >> t; //模拟时间长度
    cellQueue.push(Cell(0));    
    while (cellQueue.top().getSplitTime() <= t) //如果最先要弹出的细胞分裂时间在观察时间内 
    {
        cellQueue.top().split();    //模拟下一次细胞的分裂
        cellQueue.pop();            //将刚刚分裂的细胞弹出
    }
    return 0;
}

运行结果：
Simulation time: 5000
1042s: Cell #0 splits to #1 and #2
2336s: Cell #2 splits to #3 and #4
2673s: Cell #1 splits to #5 and #6
3004s: Cell #4 splits to #7 and #8
3329s: Cell #3 splits to #9 and #10
3647s: Cell #7 splits to #11 and #12
3979s: Cell #9 splits to #13 and #14
4190s: Cell #6 splits to #15 and #16
4265s: Cell #8 splits to #17 and #18
4305s: Cell #5 splits to #19 and #20
4613s: Cell #10 splits to #21 and #22
4782s: Cell #11 splits to #23 and #24
4810s: Cell #14 splits to #25 and #26

关联容器

关联容器的特点和接口
每个关联容器都有一个键
可以根据键高效的查找元素
接口
插入：insert
删除：erase
查找：find
定界：lower_bound ,upper_bound,equal_range
计数：count

单重关联容器（set,map)
键值是唯一的，一个键值只能对应一个元素
多重关联容器（multiset,multimap)
键值是不唯一的，一个键值可以对应多个元素
简单关联容器（set,multiset)
容器只有一个类型参数，如set,multiset，表示键类型
容器的元素就是键本身
二元关联容器（map,multimap)
容器有两个类型参数，如map<K,V>,multimap<K,V>
分别表示键和附加数据类型
容器的元素类型是pair<K,V>,即由键类型和元素类型复合而成的二元组

集合(set)

集合用来存储一组无重复的元素。由于集合的元素本身是有序的，可以高效的查找指定元素，也可以方便的得到指定大小范围的元素在容器中所处的区间

例题：
输入一串实数，将重复的去掉，取最大和最小值的中值，分别输出小于等于此中值和大于等于此中值的实数

//10_9.cpp
#include <set>
#include <iterator>
#include <utility>
/*
头文件：#include <utility>
类
pair
函数
forward 保留引用类型（或者lvalue或rvalue) 参数从被遮掩完美转发。
get 获取从元素的函数pair对象。
make_pair 用于构造类型的对象的模板 helper 函数pair，其中的组件类型基于作为参数传递的数据类型。
move 返回传入参数作为rvalue的引用。
swap 交换两个 pair 对象的元素。
运算符
*/
#include <iostream>
using namespace std;

int main() {
    set<double> s;
    while (true) {
        double v;
        cin >> v;
        if (v == 0) break;  //输入0终止
        /*
        
        类模板：template<class T1,class T2> struct pair

        参数：T1是第一个值的数据类型，T2是第二个值的数据类型。

        功能：pair将一对值(T1和T2)组合成一个值，

        这一对值可以具有不同的数据类型（T1和T2），

        两个值可以分别用pair的两个公有函数first和second访问。
        */
        //尝试将v插入
        pair<set<double>::iterator, bool> r = s.insert(v);  

        if (!r.second)      //如果v存在，输出提示信息
            cout << v << " is duplicated" << endl;
    }
    set<double>::iterator iter1 = s.begin();    //得到第一个元素的迭代器
    set<double>::iterator iter2 = s.end();      //得到末尾的迭代器
    double medium = (*iter1 + *(--iter2)) / 2;  //因为末尾的指针指向的是尾元素结束的下一个位置，所以--
    //输出小于或者等于中值的元素
    cout << "<= medium: ";
    copy(s.begin(), s.upper_bound(medium), ostream_iterator<double>(cout, " "));
    cout << endl;
    //输出大于或等于中值的元素
    cout << ">= medium: ";
    copy(s.lower_bound(medium), s.end(), ostream_iterator<double>(cout, " "));
    cout << endl;
    return 0;
}

映射（map）

映射与集合同属于单重关联容器，他们的主要区别在于，集合的元素类型是键本身，而映射的元素类型是由键和附加数据所构成的二元组。
在集合中按照键查找一个元素时，一般只是用来确定这个元素是否存在，而在映射中按照键查找一个元素时，除了能确定它的存在性外，还可以得到相应的附加数据。

例题：
有五门课程，每门都有相应学分，从中选择三门，输出学分总和

#include<iostream>
#include<map>
#include<string>
#include<utility>
using namespace std;
int main(){
    map<string,int>courses;
    //将课程信息插入courses映射中
    courses.insert(make_pair("CSAPP",3));
    courses.insert(make_pair("C++",2));
    courses.insert(make_pair("CSARCH",4));
    courses.insert(make_pair("COMPLIER",4));
    courses.insert(make_pair("OS",5));
    int n = 3;
    int sum = 0;
    while(n>0){
        string name; //输入课程名称
        cin>>name;
        map<string,int>::iterator iter = courses.find(name);//查找课程
        if (iter ==course.end())   //判断是否会找到 这里是未找到
        {
            cout<<name<<"is not available"<<endl;
        }
        else{
            sum += iter->second; //累加学分
            courses.erase(iter); //将刚选过的课程从映射中删除
            n--;
        }

        }

    cout<<"Total credit:"<<sum<<endl;
    return 0;
}

执行结果：
CSAPP
CSAPP
CSAPPis not available 因为每执行某个对象的操作后就将次对象从映射中删除 所以找不到
COMPLIER
CSARCH
Total credit:11

例题：统计一句话中每个字母出现的次数

#include <iostream>
#include <map>
#include <cctype>
/*
cctype头文件用于字符检测

isalpha//判断字符串是否为大小写字母
isupper//判断字符串是否为大写字母
islower//判断字符串是否为小写字母
tolower//把大写字母转化为小写
toupper//把小写字母转化为大写
*/
using namespace std;
int main(){
    map <char,int> s;
    char c;
    do{
        cin>>c;
        if (isalpha(c)){ //判断是否为字母
            c = tolower(c); //将字母转换为小写
            s[c]++; //将该字母的出现频率+1
        }
    }
    while(c!='.'); //碰到"."则结束输入
    //则输出每个字母出现次数
    for(map<char,int>::iterator iter = s.begin();iter!= s.end();++iter)
        cout<<iter->first<<" "<<iter->second<<" ";
    cout<<endl;
    return 0;
}