2.1 C++ note

C++

一、C++语言语法基础

(一)、从C到C++的过渡

  1. 背景介绍

    ​ 算盘 - 面向硬件的编程

    ​ 电子计算机

    ​ - 机器语言的编程1010

    ​ - 汇编语言的编程ADD

    ​ - 高级语言的编程Fortran

    ​ printf ("%d", 12);

    ​ - 结构化程序设计C/PASCL

    ​ - 顺序、分支、循环、函数

​ - 面向对象的程序设计C++/Java/C#

​ - 面向问题的程序设计

​ 1960 - Algol 60,算法语言,远离硬件,不适合进行系统开发

​ 1963 - 剑桥大学,CPL,在Algol 60的基础上增加对系统开发的支持,复杂,不易掌握,不易使用

​ 1970 - MIT,BCPL,CPL的精华版,易学易用,太慢,不实用

​ 1972 - Ken Thomposon,B语言,通过运行时支持优化BCPL的性能,缺少类型

​ 1973 - Dennis Ritchie,C语言,用C重新实现UNIX内核

​ 1978 - 《The C Programming Language》,第一个C语言的事实标准

​ 1989 - ANSI C,C89

​ 1990 - ISO C, C90

​ 1999 - ISO C 修订,C99

​ 197X - Bajarne Stroustrup,simula早期的面向对象语言,性能低下,B语言。

​ 1979 - 贝尔实验室,多核UNIX系统仿真,Cpre,通过扩展宏为C语言增加类似simula的面向对象机制。

​ C with Class:

​ simula - 类

​ Alogo 68 - 操作符重载

​ Ada - 模板、名字空间

​ Smalltalk - 引用、异常

​ C是C++的子集,C++是对C的扩展。

​ 1983 - C++命名

​ 1985 - CFront 1.0,第一款商用C++编译器

​ 1987 - GNU C++

​ 1990 - Borland C++

​ 1992 - Microsoft C++,IBM C++

​ 1998 - ISO C++98

​ 2003 - ISO C++03

​ 2011 - ISO C++2011/C++11/C++0x

  1. C++语言的使用领域:

    1.游戏开发:强建模能力,性能高。

    2.科学计算:FORTRAN,C++算法库。

    3.网络和分布式:ACE框架。

    4.桌面应用:VC/MFC,Office,QQ,多媒体

    5.操作系统和设备驱动:优化编译器的发明使C++在底层开发方面可以和C向媲美。

    6.移动终端:既需要性能,同时又要有面向对象的建模。

  2. C++比C更丰富

    (1).支持面向对象,将问题域和方法域统一化。宏观面向对象,微观面向过程。

    (2).支持泛型编程。

    int add (int a, int b) { ... }
    template\<typename T>
    T add (T a, T b) { ... }
    

    (3).支持异常机制。

    int func (void) {
        ...
    }
    int main (void) {
        if (func () == -1) {
            //错误处理;
        }
    }
    

    (4).操作符重载

  3. 第一个C++程序

    (1). 编译器:g++,如果使用gcc需要带上-lstdc++,指定其使用标准c++的运行库。

    (2). 源文件扩展名:.cpp/.cc/.C/.cxx/.c++,最好用.cpp。如果要用,可以在c头文件名前加c:#include \

    (3). 不再使用scanf/printf而是cin/cout。

    (4). 头文件:#include\大多数标准库头文件没有.h后缀。

    (5). 输出:cout – 标准输出对象

    ​ 输入运算符:<<

    ​ 提取输出运算符:>>

    #include <iostream>
    int main (void) {
        std::cout << "Hello, World !" << std::endl;
        int i;
        double d;
        char s[256];
    //    scanf ("%d%lf%s", &i, &d, s);
        std::cin >> i >> d >> s;
    //    printf ("%d %lf %s\n", i, d, s);
        std::cout << i << ' ' << d << ' ' << s << '\n';
        return 0;
    }
    

    (6). std:所有标准库的函数、对象、类型都位于std名字空间中。

    #include <iostream>
    using namespace std;
    struct Student {
        char name[128];
        int age;
        void who (void) {
            cout << "我叫" << name << ",今年" << age
                << "岁了。" << endl;
        }
    };
    int main (void) {
        Student student = {"张飞", 25}, *ps = &student;
        student.who ();
        ps->who ();
        struct A {};
        cout << sizeof (A) << endl;
        return 0;
    }
    

    (7). 名字空间:对程序中的标示符(类型、函数、变量)按照某种逻辑规则划分成若干组。

    ​ A. 定义名字空间:namespace 名字空间名 {名字空间成员;}

    ​ B. 使用名字空间:

    ​ a. 作用于限定符:名字空间名::名字空间成员,表示访问特定名字空间中特定成员。

    ​ b. 名字空间指令:using namespace 名字。空间名;在该条指令之后的代码对指令所有名字空间中的所有成员都可见,无需加“::”(作用域限定) ::为域运算符,在此表明一种限定,一个范围。

    ​ C. 名字空间声明:using 名字空间名::名字空间成员;将指定名字空间中的某个成员引入当前作用域,可直接访问这些成员,无需加“::”。4)匿名名字空间:如果一个标示符没有被显示地定义在任何名字空间中,编译器会将其缺省的置于匿名名字空间中。对匿名名字空间中的成员通过“::名字空间成员”的形式访问。

    ​ D. 名字空间合并

    ​ E. 名字空间嵌套

    #include <iostream>
    using namespace std;
    //namespace {
        void print (int money) {
            cout << money << endl;
        }
    //}
    // 农行名字空间
    namespace abc {
        int balance = 0;
        void save (int money) {
            balance += money;
        }
        void draw (int money) {
            balance -= money;
        }
    }
    namespace abc {
        void salary (int money) {
            balance += money;
        }
        void print (int money) {
            cout << "农行:";
            ::print (money);
        }
    }
    // 建行名字空间
    namespace ccb {
        int balance = 0;
        void save (int money) {
            balance += money;
        }
        void draw (int money) {
            balance -= money;
        }
        void salary (int money) {
            balance += money;
        }
    }
    int main (void) {
        using namespace abc; // 名字空间指令
        save (5000);
        cout << "农行:" << balance << endl;
        draw (3000);
        cout << "农行:" << balance    << endl;
        ccb::save (8000);
        cout << "建行:" << ccb::balance << endl;
        ccb::draw (5000);
        cout << "建行:" << ccb::balance << endl;
        using ccb::salary; // 名字空间声明
    //    using abc::salary;
        salary (6000);
        cout << "建行:" << ccb::balance << endl;
        abc::print (abc::balance);
        return 0;
    }
    

    (8).C++中的结构、联合、枚举

    ​ A. 结构

    ​ 定义结构型变量时,可以省略struct关键字。

    ​ 1)结构内部可以定义函数——成员函数。

    ​ 2)sizeof(空结构) -> 1

    #include <stdio.h>
    int main (void) {
        struct A {};
        printf ("%d\n", sizeof (struct A));
        struct A a;
        struct A* pa = &a;
        printf ("%p\n", pa);
        return 0;
    }
    

    ​ B. 联合

    ​ 增加了匿名联合概念。借用联合语法形式,描述一些变量在内存中的布局方式。

    #include <iostream>
    using namespace std;
    int main (void) {
        // 匿名联合
        union {
            int x;
            char c[4] /*= {'A', 'B', 'C', 'D'}*/;
        };
        cout << (void*)&x << ' ' << (void*)c << endl;
        x = 0x12345678;
        for (int i = 0; i < 4; ++i)
            cout << hex << (int)c[i] << ' ';
        cout << endl;
        return 0;
    }
    

    ​ C. 枚举

    ​ 枚举是一个独立的数据类型

    #include <iostream>
    using namespace std;
    int main (void) {
        enum E {a, b, c};
        E e;
        e = a;
        e = b;
        e = c;
    //    e = 1000;
    //    e = 1;
        return 0;
    }
    

    (9).C++的布尔类型【7.31/bool.cpp】

    ​ bool b = true; b = false;

    ​ cout<< sizeof (b)<< endl; // 1

    ​ b = 100;

    ​ b = 1.234;

    ​ b = “hello”;

    ​ b = ‘a’;

    ​ 可以将任何值赋值给bool类型的变量,以下四个值为false:0 ‘\0’ NULL false 其他一切值如果赋值给bool类型的变量都视为true。

    #include <iostream>
    using namespace std;
    void print (bool sex) {
        if (sex) 
            cout << "男生" << endl;
        else
            cout << "女生" << endl;
    }
    int main (void) {
        bool b = true;
        cout << sizeof (b) << endl;
        cout << b << endl;
        b = false;
        cout << b << endl;
        b = 3.14;
        cout << b << endl;
        char* p = NULL;
        b = p;
        cout << b << endl;
        cout << boolalpha << b << endl;
        bool sex;
        sex = 3;
        print (sex);
        return 0;
    }
    

    (10). C++中的运算符别名

    ​ && - and; 如:x>0&&y>0可以改写成x>0 and y>0。

    ​ || - or;

    ​ & - bitand;

    ​ ^ - xor;

    ​ { - <%

    ​ } - %>

    ​ [ - <:

    ​ ] - :>

    (11). C++中的函数

    ​ A. 重载:在同一个作用域中,函数名可以相同,参数表不同的函数,构成重载关系(总之能区分函数就可以了,函数名+数据类型(跟类型顺序也有关哦))。C++编译器会对程序中的函数做换名,将参数表中的类型信息汇合到函数名中,以保证函数名的唯一性。通过extern “c” ,可以要求编译器不做C++换名,以方便在C语言的模块中使用C++编译生成代码。

    #include <iostream>
    using namespace std;
    void foo (int a) {
        cout << "foo(int)" << endl;
    }
    void bar (int a) {}
    //int foo (int a) {}
    int foo (int a, double b) {
        cout << "foo(int,double)" << endl;
    }
    int foo (double a, int b) {
        cout << "foo(double,int)" << endl;
    }
    //int foo (int b, double a) {}
    int main (void) {
        foo (100);
        foo (100, 1.23);
        foo (1.23, 100);
    //    foo (100, 100);
        return 0;
    }
    

    ​ B. 缺省参数和哑元参数

    ​ a. 如果调用一个函数时,没有提供实参,那么对应形参就取缺省值。

    #include <iostream>
    using namespace std;
    namespace ns1 {
        int foo (int a) {
            cout << "ns1::foo(int)" << endl;
            return a;
        }
    };
    namespace ns2 {
        double foo (double a) {
            cout << "ns2::foo(double)" << endl;
            return a;
        }
    };
    int main (void) {
        using namespace ns1;
        using namespace ns2;
        cout << foo (10) << endl;
        cout << foo (1.23) << endl;
        using ns1::foo;
        cout << foo (10) << endl;
        cout << foo (1.23) << endl;
        using ns2::foo;
        cout << foo (10) << endl;
        cout << foo (1.23) << endl;
        return 0;
    }
    

    ​ b. 如果一个参数带缺省值,那么他后边的所有参数必须都带有缺省值。

    ​ c. 如果一个函数声明和定义分开,那么缺省参数只能放在声明中。

    ​ d. 避免和重载发生歧义。

    ​ e. 只有类型没有名字的形参,谓之哑元。

    #include <iostream>
    using namespace std;
    void foo (int a = 10, double b = 0.01, 
        const char* c = "tarena");
    void foo (void) {}
    void bar (int) {
        cout << "bar(int)" << endl;
    }
    void bar (int, double) {
        cout << "bar(int,double)" << endl;
    }
    int main (void) {
        foo (1, 3.14, "hello");
        foo (1, 3.14);
        foo (1);
    //    foo (); // 歧义
        bar (100);
        bar (100, 12.34);
        return 0;
    }
    void foo (int a /* = 10 */, double b /* = 0.01 */,
        const char* c /* = "tarena" */) {
        cout << a << ' ' << b << ' ' << c << endl;
    }
    

    ​ C. 内联

    ​ a. 编译器用函数的二进制代码替换函数调用语句,减少函数调用的时间开销。这种优化策略成为内联。

    ​ b. 频繁调用的函数适合内联,而稀少调用的复杂函数不适合内联。

    ​ c. 递归函数无法内联。

    ​ d. 通过inline关键字,可以建议编译对指定函数进行内联,但是仅仅是建议而已。inline void foo (int x,int y) {…….}

    (12). C++的动态内存分配

    ​ malloc/calloc/realloc/free

    ​ A. new/delete:对单个变量进行内存分配、释放。

    ​ B. new[]/delete[]:对数组进行内存分配/释放。

    #include <iostream>
    using namespace std;
    int main (void) {
    //    int* pi = (int*)malloc (sizeof (int));
    //    free (pi);
        int* pi = new int;
        *pi = 1000;
        cout << *pi << endl;
        delete pi;
        pi = NULL;
        /*
        *pi = 2000;
        cout << *pi << endl;
        */
        pi = new int[10];
        for (size_t i = 0; i < 10; ++i)
            pi[i] = i;
        for (size_t i = 0; i < 10; ++i)
            cout << pi[i] << ' ';
        cout << endl;
        delete[] pi;
        pi = NULL;
        pi = new int (1234);
        cout << *pi << endl;
        delete pi;
        pi = NULL;
        char buf[4] = {0x12,0x34,0x56,0x78};
        pi = new (buf) int;
        cout << hex << *pi << endl;
    //    delete pi;
        cout << (void*)pi << ' ' << (void*)buf << endl;
        int (*p)[4] = new int[3][4];
        delete[] p;
        int (*q)[4][5] = new int[3][4][5];
        delete[] q;
        return 0;
    }
    

    (13). 引用

    ​ A. 引用即别名。int a; int& b = a;给a起别名。b=10;cout<<a<<endl;//10

    ​ B. 引用必须初始化。int a; int* p;

    ​ a = 20; p = &a; int& b;//ERROR ! int& b = a; //OK

    ​ D. 引用一旦初始化就不能再引用其它变量。

    ​ int a = 20,c =30;

    ​ int& b = a;

    ​ b = c;//c => b/a

    ​ E. 引用的应用场景

    ​ a.引用型参数

    ​ b. 修改实参

    ​ c. 避免拷贝,通过加const可以防止在函数中意外地修改实参的值,同时还可以接受拥有常属性的实参。

    #include <iostream>
    using namespace std;
    void swap1 (int a, int b) {
        int c = a;
        a = b;
        b = c;
    }
    void swap2 (int* a, int* b) {
        int c = *a;
        *a = *b;
        *b = c;
    }
    void swap3 (int& a, int& b) {
        int c = a;
        a = b;
        b = c;
    }
    void swap4 (const char* x, const char* y) {
        const char* z = x;
        x = y;
        y = z;
    }
    void swap5 (const char** x, const char** y) {
        const char* z = *x;
        *x = *y;
        *y = z;
    }
    void swap6 (const char*& x, const char*& y) {
        const char* z = x;
        x = y;
        y = z;
    }
    struct Student {
        char name[1024];
        int age;
    };
    void print (const struct Student& s) {
        cout << s.name << "," << s.age << endl;
    //    s.age = -1;
    }
    void foo (const int& x) {
        cout << x << endl;
    }
    int main (void) {
        int a = 100, b = 200;
    //    swap1 (a, b);
    //    swap2 (&a, &b);
        swap3 (a, b);
        cout << a << ' ' << b << endl; // 200 100
        const char* x = "hello", *y = "world";
    //    swap4 (x, y);
    //    swap5 (&x, &y);
        swap6 (x, y);
        cout << x << ' ' << y << endl;
        Student s = {"张飞", 22};
        print (s);
        print (s);
        foo (100);
        return 0;
    }
    

    ​ d. 引用型返回值从一个函数中返回引用往往是为了将该函数的返回值作为左值使用。但是,一定要保留函数所返回的引用的目标在该函数返回以后依然有定义,否则将导致不确定的后果。不要返回局部变量的引用,可以返回全局、静态、成员变量的引用,也可以返回引用型形参变量本身。

    #include <iostream>
    using namespace std;
    int g_data = 100;
    int& foo (void) {
        return g_data;
    }
    int& bar (void) {
        int a = 100;
        return a;
    }
    int& fun (void) {
        int b = 200;
        return b;
    }
    int& hum (int& a) {
        return a;
    }
    int main (void) {
        int data = foo ();
        cout << data << endl; // 100
        foo () = 200;
        cout << g_data << endl;
        foo () += 100;
        ++foo ();
        cout << g_data << endl; // 301
        int& a = bar ();//引用不能再次赋值
    //    cout << fun () << endl;
        cout << a << endl; // 200,把后面的数放到了a的位置
        return 0;
    }
    

    ​ F. 引用和指针

    ​ a. 引用的本质就是指针,很多场合下引用和指针可以互换。

    ​ b. 在C++层面上引用和指针存在以下不同:

    ​ (a). 指针是实体变量,但是引用不是实体变量。

    ​ int& a=b;

    ​ sizeof (a);//4

    ​ double& d=f;

    ​ sizeof (d);//8

    ​ (b). 指针可以不初始化,但是引用必须初始化。

    ​ (c). 指针的目标可以修改,但是引用的目标的不能修改。

    ​ (d). 可以定义指针的指针,但是不能定义引用的指针。

    ​ int a;

    ​ int* p = &a;

    ​ int** pp = &p;//ok

    ​ int& r = a;

    ​ int&* pr = &r;//ERROR

    ​ (e). 可以定义指针的引用,但是不能定义引用的引用。

    ​ int a;

    ​ int* p = &a;

    ​ int*& q = p;//ok

    ​ int& r = a;

    ​ int&& s = r;//ERROR

    ​ (f). 可以定义指针的数组,但不能定义引用的数组。

    ​ int a, b, c;

    ​ int* parr[] = {&a,&b,&c};/ok

    ​ int& rarr[] = {a,b,c};//ERROR

    ​ 可以定义数组的引用。

    ​ int arr[] = {1 ,2,3};

    ​ int (&arr_ref)[3] = arr;//ok

    //指针相关 
    1.  int i = 5;
        int* p = &i;
        将p(而不是*P)的值设置为&i;初始化与赋值是完全不同的概念。
    2.  int *p;
        *p = 112233; //错
        对指针解引用之前,必须将指针初始化为一个确定的、适当的值。
    3.  int* p;
        p = (int*)0x8000000;
        将数字做地址使用时,必须强制将数字转换为适当的地址类型。
    4.  int* p = new int; // 未命名内存
        delete p;//销毁,释放空指针也是安全的。  
        new运算符根据类型来分配多大内存并将地址返回。
        int i;
        int* p = i; // 有名内存
    5.  int* p = new int[10]; // 创建动态数组
        delete[] p; //释放动态数组
        指针可以做动态创建的数组名使用:p[0]、p[1] ...
    6.    int p[10]; // 静态创建数组
        p 为首元素地址
        &p 为数组地址 
        p + 1 加一个变量的大小
        &p + 1 加一个数组大小 
        数组大小:sizeof(p) / sizeof( p[0] );
    

    (14). 显示类型转换运算符

    ​ 目标类型变量 = (目标类型)源类型变量;

    ​ A. 静态类型转换

    ​ static_cast<目标类型>(源类型变量)如果在目标类型和源类型之间某一方向上可以做隐式类型转换,那么在两个方向上都可以做静态类型转换。反之如果在两个方向都不能做类型转换,那么在任意一个方向上也不能做静态类型转换。

    ​ int* p1 = ……;

    ​ void* p1 = p2;

    ​ p1 = static_cast(p2);

    ​ char c;

    ​ int I = c;

    ​ 如果存在从源类型到目标类型的定义转换规则,那么也可以使用静态类型转换。

    #include <iostream>
    using namespace std;
    int main (void) {
        int* p1 = NULL;
        void* p2 = p1;
        p1 = static_cast<int*> (p2);
        return 0;
    }
    

    ​ B. 动态类型转换

    ​ dynamic_cast<目标类型>(源类型变量)用在具有多态性的父子类指针或引用之间。

    ​ C. 常类型转换

    ​ const_cast<目标类型>(源类型变量)给一个拥有const属性的指针或引用去常。

    ​ int a = 100;

    ​ const int* p1 = &a;

    ​ *p1 = 200;//ERROR

    ​ int p2 = const_cast<int>(p1);

    ​ *p2 = 200;//ok

    #include <iostream>
    using namespace std;
    int main (void) {
        const volatile int a = 100;  //加volatile表示不做常量优化
    //    a = 200;
        const volatile int* p1 = &a;
    //    *p1 = 200;
        int* p2 = const_cast<int*> (p1);//相当于解锁操作;
        *p2 = 200;
        cout << *p2 << endl; // 200
        cout << a << endl; // 200
        // cout << 100 << endl;
        return 0;
    }
    

    ​ D. 重解释类型转换

    ​ reinterpret_cast<目标类型>(源类型变量);在不同类型的指针或引用之间做类型转换,以及在指针和整型之间做类型转换(实质是不做常量优化,不成为字面值)。

    #include <iostream>
    using namespace std;
    int main (void) {
        int i = 0x12345678;
        char* p = reinterpret_cast<char*> (&i);
        for (size_t i = 0; i < 4; ++i)
            cout << hex << (int)p[i] << ' ';
        cout << endl;
        float* q = reinterpret_cast<float*> (&i);
        cout << *q << endl;
        void* v = reinterpret_cast<void*> (i);
        cout << v << endl;
        return 0;
    }
    

    在C中:目标类型变量 = 目标类型(源类型变量);int a = int (3.14);

  4. C++之父的建议

    (1). 少用宏,多用const,enum和inline。

    ​ #define PAI 3.14159

    ​ const double PAI = 3.14159;

    ​ #define ERORR_FILE -1;

    ​ #defile ERORR_MEM -2;

    ​ enum {

    ​ ERORR_FILE = -1,

    ​ ERORR_MEM = -2

    ​ };

    ​ #define max(a,b) ((a) > (b) ? (a) : (b))

    ​ inline int double max (double a,double b){return a > b ? a : b;}

    (2). 变量随用随时声明同时初始化。

    (3). 少用malloc/free,多用new/delete。

    (4). 少用C风格的强制类型转换,多用类型转换运算符。

    (5). 少用C风格的字符串,多用string。

    #include <iostream>
    #include <cstring>
    #include <cstdio>
    using namespace std;
    int main (void) {
        string s1 ("hello");//字符串的类。
        string s2 = "world";
        (s1 += " ") += s2;//合并s1和s2。
        cout << s1 << endl;
        string s3 = s1;
        cout << s3 << endl;
        cout << (s1 == s3) << endl;
        s3[0] = 'H';//将第一个字符替换掉了;
        cout << s3 << endl;
        cout << (s1 > s3) << endl;
        cout << s1.length () << endl;//计算字符串s1的长度;
        cout << (s1 == s3) << endl;
        cout << (strcasecmp (s1.c_str (),s3.c_str ()) == 0) << endl;//比较字符串大小,strcasecmp不区分大小写
    //    cout << (strcasecmp (s1.c_str (),s3.c_str ())) << endl;//比较字符串大小
        cout << sizeof (s1) << endl;//不能用sizeof计算字符串s1的大小;
        FILE* fp = fopen ("string.txt", "w");//记录的是指针地址而已;
    //    fwrite (&s3, sizeof (s3), 1, fp);
        fwrite (s3.c_str (), sizeof (char),s3.length (), fp);
        fclose (fp);
        return 0;
    }
    

    (6). 树立面向对象的编程思想。

