抱歉，您的浏览器无法访问本站

本页面需要浏览器支持（启用）JavaScript


了解详情 >

多态

秃头王
OOP

发布于：2022年7月19日
次浏览

多态

多态：简单的来说就是你跟你爸爸有相同的行为模式，但是具体的行为不一样就像是说你爸上班你也上班，但是工作内容不一样，你爸也会跑你也会跑但是你俩跑的姿势不一样 - 这个场景反馈的是父类和子类功能上的差别

普通的成员方法是跟着类走的

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
/*************************************************************************
        > File Name: 1.Animal.cpp
        > Author: 秃头王
        > Mail: 1658339000@qq.com
        > Created Time: 2022年07月19日 星期二 22时37分39秒
 ************************************************************************/

#include <iostream>
using namespace std;

#define BEGINS(x) namespace x {
#define ENDS(x) } // end of namespace x

BEGINS(test1)

class Animal {

public :
    void run() {
        cout << "I don't know to run" << endl;
        return ;
    }

};


class Cat : public Animal {

public :
    void run() {
        cout << "I can run with fout legs" << endl;
        return ;
    }

};

int main() {
    // 普通的成员方法是跟着类走的
    Cat a;
    Animal &b = a;
    Animal *c = &b;
    a.run();  // let this cat good  // cat 类 所以调用cat类中run方法
    b.run();  // let this animal go // animal 类的引用 所以调用 animal类中run方法
    c->run(); // let this animal go // animal 类的指针 所以调用 animal类中run方法


    return 0;
}

ENDS(test1)

int main() {
    test1::main();
    return 0;
}

虚函数

c++中的虚函数的作用主要是实现了多态的机制。关于多态，简而言之就是用父类的指针指向其子类的实例，然后通过父类的指针调用实际子类的成员函数。这种技术可以让父类的指针有”多种形态”，这是一种泛型技术。

如果调用非虚函数，则无论实际对象是什么类型，都执行基类的类型所定义的函数。

非虚函数总是在编译时根据调用该函数对象，引用或指针的类型而定。如果掉虚函数，则直到运行时才能正确调用那个函数，运行的虚函数是引用所绑定或指针所指向的对象所属类型定义的版本。虚函数必须是基类的非静态成员函数。虚函数的作用是实现动态联编，也就是在程序的运行阶段动态地选择合适的成员函数，在定义了虚函数后，可以在基类的派生类中对虚函数重新定义，在派生类中重新定义的函数应与虚函数具有相同的形参个数和形参类型。以实现统一的接口，不同定义过程。如果在派生类中没有对虚函数重新定义，则它继承其基类的虚函数。

虚函数（Virtual Function）是通过一张虚函数表（Virtual Table）来实现的。简称为V-Table。在这个表中，主是要一个类的虚函数的地址表，这张表解决了继承、覆盖的问题，保证其容真实反应实际的函数。这样，在有虚函数的类的实例中这个表被分配在了这个实例的内存中，所以，当我们用父类的指针来操作一个子类的时候，这张虚函数表就显得由为重要了，它就像一个地图一样，指明了实际所应该调用的函数。

在父类中如果某个成员方法是虚的,那么在子类中相同的函数自动变成虚的

构造函数是不能是虚构造函数的

为什么构造函数不能是虚函数呢？这里你需要知道一个概念，那就是虚函数表vtbl，每一个拥有虚成员函数的类都有一个指向虚函数表的指针。对象通过虚函数表里存储的虚函数地址来调用虚函数。

那虚函数表指针是什么时候初始化的呢？当然是构造函数。当我们通过new来创建一个对象的时候，第一步是申请需要的内存，第二步就是调用构造函数。试想，如果构造函数是虚函数，那必然需要通过vtbl来找到虚构造函数的入口地址，显然，我们申请的内存还没有做任何初始化，不可能有vtbl的。因此，构造函数不能是虚函数。

虚函数是跟着对象走的

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
#include <iostream>
using namespace std;

#define BEGINS(x) namespace x {
#define ENDS(x) } // end of namespace x


