【学习总结】C++八股文（应该会持续更新，嗯 ）

跑路吧，做游戏没有前途的，hhhh

C++基础面向对象编程部分

类部分

1. 面向对象的三大特性：封装、继承、多态
   封装：即隐藏对象的属性和实现细节，仅对外公开接口，控制在程序中属性的读和修改的访问级别
   继承：子类继承父类的特征和行为，使得子类对象（实例）具有父类的属性和方法，或子类从父类继承方法，使得子类具有父类相同的行为
   多态：指相同的消息给予不同的对象会引发不同的动作

2. 类的访问权限：private、protected、public
   private：被private限定符修饰的成员变量只能被该类的方法和友元函数访问，子类函数无法访问，在这三个限定符中封装程度是最高的，一般来说，应该尽可能将类的成员变量声明为private而不是其他，减少成员变量的暴露，只提供getter和settter方法给外界访问，这样能提高类的安全性
   protected：protected限定符修饰的成员变量和成员函数可以被该类的成员函数访问，但是不能被类对象所访问，即不能通过类对象的成员运算符来访问。另外，这些成员可以被子类的函数和友元函数访问，相比public成员 少了一个可以使用类对象直接访问的特性
   public：被public限定符所修饰的成员变量和函数可以被类的函数、子类的函数、友元函数，也可以由类的对象来访问，即可以使用成员运算符来访问。这里的友元函数，可以是该类的友元函数，也可以是该类的友元类的成员函数

3. 构造和析构关系
   构造过程为：父类先构造然后子类构造，如果有多个父类，则按照声明顺序
   析构过程为：子类先析构，最后父类再析构

4. 深拷贝与浅拷贝的区别
   这个区别一般发生在类中有成员变量为指针的时候
   深拷贝：就是将指针所指的整块内存区域都拷贝的行为
   浅拷贝：只拷贝指针的笨比行为（其实在移动语义下还是有用的）

5. 空类有哪些函数？空类的大小？
   空类有的函数就是默认的那六个函数：缺省构造函数、缺省拷贝构造函数、缺省析构函数、缺省赋值运算符、缺省取址运算符、缺省取址运算符 const
   空类的大小会被设置为1，因为空类也有可能被实例化，而实例化的对象是要具有唯一内存地址的。因此空类的大小会被设置为1才能保证实例化的时候拥有唯一的内存地址

6. 类的移动语义函数
   一般来说主要有移动构造函数和移动拷贝函数。原理其实就是与浅拷贝类似，不重新开辟内存空间拷贝对象的数据，而是直接获得临时对象的内存，省去对临时对象的拷贝然后再赋值这么一个耗时耗力的步骤。可以有效提升性能。但是要注意，使用移动语义需要将原本指向这一块内存的指针置为空，否则很容易造成内存泄露

7. 虚函数相关（必考点）
   只要类里面有虚函数，那么在该类实例化对象的内存布局上，就会在最开头加上一个虚指针（大小为系统位数，32为4字节，64为8字节）。虚指针会指向一个虚表（存放在全局存储区，因为一个类的所有对象共享一个），然后该表里的指针又会指向不同的虚函数地址。
   子类重写的虚函数会重新开辟一片内存，并且更改虚表中的指针，令其指向更改过后的函数地址，该函数绑定方式也被叫做动态绑定
   虚函数是支持多态最重要的部分，比如下面这个例子：
   

8. 类的内存对齐
   内存对齐是为了提高内存的访问效率而存在的东西。比如intel 32位cpu，每个总线周期都是从偶地址开始读取32位的内存数据，如果数据存放地址不是从偶数开始，则可能出现需要两个总线周期才能读取到想要的数据，因此需要在内存中存放数据时进行对齐
   内存对齐是一个比较简单的规则（相关例题很多，这里就请自行搜索了）：
   

9. 重载、重写与隐藏
   重载：是指同一可访问区内被声明的具有不同参数列的同名函数，不关注返回类型
   重写：是指在派生类中存在重新定义的函数（函数名，参数列表，返回值类型都必须同基类中被重写的函数一直），一般在基类中必须有Virtual修饰
   隐藏：是指派生类的函数屏蔽了与其同名的基类函数（只要同名，不管参数列表是否相同就会隐藏）

10. 构造函数能否为虚函数？析构函数为什么一定要是虚函数？
    构造函数不能为虚函数，虚函数的调用需要虚函数表指针，而该指针存放在对象的内容空间中；若构造函数声明为虚函数，那么由于对象还未创建，还没有内存空间，更没有虚函数表地址用来调用虚函数——构造函数了。
    析构函数一定要是虚函数的主要原因是为了防止内存泄露。
    此外，构造函数是没有this指针的！
    