(二)、类和对象

  1. 什么是对象

    1. 万物皆对象

    2. 程序就是一组对象,对象之间通过消息交换信息

    3. 类就是对对象的描述和抽象,对象就是类的具体化和实例化。

  2. 通过类描述对象

    属性:姓名、年龄、学号

    行为:吃饭、睡觉、学习

    类就是从属性和行为两个方面对对象进行抽象。

  3. 面向对象程序设计(OOP)

    现实世界 虚拟世界

    对象 -> 抽象 -> 类 -> 对象

    1. 至少掌握一种OOP编程语言
    2. 精通一种面向对象的元语言—UML
    3. 研究设计模式,GOF
  4. 类的基本语法

    1. 类的定义

      class 类名 {
      };
      如
      class Student {
      };
      
    2. 成员变量-属性

      class 类名 {
      };
      如:
      class Student {
          string  m_name;
          int   m_age;
      };
      
    3. 成员函数-行为

      class 类名 {
          返回类型 成员函数 (形参表){
              函数体
          }
      };
      如:
      class Student {
          string  m_name;
          int   m_age;
          void eat (const string& food){
          ……}
      };
      
    4. 访问控制属性

      (1) 共有成员:public,谁都可以访问

      (2) 私有成员:private,只有自己可以访问。

      (3) 保护成员:protected,只有自己和自己的子类可以访问。

      (4) 类的成员缺省访控属性为私有,而结构成员缺省访问属性为公有。

      int x = 10; //等号为初始化;

      另种初始化int x(10);

      int x;

      x = 10; //此时的等号为赋值符号;

      #include <iostream>
      using namespace std;
      class Student {
      private://将变量私有化;
          string m_name;
          int m_age;
      public:
          void eat (const string& food) {
              cout << m_age << "岁的" << m_name
                  << "同学正在吃" << food << "。" << endl;
          }
          void setName (const string& name) {
              if (name == "2")
                  cout << "你才" << name << "!" << endl;
              else
                  m_name = name;//不能直接访问私有,可以通过函数访问;
          }
          void setAge (int age) {
              if (age < 0)
                  cout << "无效的年龄!" << endl;
              else
                  m_age = age;
          }
      };
      int main (void) {
          Student student;//student为对象,此操作为定义一个对象;
          student.setName ("2");//通过点来读取对应的成员变量或函数;
          student.setAge (-100);
          student.setName ("张飞");
          student.setAge (20);
          student.eat ("包子");
          return 0;
      }
      
    5. 构造函数

      class 类名 {
          …
          类名 (形参表){
              构造函数体;
          }
      };
      当一个对象被创建时,构造函数会自动被执行,其参数来自构造实参。
      
    6. 构造函数可以通过构造参数实现重载。

    7. 如果一个类没有定义任何构造函数,那么系统就会缺省的为其提供一个无参构造函数,该构造函数对于基本类型的成员变量不做初始化,对于类类型的成员变量,调用其相应类型的无参构造函数初始化。

      #include <iostream>
      using namespace std;
      class A {
      public:
          A (int a) {}
      };
      class Student {
      private:
          string m_name;
          int m_age;
          A m_a;
      public:
          void eat (const string& food) {
              cout << m_age << "岁的" << m_name<< "同学正在吃" << food << "。" << endl;
          }
      //    void _ZN7Student3eatERKSs (Student* this,
      //        const string& food) {
      //        cout << this->m_age << "岁的"<<this->m_name
      //            << "同学正在吃" << food << "。" << endl;
      //    }
          void setName (const string& name) {
              if (name == "2")
                  cout << "你才" << name << "!" << endl;
              else
                  m_name = name;
          }
          void setAge (int age) {
              if (age < 0)
                  cout << "无效的年龄!" << endl;
              else
                  m_age = age;
          }
          // 构造函数
          Student (const string& name, int age) :   //函数名,参数表
              m_a (100) {
              m_name = name;
              m_age = age;
          }
          // 无参构造
          Student (void) : m_a (100) {
              m_name = "没名";
              m_age = 0;
          }
          // 单参构造
          Student (const string& name) : m_a (100),
              m_name (name),     m_age (0) {
              m_name = "哈哈";
          }
      };
      int main (void) {
          Student s1 ("张飞", 25);             //传参,隐示构造
          s1.eat ("包子");                 //必须按顺序传参,先隐在实;
      //    _ZN7Student3eatERKSs (&s1, "包子");    //
          Student s2 = Student ("赵云", 22);          //显示构造
          s2.eat ("烧饼");              //成员用点调用;
      //    _ZN7Student3eatERKSs (&s2, "烧饼");    
          Student s3;               //不能加小括号,没参就是无参构造;
          s3.eat ("煎饼果子");
          Student* s4    = new Student ("关羽", 30);        //构造实参
          s4->eat ("烤鸭");              //堆的调用,指针,用箭头
          delete s4;
          Student& s5 = *new Student ();       //引用调用
          s5.eat ("面条");          //用点
          delete &s5;
          Student sa1[3] = {s1, s2};         //第三个为0
          sa1[0].eat ("KFC");
          sa1[1].eat ("KFC");
          sa1[2].eat ("KFC");
          Student* sa2 = new Student[3] {s1, s2};       // 2011标准,new创造的数组
          sa2[0].eat ("KFC");
          sa2[1].eat ("KFC");
          sa2[2].eat ("KFC");
          delete[] sa2;            //清除
          Student s6 ("刘备");
          s6.eat ("米饭");
          return 0;
      }
      
    8. 对象的创建过程

      分配内存 –> 调用构造函数

      ​ ->调用类类型成员的构造函数 -> 构造函数的代码。

    9. 初始化表

      class 类名{
          类名(…) :初始化表{
          构造函数体;
          }
      };
      const int x = 100;
      x = 100;
      int& a = b;
      a = b;
      

      (1) 如果类中含有常量或引用型的成员变量,必须通过初始化表对其初始化。

      #include <iostream>
      using namespace std;
      int g_data = 1000;
      class A {
      public:
          A (void) : m_c (100), m_r (g_data) {  //只能放在初始化表中初始化
      //        m_c = 100;
      ///        m_r = g_data;
          }
          void print (void) {
              cout << m_c << ' ' << m_r << endl;
          }
      private:
          const int m_c;
          int& m_r;
      };
      int main (void) {
          A a;
          a.print ();
          return 0;
      }
      

      (2) 成员变量的初始化顺序仅于其被声明的顺序有关,而初始化表的顺序无关。

      class A {
          public:
          A (char* psz) : m_str (psz),
          m_len (strlen (psz)) private:
          size_t m_len;
          string m_str;
      };
      

      main.h

      #ifndef _S_H
      #define _S_H
      #include <string>
      using namespace std;
      // 声明Student类
      class Student {
      public:
          Student (const string& name = "", int age = 0);
          void eat (const string& food);
      private:
          string m_name;
          int m_age;
      };
      #endif // _S_H
      

      main.c

      #include "main.h"
      // 使用Student类
      int main (void) {
          Student s ("张飞", 25);
          s.eat ("包子");
          return 0;
      }
      

      练习:实现一个Clock类支持两种工作模式,计时器和电子钟。

      00:01:00

      14:05:37

      #include \ 需要包含的头文件

      cout << setw (10) << setfill ('0') << 12;

      0000000012

      setw设置输出宽度。setfill设置填充字符。

      Clock

      时、分、秒

      走 - 显示、滴答

      //实现一个CLOCK类支持两中工作模式,计时器和电子钟。
      #include <iostream>
      #include <iomanip>     //io流的格式控制
      using namespace std;
      class Clock {
      public:
          Clock (bool timer = true) :m_hour (0), m_min (0), m_sec (0) {         //构造函数,条件判断,初始化表
              if (! timer) {
                  time_t t = time (NULL);        //1970年到现在走秒
                  tm* local = localtime (&t);         //本地时间        //回去实现一下!
                  m_hour = local->tm_hour;        //赋值
                  m_min = local->tm_min;
                  m_sec = local->tm_sec;
              }
          }
          void run (void) {
              for (;;) {                //死循环
                  show ();
                  tick ();
              }
          }
      private:
          void show (void) {
              cout << '\r' << setfill ('0')       //\r相当于回车,当前行
                  << setw (2) << m_hour << ':'        //setw设置输出宽度
                  << setw (2) << m_min << ':'
                  << setw (2) << m_sec << flush;     //冲到内核里,从缓冲区拿出来
      //        printf ("\r%02d:%02d:%02d", m_hour,    //C的方式
      //            m_min, m_sec);
          }
          void tick (void) {
              sleep (1);//休息1秒
              if (++m_sec == 60) {
                  m_sec = 0;
                  if (++m_min == 60) {
                      m_min = 0;
                      if (++m_hour == 24)
                          m_hour = 0;
                  }
              }
          }
          int m_hour;//定义成员变量,定义为私有;
          int m_min;
          int m_sec;
      };
      int main (void) {
          Clock clock (true);    //这个clock是废物,貌似是传说中的函数重载,与类里面的那个构造函数与之相对应
      //    Clock clock (false);
          clock.run ();
          return 0;
      }
      
  5. this指针

    1. 一般而言,在类的构造函数或成员函数中,关键字this表示一个指针,对于构造函数而言,this指向正在被构造的对象,对于成员函数而言,this指向调用该函数的对象。

    2. this指针的用途

      1)在类的内部区分成员变量。

      this实质是个形参

      #include <iostream>
      using namespace std;
      class A {
      public:
          A (int data) : data (data) {//括号外面的就是成员变量
              cout << "构造: " << this << endl;//调用函数的指针this
      //        this->data = data;//加this区分成员变量
          }
          void foo (void) {
              cout << "foo: " << this << endl;
              cout << this->data << endl;//系统可以自己加箭头.通过指针找到变量;
          }
          int data;
      };
      int main (void) {
          A a (1000);
          cout << "main: " << &a << endl;
          a.foo ();
          A* pa = new A (1000);//堆里面情况也一样
          cout << "main: " << pa << endl;
          pa->foo ();
          delete pa;
      }
      

      2)在成员函数中返回调用对象自身。

      #include <iostream>
      using namespace std;
      class Counter {
      public:
          Counter (void) : m_data (0) {}
      //    Counter inc (void) {       //是克隆版
          Counter& inc (void) {       //去掉引用返回的就是克隆版
              ++m_data;
              return *this;
          }
          void print (void) {
              cout << m_data << endl;
          }
      private:
          int m_data;
      };
      int main (void) {
          Counter c;
      //    c.inc ();
      //    c.inc ();
      //    c.inc ();
          c.inc ().inc ().inc ();
          c.print (); // 3
          return 0;
      }
      

      3)在成员函数内部通过参数向外界传递调用对象自身,以实现对象间交互。

      老 -问题-> 学

      师 <-答案- 生

      class A {
          B  m_b;
      };
      class B {
          A  m_a;
      };   //ERORR,没法计算大小,指针和引用可以。
      sizeof (A) ?
      class C {
          C m_c;
      };   //ERORR
      
      //交叉类
      #include <iostream>
      using namespace std;
      class Student;           //短式声明
      class Teacher {
      public:
          void educate (Student* s);    //只是声明不做定义;
      //    {
      //        s -> ask ("什么是指针?",this);
      //        cout << "答案:" << m_answer << endl;
      //    }
          void reply (const string& answer) {
              m_answer = answer;
          }
      private:
          string m_answer;  //定义成员变量;
      };
      class Student {
      public:
          void ask (const string& question, Teacher* t) {   //此时的ask已经被指针所指向;
              cout << "问题:" << question << endl;
              t->reply ("不知道。");
          }
      };
      void Teacher::educate (Student* s) {      //外部定义
          s->ask ("什么是this指针?", this);    //this记录的是t的地址
          cout << "答案:" << m_answer << endl;
      }
      int main (void) {
          Teacher t;
          Student s;
          t.educate (&s);    //交付学生地址
          return 0;
      }
      
  6. 常函数与常对象

    1. 如果在一个类的成员函数的参数表后面加上const关键字,那么这个成员函数就被称为常函数,常函数的this指针是一个常指针。在常函数内部无法修改成员变量,除非该变量具有mutable属性。而且在常函数内部也无法调用非常函数。

    2. 常对象:拥有const属性的对象,对象引用或指针。

      常对象只能调用常函数。

      同型的常函数和非常函数可以构成重载关系。常对象调用常版本,非常对象调用非常版本(相互对应)。如果没有非常版本,非常对象也可以调用常版本。

      const XXX 函数名 (const YYY yyy) const {
          ...
      }
      

      const对应修饰:返回值、参数、this指针

      只用成员函数才有this指针,全局函数就没有。

      #include <iostream>
      using namespace std;
      class A {
      public:
      //    void bar (void) {
      //        cout << "非常bar" << endl;
      //    }
          void bar (void) const {    //将this指针变成常数
              cout << "常bar" << endl;
          }
      //  void XXXbarYYY (A* this) {}
          void foo (void) const {
      //        m_i = 100;         //前面加一个mutable就可以了
              const_cast<A*>(this)->m_i = 100;  //可以自己去常;
          }
          void print (void) const {
              cout << m_i << endl;
          }
      //    _ZNK1A3fooEv (const A* this) {        //k表明常函数,
      //        const_cast<A*>(this)->m_i = 100;    //  去常
      //    }
          int m_i;
      };
      void func (void) /*const*/ {}
      int main (void) {
          A a;
          a.foo ();
          a.print ();
          const A& r = a;     //常引用
          r.bar ();   //必须为常函数
      //    XXXbarYYY (&r); // const A*
          a.bar ();    //也可以调用非常
      //    XXXbarYYY (&a); // A*
          return 0;
      }
      
  7. 析构函数

    class 类名 {
        ~类名 (void) {  //必须没有参数
            析构函数体;
        }
    };
    

    当一个对象被销毁时自动执行析构函数。

    局部对象离开作用域时被销毁,堆对象被delete时被销毁。

    如果一个类没有定义任何析构函数,那么系统会提供一个缺省析构函数。缺省析构函数对基本类型的成员变量什么也不干,对类类型的成员变量,调用相应类型的析构函数。

    一般情况下,在析构函数中释放各种动态分配的资源。

    构造:基类->成员->子类

    析构:子类->成员->基类

    #include <iostream>
    using namespace std;
    class Double {
    public:
        Double (double data) :
            m_data (new double (data)) {    //开辟的是堆的地址
            cout << "构造" << endl;
        }
        ~Double (void) {     //析构函数,无参;自动释放内存;
            cout << "析构" << endl;
            delete m_data;
        }
        void print (void) const {
            cout << *m_data << endl;
        }
    private:
        double* m_data;
        string m_lable;
    };
    int main (void) {
    //    {
            Double d1 (3.14);
            d1.print ();
    //    }
        Double* d2 = new Double (1.23);
        delete d2;   //还可以调用析构函数
        cout << "再见!" << endl;
        return 0;
    
  8. 拷贝构造函数和拷贝赋值运算符

    1. 拷贝构造:用一个已有的对象,构造和它同类型的副本对象——克隆。

      #include <iostream>
      using namespace std;
      class Integer {
      public:
          Integer (int data = 0) : m_data (data) {}    //构造函数
          void print (void) const {
              cout << m_data << endl;
          }
      //    /*
          Integer (const Integer& that) :  //拷贝构造函数,编译器可以自己生成;
              m_data (that.m_data) {
              cout << "拷贝构造" << endl;
          }
      //    */
      private:
          int m_data;
      };
      void foo (Integer i) {
          i.print ();
      }
      Integer bar (void) {
          Integer i;
          return i;        //36行。优化策略,直接传的是i,不是匿名
      }
      int main (void) {
          Integer i1 (10);
          i1.print ();
          Integer i2 (i1); // 拷贝构造
          i2.print ();
          Integer i3 = i1; // 拷贝构造,  非赋值,这是初始化;
          i3.print ();
      //    Integer i4 (10, 20);
          cout << "调用foo()函数" << endl;
          foo (i1);
          cout << "调用bar()函数" << endl;
          Integer i4 (bar ());
          return 0;
      }
      
    2. 形如

      class X {
      X (const X& that) { ... }
      };
      

      的构造函数成为拷贝构造函数。如果一个类没有定义拷贝构造函数,系统会提供一个缺省拷贝构造函数。缺省拷贝构造函数对于基本类型的成员变量,按字节复制,对于类类型的成员变量,调用相应类型的拷贝构造函数。

    3. 在某些情况就下,缺省拷贝构造函数只能实现浅拷贝,如果需要获得深拷贝的复制效果,就需要自己定义拷贝构造函数。

      #include <iostream>
      using namespace std;
      class Integer {
      public:
          Integer (int data) : m_data (new int (data)) {}
          ~Integer (void) {
              if (m_data) {
                  delete m_data;
                  m_data = NULL;
              }
          }
          void print (void) const {
              cout << *m_data << endl;
          }
          Integer (const Integer& that) :  //拷贝构造
              m_data (new int (*that.m_data)) {}
          void set (int data) {
              *m_data = data;
          }
          Integer& operator= (const Integer& that) {
              // 防止自赋值
              if (&that != this) {
                  // 释放旧资源
                  delete m_data;
                  // 分配新资源
                  m_data = new int (*that.m_data);//实现深拷贝
                  // 拷贝新数据
              }
              // 返回自引用
              return *this;//
          }
      private:
          int* m_data;
      };
      int main (void) {
          Integer i1 (10);
          i1.print ();
          Integer i2 (i1);
          i2.print ();
          i2.set (20);
          i2.print ();
          i1.print ();
          Integer i3 (30);
          i3.print (); // 30
          i3 = i1; // 拷贝赋值,非拷贝构造,发生了浅拷贝
          // i3.operator= (i1);
          i3.print (); // 10
          i3.set (40);
          i3.print (); // 40
          i1.print (); // 10
          /*
          int a = 10, b = 20, c = 30;
          (a = b) = c;
          cout << a << endl;  //30
          */
          (i3 = i1) = i2;
      //    i3.operator=(i1).operator=(i2);
          i3.print ();
          i3 = i3;
          i3.print ();
          return 0;
      }
      
    4. 形如

      class X {
          X& operator= (const X& that) {
              ...
          }
      };
      

      的成员函数称为拷贝赋值运算符函数。如果一个类没有定义拷贝赋值运算符函数,系统会提供一个缺省拷贝赋值运算符函数。缺省拷贝赋值运算符函数对于基本类型的成员变量,按字节复制,对于类类型的成员变量,调用相应类型的拷贝赋值运算符函数。

      #include <iostream>
      using namespace std;
      class Nocopy {
      public:
          Nocopy (void) {}
      private:
          Nocopy (const Nocopy&);
          Nocopy& operator= (const Nocopy&);
      };
      void foo (ostream os) {
          os << "Hello, World !" << endl;
      }
      int main (void) {
          Nocopy n1;
          Nocopy n2 = n1;
          Nocopy n3;
          n3 = n1;
          foo (cout);
          return 0;
      }
      
    5. 在某些情况就下,缺省拷贝赋值运算符函数只能实现浅拷贝,如果需要获得深拷贝的复制效果,就需要自己定义拷贝赋值运算符函数。

      练习:实现一个简化版的字符串类String支持:

      1.用字符指针形式的字符串构造

      2.拷贝构造和拷贝赋值

      3.获取字符指针形式字符串的成员函数,类似string::c_str

      说明:不得使用std::string!

      //简化版的字符串类string;
      #include <iostream>
      #include <cstring>   // c的东东
      using namespace std;
      class String {
      public:
          String (const char* str = NULL) {   //给个指针
              m_str = new char[strlen(str?str:"")+1];   //开辟空间,加一放\0;判断一下防止strlen蹦掉
              strcpy (m_str, str ? str : "");     // 拷贝字符串到缓冲区,
          }
          ~String (void) {        //析构函数
              if (m_str) {
                  delete[] m_str;
                  m_str = NULL;
              }
          }
          String (const String& that) :
              m_str (strcpy (
                  new char[strlen(that.m_str)+1],
                  that.m_str)) {}
          /* 菜鸟
          void operator= (const String& that) {         //内存泄露
              m_str = new char[strlen(that.m_str)+1];
              strcpy (m_str, that.m_str);
          }*/
          String& operator= (const String& that) {
              if (&that != this) {
                  /* 小鸟
                  delete[] m_str;
                  m_str = new char[strlen(that.m_str)+1];    //可能自赋值,就会出错必须加if判断
                  strcpy (m_str, that.m_str);
                  */
                  /* 大鸟
                  char* str = 
                      new char[strlen(that.m_str)+1];
                  delete[] m_str;
                  m_str = strcpy (str, that.m_str);
                  */
                  // 老鸟
                  String temp (that);  //
                  swap (m_str, temp.m_str);// 交换两个参数
              }
              return *this;
          }
          const char* c_str (void) const {
              return m_str;
          }
      private:
          char* m_str;
      };
      int main (void) {
          String s1 ("Hello, World !");
          cout << s1.c_str () << endl;
          String s2 = s1;
          cout << s2.c_str () << endl;
          String s3 ("Hello, Linux !");
          try {
              s1 = s3;
          }
          catch (exception& ex) {
              cout << ex.what () << endl;
          }
          cout << s1.c_str () << endl;
          return 0;
      }
      
  9. 静态成员

    1. 静态成员变量和静态成员函数是属于类的而非属于对象。

    2. 静态成员变量,为多个对象所共享,只有一份实例,可以通过对象访问也可以通过类访问,必须在类的外部定义并初始化。静态成员变量本质上与全局变量并没有区别,只是多了类作用域的约束,和访控属性的限制。

      class Account {
          private:
          string m_name;
          double m_balance;
          static double m_rate;
      };
      
      #include <iostream>
      using namespace std;
      class A {
      public:
          static int m_i;
          static void foo (void) {
              cout << "foo:" << m_i << endl;
      //        m_d = 3.14;      //静态的不能访问普通的,因为没this指针;
      //        bar ();
          }
          double m_d;
          void bar (void) {
              m_i = 1000;
              foo ();
          }
      };
      int A::m_i = 1;    //作用域限定,必须在外面声明全局变量;
      int main (void) {
          A::m_i = 10;
          A a1, a2;
          cout << ++a1.m_i << endl;   //对象访问
          cout << a2.m_i << endl;
          A::foo ();
          a1.foo ();
          a1.bar ();
          return 0;
      }
      
    3. 静态成员函数,没有this指针,无法访问非静态成员。

    4. 单例模式

      懒汉式:

      懒汉式是指,在第一次获取这个类的实例的时候才new这个对象。即可以延迟加载该对象实例。

      懒汉式单例设计模式在多线程同时初始化实例的时候有线程安全问题, 解决的方案是,加同步锁,使用同步方法和同步代码块都能解决问题。 然而多线程每次都访问锁,导致效率低下,所以使用同步代码块,然后以双重判断的形式来解决每次都判断同步锁导致的效率低下问题。

      #include <iostream>
      using namespace std;
      // 懒汉方式
      class Singleton {
      public:
          static Singleton& getInst (void) {
              if (! m_inst)
                  m_inst = new Singleton;
              ++m_cn;
              return *m_inst;
          }
          void releaseInst (void) {    //释放实例
              if (m_cn && --m_cn == 0)
                  delete this;
          }
      private:
          Singleton (void) {
              cout << "构造:" << this << endl;
          }
          Singleton (const Singleton&);
          ~Singleton (void) {
              cout << "析构:" << this << endl;
              m_inst = NULL;
          }
          static Singleton* m_inst;
          static unsigned int m_cn;
      };
      Singleton* Singleton::m_inst = NULL;
      unsigned int Singleton::m_cn = 0;
      int main (void) {
          Singleton& s1 = Singleton::getInst ();
          Singleton& s2 = Singleton::getInst ();
          Singleton& s3 = Singleton::getInst ();
          cout << &s1 << ' ' << &s2 << ' ' << &s3 << endl;
       s3.releaseInst ();
          s2.releaseInst ();
          s1.releaseInst ();
          return 0;
      }
      

      饿汉式: 饿汉式是指,在类加载的时候即new出该类对象。 饿汉式单例模式在类加载时就创建了单例对象,它是线程安全的。

      
      
      
      //单例模式
      #include <iostream>
      using namespace std;
      // 饿汉方式
      class Singleton {
      public:
          static Singleton& getInst (void) {
              return s_inst;
          }
      private:
          Singleton (void) {}
          Singleton (const Singleton&);  //拷贝私有化
          static Singleton s_inst;
      };
      Singleton Singleton::s_inst; //静态成员变量//始终仅存在一个对象
      int main (void) {
          Singleton& s1 = Singleton::getInst ();
          Singleton& s2 = Singleton::getInst ();
          Singleton& s3 = Singleton::getInst ();
          cout << &s1 << ' ' << &s2 << ' ' << &s3 << endl;
          return 0;
      }
      
  10. 成员指针

    Student s;
    string* p = &s.m_name; // 不是
    Student s2;
    

    (一)成员变量指针

    1. 定义

      成员变量类型 类名::*指针变量名;

      string Student::*pname;
      int Student::*page;0
      
    2. 初始化/赋值

      指针变量名 = &类名::成员变量名

      pname = &Student::m_name;
      page = &Student::m_age;
      
    3. 解引用

      对象.*指针变量名(.*为引用型)

      对象指针->*指针变量名(->*为指针型)

      Student s, *p = &s;
      s.*pname = "张飞";
      cout << p->*page << endl;
      

    (二)成员函数指针

    1. 定义

      成员函数返回类型 (类名::*指针变量名) (参数表)

      void (Student::*plearn) (const string&) const;
      
    2. 初始化/赋值

      指针变量名 = &类名::成员函数名;

      plearn = &Stduent::learn;
      
    3. 解引用

      (对象.*指针变量名) (实参表);

      (对象指针->*指针变量名) (实参表);

      (s.*plearn) ("C++");
      (p->*plearn) ("UNIX");
      
      #include <iostream>
      #include <cstring>
      using namespace std;
      class Student {
      public:
          Student (const string& name, int age) :
              m_name (name), m_age (age) {}
          double m_weight;
          string m_name;
          int m_age;
          void learn (const string& lesson) const {
              cout << "我在学" << lesson << endl;
          }
          static void hello (void) {
              cout << "你好!" << endl;
          }
      };
      int main (void) {
          string Student::*pname = &Student::m_name;
          void* pv;
          memcpy (&pv, &pname, 4);
          cout << pv << endl;
          int Student::*page = &Student::m_age;
          memcpy (&pv, &page, 4);
          cout << pv << endl;
          Student s ("张飞", 25), *p = &s;
          cout << s.*pname << endl; // 
          cout << p->*page << endl;
          Student s2 ("赵云", 22);
          cout << s2.*pname << endl;
          void (Student::*plearn) (const string&) const =
              &Student::learn;
          (s.*plearn) ("C++");
          (p->*plearn) ("UNIX");
          void (*phello) (void) = Student::hello;
          phello ();
          return 0;
      }
      

(三)、操作符重载

  1. 操作符标记和操作符函数

    1. 双目操作符:L # R(通式)

      成员函数形式:L.operator# (R)

      左调右参

      全局函数形式:::operator# (L, R)

      左一右二

    2. 单目操作符:#O/O#

      成员函数形式:O.operator# ()

      全局函数形式:::operator# (O)

    3. 三目操作符:不考虑

  2. 双目操作符

    1. +/-/*//

      操作数在计算前后不变。

      表达式的值是右值。

      int func(void)

      {

      ​ char I = 10;

      ​ return 0;

      } 返回的为int型

      #include <iostream>
      using namespace std;
      class Complex {
      public:
          Complex (int r = 0, int i = 0) :
              m_r (r), m_i (i) {}
          void print (void) const {
              cout << m_r << '+' << m_i << 'i' << endl;
          }
          // 第一个const:返回右值
          // 第二个const:支持常量型右操作数
          // 第三个const:支持常量型左操作数
          const Complex operator+ (
              const Complex& r) const {
              return Complex (m_r + r.m_r, m_i + r.m_i);
          }
      private:
          int m_r;
          int m_i;
          friend const Complex operator- (const Complex&,
              const Complex&);
      };
      const Complex operator- (const Complex& l,
          const Complex& r) {
          return Complex (l.m_r - r.m_r, l.m_i - r.m_i);
      }
      int main (void) {
          const Complex c1 (1, 2);
          c1.print ();
          const Complex c2 (3, 4);
          Complex c3 = c1 + c2; // c3 = c1.operator+ (c2)
          c3.print (); // 4+6i
      //    (c1 + c2) = c3;
          c3 = c2 - c1; // c3 = ::operator- (c2, c1)
          c3.print (); // 2+2i
          return 0;
      }
      
    2. +=/-=/*=...

      左变右不变。

      表达式的值是左值,左操作数的引用。

      (a += b) = c;

      #include <iostream>
      using namespace std;
      class Complex {
      public:
          Complex (int r = 0, int i = 0) :
              m_r (r), m_i (i) {}
          void print (void) const {
              cout << m_r << '+' << m_i << 'i' << endl;
          }
          Complex& operator+= (const Complex& r) {
              m_r += r.m_r;
              m_i += r.m_i;
              return *this;
          }
          friend Complex& operator-= (Complex& l,const Complex& r) {
              l.m_r -= r.m_r;
              l.m_i -= r.m_i;
              return l;
          }
      private:
          int m_r;
          int m_i;
      };
      int main (void) {
          Complex c1 (1, 2), c2 (3, 4);
          c1 += c2; // c1.operator+= (c2)   //+=为独立的运算符
          c1.print (); // 4+6i
          Complex c3 (5, 6);
          (c1 += c2) = c3;
          c1.print (); // 5+6i
          c1 -= c2; // ::operator-= (c1, c2)
          c1.print (); // 2+2i
          (c1 -= c2) = c3;
          c1.print (); // 5+6i;
          return 0;
      }
      
    3. <</>>

      int i = 10;

      float f = 1.23;

      Complex c (...);

      cout << c << i << f << endl;

      cin >> c;

      左操作数ostream/istream类型,不能是常量,不能拷贝。

      右操作数自定义类型,对于<<可以是常量,对于>>不能是常量。

      表达式的值是左操作数的引用。

      ::operator<< (cout, c).operator<< (i).operator<< (f).operator<< (endl);

      #include <iostream>
      using namespace std;
      class Complex {
      public:
          Complex (int r = 0, int i = 0) :
              m_r (r), m_i (i) {}
          void print (void) const {
              cout << m_r << '+' << m_i << 'i' << endl;
          }
          friend ostream& operator<< (ostream& os,const Complex& r) {     //输出运算符
              return os << r.m_r << '+' << r.m_i << 'i';
          }
          friend istream& operator>> (istream& is,Complex& r) {
              return is >> r.m_r >> r.m_i;
          }
      private:
          int m_r;
          int m_i;
      };
      int main (void) {
          Complex c1 (1, 2), c2 (3, 4);
          cout << c1 << endl << c2 << endl;
      //    ::operator<<(::operator<<(cout,c1).operator<<(
      //        endl),c2).operator<<(endl);   //函数实现
          cin >> c1 >> c2;
          cout << c1 << endl << c2 << endl;
          return 0;
      }
      
  3. 单目操作符

    1. -(取负)/!/~

      操作数不变。

      表达式的值是右值。

      #include <iostream>
      using namespace std;
      class Complex {
      public:
          Complex (int r = 0, int i = 0) :
              m_r (r), m_i (i) {}
          void print (void) const {
              cout << m_r << '+' << m_i << 'i' << endl;
          }
          const Complex operator- (void) const {
              return Complex (-m_r, -m_i);
          }
          friend const Complex operator~ (const Complex& o) {
              return Complex (o.m_i, o.m_r);
          }
      private:
          int m_r;
          int m_i;
      };
      int main (void) {
          const Complex c1 (1, 2);
          Complex c2 = -c1; // c2=c1.operator-()
          c2.print (); // -1+-2i
          Complex c3 = ~c1; // c3=::operator~(c1)    //全局函数
          c3.print (); // 2+1i;
          return 0;
      }
      
    2. 前++/前--

      操作数变。

      #include <iostream>
      using namespace std;
      int main (void) {
          int i = 0;
      //    int a = 10,b = 200,c = 30;
        //  (a += b) = c;
          //cout << a << b << c <<endl;
          (i++) = 100;
      //    (++i) = 100;  //前加加返回的是左值
          cout << i << endl;
          cout << i++++++ << endl; // 103
      //    cout << ++++++i << endl; // 103
          return 0;
      }
      

      表达式的值是运算以后的值。

      表达式的值是左值,操作数的引用。

      (++i) = 100;

      ++++++i;

      #include <iostream>
      using namespace std;
      class Complex {
      public:
          Complex (int r = 0, int i = 0) :
              m_r (r), m_i (i) {}
          void print (void) const {
              cout << m_r << '+' << m_i << 'i' << endl;
          }
          Complex& operator++ (void) {
              ++m_r;
              ++m_i;
              return *this;
          }
          friend Complex& operator-- (Complex& o) {
              --o.m_r;
              --o.m_i;
              return o;
          }
      private:
          int m_r;
          int m_i;
      };
      int main (void) {
          Complex c1 (1, 2);
          Complex c2 = ++c1; // c2=c1.operator++()
          c1.print (); // 2+3i
          c2.print (); // 2+3i
          (++c1) = Complex (10, 20);
          c1.print (); // 10+20i;
          (++++++c1).print (); // 13+23i
          c2 = --c1; // c2=::operator--(c1)
          c1.print (); // 12+22i
          c2.print (); // 12+22i
          return 0;
      }
      
    3. 后++/后--

      操作数变。

      表达式的值是运算以前的值。

      表达式的值是右值。

      #include <iostream>
      using namespace std;
      class Complex {
      public:
          Complex (int r = 0, int i = 0) :
              m_r (r), m_i (i) {}
          void print (void) const {
              cout << m_r << '+' << m_i << 'i' << endl;
          }
          const Complex operator++ (int) {
              Complex old (*this);
              ++m_r;
              ++m_i;
              return old;
          }
          friend const Complex operator-- (Complex& o,
              int) {
              Complex old (o);
              --o.m_r;
              --o.m_i;
              return old;
          }
      private:
          int m_r;
          int m_i;
      };
      int main (void) {
          Complex c1 (1, 2);
          Complex c2 = c1++; // c2=c1.operator++(0)  //区分前加加
          c1.print (); // 2+3i;
          c2.print (); // 1+2i;
      //    (c1++) = c2;//错
      //    c1++++++;//错
          c2 = c1--; // c2=::operator--(c1,0)
          c1.print (); // 1+2i
          c2.print (); // 2+3i
          return 0;
      }
      
  4. 其它操作符

    1. 下标操作符:[]

      int arr[10] = { ... };

      arr[1] = 10;

      cout << arr[1] << endl;

      -----------------------

      class Array { ... };

      Array arr (...);

      arr[1] = 10;

      cout << arr[1] << endl;

      双目操作符,左操作数是一个具有容器特性的对象,右操作数是容器中特定数据元素的索引(基零的下标)。

      下标表达式的值可以是左值,也可以是右值,由容器对象的常属性决定。常容器下标表达式的值是右值,非常容器下标表达式的值是左值。

      #include <iostream>
      using namespace std;
      class Array {
      public:
          Array (size_t size = 1) :
              m_data (new int[size]) {}
          ~Array (void) {
              if (m_data) {
                  delete m_data;
                  m_data = NULL;
              }
          }
          int& operator[] (size_t i) {  //返回引用
              return m_data[i];
          }
          const int& operator[] (size_t i) const {
              return const_cast<Array&> (*this)[i];
          }
      private:
          int* m_data;
      };
      int main (void) {
          Array arr (10);
          for (size_t i = 0; i < 10; ++i)
              arr[i] = i; // arr.operator[](i) = i;
          arr[0]++;
          const Array& cr = arr;
          for (size_t i = 0; i < 10; ++i)
              cout << cr[i] << ' ';
          cout << endl;
      //    cr[0]++;//常属性不能改
          return 0;
      }
      
    2. 函数操作符:()

      如果为一个类定义了形如:

      返回类型 operator() (形参表) {...}

      的操作符函数,那么这个类所实例化的对象就可以被当做函数使用。

      #include <iostream>
      using namespace std;
      class Square {
      public:
          double operator() (double x) {
              return x * x;
          }
      };
      class Integer {
      public:
          explicit Integer (int i = 0) : m_i (i) {}    //变为显示类型转换
          void print (void) const {
              cout << m_i << endl;
          }
          Integer& operator() (int i) {
              m_i += i;
              return *this;
          }
          Integer& operator, (int i) {
              m_i += i;
              return *this;//自引用
          }
          operator int (void) const {    //
              return m_i;
          }
      private:
          int m_i;
      };
      void foo (const Integer& i) {
          i.print ();
      }
      Integer bar (void) {
          return Integer (300);
      }
      int main (void) {
          Square square;
          cout << square (3) << endl;
      //    cout << square.operator() (3) << endl;//编译器处理后
          Integer i (10);
          i (1) (2) (3) (17);
          i.print (); // 33
          i, 1, 2, 3, 17;
          i.print (); // 56
          i = (Integer)100;
          i.print ();
          foo (static_cast<Integer> (200));
          bar ().print ();
          int n = i;
          cout << n << endl;
          return 0;
      
    3. 解引用(*)和间接访问(->)操作符

      以指针的方式使用类类型的对象。

      #include <iostream>
      #include <memory>  //智能指针头文件
      using namespace std;
      class A {
      public:
          A (void) {
              cout << "构造" << endl;
          }
          ~A (void) {
              cout << "析构" << endl;
          }
          void hello (void) {
              cout << "Hello, World !" << endl;
          }
      };
      class PA {
      public:
          PA (A* p = NULL) : m_p (p) {}
          ~PA (void) {
              if (m_p) {
                  delete m_p;
                  m_p = NULL;
              }
          }
          A& operator* (void) const {
              return *m_p;
          }
          A* operator-> (void) const {
      //        return &**this;
              return m_p;
          }
          PA (PA& that) : m_p (that.release ()) {}     //
          PA& operator= (PA& that) {
              if (&that != this)
                  reset (that.release ());
              return *this;
          }
      private:
          A* release (void) {
              A* p = m_p;
              m_p = NULL;
              return p;
          }
          void reset (A* p) {
              if (p != m_p) {
                  delete m_p;
                  m_p = p;
              }
          }
          A* m_p;
      };
      void bar (auto_ptr<A> pa) {
          cout << "bar:";
          pa -> hello ();
      }
      void foo (void) {
          PA pa (new A);
      //    A* pa = new A;
      //    pa -> hello ();
      //  (*pa).hello ();
      //    A* pb = pa;
          pa -> hello (); // pa.operator->()->hello();
          (*pa).hello (); // pa.operator*().hello();
          PA pb = pa;
          pb -> hello ();
          auto_ptr<A> pa1 (new A);
          pa1 -> hello ();
          auto_ptr<A> pa2 = pa1;
          (*pa2).hello ();
          bar (pa2);
          cout << pa2.get () << endl;
      }
      // smart_ptr
      int main (void) {
          foo ();
          return 0;
      }
      
    4. 自定义类型转换和类型转换操作符

      1) 通过单参构造实现自定义类型转换

      如果A类中有一个可以接受B类对象做为唯一参数的构造函数,那么B类型的对象就可以根据该构造函数被转换为A类型。

      通过explicit关键字,可以强制使用该构造函数所完成的类型转换必须显示进行。

      2) 通过类型转换操作符函数实现自定义类型转换

      如果A类中有一个形如

      operator B (void) const { ... }

      的操作符函数,那么A类型的对象就可以根据该函数被转换为B类型。

      #include <iostream>
      #include <cstring>
      using namespace std;
      class String {
      public:
          String (const char* str = NULL) {
              m_str = new char[strlen(str?str:"")+1];
              strcpy (m_str, str ? str : "");
          }
          ~String (void) {
              if (m_str) {
                  delete[] m_str;
                  m_str = NULL;
              }
          }
          String (const String& that) :
              m_str (strcpy (
                  new char[strlen(that.m_str)+1],
                  that.m_str)) {}
          /* 菜鸟
          void operator= (const String& that) {
              m_str = new char[strlen(that.m_str)+1];
              strcpy (m_str, that.m_str);
          }*/
          String& operator= (const String& that) {
              if (&that != this) {
                  /* 小鸟
                  delete[] m_str;
                  m_str = new char[strlen(that.m_str)+1];
                  strcpy (m_str, that.m_str);
                  */
                  /* 大鸟
                  char* str = 
                      new char[strlen(that.m_str)+1];
                  delete[] m_str;
                  m_str = strcpy (str, that.m_str);
                  */
                  // 老鸟
                  String temp (that);
                  swap (m_str, temp.m_str);
              }
              return *this;
          }
          const char* c_str (void) const {
              return m_str;
          }
          operator const char* (void) const {
              return c_str ();
          }
      private:
          char* m_str;
      };
      int main (void) {
          String s1 ("Hello, World !");
          cout << s1.c_str () << endl;
          String s2 = s1;
          cout << s2.c_str () << endl;
          String s3 ("Hello, Linux !");
          try {
              s1 = s3;
          }
          catch (exception& ex) {
              cout << ex.what () << endl;
          }
          cout << s1.c_str () << endl;
          const char* psz = s1;
          cout << s1 << endl;
          cout << psz << endl;
          return 0;
      }
      

      3) 如果目标类型是类类型,源类型是基本类型,那么就只能通过在目标类型中定义以源类型为单参的构造函数实现类型转换。如果目标类型是基本类型,源类型是类类型,那么就只能通过在源类型中定义以目标类型为函数名的类型转换操作符函数实现类型转换。如果目标类型和源类型都是类类型,那么以上两种方法任取其一,但是不能同时使用。如果目标类型和源类型都是基本类型,那么无法实现自定义类型转换。

      #include <iostream>
      #include <cstdlib>
      using namespace std;
      class A {
      public:
          ~A (void) {}
          static void* operator new (size_t size) {
              void* p = malloc (size);
              cout << "我的new   :" << p << ' '
                  << size << endl;
              return p;
          }
          static void operator delete (void* p) {
              cout << "我的delete:" << p << endl;
              free (p);
          }
          static void* operator new[] (size_t size) {
              void* p = malloc (size);
              cout << "我的new[]   :" << p << ' '
                  << size << endl;
              return p;
          }
          static void operator delete[] (void* p) {
              cout << "我的delete[]:" << p << endl;
              free (p);
          }
      private:
          int m_i;
          double m_d;
          char m_c;
      };    // IIIIDDDDDDDDCXXX
      int main (void) {
          cout << sizeof (A) << endl;
          A* pa = new A;
          cout << pa << endl;
          delete pa;
          pa = new A[2];
          cout << pa << endl;
          delete[] pa;
          return 0;
      }
      
    5. new/delete操作符

      练习:实现3x3矩阵,支持+/+=//=/前++/后--/<<

      练习:实现一个日期类date,支持

      +/+=:增加天数

      -/-=:减少天数

      - :计算两个日期的间隔天数

      >> :2013 5 24

      <<:2013-5-24

  5. 关于操作符重载的限制

    1. 至少有一个操作数是类类型的。

      int a = 10, b = 20;

      int c = a + b; // 200

      int operator+ (int a, int b) {

      return a * b;

      } // ERROR !

    2. 不是所有的操作符都能重载。

      :: - 作用域限定

      . - 直接成员访问

      .* - 直接成员指针解引用

      ?: - 三目运算符

      sizeof - 获取字节数

      typeid - 获取类型信息

    3. 不是所有的操作符都可以用全局函数的方式实现。

      = - 拷贝赋值

      [] - 下标

      () - 函数

      -> - 间接成员访问

      ​ 4.不能发明新的操作符。

      x ** y; // x^y //ERORR

      #

      @

      // 日期运算。
      // 实现日期类,支持如下运算:
      // +/+=:增加指定的天数;
      // -/-=:减去指定的天数;
      // -   :两日期相差天数。
      // >>  :接受形如2012 1 14格式输入;
      // <<  :以形如2012-1-14的格式输出;
      #include <iostream>
      using namespace std;
      class Date {
      public:
          Date (int nYear = 0, int nMonth = 0,
              int nDay = 0) :
              m_nYear (nYear), m_nMonth (nMonth),
              m_nDay (nDay) {}
          Date operator+ (int nDays) const {
              return Days2Date (Date2Days () + nDays);
          }
          Date& operator+= (int nDays) {
              return *this = *this + nDays;
          }
          Date operator- (int nDays) const {
              return Days2Date (Date2Days () - nDays);
          }
          Date& operator-= (int nDays) {
              return *this = *this - nDays;
          }
          int operator- (const Date& date) const {
              return Date2Days () - date.Date2Days ();
          }
          friend istream& operator>> (istream& is,
              Date& date) {
              return is >> date.m_nYear >> date.m_nMonth
                  >> date.m_nDay;
          }
          friend ostream& operator<< (ostream& os,
              const Date& date) {
              return os << date.m_nYear << "-"
                  << date.m_nMonth << "-" << date.m_nDay;
          }
      private:
          int Date2Days (void) const {
              int nDays = (m_nYear - 1) * 365;
              for (int nYear = 1; nYear < m_nYear;
                  nYear++)
                  if (IsLeap (nYear))
                      nDays++;
              for (int nMonth = 0; nMonth < m_nMonth - 1;
                  nMonth++)
                  if (IsLeap (m_nYear))
                      nDays += s_nDaysOfMonth[1][nMonth];
                  else
                      nDays += s_nDaysOfMonth[0][nMonth];
              nDays += m_nDay;
              return nDays;
          }
          Date Days2Date (int nDays) const {
              int nYear = 1;
              for (;;) {
                  if (IsLeap (nYear)) {
                      if (nDays <= 366)
                          break;
                      nDays -= 366;
                  }
                  else {
                      if (nDays <= 365)
                          break;
                      nDays -= 365;
                  }
                  nYear++;
              }
              int nMonth = 1;
              bool bLeap = IsLeap (nYear);
              for (;;) {
                  if (bLeap) {
                      if (nDays <=
                          s_nDaysOfMonth[1][nMonth-1])
                          break;
                      nDays-=s_nDaysOfMonth[1][nMonth-1];
                  }
                  else {
                      if (nDays <=
                          s_nDaysOfMonth[0][nMonth-1])
                          break;
                      nDays-=s_nDaysOfMonth[0][nMonth-1];
                  }
                  nMonth++;
              }
              return Date (nYear, nMonth, nDays);
          }
          bool IsLeap (int nYear) const {
              return (nYear % 4 == 0 && nYear % 100 != 0)
                 || nYear % 400 == 0;
          }
          int m_nYear;
          int m_nMonth;
          int m_nDay;
          static int s_nDaysOfMonth[][12];
      };
      int Date::s_nDaysOfMonth[][12] = {
          {31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30,31},
          {31, 29, 31, 30, 31, 30, 31, 31, 30, 31, 30,31}
      };
      int main (void) {
          cout << "Enter a date: ";
          Date d1;
          cin >> d1;
          cout << "Enter the number of days: ";
          int nDays;
          cin >> nDays;
          Date d2 = d1 + nDays;
          cout << d1 << " + " << nDays << " = " << d2
              << endl;
          Date d3 (d1);
          d3 += nDays;
          cout << d1 << " += " << nDays << " -> " << d3
              << endl;
          cout << "Enter a date: ";
          cin >> d1;
          cout << "Enter the number of days: ";
          cin >> nDays;
          d2 = d1 - nDays;
          cout << d1 << " - " << nDays << " = " << d2
              << endl;
          d3 = d1;
          d3 -= nDays;
          cout << d1 << " -= " << nDays << " -> " << d3
              << endl;
          cout << "Enter a date: ";
          cin >> d1;
          cout << "Enter another date: ";
          cin >> d2;
          cout << "The days between those dates is "
              << d2 - d1 << endl;
          return 0;
      }
      