BEGINS(test2)

class Animal {

public :
    // 加上 virtual 做功能性保证
    virtual void run() {
        cout << "I don't know to run" << endl;
        return ;
    }

};


class Cat : public Animal {

public :
    // override 不做功能性的保证 -> 体现了c++设计的哲学，c++核心理念让运行时候错误变成编译时候错误，用更加的严格的编码语义,用更加的严格的编 码规范，是错误暴露在编译阶段而不是运行阶段
    void run() override {
        cout << "I can run with fout legs" << endl;
        return ;
    }

};

int main() {
    // 普通的成员方法是跟着类走的
    Cat a;
    Animal &b = a;
    Animal *c = &b;
    a.run();  // let this cat good  // cat 类 所以调用cat类中run方法
    b.run();  // let this animal go // animal 类的引用 指向Cat对象 所以调用 Cat类中run方法
    c->run(); // let this animal go // animal 类的指针 指向Cat对象  所以调用 Cat类中run方法
    return 0;
}


ENDS(test2)

int main() {
    // 普通的成员方法是跟着类走的
    // test1::main();
    // 虚函数是跟着对象走的
    test2::main();
}

运行结果

1
2
3
I can run with fout legs
I can run with fout legs
I can run with fout legs

虚函数->对象-> 运行期(运行时候才知道功能)-代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
#include <iostream>
using namespace std;

#define BEGINS(x) namespace x {
#define ENDS(x) } // end of namespace x

BEGINS(test3)

class Animal {

public :
    // 加上 virtual 做功能性保证
    virtual void run() {
        cout << "I don't know to run" << endl;
        return ;
    }

    virtual void foo() {
        cout << "foo function" << endl;
        return ;
    }

};


class Cat : public Animal {

public :
    // override 不做功能性的保证 -> 体现了c++设计的哲学，c++核心理念让运行时候错误变成编译时候错误，用更加的严格的编码语义,用更加的严格的编 码规范，是错误暴露在编译阶段而不是运行阶段
    void run() override {
        cout << "I can run with fout legs" << endl;
        return ;
    }

};


class Human : public Animal {
public :
    void run() override {
        cout << "I can run with two legs" << endl;
        return ;
    }
};

class Bird : public Animal {
public :
    void run() override {
        cout << "I can fly" << endl;
        return ;
    }
};

int main() {
    srand(time(0));
    Animal *arr[10];
    for(int i = 0; i < 10; i++) {
        switch(rand() % 3) {
            case 0 : arr[i] = new Cat(); break;
            case 1 : arr[i] = new Human(); break;
            case 2 : arr[i] = new Bird(); break;
        }
    }

    for(int i = 0; i < 10; i++) {
        arr[i]->run();
    }

    return 0;
}


ENDS(test3)

int main() {
    // 虚函数是跟着对象走的     虚函数->对象-> 运行期(运行时候才知道功能)
    test3::main();
    return 0;
}

一定当基类的函数变成虚函数(析构函数)，那么所有的派生类的函数(析构函数)也会变成虚函数

虚析构-代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
/*************************************************************************
        > File Name: 1.Animal.cpp
        > Author: 秃头王
        > Mail: 1658339000@qq.com
        > Created Time: 2022年07月19日 星期二 22时37分39秒
 ************************************************************************/

#include <iostream>
using namespace std;

#define BEGINS(x) namespace x {
#define ENDS(x) } // end of namespace x

BEGINS(test4)

class Animal {

public :
    // 加上 virtual 做功能性保证
    virtual void run() {
        cout << "I don't know to run" << endl;
        return ;
    }

    virtual ~Animal() {
        cout << "Animal destructor" << endl;
    }


};


class Cat : public Animal {

public :
    // override 不做功能性的保证 -> 体现了c++设计的哲学，c++核心理念让运行时候错误变成编译时候错误，用更加的严格的编码语义,用更加的 严格的编码规范，是错误暴露在编译阶段而不是运行阶段
    void run() override {
        cout << "I can run with fout legs" << endl;
        return ;
    }