11. C++内部缺省的成员函数：
    缺省构造函数
    缺省拷贝构造函数
    缺省析构函数
    缺省赋值运算符（=）
    缺省取址运算符（&）
    缺省取址运算符（&）的const版本

内存管理相关

1. C++内存分区：栈区、堆区、全局/静态存储区、常量存储区、代码区
   栈区：在执行函数时，函数内局部变量的存储单元都可以在栈上创建，函数执行结束时，这些存储单元会被自动释放。栈内存分配运算内置于处理器的指令集中，因此效率很高，但是分配的内存容量有限
   堆区：就是那些由new分配的内存块，他们的释放不归编译器管理，而由应用程序去控制。一般一个new就对应一个delete。如果程序员没有手动释放掉这一块内存，那么程序结束后，操作系统会自行进行一个回收
   全局/静态存储区：在C++中，统一存放全局变量和静态变量的一块内存空间。全局/静态存储区内的变量在程序编译阶段已经分配好内存空间并初始化。这块内存在程序的整个运行期间都存在。需要注意的是，整个存储区内不存在没有初始化的变量，如果我们没有去做初始化操作，那么程序会按照默认方式初始化这些变量
   常量存储区：存储的一般是字符串常量，书上将其划分到了全局存储区，统一称为数据区。（我觉得都行，只要你知道这两个东西能放在一块就行）需要注意的是，局部常量是不放在常量存储区的。
   代码区：程序被操作系统加载到内存时，所有可执行的代码被加载到代码区，也叫代码段，存储程序的代码指令。程序运行时，这段区域数据不可被修改只可以被执行。同时，这一个分区是共享的，目的是为了让多次运行的程序可以只保留一份代码副本，节约空间
2. 内存泄漏
   我们一般所说的内存泄露都是指堆上的内存泄露了。一般说的都是程序申请了一块堆上的内存然后忘记准确释放或者是释放后忘记置空指向这块区域的指针的情况。总而言之，只要是内存操作错误其实都可以被归结为内存泄露。
3. 悬空指针和野指针
   悬空指针：若指针指向一块内存空间，当这块内存空间被释放后，该指针依然指向这片空间
   野指针：是指其指向不明确的指针，是没有通过初始化得到的指针
4. 智能指针
   智能指针就是为了解决内存泄露问题而出现的指针。简而言之，它其实是一个类，通过析构函数来释放掉自己所指向的内存空间。同时，还可以防止多次释放同一内存空间，以及将值语义转换成引用语义
   智能指针有三种：auto_ptr(貌似已经弃用)，unique_ptr以及shared_ptr,weak_ptr,unique是独享指针而share是共享资源指针，有些时候会让手撕一个share_ptr

关键字相关

1. new和delete与malloc和free
   new和delelte是C++的关键字，而malloc和free是库函数，需要头文件的支持
   使用new操作符申请分配内存时，无须指定内存块大小，编译器会根据类型自动计算，而malloc会需要显式的制定内存大小
   new操作符内存分配成功时，返回的是对象类型的指针，类型严格与对象匹配，无需进行类型转换。所以new是符合类型安全性的操作符。而malloc内存分配成功返回的是void*，需要通过强制类型转换将void*转成我们所需要的类型
   new内存分配失败时，会抛出bad_alloc异常。而malloc会返回Null
   new先申请内存，后调用构造函数，初始化变量后返回。delete先析构，后归还内存
   new和delete可以重载而malloc不允许重载
   注意：使用new【】一定要搭配delete【】，否则会让编译器以为指针指向的是一个对象，而不是对象数组。因此不会调用多次析构，从而造成内存泄露。

2. explict的主要作用：禁止隐式类型转换
   由于C++支持自定义的类型转换操作，所以，当自定义类型转换操作和构造函数（会产生隐式类型转换）同时存在的时候，就有可能让编译语句产生多义性，此时就需要explict让构造函数只用于构造对象，而不会参与进隐式类型转换中
   另：在C++11之后，explict关键字也支持禁用多参数构造函数了
   