(四)、继承与多态

  1. 继承的基本概念

    人类:姓名、年龄、吃饭

    学生是人:学号、学习

    教师是人:工资、讲课

    ​ 人类 - 基类,共性

    / \ 派生V^继承

    学生 教师 - 子类,个性

  2. 继承的语法

    class 子类名 : 继承方式1 基类1, 继承方式2 基类2, ... {

    ...

    };

    继承方式:

    公有继承 - public - 最常用方式

    私有继承 - private - 缺省方式

    保护继承 - protected - 特殊的私有继承

    #include <iostream>
    using namespace std;
    class Human {
    public:
        Human (const string& name, int age) :
            m_name (name), m_age (age) {}
        void who (void) const {
            cout << m_name << "," << m_age << endl;
        }
        void eat (const string& food) const {
            cout << "我在吃" << food << endl;
        }
    protected:
        string m_name;
        int m_age;
    };
    class Student : public Human {    //继承定义
    public:
        Student (const string& name, int age, int no) :    Human (name, age), m_no (no) {}
        Student (const Student& that) :    Human (that), m_no (that.m_no) {}
        Student& operator= (const Student& that) {
            if (&that != this) {
                Human::operator= (that);   
                m_no = that.m_no;
            }
            return *this;
        }
        void learn (const string& lesson) const {
            cout << "我(" << m_name << "," << m_age
                << "," << m_no << ")在学" << lesson
                << endl;
        }
        using Human::eat;
        void eat (void) const {
            cout << "我绝食!" << endl;
        }
    //    int eat;
    private:
        int m_no;
    };
    int main (void) {
        Student s1 ("张飞", 25, 1001);
        s1.who ();
        s1.eat ("包子");
        s1.learn ("C++");
        Human* h1 = &s1;
        h1 -> who ();
        h1 -> eat ("KFC");
    //    h1 -> learn ("C");
        Student* ps = static_cast<Student*> (h1);
        ps -> learn ("C");
        Student s2 = s1;
        s2.who ();
        s2.learn ("英语");
        Student s3 ("赵云", 20, 1002);
        s3 = s2;
        s3.who ();
        s3.learn ("数学");
        return 0;
    }
    
  1. 公有继承

    ​ 1. 通过继承,在基类中定义的任何成员,也都成为了子类的成员,但是基类的私有成员,子类虽然拥有却不能直接访问。

    ​ 2. 基类中的保护成员,可以被子类直接访问,但不能在无关的类和全局域中被访问。

    ​ 3. 任何一个子类对象中都包含着它的基类子对象。如果在子类的构造函数中没有明确指明其基类子对象如何被构造,系统将采用无参的方式构造该子对象。如果在初始化表中指明了基类子对象的构造方式,就调用相应的构造函数构造该子对象。

    ​ 4. 子类对象的构造和析构顺序

    按照继承表的顺序依次构造每个基类子对象->按照声明的顺序依次构造每个成员变量->执行子类构造函数体中的代码

    析构的过程与构造严格相反

    ​ 5. 一个子类对象在任何都可以被视为它的基类对象——Is A。

    任何时候,一个子类对象的指针或者引用,都可以被隐式地转换为它的基类类型的指针或者引用,但是反过来,将基类类型的指针或者引用转换为它的子类类型必须显示地(static_cast)完成。

    Student s (...);
    Human* h = &s; // OK !
    

    ​ 6. 在子类中定义的任何和基类成员同名的标识符,都可以将基类中的该成员隐藏起来。通过作用域限定操作符“::”,可对该成员解隐藏。

  2. 继承方式对访控属性的影响

    class A {
    X:
       void foo (void) { ... }
    };
    class B : Y A {
      void bar (void) {
        foo (); // 仅需考虑X
      }
    };
    int main (void) {
      B b (...);
      b.foo(); // 不仅要考虑X还要考虑Y
    }
    class C : Z B {
      void fun (void) {
        foo(); // 不仅要考虑X还要考虑Y
      }
    };
    

    当通过一个子类对象(B)访问它从基类(A)中继承过来的成员(foo)的时候,需要考虑子类(B)从基类(A)继承时所采用的继承方式。

    1. 访控属性

      关键字 属性 基类 子类 外部 友员

      public 公有 OK OK OK OK

      protected 保护 OK OK NO OK

      private 私有 OK NO NO OK

    2. 基类的成员被继承到子类中以后,其访控属性会因不同的继承方式而异。

      基类 公有继承 保护继承 私有继承

      公有 公有 保护 私有

      保护 保护 保护 私有

      私有 私有 私有 私有

  3. 子类的构造函数和析构函数

    1. 子类隐式地调用基类的构造函数

      在子类的构造函数中没有显示地指明其基类部分如何构造,隐式地调用基类的无参构造函数。如果子类没有定义任何构造函数,其缺省无参构造函数同样会隐式地调用基类的无参构造函数

    2. 子类显式地调用基类的构造函数

      在子类构造函数的初始化表中指明其基类部分的构造方式。

      class A {
      public:
        A (void) : m_data (0) {}
        A (int data) : m_data (data) {}
      private:
        int m_data;
      };
      class B : public A {
      public:
        B (int data) : A (data) {}
      };
      
    3. 继承链的构造和初始化顺序

      class A { ... };
      class B : public A { ... };
      class C : public B { ... };
      C c (...);
      

      构造:A->B->C

      析构:C->B->A

      任何时候子类中基类子对象的构造都要先于子类构造函数中的代码。

    4. delete一个指向子类对象的基类指针,实际被执行的基类的析构函数,基类的析构函数不会调用子类析构函数,因此子类所特有的资源将形成内存泄漏。

      Human* p = new Student (...);
      delete p; // ->Human::~Human()
      delete static_cast<Student*> (p);
      
  4. 子类的拷贝构造和拷贝赋值

    子类的缺省拷贝构造和拷贝赋值除了复制子类的特有部分以外,还会复制其基类部分。如果需要自己定义子类的拷贝构造和拷贝赋值,一定不要忘记在复制子类特有部分的同时,也要复制其基类部分,否则将无法得到完整意义上的对象副本。

  5. 私有继承和保护继承

    用于防止或者限制基类中的公有接口被从子类中扩散。

    class DCT {
    public:
      void codec (void) { ... }
    };
    class Jpeg : protected DCT {
    public:
      void render (void) {
        codec (...);
      }
    };
    Jpeg jpeg;
    jpeg.codec (...); // ERROR !
    Jpeg Has A DCT,实现继承
    class Jpeg2000 : public Jpeg {
    public:
      void render (void) {
        codec (...); // OK !
      }
    };
    
  6. 多重继承

    从多于一个基类中派生子类。

    电话 媒体播放器 计算机

    ​ \ | /

    ​ 智能手机

    #include <iostream>
    using namespace std;
    class Phone {
    public:
        Phone (const string& numb) : m_numb (numb) {}
        void call (const string& numb) {
            cout << m_numb << "致电" << numb << endl;
        }
        void foo (void) {
            cout << "Phone::foo" << endl;
        }
    private:
        string m_numb;
    };
    class Player {
    public:
        Player (const string& media) : m_media (media){}
        void play (const string& clip) {
            cout << m_media << "播放器播放" << clip
                << endl;
        }
        void foo (int data) {
            cout << "Player::foo" << endl;
        }
    private:
        string m_media;
    };
    class Computer {
    public:
        Computer (const string& os) : m_os (os) {}
        void run (const string& prog) {
            cout << "在" << m_os << "上运行" << prog
                << endl;
        }
    private:
        string m_os;
    };
    class SmartPhone : public Phone, public Player,
        public Computer {
    public:
        SmartPhone (const string& numb,
            const string& media, const string& os) :
            Phone (numb), Player (media),
            Computer (os) {}
        using Phone::foo;
        using Player::foo;
    };
    int main (void) {
        SmartPhone sp ("13910110072", "MP3", "Android");
        sp.call ("01062332018");
        sp.play ("High歌");
        sp.run ("愤怒的小鸟");
        Phone* p1 = reinterpret_cast<Phone*> (&sp);
        Player* p2 = reinterpret_cast<Player*> (&sp);
        Computer* p3 = reinterpret_cast<Computer*>(&sp);
        cout << &sp << ' '<< p1 << ' ' << p2 << ' '
            << p3 << endl;
        sp.foo ();
        sp.foo (100);
        return 0;
    }
    

    ps:

    C++ using关键字作用总结

    A.在当前文件中引入命名空间

    这是我们最熟悉的用法,例如:using namespace std;

    B.在子类中使用 using 声明引入基类成员名称(参见C++ primer)

    在private或者protected继承时,基类成员的访问级别在派生类中更受限:

    class Base { public: std::size_t size() const { return n; } protected: std::size_t n; };

    class Derived : private Base { . . . };

    在这一继承层次中,成员函数 size 在 Base 中为 public,但在 Derived 中为 private。为了使 size 在 Derived 中成为 public,可以在 Derived 的 public

    部分增加一个 using 声明。如下这样改变 Derived 的定义,可以使 size 成员能够被用户访问,并使 n 能够被 Derived的派生类访问:

    class Derived : private Base { public: using Base::size; protected: using Base::n; // ...

    };

    另外,当子类中的成员函数和基类同名时,子类中重定义的成员函数将隐藏基类中的版本,即使函数原型不同也是如此。

    1. 多重继承的语法和语义与单继承并没有本质的区别,只是子类对象中包含了更多的基类子对象。它们在内存中按照继承表的先后顺序从低地址到高地址依次排列。

    2. 子类对象的指针可以被隐式地转换为任何一个基类类型的指针。无论是隐式转换,还是静态转换,编译器都能保证特定类型的基类指针指向相应类型基类子对象。但是重解释类型转换,无法保证这一点。

    3. 尽量防止名字冲突。

    4. 钻石继承和虚继承

      1) 钻石继承

      A

      / \

      B C

      \ /

      D

      class A { ... };
      class B : public A { ... };
      class C : public A { ... };
      class D : public B,public C{ ...};
      

      在最终子类(D)对象中存在公共基类(A)子对象的多份实例,因此沿着不同的继承路径访问公共基类子对象中的成员,会发生数据不一致的问题。

      //钻石继承
      #include <iostream>
      using namespace std;
      class A {
      public:
          A (int i) : m_i (i) {}
      protected:
          int m_i;
      };
      class B : virtual public A {  //虚继承
      public:
          B (int i) : A (i) {}
          void set (int i) {
              m_i = i;
          }
      };
      class C : virtual public A {  //虚继承
      public:
          C (int i) : A (i) {}
          int get (void) {
              return m_i;
          }
      };
      class D : public B, public C {
      public:
          D (int i) : B (i), C (i), A (i) {}  // 要照顾爷!!!//b和c根本不起作用
      };
      int main (void) {
          D d (1000);
          cout << d.get () << endl; // 1000
          d.set (2000);
          cout << d.get () << endl; // 2000
          return 0;
      }
      

      2) 虚继承

      在继承表中通过virtual关键字指定从公共基类中虚继承,这样就可以保证在最终子类对象中,仅存在一份公共基类子对象的实例,避免沿着不同的继承路径访问公共基类子对象中的成员时,所引发的数据不一致的问题。

      只有当所创建对象的类型回溯(su)中(往上看)存在钻石结构时,虚继承才起作用,否则编译器会直接忽略virtual关键字。

      ​ 图形:位置,绘制

      ​ / \

      矩形:宽和高 圆:半径

      ​ 绘制 绘制

      #include <iostream>
      using namespace std;
      class Shape {
      public:
          Shape (int x, int y) : m_x (x), m_y (y) {}
          virtual void draw (void) {   //虚函数,就是根据对象来调,不再根据类型调;
              cout << "形状(" << m_x << ',' << m_y << ')'
                  << endl;
          }
      protected:
          int m_x, m_y;
      };
      class Rect : public Shape {
      public:
          Rect (int x, int y, int w, int h) :
              Shape (x, y), m_w (w), m_h (h) {}
          void draw (void) {
              cout << "矩形(" << m_x << ',' << m_y << ','
                  << m_w << ',' << m_h << ')' << endl;
          }
      //    int draw (void) const {}
      private:
          int m_w, m_h;
      };
      class Circle : public Shape {
      public:
          Circle (int x, int y, int r) :
              Shape (x, y), m_r (r) {}
          void draw (void) {
              cout << "圆形(" << m_x << ',' << m_y << ','
                  << m_r << ')' << endl;
          }
      private:
          int m_r;
      };
      void render (Shape* shapes[]) {
          for (size_t i = 0; shapes[i]; ++i)
              shapes[i]->draw ();
      }
      int main (void) {
          Shape* shapes[1024] = {};
          shapes[0] = new Rect (1, 2, 3, 4);
          shapes[1] = new Circle (5, 6, 7);
          shapes[2] = new Circle (8, 9, 10);
          shapes[3] = new Rect (11, 12, 13, 14);
          shapes[4] = new Rect (15, 16, 17, 18);
          render (shapes);
          return 0;
      }
      
  7. 虚函数与多态

    如果将基类中的一个成员函数声明为虚函数(基函数前加virtual),那么子类中的同型函数就也成为虚函数,并且对基类版本形成覆盖。这时,通过一个指向子类对象的基类指针,或者一个引用子类对象的基类引用,调用该虚函数时,实际被调用的函数不由该指针或引用的类型决定,而由它们的目标对象决定,最终导致子类中覆盖版本被执行。这种现象称为多态。

    多态的使用:作为函数的参数、可以做到类型通用、可以在函数内部根据实际对象类型做出相应的动作(虚函数)、函数的返回值。

  8. 函数覆盖的条件

    overload - 重载

    override - 覆盖、重写、改写

    1. 基类版本必须是虚函数。

    2. 函数名、形参表和常属性必须严格一致。

    3. 如果返回基本类型或者对象,那么也必须严格一致。如果返回类类型的指针或引用,那么子类版本也可以返回基类版本的子类。

      class B : public A { ... };

      基类:virtual A* foo (void) {...}

      子类:A* foo (void) { ... }

      ​ B* foo (void) { ... }//B是A的子类也行;

    4. 子类的覆盖版本不能比基类版本声明更多的异常抛出。

    5. 子类覆盖版本的访控属性与基类无关。

      class A {
      public:
        virtual void foo (void) { ... }
      };
      class B : public A {
      private:
        void foo (void) { ... }
      };
      int main (void) {
        B* b = new B;
        b->foo (); // ERROR !
        A* a = new B;
        a->foo (); // OK ! -> B::foo
      }
      

      函数重写:是针对虚函数,重写要求函数名相同参数列表相同,返回值相同。

      名字隐藏:在子类中出现和父类同名的数据。

      函数重载:同一个作用域函数名相同,参数表不同。

      不同类型对象虚函数表不相同。

  9. 多态=虚函数+指针/引用

    Rect rect (...);
    Shape shape = rect;
    shape->draw (); // Shape::draw
    Shape& shape = rect;
    shape->draw (); // Rect::draw
    class A {
    public:
      A (void) {
        bar (); // A::bar
      }
      ~A (void) {
        bar (); // A::bar
      }
      void foo (void) {
        this->bar (); // B::bar
      }
      virtual void bar (void) {
        cout << 'A' << endl;
      }
    };
    class B : public A {
      void bar (void) {
        cout << 'B' << endl;
      }
    };
    int main (void) {
      B b; // A
      b.foo (); // B
      return 0;
    }
    
  10. 纯虚函数、抽象类、纯抽象类

    形如:

    virtrual 返回类型 成员函数名 (形参表) = 0;

    的虚函数被称为纯虚函数。

    #include <iostream>
    using namespace std;
    class Shape {
    public:
        Shape (int x, int y) : m_x (x), m_y (y) {}
        virtual void draw (void) = 0; //纯虚函数
    protected:
        int m_x, m_y;
    };
    class Rect : public Shape {
    public:
        Rect (int x, int y, int w, int h) :
            Shape (x, y), m_w (w), m_h (h) {}
        void draw (void) {
            cout << "矩形(" << m_x << ',' << m_y << ','
                << m_w << ',' << m_h << ')' << endl;
        }
    //    int draw (void) const {}
    private:
        int m_w, m_h;
    };
    class Circle : public Shape {
    public:
        Circle (int x, int y, int r) :
            Shape (x, y), m_r (r) {}
        void draw (void) {
            cout << "圆形(" << m_x << ',' << m_y << ','
                << m_r << ')' << endl;
        }
    private:
        int m_r;
    };
    void render (Shape* shapes[]) {
        for (size_t i = 0; shapes[i]; ++i)
            shapes[i]->draw ();
    }
    int main (void) {
        Shape* shapes[1024] = {};
        shapes[0] = new Rect (1, 2, 3, 4);
        shapes[1] = new Circle (5, 6, 7);
        shapes[2] = new Circle (8, 9, 10);
        shapes[3] = new Rect (11, 12, 13, 14);
        shapes[4] = new Rect (15, 16, 17, 18);
        render (shapes);
    //    Shape shape (1, 2);
        return 0;
    }
    

    结果:

    矩形(1,2,3,4)

    圆形(5,6,7)

    圆形(8,9,10)

    矩形(11,12,13,14)

    矩形(15,16,17,18)

    一个包含了纯虚函数类称为抽象类,抽象类不能实例化为对象(因为纯虚函数在类中只有声明没有主体)。

    如果一个类继承自抽象类,但是并没有为其抽象基类中的全部纯虚函数提供覆盖,那么该子类就也是一个抽象类。

    class A { // 纯抽象类
      virtual void foo (void) = 0;
      virtual void bar (void) = 0;
      virtual void fun (void) = 0;
    };
    class B : public A { // 抽象类
      void foo (void) { ... }
    };
    class C : public B { // 抽象类
      void bar (void) { ... }
    };
    class D : public C { // 具体类
      void fun (void) { ... }
    };
    

    除了构造和析构函数以外,所有的成员函数都是纯虚函数的类称为纯抽象类。

    虚函数表:

    class A{
      public:
       virtual void fun(){cout<<1<<endl;}   
         virtual void fun2(){cout<<2<<endl;}   
    };   
    class B:public A{
       public:
       void fun(){cout<<3<<endl;}
       void fun2(){cout<<4<<endl;}   
    };
    

    由于这两个类中有虚函数存在,所以编译器就会为他们两个分别插入一段你不知道的数据,并为他们分别创建一个表。那段数据叫做vptr指针,指向那个 表。那个表叫做vtbl,每个类都有自己的vtbl,vtbl的作用就是保存自己类中虚函数的地址,我们可以把vtbl形象地看成一个数组,这个数组的每 个元素存放的就是虚函数的地址,请看图

    img

    可以看到这两个vtbl分别为class A和class B服务。现在有了这个模型之后,我们来分析下面的代码

    A *p=new A;

    p->fun();

    毫无疑问,调用了A::fun(),但是A::fun()是如何被调用的呢?它像普通函数那样直接跳转到函数的代码处吗?No,其实是这样的,首先 是取出vptr的值,这个值就是vtbl的地址,再根据这个值来到vtbl这里,由于调用的函数A::fun()是第一个虚函数,所以取出vtbl第一个 slot里的值,这个值就是A::fun()的地址了,最后调用这个函数。现在我们可以看出来了,只要vptr不同,指向的vtbl就不同,而不同的 vtbl里装着对应类的虚函数地址,所以这样虚函数就可以完成它的任务。 调用虚函数,由运行阶段指针来确定对象,再由对象前四个字节找到对应的虚函数表,再由虚函数表来对应各自函数,从而实现多态。当有虚函数时,就产生虚函数表,虚函数表只记录虚函数

  11. 动态绑定(后期绑定、运行时绑定)

    1. 虚函数表

      class A {
      public:
        virtual void foo (void) { ... }
        virtual void bar (void) { ... }
      };
      class B : public A {
      public:
        void foo (void) { ... }
      };
      A* pa = new A;
      pa->foo (); // A::foo
      pa->bar (); // A::bar
      ---------------------
      A* pa = new B;
      pa->foo (); // B::foo
      pa->bar (); // A::bar
      
    2. 动态绑定

      当编译器看到通过指向子类对象的基类指针或者引用子类对象的基类引用,调用基类中的虚函数时,并不急于生成函数调用代码,相反会在该函数调用出生成若干条指令,这些指令在程序的运行阶段被执行,完成如下动作:

      1) 根据指针或引用的目标对象找到相应虚函数表的指针;

      2) 根据虚函数表指针,找到虚函数的地址;

      3) 根据虚函数地址,指向虚函数代码。

      由此可见,对虚函数的调用,只有运行阶段才能够确定,故谓之后期绑定或运行时绑定。

    3. 动态绑定对程序的性能会造成不利影响。如果不需要实现多态就不要使用虚函数。

  12. 运行时类型信息(RTTI)

    1. typeid操作符

      A a;
      typeid (a)返回typeinfo类型的对象的常引用。
      typeinfo::name() - 以字符串的形式返回类型名称。
      typeinfo::operator==() -类型一致
      typeinfo::operator!=() -类型不一致
      #include <typeinfo>
      
      #include <iostream>
      #include <typeinfo>
      #include <cstring>
      using namespace std;
      class A {
      public:
          virtual void foo (void) {}     // 必有虚函数表
      };
      class B : public A {};
      void print (A* pa) {
      //    if (! strcmp (typeid (*pa).name (), "1A"))
          if (typeid (*pa) == typeid (A))    //比较通用
              cout << "pa指向A对象!" << endl;
          else
      //    if (! strcmp (typeid (*pa).name (), "1B"))
          if (typeid (*pa) == typeid (B))
              cout << "pa指向B对象!" << endl;
      }
      int main (void) {
          cout << typeid (int).name () << endl;  //i
          cout << typeid (unsigned int).name () << endl;//j
          cout << typeid (double[10]).name () << endl;  //类型信息;A10_d
          cout << typeid (char[3][4][5]).name () << endl;//A3_A4_A5_c
          char* (*p[5]) (int*, short*);//函数指针数组;//A5_PFPCPiPsE
          cout << typeid (p).name () << endl;//
          cout << typeid (const char* const* const).name () << endl;    //PKPKc
          cout << typeid (A).name () << endl; //1A
          A* pa = new B;
          cout << typeid (*pa).name () << endl;//根据指针类型判断,加虚函数后就根据目标判断了;
          print (new A);
          print (new B);
      }
      
    2. dynamic_cast

  13. 虚析构函数

    将基类的析构函数声明为虚函数,delete一个指向子类对象的基类指针,实际被执行的将是子类的析构函数,而子类的析构函数可以自动调用基类的析构函数,进而保证子类特有的资源,和基类子对象中的资源都能够得到释放,防止内存泄漏。

    当父类型中出现虚函数时则应该在父类的析构函数前加 Virtval 修饰。

    如果基类中存在虚函数,那么就有必要为其定义一个虚析构函数,即使该函数什么也不做。

    与对象无关的函数都不能为虚函数。

    //虚析构函数
    #include <iostream>
    using namespace std;
    class A {
    public:
        A (void) {
            cout << "A构造" << endl;
        }
        virtual ~A (void) {   //声明成虚函数
            cout << "A析构" << endl;
        }
    };
    class B : public A {
    public:
        B (void) {
            cout << "B构造" << endl;
        }
        ~B (void) {
            cout << "B析构" << endl;
        }
    };
    int main (void) {
        A* pa = new B;
    //    B* pb = new B;
    //    delete pb;
        delete pa;
        return 0;
    }
    

    思考:

    虚函数可以内联吗?不可以

    一个类的构造函数可以被定义为虚函数吗?不可以,因为虚函数表存在对象里。

    一个类的静态成员函数可以被定义为虚函数吗?不可以,不依赖于对象。

    一个类的成员函数形式的操作符函数可以被定义为虚函数吗?可以

    一个全局函数可以被定义为虚函数吗?不可以

    class PDFParser {
    public:
      void parse (const char* file) {
        // 解析出一行文字
        on_text (...);
        // 解析出一幅图片
        on_image (...);
        // 解析出一张图形
        on_graph (...);
      }
    private:
      virtual void on_text (...) = 0;
      virtual void on_image (...) = 0;
      virtual void on_graph (...) = 0;
    };
    class PDFRender : public PDFParser {
    private:
      void on_text (...) { ... }
      void on_image (...)  { ... }
      void on_graph (...)  { ... }
    };
    PDFRender render (...);
    render.parse ("test.pdf");
    

    模板方法模式

    MFC