    ~Cat() {
        cout << "Cat destructor" << endl;
    }

};


class Human : public Animal {
public :
    void run() override {
        cout << "I can run with two legs" << endl;
        return ;
    }
    ~Human() {
        cout << "Human destructor" << endl;
    }
};

class Bird : public Animal {
public :
    void run() override {
        cout << "I can fly" << endl;
        return ;
    }
    ~Bird() {
        cout << "Bird destructor" << endl;
    }
};

int main() {
    srand(time(0));
    Animal *p;

    switch(rand() % 3) {
        case 0: p = new Cat(); break;
        case 1: p = new Human(); break;
        case 2: p = new Bird(); break;
    }

    p->run();
    // 如果基类析构不加 virtual 析构就会出现问题
    // 因为 普通的成员方法是跟着类走的
    delete p;

    return 0;
}


ENDS(test4)

int main() {
    // 普通的成员方法是跟着类走的 普通->类->编译期(你不编译运行也 知道他是什么)
    // test1::main();
    // 虚函数是跟着对象走的     虚函数->对象-> 运行期(运行时候才知道功能)
    // test2::main();
    // 运行期状态
    // test3::main();
    test4::main();
    return 0;
}

纯虚函数

纯虚函数是在基类中声明的虚函数，它在基类中没有定义，但要求任何派生类都要定义自己的实现方法。在基类中实现纯虚函数的方法是在函数原型后加“=0” virtualvoid GetName() =0。在很多情况下，基类本身生成对象是不合情理的。例如，动物作为一个基类可以派生出老虎、孔雀等子类，但动物本身生成对象明显不合常理。为了解决上述问题，将函数定义为纯虚函数，则编译器要求在派生类中必须予以重写以实现多态性。同时含有纯虚拟函数的类称为抽象类，它不能生成对象。这样就很好地解决了上述两个问题。将函数定义为纯虚函数能够说明，该函数为后代类型提供了可以覆盖的接口，但是这个类中的函数绝不会调用。声明了纯虚函数的类是一个抽象类。所以，用户不能创建类的实例，只能创建它的派生类的实例。必须在继承类中重新声明函数（不要后面的＝0）否则该派生类也不能实例化，而且它们在抽象类中往往没有定义。定义纯虚函数的目的在于，使派生类仅仅只是继承函数的接口。纯虚函数的意义，让所有的类对象（主要是派生类对象）都可以执行纯虚函数的动作，但类无法为纯虚函数提供一个合理的缺省实现。所以类纯虚函数的声明就是在告诉子类的设计者，“你必须提供一个纯虚函数的实现，但我不知道你会怎样实现它”。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
#include <iostream>
using namespace std;

#define BEGINS(x) namespace x {
#define ENDS(x) } // end of namespace x

BEGINS(test5)
    
//抽象类 - 通常用作接口 - 抽象类不生成对象
class Animal {

public :
    //纯虚函数 - 如果要让Cat产生对象的话就一定在子类中实现这个方法
    virtual void run() = 0;

};


class Cat : public Animal {

public :
    void run() override {
        cout << "I can run with four legs" << endl;
        return ;
    }

};

int main() {
    Cat a;
    return 0;
}

ENDS(test5)

int main() {
    test5::main();
    return 0;
}
// 在逻辑上我们不知道这个方法在父类中是怎么实现的，或者这个方法在在这个父类中实现是没有意义的

virtual 关键字

  • 语义: 子类的这个方法可能会跟父类的有所不同

  • 成员方法调用时:

    virtual关键字的方法跟着【对象】

    非virtual关键字的方法跟着【类】

  • 限制:

    不能用来修饰【类方法-static】

为什么虚函数可以跟着对象走？

image-20220720145502832

虚函数表

虚函数表给类带来的改变
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
/*************************************************************************
        > File Name: 2.vtable.cpp
        > Author: 秃头王
        > Mail: 1658339000@qq.com
        > Created Time: 2022年07月20日 星期三 14时55分29秒
 ************************************************************************/

#include <iostream>
using namespace std;

