程序设计与算法（三）C++面向对象程序设计 （北大MOOC）

　　第一部分 面向对象的编程

　　面向对象编程（Object-oriented programming , OOP），基于三个概念：数据抽象、继承 和 动态绑定

　　动态绑定使编译器能够在运行时决定是使用基类中定义的函数还是派生类中定义的函数，在C++中，通过基类的引用或指针调用虚函数时，发生动态绑定，调用的虚函数在运行时确定，被调用的函数是引用或指针所指向对象的实际类型所定义

　　在C++中基类必须指出希望派生类重新定义哪些函数，定义为virtual的函数即虚函数，不是基类期待派生类重新定义的，不能定义为虚函数

#include 
using namespace std;

class Base{
    int base_num;
public:
    Base( int number ): base_num(number){}
    virtual int getNum(){  //虚函数，期望派生类重定义
        return base_num;
    }
};

class Derived:public Base
{
    int derived_num;
public:
    Derived( int num1, int num2 ):Base(num1), derived_num(num2){}
    virtual int getNum(){ //重定义的函数
        return derived_num;
    }
};

void printNum(Base &b){ //基类的引用
    cout << b.getNum() << endl;
}

void printNum(const Base &b){ //临时对象是右值，可以用const绑定
    cout << "临时对象是右值，可以用const绑定" << endl;
}

/* void printNum(const Base &b){   //基类的引用是const
    cout << b.getNum() << endl; //调用了非const的函数不可以
} */


int main() 
{
    Derived d(80,90);
    printNum(d); //传的是派生类的对象
    printNum(Derived(50,60)); //临时对象是右值，可以用const绑定
    
    return 0;
}

　　第二部分 泛型编程

　　模板机制，以及标准模板库STL

　　标准模板库（Standard Template Library）就是一些常用数据结构和算法的模板的集合，有了STL，不必再写太多的标准数据结构和算法，并且可以获得非常高的性能　　