(五)、异常和I/O流

  1. 为什么要有异常——WHY?

    1. 通过返回值表达错误

      局部对象都能正确的析构

      层层判断返回值,流程繁琐

    2. 通过setjmp/longjmp远程跳转

      一步到位进入错误处理,流程简单

      局部对象会失去被析构的机会

    3. 异常处理

      局部对象都能正确的析构

      一步到位进入错误处理,流程简单

  2. 异常的语法——WHAT?

    1. 异常的抛出

      throw 异常对象;

      异常对象可以是基本类型的变量,也可以是类类型的对象。

      当程序执行错误分支时抛出异常。

    2. 异常的捕获

      try {

      可能抛出异常的语句块;

      }

      catch (异常类型1 异常对象1) {

      处理异常类型1的语句块;

      }

      catch (异常类型2 异常对象2) {

      处理异常类型2的语句块;

      }

      ...

      catch (...) {

      处理其它类型异常的语句块;

      }

      异常处理的流程,始终沿着函数调用的逆序,依次执行右花括号,直到try的右花括号,保证所有的局部对象都能被正确地析构,然会根据异常对象的类型,匹配相应的catch分支,进行有针对性的错误处理。

  3. 异常处理的使用方法——HOW?

    1. 抛出基本类型的异常,用不同的值代表不同的错误。

      #include <iostream>
      #include <cstdio>
      #include <cstdlib>
      using namespace std;
      void foo (void) {
          FILE* fp = fopen ("none", "r");
          if (! fp)
              throw "打开文件失败!";
          void* pv = malloc (0xFFFFFFFF);
          if (! pv)
              throw "内存分配失败!";
          // ...
      }
      int main (void) {
          try {
              foo ();
          }
          catch (const char* ex) {
              cout << ex << endl;
              return -1;
          }
          return 0;
      }
      
    2. 抛出类类型的异常,用不同的类型表示不同的错误。

      //类类型异常处理
      #include <iostream>
      #include <cstdio>
      #include <cstdlib>
      using namespace std;
      class Error {};
      class FileError : public Error {};
      class MemError : public Error {};
      void foo (void) {
          FILE* fp = fopen ("none", "r");
          if (! fp)
              throw FileError ();  //抛出副本,用引用接收,不能抛出局部变量的地址
          void* pv = malloc (0xFFFFFFFF);
          if (! pv)
              throw MemError ();
          // ...
      }
      int main (void) {
          try {
              foo ();
          }
          catch (FileError& ex) {
              cout << "打开文件失败!" << endl;
              return -1;
          }
          catch (MemError& ex) {
              cout << "内存分配失败!" << endl;
              return -1;
          }
          catch (Error& ex) {
              cout << "一般性错误!" << endl;//老大啊
              return -1;
          }
          return 0;
      }
      
    3. 通过类类型的异常携带更多诊断信息。

      //类类异常会携带更多信息!!!
      #include <iostream>
      #include <cstdio>
      #include <cstdlib>
      using namespace std;
      class Error {
      public:
          virtual void print (void) const = 0;
      };
      class FileError : public Error {
      public:
          FileError (const string& file, int line) :
              m_file (file), m_line (line) {}
          void print (void) const {
              cout << "在" << m_file << "文件的第"
                  << m_line << "行,发生了文件错误!"
                  << endl;
          }
      private:
          string m_file;
          int m_line;
      };
      class MemError : public Error {
      public:
          void print (void) const {
              cout << "内存不够啦!!!" << endl;
          }
      };
      void foo (void) {
          FILE* fp = fopen ("none", "r");
          if (! fp)
              throw FileError (__FILE__, __LINE__);   //显示当前行。
          void* pv = malloc (0xFFFFFFFF);
          if (! pv)
              throw MemError ();
          // ...
      }
      int main (void) {
          try {
              foo ();
          }
          catch (Error& ex) {
              ex.print ();
              return -1;
          }
          return 0;
      }
      
    4. 忽略异常和继续抛出异常。

      #include <iostream>
      using namespace std;
      void foo (void) {
          throw 10;
      }
      void bar (void) {
          try {
              foo ();
          }
          catch (int& ex) {
              --ex;  //处理一下
              throw; // 继续抛出
          }
          // ...
      }
      int main (void) {
          try {
              bar ();
          }
          catch (int& ex) {   //去掉&就是用值传递,就是10;
              cout << ex << endl; // 9
          }
          return 0;
      }
      
    5. 异常说明

      在一个函数的形参表后面写如下语句:

      ...形参表) throw (异常类型1, 异常类型2, ...) { ... }

      表示这个函数可以被捕获的异常。

      throw () - 这个函数所抛出的任何异常均无法捕获。

      没有异常说明 - 这个函数所抛出的任何异常均可捕获。

      class A {
          virtual void foo (void)
          throw (int, double) { ... }
          virtual void bar (void)
          throw () { ... }
      };
      class B : public A {
          void foo (void)
          throw (int, char) { ... }
          // ERROR
          void bar (void) { ... } // ERROR
          void bar (void)
          throw () { ... }
      };
      
      #include <iostream>
      using namespace std;
      void foo (void) throw (int, double, const char*) {  //此范围的异常才可被抛出
      //    throw 1;  //ok
      //    throw 3.14;   //ok
          throw "Hello, Exception !";
      }
      int main (void) {
          try {
              foo ();
          }
          catch (int ex) {
              cout << ex << endl;
          }
          catch (double ex) {
              cout << ex << endl;
          }
          catch (const char* ex) { 
              cout << ex << endl;
          }
          return 0;
      }
      
    6. 使用标准异常

      #include \

      #include <iostream>
      #include <stdexcept>
      #include <cstdio>
      using namespace std;
      class FileError : public exception { //系统定义最个级别的异常类
      private:
          const char* what (void) const throw () {
              return "文件访问失败!";
          }
      };
      class B {
      public:
          B (void) {
              cout << "B构造" << endl;
          }
          ~B (void) {
              cout << "B析构" << endl;
          }
      };
      class C {
      public:
          C (void) {
              cout << "C构造" << endl;
          }
          ~C (void) {
              cout << "C析构" << endl;
          }
      };
      class A : public C {
      public:
          A (void) : m_b (new B) {
              FILE* fp = fopen ("none", "r");
              if (! fp) {
                  delete m_b;
                  throw FileError ();
              }
              // ...
              fclose (fp);
          }
          ~A (void) {
              delete m_b;
          }
      private:
          B* m_b;
      //    C m_c;
      };
      int main (void) {
          try {
              A a;
              // ...
          }
          catch (exception& ex) {
              cout << ex.what () << endl;
              return -1;
          }
          return 0;
      }
      
  4. 构造函数中的异常

    构造函数可以抛出异常,而且有些时候还必须抛出异常,已通知调用者构造过程中所发生的错误。

    如果在一个对象的构造过程中抛出了异常,那么这个对象就称为不完整对象。不完整对象的析构函数永远不会被指向,因此需要在throw之前,手动释放动态的资源。

  5. 析构函数中的异常

    永远不要在析构函数中抛出异常。

    class A {
    public:
      ~A (void) {
        //throw -1;
        try {
          sysfunc ();
        }
        catch (...) {}
      }
    };
    try {
      A a;
      a.foo ();
    }
    catch (...) { ... }
    

    通过try-catch拦截所有可能引发的异常。

    #include <iostream>
    #include <cstdio>
    using namespace std;
    class A {
    public:
        A (void) {
            cout << "A构造" << endl;
        }
        ~A (void) {
            cout << "A析构" << endl;
        }
    };
    void func3 (void) {
        A a;
        FILE* fp = fopen ("none", "r");
        if (! fp) {
            cout << "throw前" << endl;
            throw -1;
            cout << "throw后" << endl;
        }
        cout << "文件打开成功!" << endl;
        // ...
        fclose (fp);
    }
    void func2 (void) {
        A a;
        cout << "func3()前" << endl;
        func3 ();
        cout << "func3()后" << endl;
        // ...
    }
    void func1 (void) {
        A a;
        cout << "func2()前" << endl;
        func2 ();
        cout << "func2()后" << endl;
        // ...
    }
    int main (void) {
        try {
            cout << "func1()前" << endl;
            func1 ();
            cout << "func1()后" << endl;
        }
        catch (int ex) {
            if (ex == -1) {
                cout << "执行失败!改天再见!" << endl;
                return -1;
            }
        }
        // ...
        cout << "执行成功!恭喜恭喜!" << endl;
        return 0;
    }
    
    #include <iostream>
    #include <cstdio>
    #include <csetjmp>
    using namespace std;
    jmp_buf g_env;  //定义缓冲区,头文件第3行;
    class A {
    public:
        A (void) {
            cout << "A构造" << endl;
        }
        ~A (void) {
            cout << "A析构" << endl;
        }
    };
    void func3 (void) {
        A a;
        FILE* fp = fopen ("none", "r");
        if (! fp)
            longjmp (g_env, -1);//跳转让别人setjmp输出,-1为返回值
        // ...
        fclose (fp);
    }
    void func2 (void) {
        A a;
        func3 ();
        // ...
    }
    void func1 (void) {
        A a;
        func2 ();
        // ...
    }
    int main (void) {
        if (setjmp (g_env) == -1) {   //占栈调两次
            cout << "执行失败!改天再见!" << endl;
            return -1;
        }
        func1 ();
        // ...
        cout << "执行成功!恭喜恭喜!" << endl;
        return 0;
    }
    
    #include <iostream>
    #include <cstdio>
    using namespace std;
    int func3 (void) {
        FILE* fp = fopen ("none", "r");
        if (! fp)
            return -1;
        // ...
        fclose (fp);
        return 0;
    }
    int func2 (void) {
        if (func3 () == -1)
            return -1;
        // ...
        return 0;
    }
    int func1 (void) {
        if (func2 () == -1)
            return -1;
        // ...
        return 0;
    }
    int main (void) {
        if (func1 () == -1) {
            cout << "执行失败!改天再见!" << endl;
            return -1;
        }
        // ...
        cout << "执行成功!恭喜恭喜!" << endl;
        return 0;
    }
    
    #include <iostream>
    using namespace std;
    class A {
    public:
        virtual void foo (void) {
            cout << "A::foo()" << endl;
        }
        virtual void bar (void) {
            cout << "A::bar()" << endl;
        }
    };
    class B : public A {
    public:
        void foo (void) {
            cout << "B::foo()" << endl;
        }
    };
    int main (void) {
        A a;
        void (**vft) (void) = *(void (***) (void))&a;//类型配平
        cout << (void*)vft[0] << ' '<< (void*)vft[1] << endl;
        vft[0] ();
        vft[1] ();
        B b;
        vft = *(void (***) (void))&b;
        cout << (void*)vft[0] << ' ' << (void*)vft[1] << endl;
        vft[0] ();
        vft[1] ();
        return 0;
    }
    
    #include <iostream>
    using namespace std;
    class A { virtual void foo (void) {} };
    class B : public A {};
    class C : public B {};
    class D {};
    int main (void) {
        B b;
        A* pa = &b;
        cout << pa << endl;   //地址
        cout << "-------- dc --------" << endl;
        // pa指向B对象,成功
        B* pb = dynamic_cast<B*> (pa);    //动态类型转换
        cout << pb << endl;
        // pa没有指向C对象,失败,安全
        C* pc = dynamic_cast<C*> (pa);//仅限于多态型
        cout << pc << endl;
        A& ra = b; //引用
        try {  //异常处理
            C& rc = dynamic_cast<C&> (ra);  //抛出异常的方式
        }
        catch (exception& ex) {   //异常捕获
            cout << "类型转换失败:" << ex.what ()//现实异常原因
                << endl;
            // ...
        }
        // pa没有指向D对象,失败,安全
        D* pd = dynamic_cast<D*> (pa);
        cout << pd << endl;
        cout << "-------- sc --------" << endl;
        // B是A的子类,成功
        pb = static_cast<B*> (pa);
        cout << pb << endl;
        // C是A的孙子类,成功,危险!
        pc = static_cast<C*> (pa);//指向B的;
        cout << pc << endl;
        // D不是A的后裔,失败,安全
    //    pd = static_cast<D*> (pa);
    //    cout << pd << endl;
        cout << "-------- rc --------" << endl;//重解释类型转换
        // 无论在编译期还是在运行期都不做检查,危险!
        pb = reinterpret_cast<B*> (pa);     //
        cout << pb << endl;
        pc = reinterpret_cast<C*> (pa);
        cout << pc << endl;
        pd = reinterpret_cast<D*> (pa);
        cout << pd << endl;
        return 0;
    }
    
  6. C++的I/O流库

    C:fopen/fclose/fread/fwrite/fprintf/fscanf/fseek/ftell...

    C++:对基本的I/O操作做了类的封装,其功能没有任何差别,用法和C的I/O流也非常近似。

    sscanf

  7. 格式化I/O

    <</>>

    //格式化I/O
    #include <iostream>
    #include <fstream>
    using namespace std;
    int main (void) {
        ofstream ofs ("format.txt");  //写;原内容被覆盖
        if (! ofs) {
            perror ("打开文件失败");
            return -1;
        }
        ofs << 1234 << ' ' << 56.78 << ' ' << "tarena"  //空格便于分割
            << '\n'; //endl;
        ofs.close ();
        ofs.open ("format.txt", ios::app); //以追加的方式打开
        if (! ofs) {
            perror ("打开文件失败");
            return -1;
        }
        ofs << "append_a_line\n";   //追加内容
        ofs.close (); //关闭
        ifstream ifs ("format.txt");  //读;
        if (! ifs) {
            perror ("打开文件失败");
            return -1;
        }
        int i;
        double d;
        string s1, s2;
        ifs >> i >> d >> s1 >> s2; //从文件中读
        cout << i << ' ' << d << ' ' << s1 << ' '<< s2 << endl;
        ifs.close (); //关闭
        return 0;
    }
    
  8. 非格式化I/O

    put/get

    //非格式化I/O
    #include <iostream>
    #include <fstream>
    using namespace std;
    int main (void) {
        ofstream ofs ("putget.txt");//写
        if (! ofs) {
            perror ("打开文件失败");
            return -1;
        }
        for (char c = ' '; c <= '~'; ++c)
            if (! ofs.put (c)) {
                perror ("写入文件失败");
                return -1;
            }
        ofs.close ();
        ifstream ifs ("putget.txt");//读
        if (! ifs) {
            perror ("打开文件失败");
            return -1;
        }
        char c;
        while ((c = ifs.get ()) != EOF)//EOF为特定判断结果,判断读取结束;
            cout << c;
        cout << endl;
        if (! ifs.eof ()) { // 用eof判断一下是否读取完毕
            perror ("读取文件失败");
            return -1;
        }
        ifs.close ();
        return 0;
    }
    
  9. 随机I/O

    seekp/seekg

    tellp/tellg

    #include <iostream>
    #include <fstream>
    using namespace std;
    int main (void) {
        fstream fs ("seek.txt", ios::in | ios::out);//能读会写,读写流.
        if (! fs) {
            perror ("打开文件失败");//打印出错信息
            return -1;
        }
        fs << "0123456789";//写
        cout << fs.tellp () << endl;//获取写位置(指针)
        cout << fs.tellg () << endl;//获取读位置(指针)
        fs.seekp (-3, ios::cur); //调整写位置,相对文件尾向前挪三位
        fs << "XYZ";//直接覆盖
        fs.seekg (4, ios::beg);//调整读位置,相对文件头
        int i;
        fs >> i; //非int就无视,调整后的位置继续读取;
        cout << i << endl;
        cout << fs.tellg () << endl;
        cout << fs.tellp () << endl;
        fs.seekg (-6, ios::end);//相对文件尾
        fs << "ABC";
        fs.close ();
        return 0;
    }
    
  10. 二进制I/O

    read/write

    K 0 - 255

    A^K=B

    B^K=A

    PKI

    HAS MD5

    //加密解密程序
    #include <iostream>
    #include <fstream>
    #include <stdexcept>
    #include <cstdlib>
    using namespace std;
    #define BUFSIZE (1024*10)
    int _xor (const char* src, const char* dst,unsigned char key) {  //明文、密文、密钥
        ifstream ifs (src, ios::binary);  //ios::binary以二进制方式
        if (! ifs) {
            perror ("打开源文件失败");
            return -1;
        }
        ofstream ofs (dst, ios::binary); //写,以二进制方式
        if (! ofs) {
            perror ("打开目标文件失败");
            return -1;
        }
        char* buf = NULL;
        try {
            buf = new char[BUFSIZE];    //读出后放缓冲区,
        }
        catch (bad_alloc& ex) { //捕获异常
            cout << ex.what () << endl;//打印原因
            return -1;
        }
        while (ifs.read (buf, BUFSIZE)) {  //读取
            for (size_t i = 0; i < BUFSIZE; ++i)
                buf[i] ^= key;//
            if (! ofs.write (buf, BUFSIZE)) {   //写入目的文件
                perror ("写入文件失败");
                return -1;
            }
        }
        if (! ifs.eof ()) {
            perror ("读取文件失败");
            return -1;
        }
        for (size_t i = 0; i < ifs.gcount (); ++i)
            buf[i] ^= key;
        if (! ofs.write (buf, ifs.gcount ())) { //ifs.gcount最后一块未读的一小块
            perror ("写入文件失败");
            return -1;
        }
        delete[] buf;
        ofs.close ();
        ifs.close ();
        return 0;
    }
    int enc (const char* plain, const char* cipher) { //加密
        srand (time (NULL)); //重置密文//随机因子//利用时间变化
        unsigned char key = rand () % 256;
        if (_xor (plain, cipher, key) == -1)
            return -1;
        cout << "密钥:" << (unsigned int)key << endl;
        return 0;
    }
    int dec (const char* cipher, const char* plain,  //解密
        unsigned char key) {
        return _xor (cipher, plain, key);
    }
    int main (int argc, char* argv[]) {
        if (argc < 3) {
            cerr << "用法:" << argv[0] << " <明文文件> <密文文件>" << endl;
            cerr << "用法:" << argv[0] << " <密文文件> <明文文件> <密钥>" << endl;
            return -1;
        }
        if (argc < 4)
            return enc (argv[1], argv[2]); //加密
        else
            return dec (argv[1], argv[2],  //解密
                atoi (argv[3]));
        return 0;
    }
    
  11. 格式控制

    in a;
    printf ("%d%x\n", a, a)
    cout << a << endl;
    

    流函数

    流控制符

    cout << hex << a;
    cout << setw (10) << a;
    
    #include <iostream>
    #include <iomanip>  //流控制符
    #include <cmath>
    #include <fstream>
    #include <sstream> //字符串流
    using namespace std;
    int main (void) {
        cout << sqrt (2) << endl;//缺省方式输出
        cout.precision (10); // 10位有效数字,流函数;持续生效!!!
        cout << sqrt (2) << endl;
        cout << sqrt (2) * 100 << endl;
        cout << setprecision (5) << sqrt (2) << endl  //将精度改为5
            << sqrt (2) * 100 << endl;
        cout << "当前精度:" << cout.precision ()  //返回当前精度
            << endl;
        cout << setprecision (2) << 1.24 << ' ' << 1.25 //保留两位有效数字//对于舍取位的前一位若是偶数五舍六入
            << ' ' << 1.26 << " " << 1.35 <<endl;   //奇入偶不入
        cout << showbase << hex << 127 << endl;  //把十六进制的标志打出来
        cout << oct << 127 << endl; //八进制标志
        cout << dec << 127 << endl; //十进制
        cout << noshowbase << hex << 127 << dec << endl;//关闭进制标志
        cout << oct << 127 << endl; //八进制标志就无效了;
        cout << setw (12) << 127 << 721 << endl;  //缺省时填充空格,仅管后面的数;
        cout << setfill ('$') << left << setw (12)<< 127 << endl; //填充字符。左对齐。生效一次;
        cout.precision (10);//精度为十
        cout.setf (ios::scientific); //科学计数法显示
        cout << sqrt (2) << endl;//精确到小数点后有效数字十位;
        cout.setf (ios::fixed);//以小数显示
        cout << sqrt (2) << endl;
        cout << 12.00 << endl;
        cout << showpoint << 12.00 << endl;//显示点,精度上面以设为十了
        cout << noshowpoint << 12.00 << endl;//去掉小数点
        ifstream ifs ("stream.txt");
        ifs.unsetf (ios::skipws); //去掉默认不再跳过空白;
        char c;
        while (ifs >> c)
            cout << c;  //默认当成分隔符读取跳过空白
        ifs.setf (ios::skipws); //跳过空白
        ifs.clear (); // 复位,清除状态位
        ifs.seekg (ios::beg);//回到文件头
    //    ifs.seekg (0,ios::beg);//回到文件头
        while (ifs >> c)
            cout << c;
        ifs.close ();
        cout << endl;
        int i = 1234;
        double d = 56.78;
        string s = "tarena";
        ostringstream oss;//输出字符串流
        oss << i << ' ' << d << ' ' << s;
        string str = oss.str ();//拿出来
        cout << str << endl;
        str = "hello 3.14 pai";
        istringstream iss; //输入字符串流
        iss.str (str);
        iss >> s >> d >> str;
        cout << s << ' ' << d << ' ' << str << endl;
        return 0;
    }
    
  12. 字符串流

    class Student {
      ...
    private:
      string m_name;
      int m_age;
    };
    Student s ("张飞", 25);
    ofs.write (&s, sizeof (s));
    
    #include <iostream>
    #include <fstream>
    #include <cstring>
    using namespace std;
    class Dog {
    public:
        Dog (const string& name = "", int age = 0) :m_age (age) {
            strcpy (m_name, name.c_str ());//
        }
        void print (void) const {
            cout << m_name << "," << m_age << endl;
        }
    private:
    //    string name;//string记录的是地址
        char m_name[128];
        int m_age;
    };
    int main (void) {
        ofstream ofs ("dog.dat");
        Dog dog ("小白", 25);//创造对象
        ofs.write ((char*)&dog, sizeof (dog));  //地址,大小
        ofs.close ();
        ifstream ifs ("dog.dat");
        Dog dog2;
        ifs.read ((char*)&dog2, sizeof (dog2));
        dog2.print ();
        ifs.close ();
        return 0;
    }
    

    初学

    C++ Primer Plus

    进阶

    C++ Primer

    Effective C++

    More Effective C++

    深入

    C++程序设计语言,Bjarena Stroustrup,机械版

    深度探索C++对象模型

    休闲

    C++语言99个常见错误

    C++语言的设计与演化,Bjarena Stroustrup