3. static关键字：用来控制存储方式和可见性
   在修饰变量的时候，static修饰的静态局部变量只执行初始化一次，而且延长了局部变量的生命周期，直到程序运行结束后才释放
   static修饰全局变量的时候，这个全局变量只能在本文件中访问，不能在其它文件中访问，即使是使用extern外部声明也不行
   static修饰一个函数，则这个函数只能在本文件中被调用，不能被其它文件所调用
   当函数中存在不想释放空间的变量时。比如可以修饰放在栈内存空间的数组
   静态数据在内存中只有一份，不会因为类的实例化而变多。
   需要注意的是，在类里面声明的静态数据成员，还需要在类外定义一次

4. const关键字：常量关键字，被修饰的变量无法更改（“只读”）
   使用const的时候有两条规则：第一，const关键字距离谁近谁就无法被更改。第二，const修饰一个变量时，一定要初始化，若不初始化，则之后都不能初始化了（因此类中的常成员变量必须在参数列之中初始化）
   修饰指针的时候，有两种情况：
   
   修饰函数参数时：被修饰的参数在函数内不可以被改变
   修饰成员变量时：成员变量不可变，必须在初始化列表中进行初始化
   修饰成员函数时：成员函数不能更改任何成员变量
   修饰对象引用时：不能改变任何成员变量，并且只能调用const修饰的常成员函数
   注意：为了代码的健壮性，当确定一段成员函数不会更改成员变量的时候，一定要将其声明为const

5. volatile关键字
   volatile关键字：提醒编译器它后面所定义的变量随时都有可能改变，因此编译后的程序每次需要存储或读取这个变量的时候，都会直接从变量地址中读取数据。如果没有volatile关键字，则编译器可能优化读取和存储，可能暂时使用寄存器中的值，如果这个变量由别的程序更新了的话，将出现不一致的现象。（一般可能用于多线程编程之中）

6.四种类型转换

• static_cast< 类型说明符 >（变量或者表达式）：
  1. 用于层次结构中的基类和派生类之间指针或者引用的转换。进行上行转换时，是安全的。进行下行转换时，是不安全的
  2. 用于基本数据类型之间的转换，如int->char，但是这种转换安全需要开发人员自行检查
  3. 把空指针转换成目标类型的空指针（new关键字就使用了这种转换）
  4. 把任何类型的表达式转换成void类型
• dynamic_cast< type-id >(expression)：
  1. 只有在派生类之间转换时才使用dynamic_cast，type_id必须是类指针，类引用或者void*
  2. 只有这种类型转换才是在运行时进行转换的，其它三种都是在编译时就进行转换
  3. 使用这种转换的基类必须要有虚函数，因为它是运行时类型检查，而这个信息一般都存储在虚函数表中
  4. 对于下行转换，dynamic_cast是安全的（当类型不一致时，传回来的是空指针），而static_cast会返回意义不明的指针造成内存访问的错误
• const_cast< 类型说明符 >（变量或者表达式）
  1. const_cast转换符是用来移除变量的const或volatile限定符，但是需要特别注意的是，const_cast不是用于移除变量的常量性，而是用于去除指向常数对象的指针或者引用的常量性，也即，其去除常量性的对象必须为指针或者引用
• reinterpret_cast< 类型说明符 >（变量或者表达式）
  1. 强制类型转换符（一般不使用），可用于指针和整数之间的转换，也可以用于不同类型的指针/成员指针/引用之间的转换
  2. 前者可以用来在指针中存储额外信息。例如在特定平台上，如果指向的类型是4字节对齐的，则指针所转成的整数的最低两位（bit）一定是0，那么就可以用这两位存储其他数据
  3. 后者可以用于通过成员访问完整结构体对象或者从完整结构体对象访问间接成员（大概和CPython的_PyObject_CAST相似），不过C++一般不需要用到这种。

7. override关键字
   这个关键字是为了重写而存在的。这里之所以提他是因为他有一个很方便的特性：帮助检查重写函数格式是否正确。避免弄错了虚函数的名字，形参而失效的情况

8. decltype关键字
   decltype可以宣则并返回操作数的数据类型，在此过程中，编译器分析表达式并且得到它的类型，但是不会计算表达式的值（可以用于一些不想写变量类型的场合，或者自己也不知道计算出来的类型是个啥的场合）

区别对比

1. 函数传值调用、传指针调用和传引用调用的区别
   传值调用：传值调用时，函数参数压栈的是参数的副本，即变量的拷贝。因此任何的修改都只会作用在副本上，而不会更改原本变量的值
   传指针调用：本质上也是一种传值调用，传递的是地址值，压栈的是指针的副本。好处在于，可以少开辟一些空间。比如值传递64位操作系统下，long传递要使用8bit，但是传指针就能只用4bit，除此之外还可以通过解指针操作去改变变量
   传引用调用：传递的是实参本身，而不是实参的一个拷贝。形参的修改就是实参的修改，因此，传引用调用要善用const来避免误操作。
   注意，函数里面能传引用的地方就尽量传引用，因为可以避免一次参数拷贝，效率较高