　　STL六大部件：容器（Containers）、分配器（Allocators）、算法（Alogrithms）、迭代器（Iterators）、仿函数(Functors,头文件为)、适配器(转换器）（Adapters）

　　一、容器（Containers）

　　容器的定义：

　　在数据存储上，有一种对象类型，它可以持有其它对象或指向其它对象的指针，这种对象类型就叫做容器。很简单，容器就是保存其它对象的对象，当然这是一个朴素的理解，这种“对象”还包含了一系列处理“其它对象”的方法。容器即物之所在，容器是STL的核心部件之一，是迭代器的依附，是算法作用的目标。　

　　容器的种类：

　　顺序容器：是一种各元素之间有顺序关系的线性表，是一种线性结构的可序群集。顺序性容器中的每个元素均有固定的位置，除非用删除或插入的操作改变这个位置。顺序容器的元素排列次序与元素值无关，而是由元素添加到容器里的次序决定。顺序容器包括：vector(向量)、list（列表）、deque（队列）。
　　关联容器：关联式容器是非线性的树结构，更准确的说是二叉树结构。各元素之间没有严格的物理上的顺序关系，也就是说元素在容器中并没有保存元素置入容器时的逻辑顺序。但是关联式容器提供了另一种根据元素特点排序的功能，这样迭代器就能根据元素的特点“顺序地”获取元素。元素是有序的集合，默认在插入的时候按升序排列。关联容器包括：map（集合）、set（映射）、multimap（多重集合）、multiset（多重映射）。
　　容器适配器：本质上，适配器是使一种不同的行为类似于另一事物的行为的一种机制。容器适配器让一种已存在的容器类型采用另一种不同的抽象类型的工作方式实现。适配器是容器的接口，它本身不能直接保存元素，它保存元素的机制是调用另一种顺序容器去实现，即可以把适配器看作“它保存一个容器，这个容器再保存所有元素”。STL 中包含三种适配器：栈stack 、队列queue 和优先级队列priority_queue 。

　　容器类自动申请和释放内存，因此无需new和delete操作。

　　不同容器的使用方法：

　　1、set  

/*
 * 维护平面点

一开始平面上一个点都没有
每次可以插入一个点，删除一个已经存在的点，或者按照x 或y 来查询一个存在的点
保证任何时候任意两个点一定是一个点严格在另一个点的右下方
即两点(x1, y1), (x2, y2)，必定有x1 > x2 且y1 < y2 ，或者x1 < x2 且y1 > y2

输入：
A 3 5
A 4 2
Qx 4
R 4 2
A 4 3
Qy 3

输入数据的每一行，格式为以下之一：
A x y
R x y
Qx x
Qy y
其中 x 与 y 都是 0 到 10^9 之间的整数
A x y 表示插入点 (x, y)
R x y 表示删除点 (x, y)，保证存在
Qx x 表示在当前所有点中，找到第一维为x的点，输出其第二维的值，保证存在
Qy y 表示在当前所有点中，找到第二维为y的点，输出其第一维的值，保证存在
总共操作数不超过100000
输出：
2
4
对于每一个 Qx 和 Qy 操作，输出一行表示对应的答案
*/


#include <set>
#include 
#include <string>
using namespace std;
// 在此处补充你的代码
struct myComp {
    bool operator()(const pair<int, int> &a, const pair<int, int> &b) {
        if (a.first > 0 && a.second > 0 && b.first > 0 && b.second > 0) {
            return a.first > b.first; //  x 值大小排序
        } else if (a.first < 0 || b.first < 0) {
            return a.second < b.second;  // y 值大小排序
        } else if (a.second < 0 || b.second < 0) {
            return a.first > b.first;  // x 值大小排序
        }
        return true;
    }

};
int main() {
    string cmd;
    setint, int>, myComp> S; // 模板类型 myComp
    while (cin >> cmd) {
        if (cmd == "A") {
            int x, y;
            cin >> x >> y;
            S.insert(make_pair(x, y)); //插入一个点
        } else if (cmd == "Qx") {
            int x;
            cin >> x;
            cout << S.lower_bound( make_pair(x, -1) )->second << endl;//返回大于等于x的第一个位置的迭代器
        } else if (cmd == "Qy") {
            int y;
            cin >> y;
            cout << S.lower_bound(make_pair(-1, y))->first << endl; //返回大于等于y的第一个位置的迭代器
        } else {
            int x, y;
            cin >> x >> y;
            S.erase(make_pair(x, y)); //删除一个点
        }
    }
    return 0;
}

　　c++语言中，multiset 是 库中一个非常有用的类型，它可以看成一个序列，插入一个数，删除一个数都能够在O(logn)的时间内完成，而且他能时刻保证序列中的数是有序的，而且序列中可以存在重复的数

/*
    输入n个整数，输出整数数列中大小排名前k的偶数
    测试用例：
    2
    9 4
    1 2 4 3 6 6 7 8 9
    3 2
    18 16 14
 */

#include 
#include <set>

using namespace std;

class MyQueue
{
    int k;  //创建对象时，k表示前k个偶数整数
    multiset < int, greater<int> > que; //multiset容器对象 元素有序且可以重复
public:

    MyQueue(int k):k(k) {}

    //容器插入对象
    friend istream & operator>>(istream&is, MyQueue &a) //对象输入 重载 >> 运算符
    {
        int num;
        is >> num;
        if (num % 2 == 0)
        {
            a.que.insert(num); //是偶数插入
        }
        return is;
    }

    //从容器输出对象
    friend ostream & operator <<(ostream&os, MyQueue &a) //对象输出 重载 << 运算符
    {
        multiset<int>::iterator p = a.que.begin(); //迭代器
        int count = 0;
        for (; count < a.k; p++)
        {
            if (count){
                os << " ";
            }            
            os << *p ; //输出元素
            count++;   //记录输出元素个数
        }
        return os;
    }
};

int main()
{
    int t;
    cin >> t;
    while(t--)
    {
        int n, k;
        cin >> n >> k;
        MyQueue q(k);
        for (int i = 0; i < n; ++i)
            cin >> q; //利用>>运算符重载 输入整数（插入到对象 q 的 multiset 容器中）
        cout<<q;
        cout << endl;
    }

    return 0;
}

　　multiset 容器，矩形类对象大小排序，默认 <运算符重载 （< 双目运算符，友元函数 ）， 模板类型（友元类），函数对象，()运算符重载，注：何时使用友元？当你想要用普通函数或非本类的成员函数，调用本类的私有成员时

/* 矩形排序
给定一系列边长已知的矩形，输出对矩形进行两种排序的结果。
在第一种排序中，先按矩形的面积从大到小排序；若两个矩形的面积相同，则周长大的排在前。
在第二种排序中，先按矩形的周长从小到大排序；若两个矩形的周长相同，则面积小的排在前。
输入：
6
3 8
4 6
10 2
6 6
4 8
3 6
第一行是一个整数n，表示输入的矩形个数。
接下来n行表示了n个矩形。每行有两个整数a与b，表示该矩形的长与宽。
输出：
36 24
32 24
24 22
24 20
20 24
18 18

18 18
24 20
24 22
20 24
32 24
36 24 */

#include 
#include <set>
using namespace std;
// 在此处补充你的代码
class Rectangle
{
    int length, width, area, perimeter; //长、宽、面积、直径
public:    
    friend class Comp;  //友元类 可以处理 Rectangle 类的数据成员
    Rectangle(int _length, int _width) : length(_length), width(_width) //构造函数
    {
        area = length * width;
        perimeter = 2 * (length + width);
    }
    //友元函数 比较对象大小
    friend bool operator<(const Rectangle &rec1, const Rectangle &rec2) //  < 运算符重载 
    {
        if (rec1.area == rec2.area)   //面积相等 直径大的在前
            return rec1.perimeter > rec2.perimeter;
        return rec1.area > rec2.area; //面积大的在前
    }
    //输出对象
    friend ostream &operator<<(ostream &os, const Rectangle &obj) // 友元函数 << 运算符重载 输出面积及直径
    {
        cout << obj.area << ' ' << obj.perimeter;
        return os;
    }
};

class Comp
{
public:
    bool operator()(const Rectangle &rec1, const Rectangle &rec2) //比较对象大小
    {
        if (rec1.perimeter == rec2.perimeter) //直径相等 面积小的在前
            return rec1.area < rec2.area;
        return rec1.perimeter < rec2.perimeter; //直径小的在前
    }
};

int main() 
{
    multiset m1;   //默认 < 运算符重载 友元函数
    multiset m2; //模板 Comp类型 函数对象（临时对象） Rectangle类的友元类 < 运算符重载 
    int n, a, b;
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> a >> b;
        m1.insert(Rectangle(a, b));
        m2.insert(Rectangle(a, b));
    }
    for (multiset::iterator it = m1.begin(); it != m1.end(); it++) {
        cout << *it << endl;
    }
    cout << endl;
    for (multiset::iterator it = m2.begin(); it != m2.end(); it++) {
        cout << *it << endl;
    }
    return 0;
}