二、数据结构和算法

(一)、基本数据结构

  1. 数据结构的基本概念

    1. 逻辑结构

      1)集合结构(集):结构中的元素除了同属一个集之外,没有任何联系。

      2)线性结构(表):结构中的元素具有一对一的前后关系。

      3)树型结构(树):结构中的元素具有一对多的父子关系。

      4)网状结构(图):结构中的元素具有多对多的交叉映射关系。

    2. 物理结构

      1)顺序结构(数组):结构中的元素存放在一段连续的地址空间中。随机访问方便,空间利用率低,插入删除不便。

      2)链式结构(链式):结构中的元素存放在彼此独立的地址空间中,每个独立的地址空间被称为节点,节点除了保存数据以外,还保存另外一个或几个相关节点的地址。空间利用率高,插入删除方便,随机访问不便。

      3.逻辑结构和物理结构的关系

      ​ 表 树 图

      顺序 数组 顺序树 复

      链式 链表 链式树 合

  2. 数据结构的基本运算

    1. 创建与销毁
    2. 插入与删除
    3. 获取与修改
    4. 排序与查找
  3. 堆栈

    1. 基本特征:后进先出

    2. 基本操作:压入(push),弹出(pop)

    3. 实现要点:初始化空间,栈顶指针,判空判满。

      1234

      19^3+29^2+39^1+49^0 -> 4

      123 -> 3

      12 -> 2

      1 -> 1

      //堆
      #include <iostream>
      using namespace std;
      // 基于顺序表的堆栈
      class Stack {
      public:
          // 构造过程中分配内存
          Stack (size_t size = 10) :m_array (new int[size]), m_size (size),m_top (0) {}           //内存分配
          // 析构过程中释放内存
          ~Stack (void) {
              if (m_array) {
                  delete[] m_array;  //回收
                  m_array = 0;
              }
          }
          // 压入
          void push (int data) {
              if (full ())
                  throw OverFlow ();
              m_array[m_top++] = data;//入栈
          }
          // 弹出
          int pop (void) {
              if (empty ())  //判空
                  throw UnderFlow ();
              return m_array[--m_top];
          }
          // 判满
          bool full (void) const {
              return m_top >= m_size;//
          }
          // 判空
          bool empty (void) const {
              return ! m_top;
          }
      private:
          // 上溢异常
          class OverFlow : public exception {   //类中类
              const char* what (void) const throw () {//重载覆盖
                  return "堆栈上溢!";
              }
          };
          // 下溢异常
          class UnderFlow : public exception {
              const char* what (void) const throw () {  //重载覆盖
                  return "堆栈下溢!";
              }
          };
          int* m_array; // 数组
          size_t m_size; // 容量
          size_t m_top; // 栈顶
      };
      void printb (unsigned int numb, int base) {
          Stack stack (256);
          do {
              stack.push (numb % base);//取模
          }    while (numb /= base);
          while (! stack.empty ()) {
              int digit = stack.pop ();//弹出一个数
              if (digit < 10) //占一位可以容下
                  cout << digit;
              else
                  cout << char (digit - 10 + 'A');//以字符形式输出
          }
          cout << endl;
      }
      int main (void) {
          try {
              Stack stack;
              for (int i = 0; ! stack.full (); ++i) //放
                  stack.push (i);
      //        stack.push (0);
              while (! stack.empty ())//拿
                  cout << stack.pop () << endl;
      //        stack.pop ();
          }
          catch (exception& ex) {
              cout << ex.what () << endl;
              return -1;
          }
          cout << "输入一个整数:" << flush;
          int numb;
          cin >> numb;
          cout << "您想看几进制:" << flush;//冲到屏幕
          int base;
          cin >> base;
          cout << "结果:";
          printb (numb, base);
          return 0;
      }
      
      // 基于链式表的堆栈
      #include <iostream>
      using namespace std;
      // 基于链式表的堆栈
      class Stack {
      public:
          // 构造过程中初始化为空堆栈
          Stack (void) : m_top (NULL) {}
          // 析构过程中销毁剩余的节点
          ~Stack (void) {
              for (Node* next; m_top; m_top = next) {
                  next = m_top->m_next;
                  delete m_top;
              }
          }
          // 压入
          void push (int data) {
              /*
              Node* node = new Node;
              node->m_data = data;
              node->m_next = m_top;
              m_top = node;*/
              m_top = new Node (data, m_top);
          }
          // 弹出
          int pop (void) {
              if (empty ())
                  throw UnderFlow ();
              int data = m_top->m_data;//数据备份
              Node* next = m_top->m_next;//备份
              delete m_top;
              m_top = next;
              return data;
          }
          // 判空
          bool empty (void) const {
              return ! m_top;
          }
      private:
          // 下溢异常
          class UnderFlow : public exception {
              const char* what (void) const throw () {
                  return "堆栈下溢!";
              }
          };
          // 节点类
          class Node {
          public:
              Node (int data = 0, Node* next = NULL) :m_data (data), m_next (next) {}
              int m_data; // 数据
              Node* m_next; // 后指针
          };
          Node* m_top; // 栈顶
      };
      int main (void) {
          try {
              Stack stack;
              for (int i = 0; i < 10; ++i)
                  stack.push (i);
              while (! stack.empty ())cout << stack.pop () << endl;//依次弹出
      //        stack.pop ();
          }
          catch (exception& ex) {
              cout << ex.what () << endl;
              return -1;
          }
          return 0;
      }
      
  4. 队列

    1. 基本特征:先进先出,FIFO

    2. 基本操作:压入(push)、弹出(pop)

      //队列
      #include <iostream>
      using namespace std;
      // 基于顺序表的队列
      class Queue {
      public:
          // 构造过程中分配内存
          Queue (size_t size = 5) :m_array (new int[size]), m_size (size),m_rear (0), m_front (0), m_count (0) {} //m_size = 5//缺省构造
          // 析构过程中释放内存
          ~Queue (void) {
              if (m_array) {
                  delete[] m_array;
                  m_array = NULL;
              }
          }
          // 压入
          void push (int data) {
              if (full ()) //满了
                  throw OverFlow ();
              if (m_rear >= m_size) //越界就跳到下面;m_size为满时的下标
                  m_rear = 0;//复位
              ++m_count;//计数
              m_array[m_rear++] = data;//放数
          }
          // 弹出
          int pop (void) {
              if (empty ())
                  throw UnderFlow ();//下溢
              if (m_front >= m_size)  //是否越界
                  m_front = 0;//复位
              --m_count;//计数
              return m_array[m_front++];//返回当前所对应的数,并下移
          }
          // 判空
          bool empty (void) const {
              return ! m_count; //为零就为空
          }
          // 判满
          bool full (void) const {
              return m_count == m_size;//计数与数组等大
          }
      private:
          // 上溢异常
          class OverFlow : public exception {
              const char* what (void) const throw () {   ///??????????
                  return "队列上溢!";
              }
          };
          // 下溢异常
          class UnderFlow : public exception {
              const char* what (void) const throw () {
                  return "队列下溢!";
              }
          };
          int* m_array; // 数组;内存空间
          size_t m_size; // 容量;//下标
          size_t m_rear; // 后端//下标
          size_t m_front; // 前端//下标
          size_t m_count; // 计数
      };
      int main (void) {
          try { //可能随时抛异常必须全放里面???????????
              Queue queue;
              queue.push (10);
              queue.push (20);
              queue.push (30);
              queue.push (40);
              queue.push (50);
      //        queue.push (60); //已满上溢
              cout << queue.pop () << endl; // 10  //弹出一个数
              queue.push (60);//放一个
              cout << queue.pop () << endl; // 20
              queue.push (70);
      //        queue.push (80); //上溢
              cout << queue.pop () << endl; // 30
              cout << queue.pop () << endl; // 40
              cout << queue.pop () << endl; // 50
              cout << queue.pop () << endl; // 60
              cout << queue.pop () << endl; // 70
      //        queue.pop ();//下溢
          }
          catch (exception& ex) {
              cout << ex.what () << endl;//????????????????
              return -1;
          }
          return 0;
      }
      
    3. 实现要点:初始化空间,从前端(front)弹出,从后端(rear)压入,循环使用,判空判满

      //链式表队列
      #include <iostream>
      using namespace std;
      // 基于链式表的队列
      class Queue {
      public:
          // 在构造过程中初始化为空队列
          Queue (void) : m_rear (NULL), m_front (NULL) {}  //空队列
          // 在析构过程中销毁剩余的节点
          ~Queue (void) {
              for (Node* next; m_front; m_front = next) { //不好理解的多练!!!!!!!!!!!!!
                  next = m_front->m_next;//拿下个数据的地址// 从前到后
                  delete m_front;
              }
          }
          // 压入
          void push (int data) {
              Node* node = new Node (data);//
              if (m_rear)
                  m_rear->m_next = node;//当前数据的地址交给上个节点存放
              else
                  m_front = node;//那就是前端
              m_rear = node; //必指向后端
          }
          // 弹出
          int pop (void) {
              if (empty ())     //判空
                  throw UnderFlow ();
              int data = m_front->m_data;   //备份数据//
              Node* next = m_front->m_next; //备份数据//下一个节点的地址
              delete m_front;
              if (! (m_front = next)) //存放下一个节点数据的地址
                  m_rear = NULL;//清除当前节点所存的地址
              return data;//弹出数据
          }
          // 判空
          bool empty (void) const {
              return ! m_front && ! m_rear;  //两个指针均为空则空
          }
      private:
          // 下溢异常
          class UnderFlow : public exception {
              const char* what (void) const throw () {
                  return "队列下溢!";
              }
          };
          // 节点 //每个元素的单元
          class Node {
          public:
              Node (int data = 0, Node* next = NULL) : m_data (data), m_next (next) {} //初始化
              int m_data; // 所存的数据
              Node* m_next; // 后指针//指向下一个节点的地址
          };
          Node* m_rear; // 后端指针
          Node* m_front; // 前端指针
      };
      int main (void) {
          try {
              Queue queue;
              for (int i = 0; i < 10; ++i)
                  queue.push (i);
              while (! queue.empty ())    //全部取出,到空为止;
                  cout << queue.pop () << endl;
          }//Node* 
          catch (exception& ex) {
              cout << ex.what () << endl;
              return -1;
          }
          return 0;
      //    de* 
      }
      
    4. 用堆栈实现队列。

      squeue.h

      #ifndef _LSTACK_H
      #define _LSTACK_H
      #include <stdexcept>
      using namespace std;
      // 基于链式表的堆栈
      class Stack {
      public:
          // 构造过程中初始化为空堆栈
          Stack (void) : m_top (NULL) {}
          // 析构过程中销毁剩余的节点
          ~Stack (void) {
              for (Node* next; m_top; m_top = next) {
                  next = m_top->m_next;
                  delete m_top;
              }
          }
          // 压入
          void push (int data) {
              /*
              Node* node = new Node;
              node->m_data = data;
              node->m_next = m_top;
              m_top = node;*/
              m_top = new Node (data, m_top);
          }
          // 弹出
          int pop (void) {
              if (empty ())
                  throw UnderFlow ();
              int data = m_top->m_data;
              Node* next = m_top->m_next;
              delete m_top;
              m_top = next;
              return data;
          }
          // 判空
          bool empty (void) const {
              return ! m_top;
          }
      private:
          // 下溢异常
          class UnderFlow : public exception {
              const char* what (void) const throw () {
                  return "堆栈下溢!";
              }
          };
          // 节点
          class Node {
          public:
              Node (int data = 0, Node* next = NULL) :
                  m_data (data), m_next (next) {}
              int m_data; // 数据
              Node* m_next; // 后指针
          };
          Node* m_top; // 栈顶
      };
      #endif // _LSTACK_H
      

      squeue.cpp

      //用堆栈实现队列
       //负负为正的道理
      #include <iostream>
      #include "lstack.h"//调用
      using namespace std;
      // 基于堆栈的队列
      class Queue {  //构造函数省略即可
      public:
          // 压入
          void push (int data) {
              m_i.push (data);
          }
          // 弹出
          int pop (void) {
              if (m_o.empty ()) {  //后堆判空
                  if (m_i.empty ()) //前堆判空
                      throw underflow_error("队列下溢!"); //标准库异常
                  while (! m_i.empty ())
                      m_o.push (m_i.pop ());//向下一个栈放数据;
              }
              return m_o.pop ();//弹出
          }
          // 判空
          bool empty (void) const {
              return m_i.empty () && m_o.empty ();  //两个栈均为空则空
          }
      private:   //创造两个栈(对象)
          Stack m_i; // 输入栈
          Stack m_o; // 输出栈
      };
      int main (void) {
          try {
              Queue queue;
              for (int i = 0; i < 10; ++i)
                  queue.push (i);
              cout << queue.pop () << endl; // 0
              cout << queue.pop () << endl; // 1
              cout << queue.pop () << endl; // 2
              cout << queue.pop () << endl; // 3
              cout << queue.pop () << endl; // 4
              queue.push (10);
              queue.push (11);
              queue.push (12);
              while (! queue.empty ()) //全部弹出 
                  cout << queue.pop () << endl;
          }
          catch (exception& ex) {
              cout << ex.what () << endl;
              return -1;
          }
          return 0;
      }
      
  5. 链表

    1. 基本特征:内存中不连续的节点序列,彼此之间通过指针相互关联,前指针(prev)指向前节点,后指针(next)指向后节点。

    2. 基本操作:追加、插入、删除、遍历

    3. 实现要点:

      void 讲故事 (void) {

      从前有座山;

      山里有个庙;

      庙里有个老和尚;

      if (老和尚圆寂了)

      ​ return;

      讲故事 ();

      }

      //  实现双向线性链表
      #include <iostream>
      #include <stdexcept>
      using namespace std;
      // 双向线性链表
      class List {
      public:
          // 构造过程中初始化为空链表
          List (void) : m_head (NULL), m_tail (NULL) {}
          // 析构过程中销毁剩余的节点
          ~List (void) {  //遍历删除所有节点
              for (Node* next; m_head; m_head = next) {
                  next = m_head->m_next;  //
                  delete m_head;
              }
          }
          // 追加
          void append (int data) {
              m_tail = new Node (data, m_tail);//新建的节点
              if (m_tail->m_prev)
                  m_tail->m_prev->m_next = m_tail;//前面节点的后指针给他
              else //前节点空
                  m_head = m_tail;  //首尾
          }
          // 插入
          void insert (size_t pos, int data) {  //提供位置和数据
              for (Node* find = m_head; find; find = find->m_next)//移动节点
                  if (pos-- == 0) {
                      Node* node = new Node (data,find->m_prev, find); //
                      if (node->m_prev)
                          node->m_prev->m_next = node;//指针取成员
                      else
                          m_head = node;
                      find -> m_prev = node;
      //                node->m_next->m_prev = node;
                      return;
                  }
              throw out_of_range ("链表越界!");//标准库异常
          }
          // 删除
          void erase (size_t pos) {  //提供位置
              for (Node* find = m_head; find; //遍历
                  find = find->m_next)
                  if (pos-- == 0) {
                      if (find->m_prev)
                          find->m_prev->m_next =find->m_next;//前面节点的后指针被赋值
                      else
                          m_head = find->m_next;//
                      if (find->m_next)
                          find->m_next->m_prev = find->m_prev;//后节点的前指针被赋值
                      else
                          m_tail = find->m_prev;
                      delete find;//删除
                      return;
                  }
              throw out_of_range ("链表越界!");//pos太大越界
          }
          // 正向遍历
          void forward (void) const {  //从前到后打印
              for (Node* node = m_head; node;node = node->m_next) //从前到后扫一遍
                  cout << node->m_data << ' ';
              cout << endl;
          }
          // 反向遍历
          void backward (void) const { //从后到前打印
              for (Node* node = m_tail; node;node = node->m_prev)
                  cout << node->m_data << ' ';
              cout << endl;
          }
          // 下标访问
          int& operator[] (size_t index) {
              for (Node* find = m_head; find;find = find->m_next)
                  if (index-- == 0)
                      return find->m_data;
              throw out_of_range ("链表越界!"); //下标过大
          }
          const int& operator[] (size_t index) const {
              return const_cast<List&> (*this) [index]; //去常
          }
      private:
          // 节点 // 内部类
          class Node {
          public:
              Node (int data = 0, Node* prev = NULL,Node* next = NULL) : m_data (data),m_prev (prev), m_next (next) {}
              int m_data; // 数据
              Node* m_prev; // 前指针
              Node* m_next; // 后指针
          };
          Node* m_head; // 头指针指向第一个节点
          Node* m_tail; // 尾指针
      };
      int main (void) {
          try {
              List list;
              list.append (10);
              list.append (30);
              list.append (50);
              list.append (60);
              list.append (80);
              list.insert (1, 20);
              list.insert (3, 40);
              list.insert (6, 70);
              list.forward ();//正向遍历
              list.backward ();//反向遍历
              list.erase (5);
              list.erase (5);
              list.erase (5);
              list.forward ();
              for (size_t i = 0; i < 5; ++i)
                  ++list[i];//左值
              const List& cr = list;
              for (size_t i = 0; i < 5; ++i)
                  cout << /*++*/cr[i] << ' ';  //右值
              cout << endl;
          }
          catch (exception& ex) {
              cout << ex.what () << endl;
              return -1;
          }
          return 0;
      }
      

      实现一个单向线性链表类

      // 练习:实现一个单向线性链表类
      // 1.建立(追加)、测长、正反向打印
      // 2.逆转
      // 3.获取中间节点值,单次遍历
      // 4.有序链表的插入和删除
      #include <iostream>
      #include <stdexcept>
      using namespace std;
      class List {
      public:
          List (void) : m_head (NULL), m_tail (NULL) {}
          ~List (void) { //释放剩余节点
              for (Node* next; m_head; m_head = next) {
                  next = m_head->m_next;
                  delete m_head;
              }
          }
          void append (int data) {  //追加
              Node* node = new Node (data);
              if (m_tail)
                  m_tail->m_next = node;
              else
                  m_head = node;
              m_tail = node;//必须
          }
          size_t size (void) const { //测长
              size_t cn = 0;
              for (Node* node = m_head; node;node = node->m_next)
                  ++cn;
              return cn;
          }
          void print (void) const { //正向打印
              for (Node* node = m_head; node;node = node->m_next)
                  cout << node->m_data << ' ';
              cout << endl;
          }
          void rprint (void) const {  //反向打印
              rprint (m_head);
              cout << endl;
          }
          /*
          void reverse (void) {   //实现逆转
              reverse (m_head);
              swap (m_head, m_tail);  //调换
          }
          */
          void reverse (void) {  //不用递归逆转
              if (m_head != m_tail) {
                  Node* p1 = m_tail = m_head; //
                  Node* p2 = p1->m_next;
                  Node* p3 = p2->m_next;
                  for (p1->m_next=NULL;p3;p3=p3->m_next) {
                      p2->m_next = p1;
                      p1 = p2;
                      p2 = p3;
                  }
                  (m_head = p2)->m_next = p1; //调整最后两个
              }
          }
          int middle (void) const {
              if (! m_head || ! m_tail)
                  throw underflow_error ("链表下溢!");
              if (m_head == m_tail)//只有一个
                  return m_head->m_data;
              Node* mid = m_head;//慢指针
              for (Node* node = m_head;//快指针
                  node->m_next && node->m_next->m_next;
                  node = node->m_next->m_next) //一次跳两个
                  mid = mid->m_next;
              return mid->m_data;
          }
          // 插入data,仍然保持有序
          void insert (int data) {
          }
          // 删除所有的data,保持有序
          void remove (int data) {
          }
      private: //节点
          class Node {
          public:
              Node (int data = 0, Node* next = NULL) :m_data (data), m_next (next) {}
              int m_data;
              Node* m_next;
          };
          void rprint (Node* head) const {    //逆向打印
              if (head) {
                  rprint (head->m_next); //逆向节点打印,利用函数递归
                  cout << head->m_data << ' ';//利用了函数堆栈
              }
          }
          void reverse (Node* head) {   //逆转  
              if (head && head->m_next) {
                  reverse (head->m_next);//
                  head->m_next->m_next = head;
                  head->m_next = NULL;
              }
          }
          Node* m_head;
          Node* m_tail;
      };
      int main (void) {
          List list;
          for (int i = 0; i < 11; ++i)
              list.append (i);
          cout << list.size () << endl;
          list.print ();
          list.rprint ();
          list.reverse ();
          list.print ();
          cout << list.middle () << endl;
          return 0;
      }
      
  6. 二叉树

    1. 基本特征

      1)树型结构的最简模型,每个节点最多有两个子节点。

      2)单根。除根节点外每个节点有且仅有一个父节点,整棵树只有一个根节点。

      3)递归结构,用递归处理二叉树问题可以简化算法。

    2. 基本操作

      1)生成

      2)遍历

      D-L-R:前序遍历

      L-D-R:中序遍历

      L-R-D:后序遍历

      有序二叉树(二叉搜索树)

      L<=D<=R

      50 70 20 60 40 30 10 90 80

      ​ 50

      ​ / \

      ​ /-- --\

      ​ 20| 70

      ​ / \ / \

      ​ 10 40 60 90

      ​ / /

      ​ 30 80

      中序遍历:10 20 30 40 50 60 70 80 90

      程序设计=数据结构+算法+设计方法学

      数值算法:微积分、方程组、有限元分析等—工程计算。

      非数值算法:查找、排序、决策、调度—系统编程。

      //   **********有序二叉树(二叉搜索树)*************
      #include <iostream>
      using namespace std;
      // 有序二叉树(二叉搜索树)
      class Tree {
      public:
          // 构造过程中初始化为空树
          Tree (void) : m_root (NULL), m_size (0) {}
          // 析构过程中销毁剩余节点
          ~Tree (void) {
              clear (); //函数
          }
          // 插入数据
          void insert (int data) {
              insert (new Node (data), m_root); //插入子树
              ++m_size; //计数
          }
          // 删除第一个匹配数据,不存在返回false
          bool erase  (int data) {  //删除一个
              Node*& node = find (data, m_root);//找
              if (node) {//不空
                  // 左插右
                  insert (node->m_left, node->m_right); //匹配节点的左子树插到右子树
                  Node* temp = node;//备份后一会在去删除
                  // 右提升
                  node = node->m_right;
                  delete temp;//删除匹配节点
                  --m_size;//计数
                  return true;
              }
              return false;
          }
          // 删除所有匹配数据
          void remove (int data) {
              while (erase (data));//循环删除
          }
          // 清空树
          void clear (void) {
              clear (m_root); //删根
              m_size = 0;
          }
          // 将所有的_old替换为_new //   替换
          void update (int _old, int _new) {
              while (erase (_old)) //删一个_old;这样不会破坏规则
                  insert (_new); //插一个_new
          }
          // 判断data是否存在(查找)
          bool find (int data) {
              return find (data, m_root) != NULL;
          }
          // 中序遍历
          void travel (void) { //判断正确与否
              travel (m_root);
              cout << endl;
          }
          // 获取大小
          size_t size (void) {
              return m_size;
          }
          // 获取树高
          size_t height (void) {
              return height (m_root);
          }
      private:
          // 节点
          class Node {
          public:
              Node (int data) : m_data (data),m_left (NULL), m_right (NULL) {}
              int m_data; // 数据
              Node* m_left; // 左树指针
              Node* m_right; // 右树指针
          };
          //插入函数
          void insert (Node* node, Node*& tree) {//节点,引用为了向成员变量赋值;子树
              if (! tree)//别名//空
                  tree = node; //父节点的下边;空//也是递归终止条件
              else if (node) {//节点
                  if (node->m_data < tree->m_data) //插左边
                      insert (node, tree->m_left); //递归,插左边????????????????
                  else
                      insert (node, tree->m_right);//递归,插右边
              }
          }
          // 返回子树tree中值与data相匹配的节点的父节点中指向该节点的成员变量的别名//(返回的是指向该节点的别名(引用;笔记中的/\))
          Node*& find (int data, Node*& tree) { //子树;返回引用
              if (! tree) //空
                  return tree;//找不到//返回指针(既是别名)
              else
              if (data == tree->m_data)//匹配的情况
                  return tree;//已经匹配
              else
              if (data < tree->m_data)//不匹配
                  return find (data, tree->m_left); //递归,在左子树里面找
              else
                  return find (data, tree->m_right); //否则在右子树里找
          }
          //删除子树
          void clear (Node*& tree) {
              if (tree) { //递归
                  clear (tree->m_left);//终止条件,自动删到叶节点
                  clear (tree->m_right);
                  delete tree;
                  tree = NULL;
              }
          }
          //中序遍历
          void travel (Node* tree) {
              if (tree) { //此一下顺序决定遍历方式 // 非空为终止条件
                  travel (tree->m_left);//递归
                  cout << tree->m_data << ' ';
                  travel (tree->m_right); //递归
              }
          }
          //获取树高
          size_t height (Node* tree) {
              if (tree) {
                  size_t lh = height (tree->m_left);//求左子树树高????????
                  size_t rh = height (tree->m_right);//求右子树树高
                  return (lh > rh ? lh : rh)+ 1;//取大加一
              }
              return 0;//空的时候
          }
          //成员变量
          Node* m_root; // 树根
          size_t m_size; // 大小
      };
      int main (void) {
          Tree tree;
          tree.insert (50);
          tree.insert (70);
          tree.insert (20);
          tree.insert (60);
          tree.insert (40);
          tree.insert (30);
          tree.insert (10);
          tree.insert (90);
          tree.insert (80);
          tree.travel ();//中序遍历
          cout << tree.size () << ' ' << tree.height ()
              << endl;
          tree.erase (70);
          tree.travel ();
          tree.insert (70);
          tree.insert (70);
          tree.insert (70);
          tree.travel ();
          tree.remove (70);
          tree.travel ();
          tree.insert (40);
          tree.insert (40);
          tree.travel ();
          tree.update (40, 69);
          tree.travel ();
          cout << boolalpha << tree.find (50) << endl;//boolalpha输出判断真假
          cout << tree.find (55) << endl;
          tree.clear ();
          tree.travel ();
          return 0;
      }
      