特性相关

1. Lambads表达式：
   C++11支持写inline函数，也可以当作对象，相当于函数匿名对象
   
   我们经常可以在Sort函数里面看到这个用于自定义排序函数，在实习过程中其实代码也有很多地方用了Lambda表达式，所以算是一个很重要的重点，可参考：Lambda表达式解析

2. 右值引用
   一般和移动语义一起使用，相当于直接让变量直接获得临时对象的内存空间从而避免多一次的拷贝操作降低性能。
   如何判断是右值其实有以下这些方法：1.右值只能出现在等号右边，能出现在左边的一般是左值 2.看看能不能对对象取地址，如果能取到地址的一般是左值，而取不到的一般是右值
   右值引用一般用于移动构造函数和移动拷贝函数，语法为&&
   std:move()函数可以将一个左值转变为右值
   这里还有一个完美转发的问题，即右值在连续传递的过程中很可能会变成一个左值，因此需要forward()来进行完美转发

3. auto自动推导
   这个没什么好说的了，可以用于for循环，当你觉得变量名或者类名很长不想写的时候使用auto，编译器就会去自动推导他的数据类型

4. 可变参数模板
   语法为“…”,可以接收任意个的模板参数，编译器的处理方法为注意分离，直到有可用的偏特化版本为止
   

其它

1. 编译过程大概分为四个步骤：
   编译预处理，编译与优化，汇编，链接
   编译预处理阶段：处理以"#"开头的指令
   编译、优化：将源码.cpp文件翻译成.s的汇编代码，同时这里会执行一些编译器自己的优化操作
   汇编：将汇编代码.s翻译成机器指令.o文件
   链接：汇编程序生成的目标文件，即.o文件。并不会立即执行，因为可能会出现.cpp文件中的函数引用了另一个.cpp文件中定义的符号或者调用了某个文件之中的函数。那链接的目的就是将这些文件连成一个整体，从而生成可执行的程序.exe文件

2. 链接也分为两种：
   静态链接：代码从其所在的静态链接库中拷贝到最终的可执行程序中，在该程序被执行时，这些代码会被装入到该进程的虚拟地址空间中
   动态链接：代码被放到动态链接库或者共享对象的某个目标文件中，链接程序只是在最终的可执行程序中记录了共享对象的名字等一些信息。在程序执行时，动态链接库的全部内容会被映射到运行时相应进行的虚拟地址的空间。
   二者的优缺点：
   静态链接：浪费空间，每个可执行程序都会有目标文件的一个副本，假如目标文件进行了更新操作，就需要进行编译链接（重新）生成可执行程序。优点是运行速度快，因为可执行程序具备了程序运行的所有内容
   动态链接：节省内存，更新方便，但是动态链接是在程序运行时，每次执行都需要链接，相比于静态链接会有一定的性能损失。

3. dll文件和lib文件的区别：
   使用场景不同：lib是编译时用到的，dll是运行时用到的。如果要完成源代码的编译，只需要lib，如果要使动态链接的程序运行起来，则只需要dll
   用途不同：如果有dll文件，那么lib一般是一些索引信息，记录了dll中函数的入口和位置，dll文件中则是函数的具体内容；如果只有lib文件，那么这个lib文件是静态编译出来的，所有的索引和实现都在这个lib文件中。这里会涉及到静态链接和动态链接的优缺点，具体参考上文
   应用对象不同：动态链接的情况下，有两个文件，一个是LIB文件，一个是DLL文件。LIB文件包含被DLL文件导出的函数名称和位置，DLL包含实际的函数和数据，应用程序使用LIB文件链接到DLL文件。在应用程序的可执行文件中，存放的不是被调用的函数代码，而是DLL中相应函数代码的地址，从而节省了内存资源。
   具体可参考：lib和dll的区别

4. 函数压栈的过程
   参数入栈：将当前参数从右至左依次压入当前系统栈之中
   返回地址入栈：将当前代码区调用指令的下一条指令地址送入栈中，供函数返回时继续执行
   代码区跳转：处理器从当前代码区跳转到调用函数的入口处
   栈帧调整包括：
   （1）保存当前栈帧状态值， 以备后面恢复本栈帧时使用（EBP入栈）
   （2）将当前栈帧切换到新的栈帧（将ESP值装入EBP，更新栈帧底部）
   （3）给新的栈帧分配空间（把ESP减去所需栈帧的大小，抬高栈顶）