#define BEGINES(x) namespace x { // namespace of x<F4>
#define ENDS(x) } // end of namespace x

BEGINES(test1)

class Base {

public :
    // 8 字节是存储虚函数表地址的
    virtual ~Base(){}

};

class A : public Base {
public :
    int x;
};

class B {
public :
    int x;

};

int main() {
    // 8 字节是存储虚函数表地址的
    cout << "sizeof(Base) = "<< sizeof(Base) << endl;
    // A类继承Base类 8 字节是虚函数表地址的,但是和Base类中虚函数表地址和A类中虚函数表的地址是不一样的
    // 但是A类中还有一个整形的变量 (最大数据类型是8字节)内存对齐
    cout << "sizeof(A)    = "<< sizeof(A) << endl;
    // B类只有一个int类型 所以只占4个字节
    cout << "sizeof(B)    = "<< sizeof(B) << endl;
    return 0;
}

ENDS(test1)


int main() {

    test1::main();
    return 0;
}

image-20220720153740845

虚函数重写方法内存管理
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
#include <iostream>
using namespace std;

#define BEGINES(x) namespace x { // namespace of x<F4>
#define ENDS(x) } // end of namespace x

BEGINES(test2)

class Base {

public :
    virtual void func1() {
        cout << "Base func1" << endl;
        return ;
    }

    virtual void func2() {
        cout << "Base func2" << endl;
        return ;
    }

    virtual void func3() {
        cout << "Base func3" << endl;
        return ;
    }

    // 8 字节是存储虚函数表地址的
    virtual ~Base(){}

};

class A : public Base {
public :
    // 重写
    void func2() override {
        cout << "A func2" << endl;
        return ;
    }
    int x;
};

class B : Base {
public :
    void func1() override {
        cout << "B func1" << endl;
        return ;
    }

    void func3() override {
        cout << "B func3" << endl;
        return ;
    }
    int x;

};

int main() {
    A a;
    B b;
    a.func1();
    a.func2();
    a.func3();
    b.func1();
    b.func2();
    b.func3();
    // 调用虚函数表的第一个位置
    // func ** 第一地址(虚函数表) [1]虚函数表就是第二个函数
    ((func **)(&a))[0][1]();
    // ((func **)(&a))[0][0] = ((func **)(&b))[0][0];
    // 交换虚函数表的首地址
    swap(((func **)(&a))[0], ((func **)(&b))[0]);
    cout << "--------------------------" << endl;
    ((func **)(&a))[0][0]();
    ((func **)(&a))[0][1]();
    // c 语言原生指针
    ((func **)(&a))[0][2]();
    return 0;
}

ENDS(test2)


int main() {
    // 类中虚函数表大小以及继承后的大小
    // test1::main();
    test2::main();
    return 0;
}

image-20220720191517840

虚函数表-代码合集

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
/*************************************************************************
        > File Name: 2.vtable.cpp
        > Author: 秃头王
        > Mail: 1658339000@qq.com
        > Created Time: 2022年07月20日 星期三 14时55分29秒
 ************************************************************************/

#include <iostream>
using namespace std;

#define BEGINES(x) namespace x { // namespace of x<F4>
#define ENDS(x) } // end of namespace x

BEGINES(test1)

class Base {

public :
    // 8 字节是存储虚函数表地址的
    virtual ~Base(){}

};

class A : public Base {
public :
    int x;
};

class B {
public :
    int x;

};

int main() {
    // 8 字节是存储虚函数表地址的
    cout << "sizeof(Base) = "<< sizeof(Base) << endl;
    // A类继承Base类 8 字节是虚函数表地址的,但是和Base类中虚函数表地址和A类中虚函数表的地址是不一样的
    // 但是A类中还有一个整形的变量 (最大数据类型是8字节)内存对齐
    cout << "sizeof(A)    = "<< sizeof(A) << endl;
    // B类只有一个int类型 所以只占4个字节
    cout << "sizeof(B)    = "<< sizeof(B) << endl;
    return 0;
}

ENDS(test1)

BEGINES(test2)

