Lesson2

从工程设计(设计算法库)的角度，看待例如selection_sort：

• 定制化需求
• 可维护性
• 清晰度

用到：

• 重载、模板、面向对象
• 各种类型

slides只有一页，不赖。

#include<iostream>

...(function define)

int main(){
    int arr[] = {64, 25, 12, 23, 11};
    int n = sizeof(arr) / sizeof(arr[0]);

    selection_sort(arr, n);
    print_array(arr, n);
}

...// function code here

算法就是每次找i位元素后的一个最小数跟i换位置。

void selection_sort(arr, n){
    for (int i = 0; i < n - 1; i++){
        int min_idx = i;
        for(int j = i + 1; j < n; j++){
            if (arr[j] < arr[min_idx]){
                min_idx = j;
            }
        }
        if(min_idx != i) {
            int tmp = arr[min_idx];
            arr[min_idx] = arr[i];
            arr[i] = tmp;
        }
    }
}
void print_array(...) // so easy that I will not write down

我们可以改一下两个部分：

int get_min(int *arr, int begin, int end){
    for (int i = begin; i < end; i++){
        if (arr[i] < arr[min_idx]){
            min_idx = i;
        }
    }
    return min_idx;
}

void swap(int &a, int &b){
    int tmp = a;
    a = b;
    b = tmp;
}// pay attention to this

这个swap，我们常规而言是void swap(int a, int b)，但是这样是错误的，因为a和b是值传递，我们并没有改变数组中两个索引的值，改成这个之后就可以了。

重载

然后出现浮点数，我们就改double...于是，欸，我们不小心忘记注释掉int的那个函数，编译的时候看到了开始拍腿大叫坏了，一运行，欸，怎么可以？

int get_min(int *double, int begin, int end){
    for (int i = begin; i < end; i++){
        if (arr[i] < arr[min_idx]){
            min_idx = i;
        }
    }
    return min_idx;
}

int get_min(int *arr, int begin, int end){
    for (int i = begin; i < end; i++){
        if (arr[i] < arr[min_idx]){
            min_idx = i;
        }
    }
    return min_idx;
}

这叫重载(overloading)，也就是场上存在两个不同的函数，但是名字相同，但是参数类型不同，编译器会出现一个自动的适应。

模板

加入这个语句：

template<typename T>
int get_min(T *arr, int begin, int end){
    for (int i = begin; i < end; i++){
        if (arr[i] < arr[min_idx]){
            min_idx = i;
        }
    }
    return min_idx;
}

这样是字符还是浮点数还是整数都no care了。

相当于编译器帮助你自动地重载了这个函数。

注意，对于每个函数，你要写作模板，你就要在函数前添加该语句，然后改你的函数。

结构体的处理

#include<string>
struct Stduent {
    int id;
    std::string name;
}

你这样模板肘必然犯错，因为没有定义所谓"小于"是怎么比较的。

struct Stduent {
    int id;
    std::string name;

    bool operator<(const Student& s) {
        return id < s.id;
    }
}

我们也可以这么写：

struct Stduent {
    int id;
    std::string name;

    // bool operator<(const Student& s) {
    //     return id < s.id;
    // }
}
bool operator<(const Student& s1, const Student& s2) {
        return s1.id < s2.id;
    }

对于输出流的定义，相当于我告诉它怎么输出"Student":

std::ostream& operator<<(std::ostream out, const Student& s){
    return out << "(" << s.id << "," << s.name << ")";
}

a pro step

假设我们需要一个图形的程序。

class Rectangle {
private:
    double w,h;
public:
    Rectangle(double w, double h) : w(w), h(h) {}
};

private的是这个类的属性，public叫这个类的构造函数constructor。

我们再添加一点东西：

class Rectangle {
private:
    double w,h;
    double area, perimeter;
public:
    Rectangle(double w, double h) : w(w), h(h) {}
    void calc_area() {
        area = w * h;
    }
    void calc_perimeter() {
        perimeter = 2 * (w + h);
    }
    ...
};

其他的图形也一样。

那我们怎么赋值，比如Rectangle *arr = {{2,3},{4,5}};吗？

这会报错，正确的写法是Rectangle *arr = {Rectangle(2,3), Rectangle(4,5)};。

以及某种神秘处理法：

for (Rectangle& r: arr){
    r.calc_area();
    r.calc_perimeter();
}

把Rectangle改成auto即for (auto& r: arr)也是可以的。

再添加两个图形：

首先我们可以定义一个常量const double PI = 3.14

class Circle {
private:
    double r;
    double area, perimeter;
public:
    Circle(double r) : r(r) {}
    void calc_area() {
        area = 3.14 * r * r;
    }
    void calc_perimeter() {
        perimeter = 2 * 3.14 * r;
    }
};

class Triangle {
private:
    double a,b,c;
    double area, perimeter;
public:
    Triangle(double a, double b, double c) : a(a), b(b), c(c) {}
    void calc_area() {
        double p = (a + b + c) / 2;
        area = sqrt(p * (p - a) * (p - b) * (p - c));
    }
    void calc_perimeter() {
        perimeter = a + b + c;
    }
}

找到一个共同点，都有double area, perimeter;

我们定义一个shape类，即：

class Shape {
protected:
    double area, perimeter;
}
class Rectangle : public Shape {
private:
    double w,h;
public:
    ...

进一步，我们也发现都有两个函数，我们写作：

class Shape {
protected:
    double area, perimeter;
public:
    void calc_area() {
        ...
    }
    void calc_perimeter() {
        ...
    }
}
class Rectangle : public Shape {
private:
    double w,h;
public:
    ...

处理之，我们就可以写：

class Shape{
protected:
    double area, perimeter;
public:
    virtual void calc_area() = 0
    virtual void calc_perimeter() = 0
};

子类去继承之的时候就要去修改这个接口，最好加上复写，即：

class Rectangle : public Shape {
private:
    double w,h;
public:
    void calc_area() override {
        area = w * h;
    }
    void calc_perimeter() override {
        perimeter = 2 * (w + h);
    }
};

友元：friend关键字如下使用：

class Shape {
protected:
    double area, perimeter;
public:
    virtual void calc_area() = 0
    virtual void calc_perimeter() = 0
    friend 
};

讲的太快了...一节课讲完了一学期的东西。