(二)、排序和查找算法

  1. 冒泡排序

    1. 算法

      1)比较相邻的元素,如果第一个比第二个大,就交换它们俩;

      2)对每一对相邻的元素做同样的工作,从开始的第一对到结尾的最后一对,使最后的元素为最大值;

      3)针对的所有的元素重复以上步骤,除了最后一个;

      4)持续每次对越来越少的元素重复以上步骤,直到没有元素需要交换为止。

    2. 评价

      平均时间复杂度:O(N^2)

      稳定

      对数据的有序性非常敏感

  2. 插入排序

    1. 算法

      1)从第一个元素开始,该元素可以认为已经有序;

      2)取出下一个元素,在已经有序的序列中从后向前扫描;

      3)若该元素大于新元素,则将该元素移到下一个位置;

      4)若该元素小于等于新元素,则将新元素放在该元素之后;

      5)重复步骤2),直到处理完所有元素。

    2. 评价

      平均时间复杂度:O(N^2)

      稳定

      对数据的有序性非常敏感

      因为没有交换,所以赋值的次数比冒泡少,速度比冒泡略快。

  3. 选择排序

    1. 算法

      首先在未排序序列中找到最小元素,与该序列的首元素交换,再从剩余未排序元素中继续寻找最小元素,放到有序序列的末尾。以此类推,直到所有元素均排序完毕。

    2. 评价

      平均时间复杂度:O(N^2)

      稳定

      对数据的有序性不敏感

      因为交换的次数少,所有速度比冒泡略快。

  4. 快速排序

    1. 算法

      1)从序列中选出一个元素作为基准;

      2)重排序列,所有比基准小的元素位于基准左侧,比基准大的元素位于基准右侧,和基准相等的元素位于任意一侧,此过程称为分组;

      3)以递归的方式对小于基准的分组和大于基准的分组分别进行排序。

    2. 评价

      平均时间复杂度:O(NlogN)

      不稳定

      如果每次能够均匀分组速度将是最快的。

      #include <stdio.h>
      #include <string.h>
      #include <stdlib.h>
      static void quickSort (void* base, size_t left,size_t right, size_t size, int (*compar) (const void*, const void*)) {
          size_t p = (left + right) / 2;
          void* pivot = malloc (size); //基准值地址
          memcpy (pivot, base + p * size, size);  //内存地址拷贝
          size_t i, j;//左右边界
          for (i = left, j = right; i < j;) {
              while (! (i >= p || compar (pivot,base + i * size) < 0)) //
                  ++i;
              if (i < p) {
                  memcpy (base + p * size,base + i * size, size);
                  p = i;
              }
              while (! (j <= p || compar (
                  base + j * size, pivot) < 0))
                  --j;
              if (j > p) {
                  memcpy (base + p * size,base + j * size, size);
                  p = j;
              }
          }
          memcpy (base + p * size, pivot, size); //位置。目标。大小
          free (pivot);//释放
          if (p - left > 1) //左侧分组
              quickSort (base, left, p - 1, size, compar);
          if (right - p > 1)//右侧分组
              quickSort (base, p+1, right, size, compar);
      }
      void my_qsort (void* base, size_t numb, size_t size,int (*compar) (const void*, const void*)) {
          quickSort (base, 0, numb -1, size, compar);
      }
      int cmpInt (const void* a, const void* b) {  //比较两个目标  //返回值为-1(>),0(=) ,1(<);
          return *(const int*)a - *(const int*)b;//比较两个整数
      }
      int cmpStr (const void* a, const void* b) { //a,b为两个元素地址
          return strcmp (*(const char* const*)a,*(const char* const*)b); //拿到字符串;比较两个字符串大小
      }
      int main (void) {
          int na[] = {34, 22, 19, 27, 30};
          size_t size = sizeof (na[0]);
          size_t numb = sizeof (na) / size;
      //    qsort (na, numb, size, cmpInt);  //数组起始地址。元素个数。每个元素的字节数。比较函数的地址;
          my_qsort (na, numb, size, cmpInt);
          size_t i;
          for (i = 0; i < numb; ++i)
              printf ("%d ", na[i]);
          printf ("\n");
          const char* sa[] = {"beijing", "chongqing","shanghai", "tianjin", "guangzhou"};
          size = sizeof (sa[0]);
          numb = sizeof (sa) / size;
      //    qsort (sa, numb, size, cmpStr);
          my_qsort (sa, numb, size, cmpStr);
          for (i = 0; i < numb; ++i)
              printf ("%s ", sa[i]);
          printf ("\n");
          return 0;
      }
      
  5. 归并排序

    1. 算法

      1)申请空间,其大小为两个有序序列之和;

      2)设定两个指针,分别指向两个有序序列的起始位置;

      3)比较两个指针的目标,选择小值放入合并空间,并将指针移到下一个位置;

      4)重复步骤3)直到某一个指针到达序列尾;

      5)将另一序列的剩余元素直接复制到合并空间。

    2. 评价

      平均时间复杂度:O(2NlogN)

      稳定

      对数据的有序性不敏感

      非就地排序,不适用于大数据量的排序。

      //******************************************* 算法*************************************
      #include <iostream>
      using namespace std;
      // 冒泡排序
      void bubbleSort (int data[], size_t size) {  //数组、大小
          for (size_t i = 0; i < size - 1; ++i) {  //趟数
      //        bool ordered = true;
              for (size_t j = 0; j < size - 1 - i; ++j) //每一趟扫描数;递减一次
                  if (data[j+1] < data[j]) {
                      int temp = data[j+1];//交换
                      data[j+1] = data[j];
                      data[j] = temp;
      //                ordered = false;
                  }
      //        if (ordered) //没进第二个for,就挑出来,结束循环
      //            break;
          }
      }
      // 插入排序
      void insertSort (int data[], size_t size) {
          for (size_t i = 1; i < size; ++i) {
              int temp = data[i];  //备份
              size_t j;
              for (j = i; j > 0 && temp < data[j-1]; --j) //向前比较找插入位置
                  data[j] = data[j-1];//一直向前移
              if (j != i)//相等时就不用交换赋值
                  data[j] = temp; //完成交换,插入
          }
      }
      // 选择排序
      void selectSort (int data[], size_t size) {
          for (size_t i = 0; i < size - 1; ++i) {
              size_t min = i;//最小的下标
              for (size_t j = i + 1; j < size; ++j)
                  if (data[j] < data[min])
                      min = j; //下标
              if (min != i) { //外面进行交换;
                  int temp = data[i];
                  data[i] = data[min];
                  data[min] = temp;
              }
          }
      }
      // 快速排序
      void quickSort (int data[], size_t left,size_t right) {  //左右边界 
          size_t p = (left + right) / 2;//取中间
          int pivot = data[p]; //中间数
          for (size_t i = left, j = right; i < j;) {
              while (! (i>= p || pivot < data[i])) // 不能碰上、比他大
                  ++i;
              if (i < p) {
                  data[p] = data[i];
                  p = i; //p放到i上
              }
              while (! (j <= p || data[j] < pivot))
                  --j;
              if (j > p) {
                  data[p] = data[j];
                  p = j;
              }
          }
          data[p] = pivot;//三点一线时
          if (p - left > 1)//左侧分组;也是终止条件
              quickSort (data, left, p - 1);
          if (right - p > 1)//右侧分组
              quickSort (data, p + 1, right);
      }
      // 异地合并
      void merge (int data1[], size_t size1, int data2[],size_t size2, int data3[]) {
          size_t i = 0, j = 0, k = 0;
          for (;;)
              if (i < size1 && j < size2) //大小比较
                  if (data1[i] <= data2[j])
                      data3[k++] = data1[i++];
                  else
                      data3[k++] = data2[j++];
              else if (i < size1)
                  data3[k++] = data1[i++];
              else if (j < size2)
                  data3[k++] = data2[j++];
              else
                  break;
      }
      // 本地合并
      void merge (int data[], size_t l, size_t m,size_t r) {
          int* res = new int[r-l+1]; 
      //    int res[r-l+1]; //动态数组
          merge (data+l, m-l+1, data+m+1, r-m, res); //调用
          for (size_t i = 0; i < r-l+1; ++i)
              data[l+i] = res[i];
          delete[] res;
      }
      // 归并排序
      void mergeSort (int data[], size_t left,size_t right) {
          if (left < right) { //只有一个数时终止
              int mid = (left + right) / 2;//分割
              mergeSort (data, left, mid);
              mergeSort (data, mid+1, right);
              merge (data, left, mid, right);//合并
          }
      }
      int main (void) {
          int data[] = {13,23,20,12,15,31,19,26,24,37};
          size_t size = sizeof (data) / sizeof (data[0]); //计算个数
          bubbleSort (data, size); //冒泡
      //    insertSort (data, size); //插入
      //    selectSort (data, size);
      //    quickSort (data, 0, size - 1); //数据、左右区间
      //    mergeSort (data, 0, size - 1);
          for (size_t i = 0; i < size; ++i)  //打印
              cout << data[i] << ' ';
          cout << endl;
          /*
          int data1[] = {10, 20, 30, 45, 66};
          int data2[] = {15, 18, 27, 33};
          int data3[9];
          merge (data1, 5, data2, 4, data3);
          for (size_t i = 0; i < 9; ++i)
              cout << data3[i] << ' ';
          cout << endl;
          // 10 15 18 20 27 30 33 45 66
      //    
          int data[] = {100,10,20,30,45,66,15,18,27,33,0};
          merge (data, 1, 5, 9);
          for (size_t i = 0; i < 11; ++i)
              cout << data[i] << ' ';
          cout << endl;
          // 100 10 15 18 20 27 30 33 45 66 0
          */
          return 0;
      }
      
  6. 线性查找

    1. 算法

      从表头开始依次比较,直到找到与查找目标匹配的元素,或者找不到。

    2. 评价

      平均时间复杂度:O(N)

      对数据的有序性没有要求。

  7. 二分查找

    1. 算法

      首先必须保证查找样本必须有序,将表中值与查找目标进行比较,如果二者相等,则查找成功,否则根据查找目标比中值大或者小,在其右侧或者左侧继续前述过程。直到查找成果或者失败。

    2. 评价

      平均时间复杂度:O(logN)

      数据必须有序!

      //###########查找##############
      //线性查找
      #include <iostream>
      using namespace std;
      int linFind (int data[], int size, int key) {
          for (int i = 0; i < size; ++i) //遍历
              if (data[i] == key)
                  return i;
          return -1;
      }
      //二分查找
      int binFind (int data[], int size, int key) {
          int left = 0;
          int right = size - 1; //边界
          while (left <= right) {
              int mid = (left + right) / 2;  //中间位置
              if (data[mid] < key)    //判断哪侧去找
                  left = mid + 1;
              else
              if (key < data[mid])
                  right = mid - 1;
              else
                  return mid;  //等于时
          }
          return -1; //没找到
      }
      int main (void) {
          int data[] = {12, 43, 56, 69, 77};
          int size = sizeof (data) / sizeof (data[0]);
          int i = linFind (data, size, /*9*/7);
          if (i == -1)
              cout << "没找到!" << endl;
          else
              cout << "data[" << i << "] = " << data[i]
                  << endl;
          i = binFind (data, size, /*69*/7);
          if (i == -1)
              cout << "没找到!" << endl;
          else
              cout << "data[" << i << "] = " << data[i]
                  << endl;
          return 0;
      }
      

三、模板和STL