class Base {

public :
    virtual void func1() {
        cout << "Base func1" << endl;
        return ;
    }

    virtual void func2() {
        cout << "Base func2" << endl;
    }

    virtual void func3() {
        cout << "Base func3" << endl;
        return ;
    }

    // 8 字节是存储虚函数表地址的
    virtual ~Base(){}

};

class A : public Base {
public :
    // 重写
    void func2() override {
        cout << "A func2" << endl;
        return ;
    }
    int x;
};

class B : public Base {
public :
    void func1() override {
        cout << "B func1" << endl;
        return ;
    }

    void func3() override {
        cout << "B func3" << endl;
        return ;
    }
    int x;

};

typedef void (*func)();

int main() {
    A a;
    B b;
    a.func1();
    a.func2();
    a.func3();
    b.func1();
    b.func2();
    b.func3();
    // 调用虚函数表的第一个位置
    // func ** 第一地址(虚函数表) [1]虚函数表就是第二个函数
    ((func **)(&a))[0][1]();
    // ((func **)(&a))[0][0] = ((func **)(&b))[0][0];
    // 交换虚函数表的首地址
    swap(((func **)(&a))[0], ((func **)(&b))[0]);
    cout << "--------------------------" << endl;
    ((func **)(&a))[0][0]();
    ((func **)(&a))[0][1]();
    ((func **)(&a))[0][2]();
    return 0;
}

ENDS(test2)

BEGINES(test3)

class Base {

public :
    virtual void func(int x) {
        cout << this << " : Class Base : " << x << endl;
        return ;
    }

    // 8 字节是存储虚函数表地址的
    virtual ~Base(){}

};

class A : public Base {
public :
    // 重写
    void func(int x) override {
        cout << "this->x = " << this->x << endl;
        cout << this << " : Class A : " << x << endl;
        return ;
    }
    int x;
};


typedef void (*func)(void *, int x);

int main() {
    A a, b;
    a.x = 1333;
    b.x = 12345;
    a.func(123);
    // 有一个隐藏参数 this, int x
    ((func **)(&a))[0][0](&a, 123);
    ((func **)(&a))[0][0](&b, 123);

    return 0;
}

ENDS(test3)

int main() {
    // 类中虚函数表大小以及继承后的大小
    // test1::main();
    // test2::main();
    test3::main();
    return 0;
}
多态下类型转换 (动态类型转型)
1
2
3
4
// 是通过虚函数表来判断什么类型的
dynamic_cast<>()
// dynamic_cast 是怎么判断 正常虚函数表，的第一是虚函数，但是虚函数表有一个-1的位置，当定位道虚函数表的第一位时候在向上找一位，在向上找一位记类的信息是什么呢，就是当前类型的信息
    dynamic_cast 就是判断-1位置到底是什么来判断当前类型是什么
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
/*************************************************************************
        > File Name: 3.dynamic_cast.cpp
        > Author: 秃头王
        > Mail: 1658339000@qq.com
        > Created Time: 2022年07月20日 星期三 22时44分39秒
 ************************************************************************/

#include <iostream>
using namespace std;

#define BEGINS(x) namespace x {
#define ENDS(x) } // end of namespace x

BEGINS(test1)

class Base {

public :
    virtual ~Base(){}

};

class A : public Base {};
class B : public Base {};
class C : public Base {};

int main() {
    srand(time(0));
    Base *p;
    switch(rand() % 4) {
        case 0 : p = new A(); break;
        case 1 : p = new B(); break;
        case 2 : p = new C(); break;
        case 3 : p = nullptr; break;
    }


    A a;
    // if(p) 空地址
    // 不管 dynamic_cast 怎么判断我都希望 dynamic_cast 指向A对象
    if(p) ((void **)(p))[0] = ((void **)(&a))[0];

    if(dynamic_cast<A*>(p) != nullptr) {
        cout << "p pointer A class Object" << endl;
    } else if (dynamic_cast<B *>(p) != nullptr) {
        cout << "p pointer B class Object" << endl;
    } else if (dynamic_cast<C *>(p) != nullptr) {
        cout << "p pointer C class Object" << endl;
    } else {
        cout << "p is nullptr" << endl;
    }

    return 0;
}