5. 函数返回的步骤如下（与三链接）：
   保存返回值：将函数的返回值保存在寄存器EAX中
   弹出当前帧，恢复上一个栈帧，具体包括：
   （1）在堆栈平衡的基础上，给ESP加上栈帧的大小，降低栈顶，回收当前栈帧的空间
   （2）将当前栈帧保存的前栈帧EBP的值弹入EBP寄存器，恢复出上一个栈帧
   （3）将函数返回地址弹给EIP寄存器
   跳转：按照函数返回地址跳回母函数中继续执行
   更为具体的可以参考这边：函数压栈与返回
   注：名词解释部分：
   ESP：栈指针寄存器(extended stack pointer)，其内存放着一个指针，该指针永远指向系统栈最上面一个栈帧的栈顶。
   EBP：基址指针寄存器(extended base pointer)，其内存放着一个指针，该指针永远指向系统栈最上面一个栈帧的底部。
   EIP：指令寄存器(extended instruction pointer)，其内存放着一个指针，该指针永远指向下一条等待执行的指令地址
   

STL与泛型编程部分

容器（Containers）

容器大致可以分为三类：

一、 顺序容器（Sequence Containers）：

1.Array（C++11引入）： 数组，固定长度的数组。之所以将Array包装成了一个容器，目的是为了能让Array享受到STL体系结构中的各种各样的便利

2.Vector（向量）：

• Vector的行为近似一个数组，并且可以动态扩充，每次扩充时内存大小扩展为两倍，因此不可能是原地扩充
• C++Vector的底层靠三个指针控制所有操作，start,finish,end_of_storage
  
• 内存空间会在插入元素的时候扩充，步骤如下：

1. 申请2倍（不一定是这个数字，具体视平台和编译器而定）于原内存空间大小的内存空间
2. 将原本Vector中的内容拷贝到新的Vector内存空间中
3. 解构并释放原本的Vector
4. 调整迭代器，使其指向新的Vector

• 因此，使用Vector的时候尽量要避免动态增长，因为会产生比较大的开销（最好是对工作大小有个预估，申请相应的内存大小）

3.Deque（双端队列）

• Deque本质上是分段连续（用Vector装入指向不同缓冲区的指针来实现的）
  
• Deque的迭代器有四个指针，种类属于random_access_iterator_tag
  

1. first和last标识出缓冲区buffer的边界
2. node在存储指针的Vector上移动，完成缓冲区的切换
3. cur是工作指针，指向遍历中的每一个元素
4. 此外，还会另设start和finish两个迭代器，用于完成函数begin()和end()的工作(具体来说是里面的cur指针指向了deque的头和尾)