(一)、模板语法

  1. 为什么要有模板?

    将类型参数化,可以实现算法与类型的分离,编写针对类型更加抽象的函数或者类。

    #include <iostream>
    using namespace std;
    int max_int (int x, int y) {
        return x > y ? x : y;
    }
    string max_str (string x, string y) {
        return x > y ? x : y;
    }
    int main (void) {
        cout << "输入两个整数:" << flush;
        int nx, ny;
        cin >> nx >> ny;
        cout << "最大值:" << max_int (nx, ny) << endl;
        cout << "输入两个字符串:" << flush;
        string sx, sy;
        cin >> sx >> sy;
        cout << "最大值:" << max_str (sx, sy) << endl;
        return 0;
    }
    
  2. 函数模板

    通用定义:

    template

    返回类型 函数模板名 (形参表) { ... }

    特化定义:

    template<>

    返回类型 函数模板名<类型实参1, ...> (形参表) { ... }

    //模版
    // ***************函数模板/模板函数****************************
    #include <iostream>
    #include <typeinfo>
    #include <cstring>
    using namespace std;
    // 函数模板/模板函数
    template<typename T>   //T为类型参数,可以被各种类型替换
    T Max (T x, T y) {  //全改为T,等着被替换,有编译器去做//后期编译
        cout << typeid (T).name () << endl;
        return x > y ? x : y;
    }
    // 模板特化
    template<> //针对char*所做的特例化
    char* Max<char*> (char* x, char* y) {  //char*类型//函数名为地址的地址//故ok //显示特化
    //char* Max(char* x, char* y) {  //char*类型//函数名为地址的地址//故ok  //隐式特化
        return strcmp (x, y) > 0 ? x : y;
    }
    template<typename T>
    void foo (void) {  //函数必须传递数据类型 //告知T的类型
        T t;
        cout << typeid (t).name () << endl;//打印类型信息
    }
    int main (void) {
        cout << "输入两个整数:" << flush;
        int nx, ny;
        cin >> nx >> ny;
        cout << "最大值:" << Max (nx, ny) << endl; //可以隐式推断//类型必须在参数表中
    //    cout << "最大值:" << Max<int> (nx, ny) << endl;//显式指明
        cout << "输入两个字符串:" << flush;
        string sx, sy;
        cin >> sx >> sy;
        cout << "最大值:" << Max (sx, sy) << endl;
        cout << "输入两个字符串:" << flush;
        char cx[256], cy[256];  //字符数组
        cin >> cx >> cy;
        cout << "最大值:" << Max (cx, cy) << endl; //变成比较地址了
    //    cout << "最大值:" << Max <string>(cx, cy) << endl;
        /*
        foo();//ERORR
        foo<int> ();//ok
        foo<double> ();//ok
        foo<string> ();//ok
        */
        return 0;
    }
    
  3. 类模板

    通用定义:

    template

    class 类模板名 { ... };

    全类特化:

    template<>

    class 类模板名<类型实参1, ...> { ... };

    成员特化:

    template<>

    返回类型 类模板名<类型实参1, ...>::成员函数名 (形参表) { ... }

    #include <iostream>
    #include <cstring>
    using namespace std;
    // 通用模板
    template<typename T>
    class Comparator {
    public:
        Comparator (T x, T y) : m_x (x), m_y (y) {}
        T min (void) const {
            return m_x < m_y ? m_x : m_y;
        }
        T max (void) const {
            return m_x > m_y ? m_x : m_y;
        }
    private:
        T m_x;
        T m_y;
    };
    /*
    // 针对char*的全模板特化//将类内所有函数特化
    template<>//特化
    class Comparator<char*> { //加特化类型
    public:
        Comparator (char* x, char* y) :m_x (x), m_y (y) {}
        char* min (void) const {
            return strcmp (m_x, m_y) < 0 ? m_x : m_y;
        }
        char* max (void) const {
            return strcmp (m_x, m_y) > 0 ? m_x : m_y;
        }
    private:
        char* m_x;
        char* m_y;
    };
    */
    // 针对char*的成员函数特化//针对个别函数特化
    template<>//特化
    char* Comparator<char*>::min (void) const {  //拿外面定义 //此处的第一个char*相当于25行的
        return strcmp (m_x, m_y) < 0 ? m_x : m_y;
    }
    template<>
    char* Comparator<char*>::max (void) const {
        return strcmp (m_x, m_y) > 0 ? m_x : m_y;
    }
    int main (void) {
        cout << "输入两个整数:" << flush;
        int nx, ny;
        cin >> nx >> ny;
        Comparator<int> cn (nx, ny); //必须给显示推断 //与下面两个类
        cout << "最小值:" << cn.min () << endl;
        cout << "最大值:" << cn.max () << endl;
        cout << "输入两个字符串:" << flush;
        string sx, sy;
        cin >> sx >> sy;
        Comparator<string> cs (sx, sy); //必须给显示推断//字符串
        cout << "最小值:" << cs.min () << endl;
        cout << "最大值:" << cs.max () << endl;
        cout << "输入两个字符串:" << flush;
        char cx[256], cy[256];
        cin >> cx >> cy;
        Comparator<char*> cc (cx, cy);//实参类型为char*//数组
        cout << "最小值:" << cc.min () << endl;
        cout << "最大值:" << cc.max () << endl;
        return 0;
    }
    
    #include <iostream>
    using namespace std;
    template<typename T>
    class A {
    public:
        class B {};
    };
    template<typename T>
    void foo (void) {
        typename A<T>::B b;//实例化A再定义一个类,再定义一个变量//没加typename就无法识别T//不能换成class//B为内部类
    }
    int main (void) {
        foo<int> ();
        return 0;
    }
    
  4. 局部特化

    //局部特化
    #include <iostream>
    using namespace std;
    template<typename T1, typename T2> //通用版本
    class A {
    public:
        A (void) {
            cout << "A<T1,T2>" << endl;
        }
    };
    template<typename T1> //局部特化
    class A<T1, int> { //T2特化为int
    public:
        A (void) {
            cout << "A<T1,int>" << endl;
        }
    };
    template<> //完全特化
    class A<int, int> {  //完全特化,全特化为int
    public:
        A (void) {
            cout << "A<int,int>" << endl;
        }
    };
    template<typename T> //通用特化//T=char*
    class B {
    public:
        B (void) {
            cout << "B<T>" << endl;
        }
    };
    template<typename T> //特化
    class B<T*> { //特化指针 //T=char
    public:
        B (void) {
            cout << "B<T*>" << endl;
        }
    };
    template<typename T>
    class B<T[10]> {//特化数组 //
    public:
        B (void) {
            cout << "B<T[10]>" << endl;
        }
    };
    template<typename T1, typename T2, typename T3>
    class C {
    public:
        C (void) {
            cout << "C<T1,T2,T3>" << endl;
        }
    };
    template<typename T1, typename T2>
    class C<T1, T2, T2> {//T3和T2的类型相同时用此特化
    public:
        C (void) {
            cout << "C<T1,T2,T2>" << endl;
        }
    };
    template<typename T1>
    class C<T1, T1*, T1*> { //T2和T3的类型相同并确为T1型指针
    public:
        C (void) {
            cout << "C<T1,T1*,T1*>" << endl;
        }
    };
    int main (void) {
        // 特化程度高的优先//依赖于特化程度
        A<double, double> a1;
        A<double, int> a2;
        A<int, int> a3;
        // 针对指针和数组的特化优先
        B<char> b1;
        B<char*> b2;
        B<char[10]> b3;
        // 匹配度高的特化优先
        C<char, short, long> c1;
        C<char, short, short> c2;
        C<char, char*, char*> c3;
        return 0;
    }
    
  5. 非类型参数和缺省参数

    1. 非类型参数的实参仅限于常量或者常量表达式。

    2. 无论类型参数还是非类型参数都可以带有缺省值,而且和函数的缺省参数一样,模板的缺省参数也必须靠右。

      #include <iostream>
      using namespace std;
      template<typename T = int, size_t S = 5> //S为非类型参数 //定义了缺省值//带缺省值必须同时都确定
      class Array {
      public:
          T& operator[] (size_t i) { 
              return m_array[i];
          }
          const T& operator[] (size_t i) const {
              return const_cast<Array&> (*this) [i];
          }
          size_t size (void) const {
              return S;
          }
          friend ostream& operator<< (ostream& os,const Array& arr) {
              for (size_t i = 0; i < arr.size (); ++i)
                  os << '(' << arr.m_array[i] << ')'; //打印
              return os;
          }
      private:
          T m_array[S]; //数组
      };
      int main (void) {
          const /*volatile挥发性*/ int x = 3, y = 7; //常量优化,用字面值取代变量
          Array<int, x+y> arr;
      //    Array<int ,10> arr;
          for (size_t i = 0; i < arr.size (); ++i)
              arr[i] = i;
          cout << arr << endl; //运算符重载
          Array<Array<int, 4>, 3> m; //二维数组3行4列
          for (size_t i = 0; i < m.size (); ++i)//行循环
              for (size_t j = 0; j < m[i].size (); ++j)//列循环
                  m[i][j] = i * m[i].size () + j;
          cout << m << endl;
          Array<double> a2;
          Array<> a3;//<>必须写
          return 0;
      }
      
  6. 有关模板的其它问题

    1. 从模板继承

      //从模版继承
      #include <iostream>
      using namespace std;
      template<typename T>
      class A {
      public:
          A (const T& t) : m_t (t) {}
          T m_t;
      };
      template<typename T, typename Y>
      class B : public A<T> {  //从A继承用T实例化A来继承
      public:
          B (const T& t, const Y& y) ://初始化基类、初始化自己
              A<T> (t), m_y (y) {}
          Y m_y;
      };
      int main (void) {
          B<int, string> b (100, "hello");
          cout << b.m_t << ' ' << b.m_y << endl;
          return 0;
      }
      
    2. 向模板派生

      //向模版派生//从不同基类继承
      #include <iostream>
      using namespace std;
      template<typename BASE>//参数化//BASE被<>的内容所取代
      class Shape : public BASE {
      public:
          void draw (void) const {
              BASE::draw ();//调用基类的draw//现形
          }
      };
      class Rect {
      public:
          void draw (void) const {
              cout << "绘制矩形..." << endl;
          }
      };
      class Circle {
      public:
          void draw (void) const {
              cout << "绘制圆形..." << endl;
          }
      };
      int main (void) {
          Shape<Rect> shape1;//Rect为基类
          shape1.draw ();
          Shape<Circle> shape2;//Circle为基类
          shape2.draw ();
          return 0;
      }
      
    3. 模板中模板成员

      1)模板型成员变量

      //模版中模版成员
      #include <iostream>
      using namespace std;
      template<typename T>
      class A {
      public:
          A (const T& t) : m_t (t) {}
          T m_t;
      };
      template<typename T, typename Y>
      class B {
      public:
          B (const T& t, const Y& y) :m_a (t), m_y (y) {}
          A<T> m_a;//与之对应
          Y m_y; //间接传递参数
      };
      int main (void) {
          B<int, string> b (100, "hello");
          cout << b.m_a.m_t << ' ' << b.m_y << endl;
          return 0;
      }
      

      2)模板型成员函数

      //模版里的模版函数
      #include <iostream>
      using namespace std;
      template<typename T>
      class A {
      public:
          A (const T& t) : m_t (t) {}
          /*
          template<typename Y> //模版里的模版函数
          void print (const Y& y) {
              cout << m_t << ' ' << y << endl;
          }
          */
          template<typename Y>
              void print (const Y& y);//定义
                  T m_t;
      };
      template<typename T>
          template<typename Y>//T和Y不再同一层
      void A<T>::print (const Y& y) {
          cout << m_t << ' ' << y << endl;
      }
      int main (void) {
          A<int> a (100);
          a.print<string> ("hello");
          return 0;
      }
      

      3)模板型成员类型

      //模版里的成员类
      #include <iostream>
      using namespace std;
      template<typename T, typename Y>
      class A {
      public:
          A (const T& t, const Y& y) :m_t (t), m_b (y) {}
          /*
          template<typename X>  //内部定义
          class B {
          public:
              B (const X& x) : m_x (x) {} //模版成员类型
              X m_x;
          };
          */
          template<typename X> class B;
          T m_t;
          B<Y> m_b;
      };
      template<typename T, typename Y> //外部定义
          template<typename X>
      class A<T, Y>::B {
      public:
          B (const X& x) : m_x (x) {}
          X m_x;
      };
      int main (void) {
          A<int, string> a (100, "hello");
          cout << a.m_t << ' ' << a.m_b.m_x << endl;
          return 0;
      }
      
    4. 模板型模板实参

      //模版型模版实参
      #include <iostream>
      using namespace std;
      template<typename T>
      class A {
      public:
          A (const T& t) : m_t (t) {}
          T m_t;
      };
      template<typename X, typename Z,template<typename T> class Y> //Y为模版
      class B {
      public:
          B (const X& i, const Z& s) : m_i (i), m_s (s) {}
          Y<X> m_i; //X为int
          Y<Z> m_s; //Z为string
      };
      int main (void) {
          B<int, string, A> b (100, "hello"); //与第10行一一配对
          cout << b.m_i.m_t << ' ' << b.m_s.m_t << endl;
          return 0;
      }
      
  7. 容器和迭代器

    //容器和迭代器(双向线性链表模版)
    #include <iostream>
    #include <stdexcept>
    #include <cstring>
    using namespace std;
    // 双向线性链表容器模板
    template<typename T> //T数据类型
    class List {
    public:
        // 构造、析构、拷贝构造、拷贝赋值 //必须深拷贝
        List (void) : m_head (NULL), m_tail (NULL) {}
        ~List (void) {
            clear ();
        }
        //拷贝构造
        List (const List& that) : m_head (NULL),m_tail (NULL) { //深拷贝
            for (Node* node = that.m_head; node;node = node->m_next) //拷贝元遍历
                push_back (node->m_data);//压入
        }
        //拷贝赋值
        List& operator= (const List& that) {
            if (&that != this) {
                List list (that);
                swap (m_head, list.m_head);
                swap (m_tail, list.m_tail);
            }
            return *this;
        }
        // 获取首元素
        T& front (void) { //左值
            if (empty ())
                throw underflow_error ("链表下溢!"); //标准异常
            return m_head->m_data;
        }
        const T& front (void) const { //右值
            return const_cast<List*> (this)->front (); //去常
        }
        // 向首部压入
        void push_front (const T& data) {
            m_head = new Node (data, NULL, m_head);//构建节点
            if (m_head->m_next) //有后节点
                m_head->m_next->m_prev = m_head;
            else //没后节点
                m_tail = m_head;
        }
        // 从首部弹出
        void pop_front (void) { //不用要返回值,front可以帮助实现
            if (empty ()) //非空
                throw underflow_error ("链表下溢!");
            Node* next = m_head->m_next; //备份后指针
            delete m_head;
            m_head = next;
            if (m_head)
                m_head->m_prev = NULL;//
            else  //最后一个节点
                m_tail = NULL;
        }
        // 获取尾元素
        T& back (void) {
            if (empty ())
                throw underflow_error ("链表下溢!");
            return m_tail->m_data;
        }
        const T& back (void) const {  //右值
            return const_cast<List*> (this)->back (); //去常,返回右值
        }
        // 向尾部压入
        void push_back (const T& data) {
            m_tail = new Node (data, m_tail);
            if (m_tail->m_prev)//有前节点
                m_tail->m_prev->m_next = m_tail;
            else//没前节点
                m_head = m_tail;
        }
        // 从尾部弹出
        void pop_back (void) {
            if (empty ())
                throw underflow_error ("链表下溢!");
            Node* prev = m_tail->m_prev;//备份
            delete m_tail;
            m_tail = prev;
            if (m_tail)
                m_tail->m_next = NULL;
            else
                m_head = NULL;
        }
        // 删除所有匹配元素
        void remove (const T& data) {//由值匹配,相同的全删除
            for (Node* node = m_head, *next; node;node = next) {
                next = node->m_next; //存放后节点的地址
                if (equal (node->m_data, data)) {//用函数调用
                    if (node->m_prev)//匹配
                        node->m_prev->m_next =node->m_next;
                    else
                        m_head = node->m_next;
                    if (node->m_next)
                        node->m_next->m_prev = node->m_prev;
                    else
                        m_tail = node->m_prev;
                    delete node;
                }
            }
        }
        // 清空
        void clear (void) {
            for (Node* next; m_head; m_head = next) {
                next = m_head->m_next;
                delete m_head;
            }
            m_tail = NULL;//最后一个置空
        }
        // 判空
        bool empty (void) const {
            return ! m_head && ! m_tail;
        }
        // 获取大小
        size_t size (void) const {
            size_t count = 0;
            for (Node* node = m_head; node;
                node = node->m_next)
                ++count;//计数
            return count;
        }
        // 重载插入输出流
        friend ostream& operator<< (ostream& os,const List& list) {
            for (Node* node = list.m_head; node;node = node->m_next)
                os << *node; //打印每一个
            return os;
        }
    private:
        // 节点
        class Node {
        public:
            Node (const T& data = 0, Node* prev = NULL,Node* next = NULL) : m_data (data),m_prev (prev), m_next (next) {}
            friend ostream& operator<< (ostream& os,const Node& node) { //运算符重载
                return os << '(' << node.m_data << ')';
            }
            T m_data; // 数据
            Node* m_prev; // 前指针
            Node* m_next; // 后指针
        };
        bool equal (const T& a, const T& b) const {
            return a == b;
        }
        Node* m_head; // 头指针
        Node* m_tail; // 尾指针
    public:
        // 正向迭代器(模拟指针的功能)
        class Iterator {
        public:
            Iterator (Node* head = NULL,Node* tail = NULL, Node* node = NULL) :m_head (head), m_tail (tail),m_node (node) {}
            bool operator== (const Iterator& it) const { //支持==
                return m_node == it.m_node;//两对像是否是一个
            }
            bool operator!= (const Iterator& it) const { //支持!=
                return ! (*this == it);
            }
            Iterator& operator++ (void) {//从一个跳到下一个元素//前++
                if (m_node)//非空
                    m_node = m_node->m_next; //下移
                else
                    m_node = m_head;//循环回来到头
                return *this;//返回子引用
            }
            const Iterator operator++ (int) {//后++
                Iterator old = *this;
                ++*this;//对自己前++
                return old;
            }
            Iterator& operator-- (void) { //前--
                if (m_node)
                    m_node = m_node->m_prev;
                else
                    m_node = m_tail;
                return *this;
            }
            const Iterator operator-- (int) {//后--
                Iterator old = *this;//备份
                --*this;//对前--
                return old;
            }
            T& operator* (void) const { //*
                return m_node->m_data;
            }
            T* operator-> (void) const {//->
                return &**this;
            }
        private:
            Node* m_head;//头
            Node* m_tail;//尾
            Node* m_node;//节点
            friend class List;//友元声明
        };
        Iterator begin (void) { //起始迭代器
            return Iterator (m_head, m_tail, m_head);
        }
        Iterator end (void) {//终止迭代器
            return Iterator (m_head, m_tail);
        }
        Iterator insert (Iterator loc, const T& data) {//插入
            if (loc == end ()) {//最后一个节点的下一个位置
                push_back (data);//追加压入
                   return Iterator (m_head, m_tail,m_tail);//返回新的数据
            }
            else {
                Node* node = new Node (data,loc.m_node->m_prev, loc.m_node);
                if (node->m_prev)//有前节点
                    node->m_prev->m_next = node;
                else
                    m_head = node;
                node->m_next->m_prev = node;
                return Iterator (m_head, m_tail, node);//返回指向node的迭代器
            }
        }
        Iterator erase (Iterator loc) {//删除
            if (loc == end ())//空指针
                throw invalid_argument ("无效迭代器!");
            if (loc.m_node->m_prev)//存在
                loc.m_node->m_prev->m_next =loc.m_node->m_next;
            else
                m_head = loc.m_node->m_next;
            if (loc.m_node->m_next)
                loc.m_node->m_next->m_prev = loc.m_node->m_prev;
            else
                m_tail = loc.m_node->m_prev;
            Node* next = loc.m_node->m_next;//备份
            delete loc.m_node;//删除
            return Iterator (m_head, m_tail, next);//返回迭代器
        }
    };
    // 针对const char*的特化
    template<>
    bool List<const char*>::equal (const char* const& a,const char* const& b) const {
        return strcmp (a, b) == 0;
    }
    // 测试用例
    int main (void) {
        try {
            List<int> list1;
            list1.push_front (20);
            list1.push_front (10);
            list1.push_back (30);
            list1.push_back (40);
            cout << list1 << endl; //10,20,30,40
            cout << list1.front () << ' ' << list1.back () << endl; //10,40
            list1.pop_front ();
            list1.pop_back ();
            cout << list1 << endl; //20,30
            ++list1.front (); //左值
            --list1.back ();
            cout << list1 << endl;//21,29
            list1.push_back (21);
            list1.push_back (25);
            list1.push_back (21);
            list1.push_back (21);
            cout << list1 << endl;//
            list1.remove (21);//
            cout << list1 << endl;//
            List<int> list2 = list1;//拷贝构造
            cout << list2 << endl;
            list2.back () = 100;
            cout << list2 << endl;
            cout << list1 << endl;
            list2 = list1;//赋值
            cout << list2 << endl;
            list2.front () = 100;
            cout << list2 << endl;
            cout << list1 << endl;
            cout << list1.size () << endl;
            list1.clear ();
            cout << list1 << endl;
            cout << boolalpha << list1.empty () << endl; //以值的形式显示
    //        List<string> list3;//字符串
            List<const char*> list3;
            list3.push_back ("beijing");
            list3.push_back ("tianjin");
            list3.push_front ("tianjin");
            list3.push_back ("shanghai");
            list3.push_back ("beijing");
            cout << list3 << endl;
            list3.remove (string ("beijing").c_str ());//变为C风格串再取C风格串
            cout << list3 << endl;
    //调用迭代器   // it 相当于节点指针
            for (List<const char*>::Iterator it =list3.begin (); it != list3.end ();++it)  //调用开始到结束
                cout << *it << ' ';
            cout << endl;
            List<const char*>::Iterator it =list3.begin ();//取起始迭代器
            it++;//下移
            it = list3.insert (it, "chongqing");//位置、内容
            cout << list3 << endl;
            list3.erase (it);//删除
            cout << list3 << endl;
        }
        catch (exception& ex) {
            cout << ex.what () << endl;
            return -1;
        }
        return 0;
    }
    