ENDS(test1)

int main() {
    test1::main();
    return 0;
}

dynamic_cast他为什么要用虚函数表的-1位置类型信息去作为类型转换判断的依据？

image-20220721161916508

为什么虚函数表的类型信息要放在-1?

类型信息大小是不固定的，为什么放在上面因为取的时候方便

手动实现-queu、priority_queue

实现 queue (队列)：

  • 循环队列

  • 自动扩容 (2倍扩容法)

  • 插入、删除

  • 查看队头

  • 大小

实现 priority_queue (优先队列)：默认大顶堆

  • 自动扩容 (2倍扩容法)
  • 插入、删除
  • 查看队头
  • 大小
  • 自定义优先比较规则
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
/*************************************************************************
    > File Name: 4.priority_queue.cpp
    > Author: 秃头王
    > Mail: 1658339000@qq.com
    > Created Time: 2022年07月21日 星期四 16时33分12秒
 ************************************************************************/

#include <iostream>
#include <string>
#include <functional>
#include <stdlib.h>

using namespace std;

#define BEGINS(x) namespace x {
#define ENDS(x) } // end of namespace x

// BEGINS(ttw)

class IQueue {

public :

    virtual void push(int) = 0;
    virtual void pop() = 0;
    // virtual bool empty() = 0;
    virtual int top() = 0;
    /*
    virtual int front() = 0;
    virtual int size() = 0;
    */
    virtual bool empty() const = 0;
    virtual int top() const = 0;
    virtual int front() const = 0;
    virtual int size() const = 0;
    virtual ~IQueue() {}

};

class queue : public IQueue {

public :

    queue(const int n = 10) : data((int *)calloc(sizeof(int), n)), head(0), tall(0),count(0), __size(n) {

    }
    void push(const int val) override {
        if(count == __size) {
            expand();
        }
        data[tall++] = val;
        tall %= __size;
        count += 1;
        return ;
    }
    void pop() override {
        if(empty()) return ;
        head += 1;
        head %= __size;
        count -= 1;
        return ;
    }
    bool empty() const override { return count == 0; }
    int  front() const override {
        return this->empty() ? false : data[head];
    }
    int  size() const override { return count; }
    void swap(queue &q) {
        std::swap(this->data, q.data);
        std::swap(this->head, q.head);
        std::swap(this->tall, q.tall);
        std::swap(this->count, q.count);
        std::swap(this->__size, q.__size);
        return ;
    }
    /*
    bool empty() override { return count == 0; }
    int  front() override {
        return this->empty() ? false : data[head];
    }
    int  size() override { return count; }
    */
    ~queue() {
        if(data) delete [] data;
        return ;
    }

private :
    int *data;
    int head, tall, count, __size;

    void expand() {
        queue q(2 * __size);
        while(!empty()) {
            q.push(this->top());
            this->pop();
        }
        this->swap(q);
        return ;
    }

    int  top() override {
        return this->empty() ? false : data[head];
    }
   int  top() const override {
        return this->empty() ? false : data[head];
    }
    friend ostream &operator<<(ostream &out, const queue &);
};


class priority_queue : public IQueue {

private :
    // 正常下标从1开始的话就是 左孩子: 2 * i 右孩子: 2 * i + 1
    // 下标从0开始的话 左孩子: 2 * i + 1
    // data 在初始化时做的偏移量 访问data[1] == raw_data[0]
    int *raw_data, *data;
    int count, __size;
    function<int(int, int)> cmp;

    void expand() {
        priority_queue q(2 * __size, cmp);
        while(!empty()) {
            q.push(this->top());
            this->pop();
        }
        this->swap(q);
        return ;
    }

    friend ostream &operator<<(ostream &out, const priority_queue &);

public :
    priority_queue(int n = 10, function<int(int, int)> cmp = less<int>()) : raw_data(new int[n]), data(raw_data - 1), count(0), __size(n), cmp(cmp) {}