• 以insert(）函数为例：

1. 如果是最前端，则交给push_front()函数去做
2. 如果是最后端，则交给push_back()函数去做
3. 其余情况会调用deque自己的insert_aux()，首先会计算安插点前方的元素多还是后方的元素多(为了节省Copy的性能)，然后将整体往元素少的方向推动，空出的位置插入元素

• 此外，deque还重载了一系列的操作符去模拟连续空间，比如”-“就要计算缓冲区相隔多少个再乘上缓冲区大小，最后再加上各自的元素个数，同理，还有”++“”–“”+=“之类的操作来模拟数组的随机存储

4.List与Forward-List（C++11）：

• 没什么好说的，链表是最基础的数据结构了，STL也提供了容器，注意List是双向链表，Forward-List是单向链表即可(少一个指针的内存空间有些时候是十分提升存储性能的)
  

这两个容器可以参考这里的博文

二、关联容器（Associative Containers）：

1.set和mutiset：

• Set表的Key和Value是一样的，不存在映射关系，而MutiSet则表示一个表里面可以同时存储相同的Key（一般来说是不能相同的）
• 底层实现是红黑树

2.Map和MutiMap

• Map表则是一个Key对应一个Value，Muti同理，可以有多个Key
• 底层同样使用红黑树

三、Unordered Containers（无序容器，C++11开始引入）：
这一类也不多讲，分别有Unordered Set/Unordered Map以及他们的Muti，但是底层的实现倒是需要好好了解一下。
这一类的容器底层都是使用HashTable实现的，为了快速查找，同时，解决冲突的方法使用的是链式解决法。（小提一句，JAVA底层貌似使用了红黑树来直接处理，同样也可以节省冲突发生时的查找时间）并且，为了保证最高的查找效率，一般需要维持元素和对应挂的格子数量相近，否则，就需要Rehash来得到新的结果

迭代器（iterator）

迭代器的主要目标就是从容器中获得算法运行时需要的几个关键数据：
1.iterator_category（迭代器种类）
2.value_type（元素的类别）
3.diffence_type（距离的表达方式）
另外的两个reference_type和pointer_type则目前没有在STL中使用过
算法会根据这些名称去通过迭代器而获得正确的数据来执行相关操作。（由于迭代器有可能不是一个类，而是一个指针，所以就需要萃取机制去让指针拥有这些相同的属性）

同时，迭代器具有以下五类：

算法（algorithm）

容器和迭代器的包装在我个人的理解中是为了更好的服务于算法。这一部分其实没有很多要讲的，常见函数sort(),upper_bound(),lower_bound(),next_permutation()等等慢慢学着会用就好了。算法的头文件是
< algorithm >

仿函数（Functor）

• 仿函数就是使一个类的使用看上去像函数，一般来说是使用重载"()"符号来实现的
• 每一个标准库的仿函数都继承自binary_function或unary_function，不然就无法融入STL的体系结构。这两个父类更改了模板变量名（typedef），从而让适配器可以得到相应的信息

适配器（adpater）

在STL组件中，扮演者轴承、转换器的角色。Adapter这个概念，事实上是一种设计模式。定义如下：将一个class 的接口转换为另一个 class 的接口，使原本因接口不兼容而不能合作的 class，可以一起运作。容器，迭代器，仿函数均有适配器
比如容器的适配器：队列和栈（Deque的不同表现形式）
迭代器的适配器：反向迭代器（Reverse Iterators）
仿函数的适配器：bind（）等

分配器（allocator）

由于现在C++的默认分配器已经算是够用了，所以这里没有太多需要介绍的东西。但是结合游戏开发就有要说的了。
由于内存操作其实是相当费时费力的行为，并且由于New底层也会去调用Malloc（）函数，所以切割出来的内存区块一般都会带有Cookie，所以为了节约开销和内存空间，其实是很有必要自己设计内存分配器用以优化内存性能开销的。具体的以后我可能会单开博客讨论，这里只说一种侯捷老师介绍的，在游戏引擎架构里面被称为池分配器的结构：
池分配器：

我们来分析一下它的工作过程：加入一块内存，即容器元素所需的内存大小为50，则会被预先调整为56（8bit的倍数），然后去管理56字节大小的链表中拿取内存块。如果该链表下已经没有内存块了，则会调用malloc()向操作系统要来一大块内存，切割之后继续使用。
这样做有两个好处：
1.有效降低了Malloc（）次数，节省性能开销
2.减少了Cookie所占的空间，在数据量较大的时候可以节约非常多的内存空间

代码类

三大排序与洗牌

整个程序都是自己写的，哪里不懂或者我哪里写错了欢迎指出~

#include<iostream>
#include<vector>

using namespace std;


//类整体
class Solution{
public:
	void Shuffle(vector<int>& arr);//简单的洗个牌
	void QuickSort(vector<int>& arr);//快速排序
	void HeapSort(vector<int>& arr);//堆排序
	void MergeSort(vector<int>& arr);//归并排序
private:
	void QuickSortSup(vector<int>& arr, int ileft, int right);
	void HeapKeep(vector<int>& arr, int i, int n);//建堆函数
	void MergeSortSup(vector<int>& arr, int left, int right);
	void MergeHelp(vector<int>&arr, int left, int mid, int right);
};


void Solution::Shuffle(vector<int>& arr) {
	int n = arr.size();
	for (int i = n-1; i >= 0; i--) {
		swap(arr[i], arr[rand() % (i + 1)]);
	}
}

void Solution::QuickSort(vector<int>& arr) {
	int n = arr.size()-1;//传递最右边的元素
	QuickSortSup(arr, 0, n);
}


void Solution::QuickSortSup(vector<int>&arr, int left, int right) {//递归方式实现
	if (left > right) {
		return;
	}
	int i = left;
	int j = right;
	int key = arr[left];
	while (i < j) {
		while (i<j && arr[j] > key) {
			j--;
		}
		if (i < j) {
			swap(arr[i], arr[j]);
		}
		while (i < j&& arr[i] <= key) {
			i++;
		}

		if (i < j) {
			swap(arr[i], arr[j]);
		}
	}
	arr[i] = key;//还原
	QuickSortSup(arr, left, i - 1);
	QuickSortSup(arr, i + 1, right);
}

void Solution::HeapSort(vector<int>& arr) {
	int n = arr.size()-1;
	for (int i = n / 2; i >= 0; i--) {
		HeapKeep(arr, i, n);
	}
	for (int i = n; i >= 0; i--) {
		swap(arr[0], arr[i]);
		HeapKeep(arr, 0, i-1);//注意这里，如果n是数组长度的话，是不用传i-1的，for循环一开始传i-1就好
	}


}

void Solution::MergeSort(vector<int>& arr) {
	MergeSortSup(arr, 0, arr.size() - 1);
}

void Solution::MergeSortSup(vector<int>& arr, int left, int right) {
	if (left >= right) {
		return;
	}
	int mid = left + (right - left) / 2;
	MergeSortSup(arr, left, mid);
	MergeSortSup(arr, mid + 1, right);
	MergeHelp(arr, left, mid, right);
}

void Solution::MergeHelp(vector<int>& arr, int left, int mid, int right) {
	int n = right - left + 1;
	int* a = new int [n];
	int s1 = left;
	int s2 = mid + 1;
	int i = 0;
	while (s1 <= mid && s2 <= right) {
		if (arr[s1] >= arr[s2]) {
			a[i++] = arr[s2++];
		}
		else {
			a[i++] = arr[s1++];
		}
	}

	while (s1 <= mid) {
		a[i++] = arr[s1++];
	}
	while (s2 <= right) {
		a[i++] = arr[s2++];
	}
	
	for (int j = 0; j < n; j++) {
		arr[left + j] = a[j];
	}
}

void Solution::HeapKeep(vector<int>& arr,int i,int n) {
	int leftson = i * 2 + 1;
	int rightson = i * 2 + 2;
	int largest = i;

	if (leftson<=n && arr[leftson] > arr[largest]) {
		largest = leftson;
	}
	if (rightson<=n && arr[rightson] > arr[largest]) {
		largest = rightson;
	}
	
	if (largest != i) {
		swap(arr[i], arr[largest]);
		HeapKeep(arr, largest, n);
	}
}





void displayVector(vector<int>& arr) {
	cout << "arr数组目前元素为：    ";
	for (int i = 0; i < arr.size();i++)
	{
		cout << arr[i] << " ";
	}

	cout << endl;
}


int main() {
	vector<int> arr = { 1,1,2,3,4,5,6,7,8,8,9,10,-1 };//在此处更改测试数据
	Solution* solution = new Solution();

	cout << "快速排序" << endl;
	solution->Shuffle(arr);
	displayVector(arr);
	solution->QuickSort(arr);
	displayVector(arr);
	
	cout << "堆排序" << endl;
	solution->Shuffle(arr);
	displayVector(arr);
	solution->HeapSort(arr);
	displayVector(arr);

	cout << "归并排序" << endl;
	solution->Shuffle(arr);
	displayVector(arr);
	solution->MergeSort(arr);
	displayVector(arr);

	return 0;
}

MyString类

对这个类有别的功能要求都可以提给我，我尽量做

#define _CRT_SECURE_NO_WARNINGS//解决strcpy无法使用
#include<iostream>
#include<vector>
#include <cstring>


using namespace std;

//注意strlen返回的大小不包括\0
class Mystring {
public:
	Mystring(const char* s=0);
	Mystring(const Mystring &str);
	Mystring& operator = (const Mystring &str);
	friend ostream &operator<<(ostream &o, const Mystring &str)
	{
		o << str.mystr;
		return o;
	}
	~Mystring();
	
private:
	char* mystr;
	int m_size;
};

Mystring::Mystring(const char* s) {
	if (s != nullptr) {
		m_size = strlen(s);
		mystr = new char[m_size+1];
		strcpy(mystr,s);
	}
	else {//空指针时要单独处理
		m_size = 0;
		mystr = new char[m_size + 1];
		mystr[0] = '\0';
	}
}

Mystring::Mystring(const Mystring &str) {
	m_size = str.m_size;
	mystr = new char[m_size + 1];
	strcpy(mystr, str.mystr);
}

Mystring::~Mystring() {
	delete[] mystr;
}

Mystring& Mystring::operator=(const Mystring& str) {
	//需要添加自我赋值判断
	if (&str == this) {
		return *this;
	}

	m_size = str.m_size;
	delete[] mystr;
	mystr = new char[m_size+1];
	strcpy(mystr, str.mystr);
	return *this;
}


int main() {
	char s1[] = "This is first Mystring";
	char s2[] = "This is third Mystring";
	Mystring mystring1(s1);
	cout << mystring1<<endl;
	Mystring mystring2(mystring1);
	cout << mystring2<<endl;
	Mystring mystring3(s2);
	cout << mystring3 << endl;
	mystring3 = mystring2;
	cout << mystring3 << endl;
}

智能指针Shared_ptr

#include<string>
#include <iostream>


using namespace std;

template<typename T>
class Sharedptr {
	public:
		//空参数构造，空指针
		Sharedptr():count(0),ptr((T*)0){}
		//构造函数，必须new出内存空间
		Sharedptr(T* p):count(new int(1)),ptr(p){}
		//拷贝构造函数，使其引用次数加1
		Sharedptr(Sharedptr<T>& other) : count( &(++ *other.count)),ptr(other.ptr){}
		//重载operator* 和 operator->实现指针功能
		T* operator->() { return ptr; }
		T& operator*() { return *ptr; }
		//重载operator = 
		//如果原来的sharedptr已经有对象，则让其引用对象次数减一并且判断是否为0，是否调用Delete然后将新的引用对象次数-1
		Sharedptr<T>& operator = (Sharedptr<T>& other) {
			if (this == &other) return *this;//与Mystring类的处理一样
			++* other.count;
			if (this->ptr && 0 == -- *this->count) {
				delete count;
				delete ptr;
				cout << "delete ptr=" << endl;
			}
			this->ptr = other.ptr;
			this->count = other.count;
			return *this;
		}
		~Sharedptr() {
			if (ptr&&-- * count == 0) {
				delete count;
				delete ptr;
				cout << "delete ptr~" << endl;
			}
		}
		int getRef() {//得到引用数量
			return *count;
		}
	private:
		int* count;
		T* ptr;

};

int main()
{
	Sharedptr<string> pstr(new string("abc"));
	cout << "pstr:" << pstr.getRef() << " " << *pstr << endl;

	Sharedptr<string> pstr2(pstr);
	cout << "pstr:" << pstr.getRef() << " " << *pstr << endl;
	cout << "pstr2:" << pstr2.getRef() << " " << *pstr2 << endl;

	Sharedptr<string> pstr3(new string("hao"));
	cout << "pstr3:" << pstr3.getRef() << " " << *pstr3 << endl;

	pstr3 = pstr2;
	cout << "pstr:" << pstr.getRef() << " " << *pstr << endl;
	cout << "pstr2:" << pstr2.getRef() << " " << *pstr2 << endl;
	cout << "pstr3:" << pstr3.getRef() << " " << *pstr3 << endl;
}

单例模式（懒汉与饿汉）

#include<iostream>

using namespace std;
//https://blog.csdn.net/hit0803107/article/details/54411180?utm_medium=distribute.pc_relevant.none-task-blog-baidujs_title-0&spm=1001.2101.3001.4242

class Singleton1 {//懒汉模式加载 
public:
	static Singleton1& GetInstance() {
		if (s_instance == nullptr) {
			s_instance = new Singleton1();
		}
		return *s_instance;
	}
	void dosomething() {
		cout << "使用懒汉模式做了一些事情" << endl;
	}

private:
	Singleton1() {
		cout << "懒汉模式单例被创建" << endl;
	}
	~Singleton1();
	Singleton1(const Singleton1&);//禁止使用拷贝构造和拷贝赋值函数 来创建单例模式的副本 
	Singleton1& operator=(const Singleton1&);

private:
	static Singleton1* s_instance;
};

class Singleton2 {//饿汉模式加载 
public:
	static Singleton2& GetInstance() {
		return *s_instance;
	}
	void dosomething() {
		cout << "使用饿汉模式做些事情" << endl;
	}

private:
	Singleton2() {
		cout << "饿汉模式单例被创建" << endl;
	}
	~Singleton2();
	Singleton2(const Singleton2&);
	Singleton2& operator=(const Singleton2&);

private:
	static Singleton2* s_instance;
};

Singleton1* Singleton1::s_instance = nullptr;
Singleton2* Singleton2::s_instance = new Singleton2();

int main() {
	Singleton1 &s1 = Singleton1::GetInstance();//懒汉模式加载
	Singleton2 &s2 = Singleton2::GetInstance();//饿汉模式加载
	s1.dosomething();
	s2.dosomething();
}