　　2、 容器的 for_each(iterator,iterator,pointer)（第三个参数：pointer是指向函数的指针：全局函数 或  函数对象-->临时对象）

　　临时对象，就是一种无名对象(unamed objects)，临时对象：类名之后直接加一对小括号 () 或者大括号 {}（列表初始化），并可指定初值，其意义相当于调用相应的构造函数并且不指定对象名

　　函数对象（function object），形式上是一个类实例化的对象，本质上是为了实现某种与函数等价的功能，函数对象的思想是：用类来封装一个函数功能，然后用这个类实例化不同的函数对象，若一个类重载了运算符()，则该类的对象就成为函数对象    注：重载()运算符，参数没有限制，比如：bool operator()(int a,int b,int c){...}

/*
    完成以下程序，使得输入的整数x，以及若干正整数，将
大于x的正整数输出；然后输入若干字符串，将字符串长度大于x的字符串输出
    测试用例：
    2
    5 6
    1 3 59 30 2 40
    this is hello please me ha
    1 1
    4
    this
    输出：
    59,30,40,
    please,
    4,
    this,
 */

#include  //for_each 头文件
#include 
#include 

using namespace std;


class Printer
{
    int size;

public:
    Printer(int x) : size(x) {}

    void operator()(int x)  //运算符()重载
    {
        if (x > size)
            cout << x << ',';
    }

    void operator()(string str) //运算符()重载
    {
        if (str.size() > size)
            cout << str << ',';
    }
};

int main()
{
    int t;
    cin >> t;
    while(t--)
    {
        int n,x;
        cin >> x >> n;

        vector<int> intVec;
        for(int i = 0; i < n; ++i)
        {
            int y;
            cin >> y;
            intVec.push_back(y);
        }
        for_each(intVec.begin(), intVec.end(), Printer(x)); //Printer(x)是函数对象
        cout << endl;

        vector<string> strVec;
        for(int i = 0; i < n; ++i)
        {
            string str;
            cin >> str;
            strVec.push_back(str);
        }
        for_each(strVec.begin(), strVec.end(), Printer(x));
        cout << endl;
    }
    return 0;
}

　　全局函数：

#include 
#include 
#include   //for_each 

using namespace std;

//全局函数
void printElem(int elem, const char* prefix)
{
    cout << prefix << elem << endl;
}

int main()
{
    int ia[] = {1, 2, 3};
    vector<int> ivec(ia, ia + sizeof(ia) / sizeof(int));
    for_each(ivec.begin(), ivec.end(), bind2nd(ptr_fun(printElem), "Element:"));
    
    return 0;
}

　　3、 容器的 sort 参数：< 运算符重载，函数对象（重载 () 运算符），全局函数，容器的 for_each 的参数为全局函数