    int  top() const override {
        return this->empty() ? false : data[1];
    }

    int  top() override {
        return this->empty() ? false : data[1];
    }

    void push(const int val) override {
        if(count == __size) {
            expand();
        }
        count += 1;
        data[count] = val;
        up_maintain(count);
        return ;
    }
    void pop() override {
        if(empty()) return ;
        data[1] = data[count];
        count -= 1;
        down_maintain(1);
        return ;
    }

    void up_maintain(int ind) {
        if (ind == 1) return ;
        // if(data[int] > data[ind >> 1]) {
        if (cmp(data[ind >> 1], data[ind])) {
            std::swap(data[ind], data[ind >> 1]);
            up_maintain(ind >> 1);
        }
        return ;
    }

    void down_maintain(int ind) {
        if((ind << 1) >  count) return ;
        int temp = ind;
        #define LIND(x) (x << 1)
        #define RIND(x) (x << 1 | 1)
        /*
            if(data[temp] < data[ind << 1]) temp = ind << 1;
            if((ind << 1 | 1) <= count && data[temp] < data[ind << 1 | 1]) temp = data[ind << 1 | 1];
        */
        if(cmp(data[temp], data[LIND(ind)])) temp = LIND(ind);
        // if(data[temp] < data[LIND(ind)]) temp = LIND(ind);
        if(RIND(ind) <= count && cmp(data[temp], data[RIND(ind)])) temp = data[RIND(ind)];
        //if((RIND(ind)) <= count && data[temp] < data[RIND(ind)]) temp = data[RIND(ind)];
        if(temp == ind) return ;
        std::swap(data[temp], data[ind]);
        down_maintain(temp);
        return ;
    }

    bool empty() const override { return count == 0; }
    int  front() const override {
        return this->empty() ? false : data[1];
    }
    int  size() const override { return count; }
    void swap(priority_queue &q) {
        std::swap(this->raw_data, q.raw_data);
        std::swap(this->data, q.data);
        std::swap(this->count, q.count);
        std::swap(this->__size, q.__size);
        return ;
    }
    ~priority_queue() {
        if(data) delete [] raw_data;
        return ;
    }

};

// ENDS(ttw)

ostream &operator<<(ostream &out, const queue &q) {
    out << "queue : ";
    for(int i = 0, j = q.head; i < q.count; i += 1, j += 1) {
        j %= q.__size;
        out << q.data[i] << " ";
    }
    cout << endl;
    return out;
}

ostream &operator<<(ostream &out, const priority_queue &q) {
    out << "priority_queue : ";
    for(int i = 0; i < q.count; i += 1) {
        out << q.raw_data[i] << " ";
    }
    cout << endl;
    return out;
}

/*
 * 1: 实现 queue 普通队列
 * 2: 实现 priority_queue 优先队列
 * 3: 实现【优先队列】自定义优先规则
 */

bool cmp(int x, int y) {
    return x > y;
}

int main() {
    int op, val;
    // ttw::
    queue q1;
    // ttw::
    priority_queue q2;
    priority_queue q3(1, cmp);
    while(cin >> op) {
        switch(op) {
            case 0: {
                cin >> val;
                q1.push(val);
                q2.push(val);
                q3.push(val);
            } break;
            case 1: {
                cout << "    queue front : " << q1.front() << endl;
                cout << "  priority_less : " << q2.top() << endl;
                cout << "priority_greate : " << q3.top() << endl;
                q1.pop();
                q2.pop();
                q3.pop();
            } break;
        }
        cout << q1;
        cout << q2;
        cout << q3;
    }

    return 0;
}

源码文件*.cpp

点我跳转:https://github.com/qzwl123/C-/tree/main/%E5%A4%9A%E6%80%81

博客内容遵循 署名-非商业性使用-相同方式共享 4.0 国际 (CC BY-NC-SA 4.0) 协议

本文永久链接是：https://tutouwang.vercel.app/2022/07/19/OOP/%E5%A4%9A%E6%80%81/

更新于：2022年9月24日

评论