(二)、STL

  1. 标准模板库(STL)

    1. 定义了一系列的容器模板,实现泛型化的数据结构。

      1)向量(vector),内存连续,支持下标访问和随机迭代,只有在尾部进行插入和删除效率才比较高。

      2)列表(list),内存不连续,不支持下标访问和随机迭代,在任何位置进行插入和删除效率都很高。

      3)双端队列(deque),内存连续,支持下标访问和随机迭代,在首尾两端进行插入和删除效率都比较高。

      以上三种合称为线性容器。

      4)堆栈(stack),后进先出

      5)队列(queue),先进先出

      6)优先队列(priority_queue),优者先出

      以上三种合称为适配器容器,通过某种线性容器适配。

      7)映射(map),键值对(KVP)的集合,按键升序,键唯一。

      8)集合(set),没有值只有键的映射。

      9)多重映射(multimap),允许重复键的映射。

      10)多重集合(multiset),没有值只有键的多重映射。

      以上四种合称为关联容器。通过有序树表达数据的关联性。

    2. 泛型函数

      template<typename T>
      void swap (T& a, T& b) {
        T c = a;
        a = b;
        b = c;
      }
      template<typename IT>
      void print (IT begin, IT end) {
        while (begin != end)
          cout << *begin++ << ' ';
        cout << endl;
      }
      int a[5] = {1, 2, 3, 4, 5};
      print (a, a + 5);
      List list;
      list.push_back (...);
      ...
      print (list.begin (), list.end ());
      
      //打印//泛型函数 
      #include <iostream>
      //#include <algorithm>
      using namespace std;
      template<typename IT, typename DOIT>
      void for_each (IT begin, IT end, DOIT doit) {
          while (begin != end)
              doit (*begin++);
      }
      void print (int& x) {
          cout << x; 
          cout << endl;
      }
      void add (int& x) {
          ++x;
      }
      int main (void) {
          int a[5] = {1, 2, 3, 4, 5};
      //    char B[5] = {'a', 'b', 'c', 'd', 'e'};
      //    cout << "0结果:" << *(B + 2)<< endl;
      //    cout << "0结果:" << B[2] << endl;
      //    size_t size = sizeof(B)/sizeof(B[0]); //这种情况下并不是按指针计算
      //    size_t size = sizeof(a+1);
      //    size_t size1 = sizeof(a[0]+1);
      //    size_t size2 = sizeof(&a[0]);
      //    size_t size3 = sizeof(a);
      //    cout << "1结果:" << B << endl;
      //    cout << "2结果:" << B[0] << endl;
      //    cout << "大小" << size << endl;
      //    cout << "1大小" << size1 << endl;
      //    cout << "结果:" << a+1 << endl;
      //    cout << "结果:" << &(a[0]+1) << endl;
      
          for_each (a, a + 5, print);//每一个都会调用print
          for_each (a, a + 5, add);//处理
          for_each (a, a + 5, print);//打印
          return 0;
      }
      
    3. 实用工具

      auto_ptr

      string

      pair

  2. STL容器共性

    1. 所有的容器都支持拷贝构造和拷贝赋值,可以完整意义上的容器对象副本。

    2. 所有的容器都支持“==”运算符。容器的相等:容器的类型相同,容器中元素的类型相同,容器中元素的个数相等,对应元素还要满足相等性的判断。

    3. 容器中元素都是放入源对象拷贝。

      int b;

      int a[3];

      a[0] = b;

      a[0]++;

    4. 容器中元素需要支持完整的拷贝语义。auto_ptr不适合放在容器中使用。

    5. 如果需要对容器的元素进行排序或者查找操作,该元素的类型还需要支持“<”和“==”操作符。

  3. 向量(vector)

    1. 基本特点

      1)连续内存和下标访问

      2)动态内存管理

      int a[10];

      int *b = new int[10];

      3)通过预分配内存空间减小动态内存管理的额外开销

      4)可以再随机位置做插入和删除,但只有在接近尾部的操作才是高效的。

    2. 定义变量

      #include <vector>
      using namespace std;
      vector<int> vi;
      vector<string> vs;
      
    3. 迭代器

      vector<...>::iterator - 正向迭代器

      vector<...>::const_iterator - 常正向迭代器

      vector<...>::reverse_iterator - 反向迭代器

      vector<...>::const_reverse_iterator - 常反向迭代器

      向量的四种迭代器都是随机迭代器,可以和整数做加减运算。

      通过vector<...>调用,begin()返回起始迭代器,end()返回终止迭代器,最后一个元素的下一个位置。rbegin()返回起始反向迭代器,rend()返回终止反向迭代器。

      通过const vector\<...>&/*调用以上函数,返回的将是const_iterator/const_reverse_interator。

      //向量
      #include <iostream>
      #include <vector> //向量头文件
      using namespace std;
      class A {
      public:
          A (int i = 0) : m_i (i) {}; //无参必须通过零初始化
      //    A (int i) : m_i (i) {}; //无参必须通过零初始化
          int m_i;
      };
      void print (const vector<int>& vi) {//用引用传参//避免修改原始值
          size_t size = vi.size ();//求大小
              cout << size << endl;
          for (size_t i = 0; i < size; ++i)
              cout << vi[i] << ' ';
          cout << endl;
      }
      int main (void) {
          //定义变量
          vector<int> vi;
          vi.push_back (10);//后端压入
          vi.push_back (20);
          vi.push_back (30);
          vi.push_back (20);
          vi.push_back (10);
          print (vi);//
          vi.pop_back ();//后边弹出
          print (vi);
          ++vi.front ();//左值//返回的是引用
          vi.back () = 100;
          cout << vi.front () << ' ' << vi.back () << endl;
          //迭代器
          typedef vector<int>::iterator IT; //起个别名
          typedef vector<int>::const_iterator CIT;
          typedef vector<int>::reverse_iterator RIT;
          typedef vector<int>::const_reverse_iterator CRIT;
          for (IT it = vi.begin (); it != vi.end (); ++it) //正向迭代
              ++*it;//元素自增
          const vector<int>& cvi = vi;
          for (CIT it = cvi.begin (); it != cvi.end (); ++it)
              cout << /*--*/*it << ' ';//禁止修改(常属性)
          cout << endl;
          for (CRIT it = cvi.rbegin (); it!=cvi.rend(); ++it) //反向迭代(常)
              cout << *it << ' ';
          cout << endl;
          vector<string> vs;
          vs.push_back ("beijing");
          vs.push_back ("tianjin");
          vs.push_back ("shanghai");
          cout << *(vs.begin () + 2) << endl;//shanghai
          *const_cast<char*> ((vs.end () - 1)->c_str ())='S';//去常//修改
          cout << *(vs.end () - 1) << endl;//end指的是最后一个的下一个
          //预分配和初始化
          vector<int> vi2 (10); //无参方式
          print (vi2);
          //类类型对象的向量
          vector<A> va (10);
          for (vector<A>::const_iterator it = va.begin ();it != va.end (); ++it)//用到了迭代器
              cout << it->m_i << ' ';
          cout << endl;
          vector<int> vi3 (10, 8); //有参方式
          print (vi3);
          vector<A> va2 (10, A (8));
          for (vector<A>::const_iterator it = va2.begin ();
              it != va2.end (); ++it)
              cout << it->m_i << ' ';
          cout << endl;
          return 0;
      }
      
    4. 预分配和初始化

      vector\ vi (10);

      将vi初始化10个int元素,初始值为0。

      vector\<类> vc (10);

      将vi初始化10个类类型的元素,通过无参构造函数初始化。

      vector\ vi (10, 8);

      将vi初始化10个int元素,初始值为8。

      vector\<类> vc (10, 类 (...));

      将vi初始化10个类类型的元素,通过拷贝构造函数初始化。

    5. size()/resize()/clear()/capacity()/reserve()

      size() - 获取元素个数,而不是容量。

      resize() - 增减元素的个数,增引发构造,减引发析构。如果在新增元素时发现当前容量不够,自动扩容。但是在减少元素时不会自动收缩容量。

      clear() - 清空所有的元素,导致析构。同样不会自动收缩容量。

      capacity() - 获取容量,以元素为单位。

      reserve() - 手动扩容。新增部分不做初始化。

      #include <iostream>
      #include <vector>
      using namespace std;
      void print (const vector<int>& vi) {
          cout << "大小:" << vi.size () << endl;
          cout << "容量:" << vi.capacity () << endl;
          for (vector<int>::const_iterator it = vi.begin (); it != vi.end (); ++it) //迭代打印
              cout << *it << ' ';
          cout << endl;
      }
      int main (void) {
          vector<int> vi (5, 3);//用3初始化
          print (vi); //打印
          vi.push_back (4);//加一个
          print (vi);// 6个元素,10//容量翻一倍(预分配)
          vi[6] = 100;//放的100不被记录
          cout << vi[6] << endl;
          vi.push_back (5);//100将被冲走
          cout << vi[6] << endl;
          vi.resize (12);//修改元素个数为12(预分配容量大下至少为12)
          print (vi);//12,14
          vi.resize (2);
          print (vi);//2,14
          vi.clear ();//清除
          print (vi);//0,14
          vi.reserve (20);//预留20
          print (vi);
          cout << vi[19] << endl;//可以访问,因为内存已经分配给向量了
          vi.reserve (5);
          print (vi);
          return 0;
      }
      
    6. insert()/erase()/sort()/find()

      insert()/erase() - 根据迭代器参数做插入和删除。

      sort()/find() - 全局算法函数,排序(快速)和查找

      #include <algorithm>//泛型算法
      #include <vector>  //预分配和初始化
      #include "print.h" //打印函数
      template<typename iterator, typename type>//iterator迭代器
      //自己实现的find
      iterator find (iterator begin, iterator end,const type& key) { //
          for (; begin != end; ++begin)
              if (*begin == key)
                  break;
          return begin;
      }    
      //定义规则
      bool cmpInt (const int& a, const int& b) {//单独定义的函数
          return a > b; //由大到小
      }
      //用类定义规则
      class CmpInt {
      public:
          CmpInt (bool less = true) : m_less (less) {}
          bool operator() (const int& a, const int& b) const{
              return m_less ? (a < b) : (a > b);//判断
          }
      private:
          bool m_less;
      };
      //实现
      int main (void) {
          int ai[] = {10, 20, 30, 40, 50};
          vector<int> vi (ai, &ai[5]);//已有容器去构造
          print (vi.begin (), vi.end ());
          vector<int>::iterator it = vi.begin ();//迭代
          it = vi.insert (it + 1, 15);//20前插如//返回的为新插的元素
          print (vi.begin (), vi.end ()); //it以指向15
          ++++++it;
          it = vi.erase (it);//删除了40//返回的是被删除元素后面的元素
          print (vi.begin (), vi.end ());
          cout << *it << endl; // 50//因为40以被删除
          vi.insert (vi.begin (), 37);//前插37
          vi.insert (vi.begin () + 2, 43);
          vi.insert (vi.begin () + 4, 29);
          vi.push_back (18);
          vi.push_back (24);
          print (vi.begin (), vi.end ());
          sort (vi.begin (), vi.end ());//需要头文件algorithm  //  默认由小到大排序
          cout << "-----------1---------------" << endl;
          print (vi.begin (), vi.end ());
          sort (vi.begin (), vi.end (),/*cmpInt*/CmpInt (false));//end始终为最后一个元素的下个位置//3个参数
          print (vi.begin (), vi.end ());
          it = ::find (vi.begin (), vi.end (), 18);//范围//目标(元素)
      //    it = find (vi.begin (), vi.end (), 38);//范围//目标(元素)//用系统的find
          if (it == vi.end ())//到头了没找到//end为最后一个的下一个(但这是单向向量)
              cout << "没找到!" << endl;
          else
              cout << "找到了:" << *it << endl;
          return 0;
      }
      
    7. 类类型对象的向量

      1)无参构造

      2)拷贝构造

      3)拷贝赋值

      4)operator==:find

      5)operator</operator基本类型/比较器

      #include <vector>
      #include <algorithm>
      #include "print.h"
      class A {
      public:
          A (int i = 0) : m_i (i) {
              cout << "无参构造:" << this << endl;
          }
          A (const A& that) : m_i (that.m_i) {
              cout << "拷贝构造:" << &that << "->" << this << endl;
          }
          A& operator= (const A& that) {
              cout << "拷贝赋值:" << &that << "->" << this << endl;
              if (&that != this)
                  m_i = that.m_i;
              return *this;
          }
          ~A (void) {
              cout << "析构函数:" << this << endl;
          }
          operator int& (void) {//类型转换
              return m_i;
          }
          /*
          operator const int& (void) const {
              return static_cast<int&> ( //提供类型转换//
                  const_cast<A&> (*this));
          }
          */
          bool operator== (const A& that) const {//提供==运算符支持
              return m_i == that.m_i;
          }
          /*
          bool operator< (const A& that) const {
              return m_i < that.m_i;
          }
          */
          bool operator() (const A& a, const A& b) const {//提供<运算符支持
              return a.m_i < b.m_i;  //三参
          }
      private:
          int m_i;
      };
      int main (void) {
          cout << "---- 1 ----" << endl;
          vector<A> va (3); //头文件vector
          cout << "---- 2 ----" << endl;
          va.push_back (A ());//内存转移
          cout << "---- 3 ----" << endl;
          va.erase (va.begin ());//拷贝赋值
          cout << "---- 0 ----" << endl;
          va[0] = A (10);
          va[1] = A (50);
          va[2] = A (70);
          va.push_back (A (60));
          vector<A>::iterator it = find (va.begin (),va.end (), A (70));//查找//必须提供==运算符
          if (it == va.end ())
              cout << "没找到!" << endl;
          else
              cout << "找到了:" << *it << endl;
      //    sort (va.begin (), va.end ());//必须提供<运算符支持
          sort (va.begin (), va.end (), va[0]);//必须提供<运算符支持
          print (va.begin (), va.end ());
          return 0;
      }
      

      练习:编写程序读取m.dat中的电影票房记录,找出票房前十名,按票房从高到低的顺序写入另一文件中。

      m.dat

      《2012》                                索尼                $769.7
      《哈利波特与死亡圣器(上)》              华纳兄弟            $952.0
      《星球大战》                            二十世纪福克斯      $775.4
      《怪物史莱克4》                         派拉蒙/梦工厂       $750.0
      《阿凡达》                              二十世纪福克斯      $2,782.2
      《哈利波特与火焰杯》                    华纳兄弟            $895.9
      《哈利波特与混血王子》                  华纳兄弟            $934.0
      《指环王2:双塔奇兵》                   新线                $925.3
      《蝙蝠侠前传2:黑暗骑士》               华纳兄弟            $1,001.9
      《哈利波特与魔法石》                    华纳兄弟            $974.7
      《海底总动员》                          迪士尼              $867.9
      《功夫熊猫》                            派拉蒙/梦工厂       $631.7
      《加勒比海盗3:世界的尽头》             迪士尼              $961.0
      《哈利波特与阿兹卡班的囚徒》            华纳兄弟            $795.6
      《E.T.》                                环球                $792.9
      《夺宝奇兵4:水晶骷髅王国》             派拉蒙              $786.6
      《指环王3:王者归来》                   新线                $1,119.1
      《怪物史莱克2》                         梦工厂              $919.8
      《玩具总动员3》                         迪士尼              $1,063.2
      《黑客帝国2:重装上阵》                 华纳兄弟            $742.1
      《飞屋环游记》                          迪士尼              $731.3
      《盗梦空间》                            华纳兄弟            $824.8
      《蜘蛛侠1》                             索尼                $821.7
      《独立日》                              二十世纪福克斯      $817.4
      《暮光之城2:新月》                     Sum.                $709.8
      《变形金刚》                            派拉蒙/梦工厂       $709.7
      《暮光之城3:月食》                     Sum.                $698.5
      《爱丽丝漫游仙境》                      迪士尼              $1,024.3
      《阿甘正传》                            派拉蒙              $677.4
      《灵异第六感》                          迪士尼              $672.8
      《星战前传3:西斯的复仇》               二十世纪福克斯      $848.8
      《蜘蛛侠3》                             索尼                $890.9
      《达芬奇密码》                          索尼                $758.2
      《哈利波特与凤凰社                      华z纳兄弟           $938.2
      《变形金刚2:堕落者的复仇》             派拉蒙/梦工厂       $836.3
      《狮子王》                              迪士尼              $783.8
      《蜘蛛侠2》                             索尼                $783.8
      《泰坦尼克号》                          派拉蒙              $1,843.2
      《怪物史莱克3》                         派拉蒙/梦工厂       $799.0
      《冰河世纪2:消融》                     二十世纪福克斯      $655.4
      《加勒比海盗1:黑珍珠号的诅咒》         迪士尼              $654.3
      《星战前传2:克隆人的进攻》             二十世纪福克斯      $649.4
      《哈利波特与密室》                      华纳兄弟            $878.6
      《加勒比海盗2:亡灵宝藏》               迪士尼              $1,066.2
      《侏罗纪公园》                          环球                $914.7
      《冰河世纪3:恐龙的黎明》               二十世纪福克斯      $886.7
      《星球大战前传1:魅影危机》             二十世纪福克斯      $924.3
      《指环王1:护戒使者》                   新线                $870.8
      《超人总动员》                          迪士尼              $631.4
      《纳尼亚传奇》                          迪士尼              $745.0
      

      t.dat

      《阿凡达》 二十世纪福克斯 $2,782.2
      《泰坦尼克号》 派拉蒙 $1,843.2
      《指环王3:王者归来》 新线 $1,119.1
      《加勒比海盗2:亡灵宝藏》 迪士尼 $1,066.2
      《玩具总动员3》 迪士尼 $1,063.2
      《爱丽丝漫游仙境》 迪士尼 $1,024.3
      《蝙蝠侠前传2:黑暗骑士》 华纳兄弟 $1,001.9
      《哈利波特与魔法石》 华纳兄弟 $974.7
      《加勒比海盗3:世界的尽头》 迪士尼 $961.0
      《哈利波特与死亡圣器(上)》 华纳兄弟 $952.0
      

      top.cpp

      //票房读取排序写入系统
      #include <iostream>
      #include <fstream>
      #include <vector>
      #include <algorithm>
      using namespace std;
      class Movie {
      public:
          friend istream& operator>> (istream& is,Movie& movie) { //读取一行
              return is >> movie.m_title >> movie.m_comp >> movie.m_gross;
          }
          friend ostream& operator<< (ostream& os,const Movie& movie) {//写一行
              return os << movie.m_title << ' ' << movie.m_comp << ' ' << movie.m_gross;
          }
          bool operator< (const Movie& movie) const {
              return gross () > movie.gross (); //比较排序
          }
      private:
          double gross (void) const {
              string str (m_gross);
              size_t pos = 0;
              while ((pos = str.find_first_of ("$,", pos)) != string::npos) //查找过滤$和,从pos开始找//返回索引
                  str.erase (pos, 1);//删除
              return atof (str.c_str ());//字符串改为浮点数
          }
          string m_title;//电影名
          string m_comp; //公司
          string m_gross;//票房
      };
      bool read (const char* file, vector<Movie>& vm) {
          ifstream ifs (file);
          if (! ifs) {
              perror ("打开票房文件失败");
              return false;
          }
          Movie movie;
          while (ifs >> movie) //读一行
              vm.push_back (movie);
          ifs.close ();//关闭
          return true;
      }
      bool write (const char* file, const vector<Movie>& vm){
          ofstream ofs (file);
          if (! ofs) {
              perror ("打开排行文件失败");
              return false;
          }
          for (vector<Movie>::const_iterator it = vm.begin();it != vm.end (); ++it)//迭代 //it为movie
              ofs << *it << endl;
          ofs.close ();
          return true;
      }
      int main (int argc, char* argv[]) {
          if (argc < 3) {//检验参数的个数,包括执行文件(./a.out)
              cerr << "用法:" << argv[0] << " <票房文件> <排行文件>" << endl;
              return -1;
          }
          vector<Movie> vm;
          if (! read (argv[1], vm))
              return -1;
          sort (vm.begin (), vm.end ());
          if (vm.size () > 10)//前十个
              vm.resize (10);
          if (! write (argv[2], vm))
              return -1;
          return 0;
      }
      
  4. 双端队列(deque)

    1. 连续内存,下标访问和随机迭代,在首尾两端都可以进行高效的增删。

    2. 因为要维护首尾两端的开放性,因此双端队列和向量相比,其空间和时间复杂度要略高一些。

    3. 比vector多了push_front/pop_front,少了reserve。

      //双向队列
      #include <deque>
      #include <algorithm>
      #include "print.h"
      int main (void) {
          deque<int> di;
          di.push_back (24);//后端压入
          di.push_back (33);
          di.push_front (18);//前段压入
          di.push_front (68);
          di.insert (di.begin () + 2, 47);//插入
          print (di.begin (), di.end ()); //获得起始和终点迭代器 68 18 47 24 33
          di.pop_back ();
          di.pop_front ();
          di.erase (di.begin () + 1);//删除
          print (di.begin (), di.end ()); // 18 24
          di.push_back (20);
          sort (di.begin (), di.end ());//排序
          print (di.begin (), di.end ()); // 18 20 24
          size_t size = di.size ();//获取大小
          for (size_t i = 0; i < size; ++i)
              cout << di[i] << ' ';//支持下标访问
          cout << endl;
          di.resize (10);//永远在后边增加
          print (di.begin (), di.end ());
          return 0;
      }
      
  5. 列表(list)

    front/back
    push_front/pop_front
    push_back/pop_back
    insert/erase/remove
    size
    

    listprint.h

    #ifndef _PRINT_H
    #define _PRINT_H
    #include <iostream>
    using namespace std;
    template<typename iterator> //模版/迭代
    void print (iterator begin, iterator end) {
        while (begin != end)
            cout << *begin++ << ' ';
        cout << endl;
    }
    #endif // _PRINT_H
    

    list.cpp

    //列表
    #include <list>
    #include "listprint.h"
    int main (void) {
        list<int> li; //模版已在.h文件中声明
        li.push_back (34);
        li.push_back (28);
        li.push_back (34);
        li.push_back (34);
        li.push_back (55);
        li.push_back (34);
        print (li.begin (), li.end ());
        li.unique ();//修改//唯一化
        print (li.begin (), li.end ());
        li.sort ();//成员函数的sort//排序
        print (li.begin (), li.end ());
        li.unique ();
        print (li.begin (), li.end ());
        //splice功能实现
        list<int> li2;
        li2.push_front (100);
        li2.push_front (200);
        li2.push_front (300);
        list<int>::iterator pos = li.begin ();//迭代
        ++pos;//下个元素
    //    li.splice (pos, li2);//把整体剪切到pos处
        list<int>::iterator start = li2.begin ();
        ++start;
    //    li.splice (pos, li2, start);//切特指的
        list<int>::iterator end = li2.end ();
        li.splice (pos, li2, start, end);//剪切特定区间的
        print (li.begin (), li.end ());
        cout << li2.size () << endl;
        return 0;
    }
    
    1. sort

    2. unique - 将连续出现的相同元素唯一化。

      23 35 35 35 60 12 35 35 99 35 22

      |unique

      V

      23 35 60 12 35 99 35 22

    3. splice - 将参数链表的部分或全部剪切到调用链表的特定位置。

      void splice (

      iterator pos,

      list& lst);

      list1.splice (pos, list2);

      将list2中的全部数据剪切到list1的pos处。

      void splice (

      iterator pos,

      list &lst,

      iterator del);

      将list2中del所指向数据剪切到list1的pos处。

      void splice (

      iterator pos,

      list& lst,

      iterator start,

      iterator end );

      将list2中start和end之间的数据剪切到list1的pos处。

    4. merge - 合并

      void merge (list& lst);

      void merge (list& lst, Comp compfunction);

      将有序的参数列表合并到调用列表中,保证合并后的调用列表依然有序。

      注意:任何容器,在结构性修改之前获得的迭代器,有可能因为这种修改而失效,或者不能标识正确的位置,需要重新初始化。

      //合并merge
      #include <list>//列表
      #include "../day12/print.h"//链接文件
      int main (void) {
          int ai1[] = {13, 45, 67, 88, 92, 107};
          int ai2[] = {22, 23, 37, 50, 69, 100, 109};
          list<int> li1 (ai1, ai1 + 6); //整体压入
          list<int> li2 (ai2, ai2 + 7);
          print (li1.begin (), li1.end ());
          print (li2.begin (), li2.end ());
          li1.merge (li2);//合并后li2就没了,把指针都串到li1中去了
          print (li1.begin (), li1.end ());
          print (li2.begin (), li2.end ());
          list<int>::iterator it = li1.begin ();//获得起始迭代器
          li1.insert (it, 1000);//it仍指向13
          it = li1.begin ();//回到起始位置
          li1.insert (it, 2000);
          print (li1.begin (), li1.end ());
          return 0;
      }
      
  6. 堆栈

    stack  底层容器vector/deque/list
    push   push_back
    pop    pop_back
    top    back
    size   size
    empty  empty
    ...    ...
    #include <stack>
    stack<int, vector<int> > si;
    stack<string, list<string> > ss;
    stack<double> sd; // 缺省底层容器deque
    template<typename T, typename C>
    stack {
    public:
      void push (const T& data) {
        m_container.push_back (data);
      }
      void pop (void) {
        m_conainer.pop_back ();
      }
      T& top (void) {
        return m_container.back ();
      }
    private:
      C m_container;
    };
    
    //堆栈
    #include <iostream>
    #include <stack>
    #include <vector>
    using namespace std;
    int main (void) {
        stack<string, vector<string> > ss;//堆栈 //>空格>
        ss.push ("吃饭");//放入字符串
        ss.push ("喜欢");
        ss.push ("偶");
        while (! ss.empty ()) {
            cout << ss.top ();//先得弹出然后在去pop
            ss.pop ();//不返回(没有返回值)只弹出
        }
        cout << endl;
        return 0;
    }
    
  7. 队列

    queue   底层容器deque/list
    push    push_back
    pop     pop_front
    front   front
    back    back
    size    size
    empty   empty
    ...
    queue<int, list<int> > qi;
    queue<string> qs; // 缺省底层容器deque
    
    //队列
    #include <iostream>
    #include <queue>
    #include <list>
    using namespace std;
    int main (void) {
        queue<string, list<string> > qs;//队列
        qs.push ("我");//汉字必须为字符串格式,不能用char表示
        qs.push ("要");
        qs.push ("吃");
        qs.push ("饭");
        while (! qs.empty ()) {
            cout << qs.front ();
            qs.pop ();//弹出不返回
        }
        cout << endl;
        return 0;
    }
    
  8. 优先队列(priority_queue)

    优者先出

    底层容器:vector/deque/list,缺省deque

    通过类型实参以比较器的形式定义比较规则

    //优先队列
    #include <iostream>
    #include <queue>//用队列的头文件
    using namespace std;
    class Student {
    public:
        Student (const string& name, float score) :m_name (name), m_score (score) {}
        void print (void) const {
            cout << m_name << "," << m_score << endl;
        }
        bool operator< (const Student& student) const { //对<运算符提供支持
            return m_score > student.m_score; //实际这里的>号控制着顺序
        }
    private:
        string m_name;//名字
        float m_score;//分数
    };
    class CmpInt {
    public:
        bool operator() (int a, int b) {//自己定义
            return a > b;
        }
    };
    int main (void) {
    //    priority_queue<int> pqi;//默认规则//由大到小
        priority_queue<int, deque<int>, CmpInt> pqi;//优先队列//自己定义规则//比较器//第二个参数不能少
        pqi.push (23);
        pqi.push (12);
        pqi.push (23);
        pqi.push (27);
        pqi.push (19);
        while (! pqi.empty ()) {
            cout << pqi.top () << ' ';//用top取出
            pqi.pop ();
        }
        cout << endl;
        priority_queue<Student> pqs;//对类
        pqs.push (Student ("张飞", 65));
        pqs.push (Student ("关羽", 60));
        pqs.push (Student ("赵云", 85));
        pqs.push (Student ("刘备", 95));
        pqs.push (Student ("曹操", 25));
        while (! pqs.empty ()) {
            pqs.top ().print ();//打印
            pqs.pop ();
        }
        return 0;
    }
    
  9. 映射(map)

    1. key-value对的容器,通过pair表示key-value对。

      template<typename FIRST, typename SECOND>
      class pair {
      prublic:
        ...
        FIRST first;
        SECOND second;
      };
      
      //映射
      #include <iostream>
      #include <map>
      using namespace std;
      class Candidate {
      public:
          Candidate (const char* name = "") :m_name (name), m_votes (0) {}
          const string& name (void) const {//返回
              return m_name;
          }
          size_t votes (void) const { //返回
              return m_votes;
          }
          void vote (void) {//投票
              ++m_votes;
          }
      private:
          string m_name; //人名
          size_t m_votes; //票数
      };
      int main (void) {
          map<char, Candidate> mc;  //key、值 //自动按key升序
          mc.insert (make_pair ('B', "赵云"));//二叉树//无需指定位置//造一个pair(工厂函数)//第一种
          mc.insert (pair<char, Candidate> ('A', "张飞"));//对应对象//构造pair//第二种
          mc['D'] = "刘备";//支持下标运算符//第三种
          mc['E'] = "曹操";
          mc['C'] = "关羽";
          mc['D'] = "黄忠";//只能放一个(key不能重复),把原来的取代//下标可被覆盖
          mc.insert (pair<char, Candidate> ('A', "马超"));//不覆盖//直接忽略
          typedef map<char, Candidate>::iterator IT;//定义别名
          typedef map<char, Candidate>::const_iterator CIT;
          for (size_t i = 0; i < 10; ++i) {//投票
              for (CIT it=mc.begin (); it != mc.end (); ++it) //迭代
                  cout << '(' << it->first << ')' << it->second.name () << ' ';//打印信息//it指向pair//打印key、人名
              cout << endl << "请投下宝贵的一票:" << flush;
              char key;
              cin >> key;//接收
              IT it = mc.find (key);//查找//若未找到自动调用终止迭代器
              if (it == mc.end ()) {
                  cout << "此票作废!" << endl;
                  continue;
              }
              it->second.vote ();//投票成功//++一次
          }
          CIT win = mc.begin ();//初始化
          for (CIT it = mc.begin (); it != mc.end (); ++it){//遍历
              cout << it->second.name () << "获得" << it->second.votes () << "票。" << endl;//打印
              if (it->second.votes () > win->second.votes ())//比较找最多的
                  win = it;
          }
          cout << "恭喜" << win->second.name () << "同学当选"
              "为首席保洁员!" << endl;
          return 0;
      }
      
    2. key唯一且升序。

    3. 支持下标运算符,可以用[key]访问value。

    4. 可以通过比较器类型自定义key升序的规则。

      统计一个文本文件中每个单词出现的频率。按照词汇表的顺序打印输出。

      apple : 2

      beijing : 2

      c++ : 3

      ...

      //扫描排序
      #include <iostream>
      #include <fstream>
      #include <map>
      #include <cstring>
      using namespace std;
      class CmpStr {
      public:
          bool operator() (const string& a, const string& b) const {
              return strcasecmp (a.c_str (), b.c_str ()) < 0;//不区分大小写比较//取c风格字符串
          }
      };
      class A {
      public:
          A (int i) : m_i (i) {}
          bool operator< (const A& a) const {  //提供<运算符的支持
              return m_i < a.m_i;
          }
          int m_i;
      };
      int main (int argc, char* argv[]) {//程序  数组
          if (argc < 2) {//程序名//文件名
              cerr << "用法:" << argv[0] << " <文件>"<<endl;
              return -1;
          }
          ifstream ifs (argv[1]);//扫描读取
          if (! ifs) {
              perror ("打开文件失败");
              return -1;
          }
          map<string, int, CmpStr> msi;//定义映射//单词、数字、比较器
          string word;
          while (ifs >> word)//把单词放word里
              ++msi[word];//替换//++
          ifs.close (); //关闭文件
          for (map<string, int>::iterator it = msi.begin (); it != msi.end (); ++it) //迭代器//打印
              cout << it->first << " : " << it->second<<endl;
          map<A, int> mai;//自身必须支持<运算符
          mai[A (100)] = 1000;
          mai[A (500)] = 5000;
          mai[A (300)] = 3000;
          mai[A (400)] = 4000;
          mai[A (200)] = 2000;
          map<A, int>::iterator it = mai.find (A (400)); 
          //查找//返回迭代器//但不需要提供支持==运算符(这是一颗有序树通过两个<来比较故不需要==运算符)(a !< b && b !< a 所以 a==b)
          cout << it->second << endl;
          return 0;
      }
      
  10. 集合

    //集合
    #include <iostream>
    #include <set>
    #include <fstream>
    using namespace std;
    int main (void) {
        ifstream ifs ("test.txt");
        set<string> ss;//集合
        string word;
        while (ifs >> word)//一个个单词往word里面放,自动判断空格
            ss.insert (word);//重复就插不进去
        ifs.close ();//关闭
        for (set<string>::iterator it = ss.begin (); it != ss.end (); ++it)
            cout << *it << endl;
        cout << "共" << ss.size () << "个不同单词。" << endl;
        return 0;
    }
    
  11. 多重映射

    key可重复,升序,迭代时key相同的元素相邻。

    upper_bound(key)成员函数返回和参数key相匹配的所有记录中最后一条记录的下一条记录的迭代器。

    //多重映射
    #include <iostream>
    #include <map>
    using namespace std;
    int main (void) {
        multimap<string, int> msi;//多重映射//名字为key
        msi.insert (make_pair ("张飞", 100000));
        msi.insert (make_pair ("赵云", 200000));
        msi.insert (make_pair ("张飞", 300000));
        msi.insert (make_pair ("关羽", 400000));
        msi.insert (make_pair ("赵云", 500000));
        msi.insert (make_pair ("关羽", 600000));
        typedef multimap<string, int>::const_iterator CIT; //迭代//换名
        for (CIT it = msi.begin (); it != msi.end ();++it)
            cout << it->first << " : " << it->second<<endl;
        cout << "-------------" << endl;
        for (CIT it = msi.begin (); it != msi.end();++it){ //遍历
            string key = it->first; //拿出key
            CIT end = msi.upper_bound (key); //上界upper_bound返回的是与key匹配的最后一条的下一条的迭代器
            int sum = 0;
            for (; it != end; ++it)//一直到key处都是重复的,进行累加
                sum += it->second;
            cout << key << " : " << sum << endl;
            --it;//抵消一次17行for的++//也同时防止了越界
        }
        return 0;
    }
    
  12. 多重集合

    //多重集合
    #include <iostream>
    #include <set>
    using namespace std;
    int main (void) {
        const char* candidates[] = {"张飞", "赵云", "关羽", "刘备", "曹操", NULL};
        multiset<string> ms;//多重集合
        for (size_t i = 0; i < 10; ++i) {
            for (size_t i = 0; candidates[i]; ++i)
                cout << '(' << char ('A' + i) << ')' << candidates[i] << ' ';//A B C D E
            cout << endl << "请投下您庄严的一票:" <<flush;
            char key;
            cin >> key;
            if (key < 'A' || 'E' < key) {
                cout << "此票作废!" << endl;
                continue;
            }
            ms.insert (candidates[key-'A']);//投票//多重集合,可重复
        }
        multiset<string>::iterator win = ms.begin ();  //定义迭代器
        for (multiset<string>::iterator it = ms.begin ();it != ms.end (); ++it) { //
            cout << *it << "获得" << ms.count (*it) //count自动统计获得票数(重复的次数)
                << "票。" << endl;
            if (ms.count (*it) > ms.count (*win)) //获取最大的
                win = it;
            it = ms.upper_bound (*it); //
            --it;//抵消一次for里面的++//没有这行将是死循环(因为it在if中就可能移动从而自增)
        }
        cout << "热烈祝贺" << *win << "当选垃圾长!" << endl;
        return 0;
    }
    
  13. 泛型算法

    1. STL中包含60种泛型算法,其中包含23种非修改算法,如find,37种修改算法,如sort。

      print.h

      #ifndef _PRINT_H
      #define _PRINT_H
      #include <iostream>
      using namespace std;
      template<typename iterator> //模版/迭代
      void print (iterator begin, iterator end) {
          while (begin != end)
              cout << *begin++ << ' ';
          cout << endl;
      }
      #endif // _PRINT_H
      

      sort.h

      //泛型快速排序
      #include <vector>
      #include <list>
      #include "print.h"
      template<typename type>
      void my_swap (type& a, type& b) { //交换
          type c = a;
          a = b;
          b = c;
      }
      template<typename iterator>
      void my_sort (iterator begin, iterator end) {//快速排序
          iterator p = begin; //拿第一个作为基准值
          iterator last = end; //有边界//不一定支持-所以不能直接-1
          --last;//-1//?应该是:表示最后一个的前一个(p为头左边没有了只能从右边开始)
          for (iterator i = begin, j = last; i != j;) {//只能写!=
              while (! (i == p || *p < *i))
                  ++i;//右移
              if (i != p) {
                  my_swap (*p, *i);//交换代替覆盖
                  p = i;//p放到i处
              }
              while (! (j == p || *j < *p))
                  --j;
              if (j != p) {
                  my_swap (*p, *j);
                  p = j;//p挪到j处
              }
          }
          iterator it = begin;//定义个迭代器
          ++it;//挪到下个位置
          if (p != begin && p != it)//p左边至少两个
              my_sort (begin, p);//p前面的后面的那个还是p
          it = p;
          ++it;
          if (it != end && it != last)//it右边至少两个
              my_sort (it, end);
      }
      //三参sort//提供比较器
      template<typename iterator, typename comparator>
      void my_sort (iterator begin, iterator end, comparator cmp) {
          iterator p = begin;
          iterator last = end;
          --last;
          for (iterator i = begin, j = last; i != j;) {
              while (! (i == p || cmp (*p, *i)))//调用比较器
                  ++i;
              if (i != p) {
                  my_swap (*p, *i);
                  p = i;
              }
              while (! (j == p || cmp (*j, *p)))//调用比较器
                  --j;
              if (j != p) {
                  my_swap (*p, *j);
                  p = j;
              }
          }
          iterator it = begin;
          ++it;
          if (p != begin && p != it)
              my_sort (begin, p, cmp);
          it = p;
          ++it;
          if (it != end && it != last)
              my_sort (it, end, cmp);
      }
      class CmpInt {//定义比较器
      public:
          bool operator() (int a, int b) const {
              return a > b; //降序
          }
      };
      int main (void) {
          int na[] = {13, 24, 22, 19, 44, 56, 88, 22}; //数组
          vector<int> vi (na, na + 8);//向量
          list<int> li (na, na + 8);//列表
          my_sort (na, na + 8); //自己定义的快速排序
          print (na, na + 8);
          my_sort (vi.begin (), vi.end ());
          print (vi.begin (), vi.end ());
          my_sort (li.begin (), li.end (), CmpInt ());
          print (li.begin (), li.end ());
          return 0;
      }
      
    2. STL中的泛型算法多数都会迭代器实现对容器元素的访问。

    3. STL中的泛型算法凡是涉及到比较大小的算法,都支持两种比较方案——“<”运算符和比较器函数对象。

    4. 除了STL中的容器以外,程序员也可以使自定义的容器,获得STL泛型算法的支持,只要改自定义类型能够支持此算法对迭代器的使用规则即可。

    5. 练习:实现一个泛型的拷贝函数,用将一个容器中数据拷贝到另一个容器中。

      ​ POP->OOP->DP

      //面向对象C++风格 OOP //计算器 
      #include <iostream>
      using namespace std;
      class Calculator {
      public:
          Calculator (char op) : m_op (op) {}
          double calculate (double x, double y) {
              switch (m_op) {
                  case '+':
                      return x + y;
                  case '-':
                      return x - y;
                  case '*':
                      return x * y;
                  case '/':
                      return x / y;
                  default:
                      throw "无效运算符号!";
              }
          }
      private:
          char m_op;
      };
      int main (void) {
          cout << "左操作数:" << flush;
          double x;
          cin >> x;
          cout << "右操作数:" << flush;
          double y;
          cin >> y;
          cout << "运算符号:" << flush;
          char op;
          cin >> op;
          cout << "运算结果:" << Calculator (op).calculate (x, y) << endl;
          return 0;
      }
      
      //面向过程C风格 POP //计算器 
      #include <iostream>
      using namespace std;
      int main (void) {
          cout << "左操作数:" << flush;
          double x;
          cin >> x;
          cout << "右操作数:" << flush;
          double y;
          cin >> y;
          cout << "运算符号:" << flush;
          char op;
          cin >> op;
          double z;
          switch (op) {
              case '+':
                  z = x + y;
                  break;
              case '-':
                  z = x - y;
                  break;
              case '*':
                  z = x * y;
                  break;
              case '/':
                  z = x / y;
                  break;
              default:
                  cout << "无效运算符号!" << endl;
                  return -1;
          }
          cout << "运算结果:" << z << endl;
          return 0;
      }
      

打赏

微信支付 支付宝支付

License

本作品由Simonhttp://www.uusystem.com)创作,采用知识共享署名-非商业性使用-禁止演绎 2.5 中国大陆许可协议进行许可。 欢迎转载,但任何转载必须保留完整文章,在显要地方显示此声明以及原文链接。如您有任何疑问或者授权方面的协商,请邮件:postmaster@uusystem.com。

results matching ""

    No results matching ""