/*
三生三世

测试用例：3代表3个电视剧，以下是 每个电视剧的剧名 及 演员阵容、剧情和演技的分数
3
In the Name of People
98 97 99
Life After Life, Blooms Over Blooms
99 82 73
Ming Dynasty: 1566
97 100 100
输出：按分数（分别为演员阵容、剧情和演技的分数）从大到小排序3次，并按排序输出剧名

*/
#include    //string
#include        //list
#include   // sort
using namespace std;

class TV_Drama {
public:
    char name[100]; //电视剧
    int actor;  //演员阵容评分
    int story;  //剧情评分
    int acting_skill; //演技评分
    // 在此处补充你的代码
    TV_Drama(string _name, int _actor, int _story, int _acting_skill) :
            actor(_actor), story(_story), acting_skill(_acting_skill) {
        _name.copy(name, _name.size(), 0); //string类的函数
        name[_name.size()] = 0; //字符串结束符     name 电视剧剧名
    }
    bool operator <(const TV_Drama &obj) { //对象比较，重载比较运算符  <
        return actor > obj.actor;   //从高到低排序
    }
};


void Printer(const TV_Drama &obj) { //全局函数
    cout << obj.name << ';';
    //cout <<"--" << obj.actor << "--" << obj.story << "--" << obj.acting_skill<< endl;
}
bool comparator_1(const TV_Drama &o1, const TV_Drama &o2) { //全局函数
    return o1.story > o2.story;  //从高到低排序
}

class comparator_2 { //函数对象 ，重载了小括号 () 运算符
public:
    bool operator()(const TV_Drama &o1, const TV_Drama &o2) {
        return o1.acting_skill > o2.acting_skill;   //从高到低排序
    }
};

int main() {
    list lst;  //对象容器
    int n;
    cin >> n;
    char _name[100];
    int _actor, _story, _acting_skill;
    for (int i = 0; i < n; i++) {
        cin.ignore();  //cin.ignore()函数用于忽略或清除输入缓冲区中的一个或多个字符
        cin.getline(_name, 100);
        cin >> _actor >> _story >> _acting_skill;
        lst.push_back(TV_Drama(_name, _actor, _story, _acting_skill));
    }

    lst.sort(); //无参 默认对象从小到大，重载 < 运算符改为 从大到小
    for_each(lst.begin(), lst.end(), Printer);
    cout << endl;

    lst.sort(comparator_1);   //全局函数
    for_each(lst.begin(), lst.end(), Printer);
    cout << endl;

    lst.sort(comparator_2()); //函数对象
    for_each(lst.begin(), lst.end(), Printer);
    cout << endl;

    return 0;
}

　　4、

#include 
#include 

　　二、算法

　　又见模板，模板，[]运算符重载，成员函数

/*
又见模板

输入：
1
1 2 3 4 5 6 7 8 9 10
4.2 0.0 3.1 2.7 5.2
Hello , world !

第一行是整数n，表示有n组数据
每组数据有3行
第一行是10个整数
第二行是5个小数
第三行是4个不带空格的字符串，它们之间用空格分隔

输出：
3
15.2
Hello,world!
 */
 
#include 
#include <string>
using namespace std;
// 在此处补充你的代码

template int size>
class A
{
    T *p; //指针
public:
    A(T *obj) : p(new T[size])
    {
        for (int i = 0; i < size; i++)
            p[i] = obj[i];
    }
    T &operator[](int n) { return p[n]; }  //[]运算符重载
    T sum()
    {
        T su = *p;
        for (int i = 1; i < size; i++)
            su += p[i]; //string 类 += 是字符串连接
        return su;
    }
};

int main() 
{    
    int t;
    cin >> t;
    while( t -- ) 
    {     //1、int类型 数组
        int b1[10];
        for(int i = 0;i < 10; ++i)         
            cin >> b1[i];
        
        A<int, 10> a1 = b1;    //构造函数
        cout << a1[2] << endl; // []运算符重载
            
        //2、double类型 数组
        double b2[5] ;
        for(int i = 0;i < 5; ++i)     
            cin >> b2[i];
        
        A<double, 5> a2 = b2; //构造函数
        cout << a2.sum() << endl; // sum成员函数
        
        //3、string类型 数组
        string b3[4] ;
        for(int i = 0;i < 4; ++i)     
            cin >> b3[i];
        
        A<string, 4> a3 = b3; //构造函数  
        cout << a3.sum() << endl; // 调用sum成员函数
    }
    return 0;
}

　　魔兽5

#include 
#include <string>
#include  
#include 
#include