C++入门之实战（1）

最近更新的有点慢，主要是因为我自己有点纠结了，有点不知道应该写一些什么内容了。我想，除了介绍一些理论知识，还要穿插一些实战才可以，但是实战的内容不好写，我在考虑是否要录一些视频，视频在表达起来更容易，呈现的内容也更多。但我也深知文章对人的重要性，有时候文章接受起来更容易，特别是短小精简的文章。

因为是入门系列文章，今天介绍一个非常简单的例子。

一个最简单的C++工程项目，只需要一个源代码文件就可以实现，那就是main.cpp文件。在c++开发环境中，程序运行都是从main（）函数开始的。然而在实践中，不可能只用一个mian.cpp文件写完所有代码。在一般的编程规范中，c++工程项目中一般有三种文件：头文件、源代码文件和main.cpp文件。

其中，main函数声明和定义在main.cpp文件中， 头文件用来一般类和函数等的声明，源代码文件用来一般类和函数等的定义。在之前的几篇文章中，我都将类的声明和定义写在了头文件中，也即在类的声明处定义该类，也不是不行，但不一定符合规范。声明和定义应该是要分开的，除非函数的实现很短小（只有几行）。

图1 基本的工程结构

如图1所示是c++基本的工程结构，在helloworld.h中是类HelloWorld的声明，在helloworld.cpp中的类的定义。在mian.cpp中是主函数main().(我用的是qtcreator，下载安装qt5以上自带qtcreator，有时间，我做一个专门说明IDE的文章或视频）。

图1 helloworld.h文件

图2 helloworld.cpp

在helloworld.h中HelloWorld是类名，以class关键字来声明。HelloWorld和~HelloWorld分别是构造函数和析构函数，函数名就是类名。void Show();是成员函数。string _str是成员变量又叫数据成员。可以看到，在helloworld.h中只进行了相关元素的声明。另外，在写头文件的时候一般在文件开头加入图上的宏定义，宏定义名称在不同的文件中是不同的，以避免一个头文件被#include 多次，在编译的时候报重定义的错误。

在helloworld.cpp中对类中的成员函数进行定义，所谓定义，也就是对函数们进行了实现，将函数中实现的逻辑写了出来。其中 ：： 表示域作用符，HelloWorld：：Show（）表示Show是在类HelloWorld中声明的。再定义构造函数的时候，注意到_str的初始化没有，那个叫做通过初始化列表来初始化成员变量，这样进行初始化，比在{ }内初始化得更早。当然在helloworld.cpp中首先要#include \”helloworld.h\”.

在main.cpp中，使用HelloWorld类，首先#include \”helloworld.h\”.然后用法如图上所示。

另外，提示，要是用string，则要#include<string> ,要使用cout ，则要#include <iostrean>.

#include \”xxx\” 和 #include <mmm>的区别在于，xxx是自己写的头文件，mmm是系统头文件。

这是一个最简单的工程，体现了一点面向对象的思想，即将helloworld封装成一个类。这也是c++代码的基本组织方式。

今天就先到这里，今天码字比较多，有点违反我的“简单”原则，我想下一次类似实战的文章还是录视频能更说清楚。我的目的就是希望帮大家更容易入门，因为我知道自己当初有多痛苦。

谢谢阅览，希望多提宝贵意见，也顺便关注一下，以后大家多多交流，共同进步。

这些C++工程师面试题你都会了吗？

面试中常见的C++面试题总结，快来看看，是否对你有帮助！

1、写出完整版的strcpy函数

char * strcpy( char *strDest, const char *strSrc )

{

assert( (strDest != NULL) && (strSrc != NULL) );

char *address = strDest;

while( (*strDest++ = * strSrc++) != ‘\\0’ );

return address;

}

要点：

使用assert断言函数，判断参数是否为NULL；

遇\’\\0\’则停止赋值；

返回新的字符串的首地址。

2、指出代码错误

void Test( void )

{

char *str = (char *) malloc( 100 );

strcpy( str, \”hello\” );

free( str );

… //省略的其它语句

}

错误有二：

使用malloc分配内存后，应判断是否分配成功；

free之后，应置str为NULL，防止变成野指针。

PS：malloc函数

malloc函数是一种分配长度为num_bytes字节的内存块的函数，可以向系统申请分配指定size个字节的内存空间。malloc的全称是memory allocation，中文叫动态内存分配，当无法知道内存具体位置的时候，想要绑定真正的内存空间，就需要用到动态的分配内存。

第一、malloc 函数返回的是 void * 类型。

对于C++，如果你写成：p = malloc (sizeof(int)); 则程序无法通过编译，报错：“不能将 void* 赋值给 int * 类型变量”。

所以必须通过 (int *) 来将强制转换。而对于C，没有这个要求，但为了使C程序更方便的移植到C++中来，建议养成强制转换的习惯。

第二、函数的实参为 sizeof(int) ，用于指明一个整型数据需要的大小。

在Linux中可以有这样：malloc(0),这是因为Linux中malloc有一个下限值16Bytes，注意malloc(-1)是禁止的；但是在某些系统中是不允许malloc(0)的。

malloc 只管分配内存，并不能对所得的内存进行初始化，所以得到的一片新内存中，其值将是随机的。

3、分别给出BOOL，int，float，指针变量 与“零值”比较的 if 语句

BOOL型变量：if(!var)

int型变量： if(var==0)

float型变量：

const float EPSINON = 0.00001;

if ((x >= – EPSINON) && (x <= EPSINON)

指针变量：if(var==NULL)

4、以下为Windows NT下的32位C++程序，请计算sizeof的值

void Func ( char str[100] )

{

sizeof( str ) = ?

}

void *p = malloc( 100 );

sizeof ( p ) = ?

sizeof( str ) = 4

sizeof ( p ) = 4

Func ( char str[100] )函数中数组名作为函数形参时，在函数体内，数组名失去了本身的内涵，仅仅只是一个指针；在失去其内涵的同时，它还失去了其常量特性，可以作自增、自减等操作，可以被修改。

但是数组名在不作形参时，仍然代表整个数组，这时的sizeof应返回数组长度。

sizeof返回的单位是字节。对于结构体，sizeof返回可能会有字节填充。结构体的总大小为结构体最宽基本类型成员大小的整数倍。

5、写一个“标准”宏MIN，这个宏输入两个参数并返回较小的一个。另外，当你写下面的代码时会发生什么事？

least = MIN(*p++, b);

答案：

#define MIN(A,B) ((A) <= (B) ? (A) : (B))

四个注意点：

宏定义中，左侧为宏名和参数，右侧为宏的实现；

在宏的实现中，所有参数应用括号括起来；

整个宏的实现的外面也要用括号括起来；

最后没有分号。

写下如上代码会导致p自增两次。

6、ifndef、extern的用法

条件指示符#ifndef 的最主要目的是防止头文件的重复包含和编译。

extern修饰变量的声明。

如果文件a.c需要引用b.c中变量int v，就可以在a.c中声明extern int v，然后就可以引用变量v。

这里需要注意的是，被引用的变量v的链接属性必须是外链接（external）的，也就是说a.c要引用到v，不只是取决于在a.c中声明extern int v，还取决于变量v本身是能够被引用到的。

7、请说出static和const关键字尽可能多的作用

static:

1. 修饰普通变量，修改变量的存储区域和生命周期，使变量存储在静态区，在main函数运行前就分配了空间，如果有初始值就用初始值初始化它，如果没有初始值系统用默认值初始化它。在每次调用时，其值为上一次调用后改变的值，调用结束后不释放空间。此变量只在声明变量的文件内可见。

2. 修饰普通函数，表明函数的作用范围，仅在定义该函数的文件内才能使用。在多人开发项目时，为了防止与他人命令函数重名，可以将函数定义为static。

3. 修饰成员变量，修饰成员变量使所有的对象只保存一个该变量，而且不需要生成对象就可以访问该成员。

4. 修饰成员函数，修饰成员函数使得不需要生成对象就可以访问该函数，但是在static函数内不能访问非静态成员。

const:

1. 修饰变量，说明该变量不可以被改变；

2. 修饰指针，分为指向常量的指针和指针常量；

3. 常量引用，经常用于形参类型，即避免了拷贝，又避免了函数对值的修改；

4. 修饰成员函数，说明该成员函数内不能修改成员变量。

8、请说一下C/C++ 中指针和引用的区别？

1.指针有自己的一块空间，而引用只是一个别名；

2.使用sizeof看一个指针的大小是4，而引用则是被引用对象的大小；

3.指针可以被初始化为NULL，而引用必须被初始化且必须是一个已有对象 的引用；

4.作为参数传递时，指针需要被解引用才可以对对象进行操作，而直接对引用的修改都会改变引用所指向的对象；

5.可以有const指针，但是没有const引用；

6.指针在使用中可以指向其它对象，但是引用只能是一个对象的引用，不能被改变；

7.指针可以有多级指针（**p），而引用只有一级；

8.指针和引用使用++运算符的意义不一样；

9.如果返回动态内存分配的对象或者内存，必须使用指针，引用可能引起内存泄露。

9、给定三角形ABC和一点P(x,y,z)，判断点P是否在ABC内，给出思路并手写代码

根据面积法，如果P在三角形ABC内，那么三角形ABP的面积+三角形BCP的面积+三角形ACP的面积应该等于三角形ABC的面积。

10、野指针是什么？

野指针就是指向一个已删除的对象或者未申请访问受限内存区域的指针。

11、为什么析构函数必须是虚函数？为什么C++默认的析构函数不是虚函数？

将可能会被继承的父类的析构函数设置为虚函数，可以保证当我们new一个子类，然后使用基类指针指向该子类对象，释放基类指针时可以释放掉子类的空间，防止内存泄漏。

C++默认的析构函数不是虚函数是因为虚函数需要额外的虚函数表和虚表指针，占用额外的内存。而对于不会被继承的类来说，其析构函数如果是虚函数，就会浪费内存。因此C++默认的析构函数不是虚函数，而是只有当需要当作父类时，设置为虚函数。

PS：C++类的六个默认成员函数：

构造函数：一个特殊的成员函数，名字与类名相同，创建类类型对象的时候，由编译器自动调用，在对象的生命周期内只且调用一次，以保证每个数据成员都有一个合适的初始值。

拷贝构造函数：只有单个形参，而且该形参是对本类类型对象的引用（常用const修饰），这样的构造函数称为拷贝构造函数。拷贝构造函数是特殊的构造函数，创建对象时使用已存在的同类对象来进行初始化，由编译器自动调用。

析构函数：与构造函数功能相反，在对象被销毁时，由编译器自动调用，完成类的一些资源清理和收尾工作。

赋值运算符重载：对于类类型的对象我们需要对‘=’重载，以完成类类型对象之间的赋值。

取址操作符重载：函数返回值为该类型的指针，无参数。

const修饰的取址运算符重载。

12、C++中析构函数的作用？

析构函数与构造函数对应，当对象结束其生命周期，如对象所在的函数已调用完毕时，系统会自动执行析构函数。

析构函数名也应与类名相同，只是在函数名前面加一个位取反符~，例如~stud( )，以区别于构造函数。它不能带任何参数，也没有返回值（包括void类型）。只能有一个析构函数，不能重载。

如果用户没有编写析构函数，编译系统会自动生成一个缺省的析构函数（即使自定义了析构函数，编译器也总是会为我们合成一个析构函数，并且如果自定义了析构函数，编译器在执行时会先调用自定义的析构函数再调用合成的析构函数），它也不进行任何操作。所以许多简单的类中没有用显式的析构函数。

如果一个类中有指针，且在使用的过程中动态的申请了内存，那么最好显示构造析构函数在销毁类之前，释放掉申请的内存空间，避免内存泄漏。

类析构顺序：1）派生类本身的析构函数；2）对象成员析构函数；3）基类析构函数。

13、map和set有什么区别，分别又是怎么实现的？

map和set都是C++的关联容器，其底层实现都是红黑树（RB-Tree）。由于 map 和set所开放的各种操作接口，RB-tree 也都提供了，所以几乎所有的 map 和set的操作行为，都只是转调 RB-tree 的操作行为。

map和set区别在于：

（1）map中的元素是key-value（关键字—值）对：关键字起到索引的作用，值则表示与索引相关联的数据；Set与之相对就是关键字的简单集合，set中每个元素只包含一个关键字。

（2）set的迭代器是const的，不允许修改元素的值；map允许修改value，但不允许修改key。其原因是因为map和set是根据关键字排序来保证其有序性的，如果允许修改key的话，那么首先需要删除该键，然后调节平衡，再插入修改后的键值，调节平衡，如此一来，严重破坏了map和set的结构，导致iterator失效，不知道应该指向改变前的位置，还是指向改变后的位置。所以STL中将set的迭代器设置成const，不允许修改迭代器的值；而map的迭代器则不允许修改key值，允许修改value值。

（3）map支持下标操作，set不支持下标操作。map可以用key做下标，map的下标运算符[ ]将关键码作为下标去执行查找，如果关键码不存在，则插入一个具有该关键码和mapped_type类型默认值的元素至map中，因此下标运算符[ ]在map应用中需要慎用，const_map不能用，只希望确定某一个关键值是否存在而不希望插入元素时也不应该使用，mapped_type类型没有默认值也不应该使用。如果find能解决需要，尽可能用find。

14、C++中类成员的访问权限有哪些？

C++通过 public、protected、private 三个关键字来控制成员变量和成员函数的访问权限，它们分别表示公有的、受保护的、私有的，被称为成员访问限定符。在类的内部（定义类的代码内部），无论成员被声明为 public、protected 还是 private，都是可以互相访问的，没有访问权限的限制。在类的外部（定义类的代码之外），只能通过对象访问成员，并且通过对象只能访问 public 属性的成员，不能访问 private、protected 属性的成员。

private和protected的区别是，子类的对象也可以访问protected，但只有本类的对象可以访问private。子类的对象也可以访问private，但只有本类的对象可以访问protected。

15、C++中struct和class的区别？

在C++中，可以用struct和class定义类，都可以继承。区别在于：struct的默认继承权限和默认访问权限是public，而class的默认继承权限和默认访问权限是private。

16、一个C++源文件从文本到可执行文件经历的过程？

对于C++源文件，从文本到可执行文件一般需要四个过程：

预处理阶段：对源代码文件中文件包含关系（头文件）、预编译语句（宏定义）进行分析和替换，生成预编译文件。

编译阶段：将经过预处理后的预编译文件转换成特定汇编代码，生成汇编文件

汇编阶段：将编译阶段生成的汇编文件转化成机器码，生成可重定位目标文件

链接阶段：将多个目标文件及所需要的库连接成最终的可执行目标文件

17、include头文件的顺序以及双引号””和尖括号<>的区别？

Include头文件的顺序：对于include的头文件来说，如果在文件a.h中声明一个在文件b.h中定义的变量，而不引用b.h。那么要在a.c文件中引用b.h文件，并且要先引用b.h，后引用a.h,否则汇报变量类型未声明错误。

双引号和尖括号的区别：编译器预处理阶段查找头文件的路径不一样。

对于使用双引号包含的头文件，查找头文件路径的顺序为：

当前头文件目录

编译器设置的头文件路径（编译器可使用-I显式指定搜索路径）

系统变量CPLUS_INCLUDE_PATH/C_INCLUDE_PATH指定的头文件路径

对于使用尖括号包含的头文件，查找头文件的路径顺序为：

编译器设置的头文件路径（编译器可使用-I显式指定搜索路径）

系统变量CPLUS_INCLUDE_PATH/C_INCLUDE_PATH指定的头文件路径

18、malloc的原理，另外brk系统调用和mmap系统调用的作用分别是什么？

Malloc函数用于动态分配内存。为了减少内存碎片和系统调用的开销，malloc其采用内存池的方式，先申请大块内存作为堆区，然后将堆区分为多个内存块，以块作为内存管理的基本单位。当用户申请内存时，直接从堆区分配一块合适的空闲块。Malloc采用隐式链表结构将堆区分成连续的、大小不一的块，包含已分配块和未分配块；同时malloc采用显示链表结构来管理所有的空闲块，即使用一个双向链表将空闲块连接起来，每一个空闲块记录了一个连续的、未分配的地址。

当进行内存分配时，Malloc会通过隐式链表遍历所有的空闲块，选择满足要求的块进行分配；当进行内存合并时，malloc采用边界标记法，根据每个块的前后块是否已经分配来决定是否进行块合并。

Malloc在申请内存时，一般会通过brk或者mmap系统调用进行申请。其中当申请内存小于128K时，会使用系统函数brk在堆区中分配；而当申请内存大于128K时，会使用系统函数mmap在映射区分配。

19、C++的内存管理是怎样的？

在C++中，虚拟内存分为代码段、数据段、BSS段、堆区、文件映射区以及栈区六部分。

代码段:包括只读存储区和文本区，其中只读存储区存储字符串常量，文本区存储程序的机器代码。

数据段：存储程序中已初始化的全局变量和静态变量

bss 段：存储未初始化的全局变量和静态变量（局部+全局），以及所有被初始化为0的全局变量和静态变量。

堆区：调用new/malloc函数时在堆区动态分配内存，同时需要调用delete/free来手动释放申请的内存。

映射区:存储动态链接库以及调用mmap函数进行的文件映射

栈区：使用栈空间存储函数的返回地址、参数、局部变量、返回值

20、如何判断内存泄漏？

内存泄漏通常是由于调用了malloc/new等内存申请的操作，但是缺少了对应的free/delete。为了判断内存是否泄露，我们一方面可以使用linux环境下的内存泄漏检查工具Valgrind,另一方面我们在写代码时可以添加内存申请和释放的统计功能，统计当前申请和释放的内存是否一致，以此来判断内存是否泄露。

21、什么时候会发生段错误？

段错误通常发生在访问非法内存地址的时候，具体来说分为以下几种情况：

使用野指针

试图修改字符串常量的内容

22、new和malloc的区别？

1、new分配内存按照数据类型进行分配，malloc分配内存按照指定的大小分配；

2、new返回的是指定对象的指针，而malloc返回的是void*，因此malloc的返回值一般都需要进行类型转化。

3、new不仅分配一段内存，而且会调用构造函数，malloc不会。

4、new分配的内存要用delete销毁，malloc要用free来销毁；delete销毁的时候会调用对象的析构函数，而free则不会。

5、new是一个操作符可以重载，malloc是一个库函数。

6、malloc分配的内存不够的时候，可以用realloc扩容。扩容的原理？new没用这样操作。

7、new如果分配失败了会抛出bad_malloc的异常，而malloc失败了会返回NULL。

8、申请数组时： new[]一次分配所有内存，多次调用构造函数，搭配使用delete[]，delete[]多次调用析构函数，销毁数组中的每个对象。而malloc则只能sizeof(int) * n。

23、A* a = new A; a->i = 10;在内核中的内存分配上发生了什么？

1）A *a：a是一个局部变量，类型为指针，故而操作系统在程序栈区开辟4/8字节的空间（0x000m），分配给指针a。

2）new A：通过new动态的在堆区申请类A大小的空间（0x000n）。

3）a = new A：将指针a的内存区域填入栈中类A申请到的地址的地址。即*（0x000m）=0x000n。

4）a->i：先找到指针a的地址0x000m，通过a的值0x000n和i在类a中偏移offset，得到a->i的地址0x000n + offset，进行*(0x000n + offset) = 10的赋值操作，即内存0x000n + offset的值是10。

24、一个类，里面有static，virtual，之类的，来说一说这个类的内存分布？

1、static修饰符

1）static修饰成员变量

对于非静态数据成员，每个类对象都有自己的拷贝。而静态数据成员被当做是类的成员，无论这个类被定义了多少个，静态数据成员都只有一份拷贝，为该类型的所有对象所共享(包括其派生类)。所以，静态数据成员的值对每个对象都是一样的，它的值可以更新。

因为静态数据成员在全局数据区分配内存，属于本类的所有对象共享，所以它不属于特定的类对象，在没有产生类对象前就可以使用。

2）static修饰成员函数

与普通的成员函数相比，静态成员函数由于不是与任何的对象相联系，因此它不具有this指针。从这个意义上来说，它无法访问属于类对象的非静态数据成员，也无法访问非静态成员函数，只能调用其他的静态成员函数。

Static修饰的成员函数，在代码区分配内存。

2、C++继承和虚函数

C++多态分为静态多态和动态多态。静态多态是通过重载和模板技术实现，在编译的时候确定。动态多态通过虚函数和继承关系来实现，执行动态绑定，在运行的时候确定。

动态多态实现有几个条件：

(1) 虚函数；

(2) 一个基类的指针或引用指向派生类的对象；

基类指针在调用成员函数(虚函数)时，就会去查找该对象的虚函数表。虚函数表的地址在每个对象的首地址。查找该虚函数表中该函数的指针进行调用。

每个对象中保存的只是一个虚函数表的指针，C++内部为每一个类维持一个虚函数表，该类的对象的都指向这同一个虚函数表。

虚函数表中为什么就能准确查找相应的函数指针呢？因为在类设计的时候，虚函数表直接从基类也继承过来，如果覆盖了其中的某个虚函数，那么虚函数表的指针就会被替换，因此可以根据指针准确找到该调用哪个函数。

3、virtual修饰符

如果一个类是局部变量则该类数据存储在栈区，如果一个类是通过new/malloc动态申请的，则该类数据存储在堆区。

如果该类是virutal继承而来的子类，则该类的虚函数表指针和该类其他成员一起存储。虚函数表指针指向只读数据段中的类虚函数表，虚函数表中存放着一个个函数指针，函数指针指向代码段中的具体函数。

如果类中成员是virtual属性，会隐藏父类对应的属性。

25、静态变量什么时候初始化？

静态变量存储在虚拟地址空间的数据段和bss段，C语言中其在代码执行之前初始化，属于编译期初始化。而C++中由于引入对象，对象生成必须调用构造函数，因此C++规定全局或局部静态对象当且仅当对象首次用到时进行构造。

26、TCP怎么保证可靠性？

TCP保证可靠性：

（1）序列号、确认应答、超时重传

数据到达接收方，接收方需要发出一个确认应答，表示已经收到该数据段，并且确认序号会说明了它下一次需要接收的数据序列号。如果发送发迟迟未收到确认应答，那么可能是发送的数据丢失，也可能是确认应答丢失，这时发送方在等待一定时间后会进行重传。这个时间一般是2*RTT(报文段往返时间）+一个偏差值。

（2）窗口控制与高速重发控制/快速重传（重复确认应答）

TCP会利用窗口控制来提高传输速度，意思是在一个窗口大小内，不用一定要等到应答才能发送下一段数据，窗口大小就是无需等待确认而可以继续发送数据的最大值。如果不使用窗口控制，每一个没收到确认应答的数据都要重发。

使用窗口控制，如果数据段1001-2000丢失，后面数据每次传输，确认应答都会不停地发送序号为1001的应答，表示我要接收1001开始的数据，发送端如果收到3次相同应答，就会立刻进行重发；但还有种情况有可能是数据都收到了，但是有的应答丢失了，这种情况不会进行重发，因为发送端知道，如果是数据段丢失，接收端不会放过它的，会疯狂向它提醒……

（3）拥塞控制

如果把窗口定的很大，发送端连续发送大量的数据，可能会造成网络的拥堵（大家都在用网，你在这狂发，吞吐量就那么大，当然会堵），甚至造成网络的瘫痪。所以TCP在为了防止这种情况而进行了拥塞控制。

慢启动：定义拥塞窗口，一开始将该窗口大小设为1，之后每次收到确认应答（经过一个rtt），将拥塞窗口大小*2。

拥塞避免：设置慢启动阈值，一般开始都设为65536。拥塞避免是指当拥塞窗口大小达到这个阈值，拥塞窗口的值不再指数上升，而是加法增加（每次确认应答/每个rtt，拥塞窗口大小+1），以此来避免拥塞。

将报文段的超时重传看做拥塞，则一旦发生超时重传，我们需要先将阈值设为当前窗口大小的一半，并且将窗口大小设为初值1，然后重新进入慢启动过程。

快速重传：在遇到3次重复确认应答（高速重发控制）时，代表收到了3个报文段，但是这之前的1个段丢失了，便对它进行立即重传。

然后，先将阈值设为当前窗口大小的一半，然后将拥塞窗口大小设为慢启动阈值+3的大小。

这样可以达到：在TCP通信时，网络吞吐量呈现逐渐的上升，并且随着拥堵来降低吞吐量，再进入慢慢上升的过程，网络不会轻易的发生瘫痪。

27、红黑树和AVL树的定义，特点，以及二者区别

平衡二叉树（AVL树）：

平衡二叉树又称为AVL树，是一种特殊的二叉排序树。其左右子树都是平衡二叉树，且左右子树高度之差的绝对值不超过1。一句话表述为：以树中所有结点为根的树的左右子树高度之差的绝对值不超过1。将二叉树上结点的左子树深度减去右子树深度的值称为平衡因子BF，那么平衡二叉树上的所有结点的平衡因子只可能是-1、0和1。只要二叉树上有一个结点的平衡因子的绝对值大于1，则该二叉树就是不平衡的。

红黑树：

红黑树是一种二叉查找树，但在每个节点增加一个存储位表示节点的颜色，可以是红或黑（非红即黑）。通过对任何一条从根到叶子的路径上各个节点着色的方式的限制，红黑树确保没有一条路径会比其它路径长出两倍，因此，红黑树是一种弱平衡二叉树，相对于要求严格的AVL树来说，它的旋转次数少，所以对于搜索，插入，删除操作较多的情况下，通常使用红黑树。

性质：

1. 每个节点非红即黑

2. 根节点是黑的;

3. 每个叶节点（叶节点即树尾端NULL指针或NULL节点）都是黑的;

4. 如果一个节点是红色的，则它的子节点必须是黑色的。

5. 对于任意节点而言，其到叶子点树NULL指针的每条路径都包含相同数目的黑节点;

区别：

AVL 树是高度平衡的，频繁的插入和删除，会引起频繁的rebalance，导致效率下降；红黑树不是高度平衡的，算是一种折中，插入最多两次旋转，删除最多三次旋转。

28、map和unordered_map优点和缺点

对于map，其底层是基于红黑树实现的，优点如下：

1)有序性，这是map结构最大的优点，其元素的有序性在很多应用中都会简化很多的操作

2)map的查找、删除、增加等一系列操作时间复杂度稳定，都为logn

缺点如下：

1）查找、删除、增加等操作平均时间复杂度较慢，与n相关

对于unordered_map来说，其底层是一个哈希表，优点如下：

查找、删除、添加的速度快，时间复杂度为常数级O(c)

缺点如下：

因为unordered_map内部基于哈希表，以（key,value）对的形式存储，因此空间占用率高

Unordered_map的查找、删除、添加的时间复杂度不稳定，平均为O(c)，取决于哈希函数。极端情况下可能为O(n)

29、Top(K)问题

1、直接全部排序（只适用于内存够的情况）

当数据量较小的情况下，内存中可以容纳所有数据。则最简单也是最容易想到的方法是将数据全部排序，然后取排序后的数据中的前K个。

这种方法对数据量比较敏感，当数据量较大的情况下，内存不能完全容纳全部数据，这种方法便不适应了。即使内存能够满足要求，该方法将全部数据都排序了，而题目只要求找出top K个数据，所以该方法并不十分高效，不建议使用。

2、快速排序的变形 （只使用于内存够的情况）

这是一个基于快速排序的变形，因为第一种方法中说到将所有元素都排序并不十分高效，只需要找出前K个最大的就行。

这种方法类似于快速排序，首先选择一个划分元，将比这个划分元大的元素放到它的前面，比划分元小的元素放到它的后面，此时完成了一趟排序。如果此时这个划分元的序号index刚好等于K，那么这个划分元以及它左边的数，刚好就是前K个最大的元素；如果index > K，那么前K大的数据在index的左边，那么就继续递归的从index-1个数中进行一趟排序；如果index < K，那么再从划分元的右边继续进行排序，直到找到序号index刚好等于K为止。再将前K个数进行排序后，返回Top K个元素。这种方法就避免了对除了Top K个元素以外的数据进行排序所带来的不必要的开销。

3、最小堆法

这是一种局部淘汰法。先读取前K个数，建立一个最小堆。然后将剩余的所有数字依次与最小堆的堆顶进行比较，如果小于或等于堆顶数据，则继续比较下一个；否则，删除堆顶元素，并将新数据插入堆中，重新调整最小堆。当遍历完全部数据后，最小堆中的数据即为最大的K个数。

4、分治法

将全部数据分成N份，前提是每份的数据都可以读到内存中进行处理，找到每份数据中最大的K个数。此时剩下N*K个数据，如果内存不能容纳N*K个数据，则再继续分治处理，分成M份，找出每份数据中最大的K个数，如果M*K个数仍然不能读到内存中，则继续分治处理。直到剩余的数可以读入内存中，那么可以对这些数使用快速排序的变形或者归并排序进行处理。

5、Hash法

如果这些数据中有很多重复的数据，可以先通过hash法，把重复的数去掉。这样如果重复率很高的话，会减少很大的内存用量，从而缩小运算空间。处理后的数据如果能够读入内存，则可以直接排序；否则可以使用分治法或者最小堆法来处理数据。

30、栈和堆的区别，以及为什么栈要快？

堆和栈的区别：

堆是由低地址向高地址扩展；栈是由高地址向低地址扩展

堆中的内存需要手动申请和手动释放；栈中内存是由OS自动申请和自动释放，存放着参数、局部变量等内存

堆中频繁调用malloc和free,会产生内存碎片，降低程序效率；而栈由于其先进后出的特性，不会产生内存碎片

堆的分配效率较低，而栈的分配效率较高

栈的效率高的原因：

栈是操作系统提供的数据结构，计算机底层对栈提供了一系列支持：分配专门的寄存器存储栈的地址，压栈和入栈有专门的指令执行；而堆是由C/C++函数库提供的，机制复杂，需要一系列分配内存、合并内存和释放内存的算法，因此效率较低。

31、写个函数在main函数执行前先运行

__attribute((constructor))void before()

{

printf(\”before main\\n\”);

}

32、extern“C”的作用？

C++调用C函数需要extern C，因为C语言没有函数重载。

33、STL迭代器删除元素

1.对于序列容器vector,deque来说，使用erase(itertor)后，后边的每个元素的迭代器都会失效，但是后边每个元素都会往前移动一个位置，但是erase会返回下一个有效的迭代器；

2.对于关联容器map set来说，使用了erase(iterator)后，当前元素的迭代器失效，但是其结构是红黑树，删除当前元素的，不会影响到下一个元素的迭代器，所以在调用erase之前，记录下一个元素的迭代器即可。

3.对于list来说，它使用了不连续分配的内存，并且它的erase方法也会返回下一个有效的iterator。

34、vector和list的区别与应用有哪些？

1、概念：

1）Vector

连续存储的容器，动态数组，在堆上分配空间

底层实现：数组

两倍容量增长：

vector 增加（插入）新元素时，如果未超过当时的容量，则还有剩余空间，那么直接添加到最后（插入指定位置），然后调整迭代器。

如果没有剩余空间了，则会重新配置原有元素个数的两倍空间，然后将原空间元素通过复制的方式初始化新空间，再向新空间增加元素，最后析构并释放原空间，之前的迭代器会失效。

性能：

访问：O(1)

插入：在最后插入（空间够）：很快

在最后插入（空间不够）：需要内存申请和释放，以及对之前数据进行拷贝。

在中间插入（空间够）：内存拷贝

在中间插入（空间不够）：需要内存申请和释放，以及对之前数据进行拷贝。

删除：在最后删除：很快

在中间删除：内存拷贝

适用场景：经常随机访问，且不经常对非尾节点进行插入删除。

2、List

动态链表，在堆上分配空间，每插入一个元数都会分配空间，每删除一个元素都会释放空间。

底层：双向链表

性能：

访问：随机访问性能很差，只能快速访问头尾节点。

插入：很快，一般是常数开销

删除：很快，一般是常数开销

适用场景：经常插入删除大量数据

2、区别：

1）vector底层实现是数组；list是双向 链表。

2）vector支持随机访问，list不支持。

3）vector是顺序内存，list不是。

4）vector在中间节点进行插入删除会导致内存拷贝，list不会。

5）vector一次性分配好内存，不够时才进行2倍扩容；list每次插入新节点都会进行内存申请。

6）vector随机访问性能好，插入删除性能差；list随机访问性能差，插入删除性能好。

3、应用

vector拥有一段连续的内存空间，因此支持随机访问，如果需要高效的随即访问，而不在乎插入和删除的效率，使用vector。

list拥有一段不连续的内存空间，如果需要高效的插入和删除，而不关心随机访问，则应使用list。

35、STL里resize和reserve的区别？

resize()：改变当前容器内含有元素的数量(size())，eg: vectorv; v.resize(len);v的size变为len,如果原来v的size小于len，那么容器新增（len-size）个元素，元素的值为默认为0.当v.push_back(3);之后，则是3是放在了v的末尾，即下标为len，此时容器是size为len+1；

reserve()：改变当前容器的最大容量（capacity）,它不会生成元素，只是确定这个容器允许放入多少对象，如果reserve(len)的值大于当前的capacity()，那么会重新分配一块能存len个对象的空间，然后把之前v.size()个对象通过copy construtor复制过来，销毁之前的内存。

36、源码到可执行文件的过程？

1）预编译

主要处理源代码文件中的以“#”开头的预编译指令。处理规则见下

1、删除所有的#define，展开所有的宏定义。

2、处理所有的条件预编译指令，如“#if”、“#endif”、“#ifdef”、“#elif”和“#else”。

3、处理“#include”预编译指令，将文件内容替换到它的位置，这个过程是递归进行的，文件中包含其他文件。

4、删除所有的注释，“//”和“/**/”。

5、保留所有的#pragma 编译器指令，编译器需要用到他们，如：#pragma once 是为了防止有文件被重复引用。

6、添加行号和文件标识，便于编译时编译器产生调试用的行号信息，和编译时产生编译错误或警告是能够显示行号。

2）编译

把预编译之后生成的xxx.i或xxx.ii文件，进行一系列词法分析、语法分析、语义分析及优化后，生成相应的汇编代码文件。

1、词法分析：利用类似于“有限状态机”的算法，将源代码程序输入到扫描机中，将其中的字符序列分割成一系列的记号。

2、语法分析：语法分析器对由扫描器产生的记号，进行语法分析，产生语法树。由语法分析器输出的语法树是一种以表达式为节点的树。

3、语义分析：语法分析器只是完成了对表达式语法层面的分析，语义分析器则对表达式是否有意义进行判断，其分析的语义是静态语义——在编译期能分期的语义，相对应的动态语义是在运行期才能确定的语义。

4、优化：源代码级别的一个优化过程。

5、目标代码生成：由代码生成器将中间代码转换成目标机器代码，生成一系列的代码序列——汇编语言表示。

6、目标代码优化：目标代码优化器对上述的目标机器代码进行优化：寻找合适的寻址方式、使用位移来替代乘法运算、删除多余的指令等。

3）汇编

将汇编代码转变成机器可以执行的指令(机器码文件)。 汇编器的汇编过程相对于编译器来说更简单，没有复杂的语法，也没有语义，更不需要做指令优化，只是根据汇编指令和机器指令的对照表一一翻译过来，汇编过程有汇编器as完成。经汇编之后，产生目标文件(与可执行文件格式几乎一样)xxx.o(Windows下)、xxx.obj(Linux下)。

4）链接

将不同的源文件产生的目标文件进行链接，从而形成一个可以执行的程序。链接分为静态链接和动态链接：

1、静态链接：

函数和数据被编译进一个二进制文件。在使用静态库的情况下，在编译链接可执行文件时，链接器从库中复制这些函数和数据并把它们和应用程序的其它模块组合起来创建最终的可执行文件。

空间浪费：因为每个可执行程序中对所有需要的目标文件都要有一份副本，所以如果多个程序对同一个目标文件都有依赖，会出现同一个目标文件都在内存存在多个副本；

更新困难：每当库函数的代码修改了，这个时候就需要重新进行编译链接形成可执行程序。

运行速度快：但是静态链接的优点就是，在可执行程序中已经具备了所有执行程序所需要的任何东西，在执行的时候运行速度快。

2、动态链接：

动态链接的基本思想是把程序按照模块拆分成各个相对独立部分，在程序运行时才将它们链接在一起形成一个完整的程序，而不是像静态链接一样把所有程序模块都链接成一个单独的可执行文件。

共享库：就是即使需要每个程序都依赖同一个库，但是该库不会像静态链接那样在内存中存在多分，副本，而是这多个程序在执行时共享同一份副本；

更新方便：更新时只需要替换原来的目标文件，而无需将所有的程序再重新链接一遍。当程序下一次运行时，新版本的目标文件会被自动加载到内存并且链接起来，程序就完成了升级的目标。

性能损耗：因为把链接推迟到了程序运行时，所以每次执行程序都需要进行链接，所以性能会有一定损失。

37、tcp握手为什么两次不可以？为什么不用四次？

两次不可以：tcp是全双工通信，两次握手只能确定单向数据链路是可以通信的，并不能保证反向的通信正常

不用四次：

本来握手应该和挥手一样都是需要确认两个方向都能联通的，本来模型应该是：

1.客户端发送syn0给服务器

2.服务器收到syn0，回复ack(syn0+1)

3.服务器发送syn1

4.客户端收到syn1，回复ack(syn1+1)

因为tcp是全双工的，上边的四部确认了数据在两个方向上都是可以正确到达的，但是2，3步没有没有上下的联系，可以将其合并，加快握手效率，所有就变成了3步握手。

面试找工作不是一朝一夕就可以完成的事情，而且失败的面试经历未必是坏事，积累面试经验也是一种进步，希望这里可以帮到你。

学习IT相关内容，找“职坐标在线”

怎样才算学会了C++基础，一篇文章学习了解（包含Qt内容）

C++的基础语法包括以下几个方面：

  1. 注释

C++支持单行注释（以“//”开头）和多行注释（以“/”开头，“/”结尾）。

  1. 标识符

标识符是指变量、函数、类、结构体等的名称。标识符必须以字母或下划线开头，后面可以是字母、数字或下划线。C++对大小写敏感。

  1. 关键字

C++有一些关键字，这些关键字具有特殊的含义，不能用作标识符。例如：int、double、if、else、for、while等。

  1. 数据类型

C++有基本数据类型和用户自定义数据类型。基本数据类型包括整型、浮点型、字符型、布尔型等。用户自定义数据类型包括结构体、枚举、类等。

  1. 变量

变量是指用来存储数据的内存位置。定义变量时需要指定变量的数据类型和名称。变量的值可以在程序运行过程中被修改。

  1. 常量

常量是指不能被修改的值。C++有字面常量和符号常量。字面常量是指直接在代码中使用的常量值，例如：10、3.14、\’A\’等。符号常量是指用#define或const关键字定义的常量，例如：#define PI 3.14、const int MAX_NUM = 100等。

  1. 运算符

C++支持算术运算符、关系运算符、逻辑运算符、位运算符等。例如：+、-、*、/、%、==、!=、<、>、&&、||、&、|等。

  1. 控制语句

C++有选择结构和循环结构两种控制语句。选择结构包括if语句和switch语句，循环结构包括while语句、do-while语句和for语句。这些控制语句可以根据条件执行不同的代码块，从而控制程序的执行流程。

  1. 函数

预处理：预定义宏 编译：编译程序所要作得工作就是通过词法分析和语法分析，在确认所有的指令都符合语法规则之后，将其翻译成等价的中间代码表示或汇编代码。 汇编：汇编语言代码翻译成目标机器指令的过程 连接：链接程序的主要工作就是将有关的目标文件彼此相连接，也即将在一个文件中引用的符号同该符号在另外一个文件中的定义连接起来，使得所有的这些目标文件成为一个能够诶操作系统装入执行的统一整体。

C++的内存分区主要包括以下几个部分：

  1. 栈区（Stack）：由编译器自动分配和释放，存放函数的参数值、局部变量的值等，其特点是先进后出。
  2. 堆区（Heap）：一般由程序员分配和释放，若程序员不释放，程序结束时可能由操作系统回收，其特点是先进先出。
  3. 全局区（Static）：存放全局变量和静态变量，包括初始化的和未初始化的，程序结束后由操作系统回收。
  4. 常量区（Const）：存放常量，如字符串常量等，程序结束后由操作系统回收。
  5. 代码区（Code）：存放程序的代码，由操作系统分配和回收，不允许写入。

在程序运行过程中，栈区、堆区和全局区的大小可以动态变化，而常量区和代码区的大小是固定的。程序员在使用内存时，需要注意内存分配和释放，以避免内存泄漏和内存溢出等问题。

  1. 栈区：函数中的局部变量，比如：
  1. 堆区：动态分配的内存，比如：
  1. 全局区：全局变量和静态变量，比如：
  1. 常量区：常量字符串，比如：
  1. 代码区：程序的代码，比如：

C++中，引用和指针都可以用来间接访问变量，但它们之间有以下区别：

  1. 引用必须在定义时被初始化，而指针可以先定义再赋值。
  2. 引用不允许指向空，而指针可以指向空。
  3. 引用在使用时不需要解引用操作，而指针需要使用星号(*)操作符来解引用。

下面是一个例子，演示了引用和指针的使用：

输出结果：

在函数参数中，引用和指针都可以用来传递参数，但它们之间也有一些区别：

  1. 引用作为函数参数时，传递的是实参的别名，函数内部对引用的修改会直接影响到实参的值。而指针作为函数参数时，传递的是实参的地址，需要使用解引用操作符(*)来访问实参的值，函数内部对指针的修改不会影响到实参的地址，但可以通过指针解引用修改实参的值。
  2. 引用作为函数参数时，不需要使用取地址符(&)来传递参数，而指针作为函数参数时需要使用取地址符(&)来传递参数。
  3. 引用作为函数参数时，不能为null，而指针作为函数参数时可以为null。

下面是一个例子，演示了引用和指针作为函数参数的使用：

输出结果：

可以看到，通过引用和指针都可以修改实参的值，但引用更加简洁，不需要使用解引用操作符(*)，并且可以避免空指针的问题。但指针可以指向null，有时候也是很有用的。

C++的构造函数和析构函数是特殊的成员函数，用于在对象创建和销毁时执行特定的操作。构造函数用于初始化对象的成员变量，而析构函数用于释放对象占用的资源。

以下是一个示例代码：

注意事项：

  1. 构造函数和析构函数的名称与类名相同，且没有返回类型。
  2. 构造函数可以有参数，用于初始化成员变量，也可以没有参数。
  3. 如果没有定义构造函数，则编译器会生成默认的构造函数。
  4. 如果一个类定义了析构函数，则编译器不会生成默认的析构函数。
  5. 构造函数和析构函数的访问权限可以是public、protected或private。
  6. 构造函数和析构函数不能被继承。
  7. 在构造函数中，可以使用初始化列表来初始化成员变量，这比在构造函数体中赋值更高效。
  8. 在析构函数中，应该释放对象占用的资源，如堆内存、文件句柄等。

C++的三大特征是：

  1. 封装

封装是将数据和操作数据的方法（函数）组合在一起，形成一个类。类将数据和方法封装在一起，使得数据不能被外部直接访问和修改，只能通过类的公共接口进行访问和修改。这样可以保证数据的安全性和可靠性，同时也提高了代码的可维护性和可扩展性。

下面举一个例子来说明封装的概念。假设我们要写一个银行账户管理系统，每个账户包括账户名称、账户号码、账户余额等信息。我们可以定义一个Account类来封装这些信息，具体实现如下：

在上面的代码中，我们将数据成员（name、number、balance）声明为私有的，外部代码无法直接访问和修改这些数据。同时，我们提供了公共成员函数（getName、getNumber、getBalance、deposit、withdraw）来访问和修改这些数据。这样，外部代码只能通过公共接口来操作数据，从而保证了数据的安全性和可靠性。

例如，我们可以通过以下代码创建一个账户对象，并进行存款和取款操作：

通过封装，我们可以将数据和操作数据的方法封装在一起，提高了代码的可维护性和可扩展性，同时也保证了数据的安全性和可靠性。

  1. 继承

继承是指一个类可以从另一个类中继承属性和方法。被继承的类称为基类或父类，继承的类称为派生类或子类。子类可以重写父类的方法，也可以添加新的属性和方法。继承可以提高代码的重用性和扩展性，同时也可以实现多态性。

C++继承是面向对象编程中的一种重要概念，它允许一个类继承另一个类的属性和方法。C++支持单继承和多继承两种方式。

单继承：一个派生类只能继承一个基类的属性和方法。语法格式如下：

继承方式可以是public、protected或private，分别表示公有继承、保护继承和私有继承。

下面是一个简单的单继承示例：

在这个示例中，Animal是基类，Cat是派生类。Cat继承了Animal的属性和方法，并且添加了自己的方法meow。创建Cat的实例后，可以调用父类的方法eat和子类自己的方法meow。

多继承：一个派生类可以继承多个基类的属性和方法。语法格式如下：

下面是一个简单的多继承示例：

在这个示例中，Bird继承了Animal和Flyable两个基类的属性和方法，并且添加了自己的方法chirp。创建Bird的实例后，可以调用父类的方法eat和fly以及子类自己的方法chirp。

C++继承还涉及到虚函数、重载、多态等高级特性，这些特性可以更好地组织和管理复杂的程序。

  1. 多态

多态是指同一种类型的对象，在不同的情况下表现出不同的行为。C++实现多态的方式有两种：虚函数和模板。虚函数是指在基类中定义一个虚函数，在派生类中可以重写该函数，通过基类指针或引用调用该函数时，会根据指向的对象类型来调用相应的函数。模板是指定义一个通用的函数或类，可以接受不同类型的参数，根据参数类型的不同，会生成不同的函数或类，从而实现多态。多态可以提高代码的灵活性和可扩展性。

C++多态是面向对象编程中的一种重要概念，它允许不同的对象对同一个消息作出不同的响应。多态可以提高代码的可维护性和可扩展性，使得程序更加灵活。

C++多态实现的基础是虚函数（Virtual Function），虚函数是在基类中声明的函数，在派生类中可以被重写（Override）。通过在基类中将函数声明为虚函数，可以使得派生类中的同名函数自动成为虚函数，并且可以被动态绑定（Dynamic Binding）。

下面是一个简单的多态示例：

在这个示例中，Animal是基类，Cat和Dog是派生类。Animal中的speak函数被声明为虚函数，Cat和Dog重写了speak函数。创建Animal的指针指向Cat和Dog的实例后，调用speak函数会根据实际指向的对象来动态绑定，从而实现了多态。

C++多态还可以通过抽象类（Abstract Class）和纯虚函数（Pure Virtual Function）实现。抽象类是不能被实例化的类，它包含至少一个纯虚函数，纯虚函数是没有实现的虚函数，派生类必须重写纯虚函数才能被实例化。抽象类和纯虚函数可以强制规定派生类必须实现的接口，从而使得程序更加健壮和可靠。

C++中的模板是一种通用的编程工具，它允许我们编写可重用的代码，以适应不同类型的数据。模板可以定义类模板和函数模板，其中类模板用于定义通用的数据类型，而函数模板用于定义通用的函数。

类模板示例：

在此示例中，我们定义了一个名为myVector的类模板，它使用类型T作为参数。该类有一个私有数据成员data，它是一个指向T类型的指针，还有一个size变量，用于存储向量的大小。该类还定义了一个构造函数和一个运算符[]，用于访问向量中的元素。

函数模板示例：

在此示例中，我们定义了一个名为maximum的函数模板，它使用类型T作为参数。该函数接受两个参数x和y，它们必须是相同类型的。该函数比较x和y的值，并返回较大的那个。

使用模板的示例：

在此示例中，我们首先创建了一个myVector对象v，它存储了5个整数。然后，我们使用maximum函数模板来比较不同类型的值，例如整数、浮点数和字符。这些值都是模板参数T的实例化。

C++11是C++语言的一个重要版本，引入了许多新特性，包括语言特性、标准库特性等。下面是C++11的一些新特性：

  1. 自动类型推导（auto关键字）

C++11引入了auto关键字，可以自动推导变量的类型：

  1. 基于范围的for循环（range-based for循环）

C++11引入了基于范围的for循环，可以方便地遍历容器中的元素：

  1. nullptr关键字

C++11引入了nullptr关键字，可以代替NULL指针常量：

  1. 右值引用（rvalue reference）

C++11引入了右值引用，可以绑定到右值表达式上：

右值引用可以用于实现移动语义和完美转发。

  1. 移动语义（move semantics）

C++11引入了移动语义，可以将资源所有权从一个对象转移到另一个对象，避免不必要的复制操作：

  1. lambda表达式

C++11引入了lambda表达式，可以方便地定义匿名函数：

  1. constexpr关键字

C++11引入了constexpr关键字，可以在编译时求值：

  1. 智能指针（smart pointers）

C++11引入了智能指针，可以自动管理资源的生命周期，避免内存泄漏：

  1. 回调函数
  1. thread多线程与共享内存&互斥量mutex

STL（Standard Template Library）是C++标准库的一个重要组成部分，它提供了一组通用的模板类和函数，用于实现各种常用的数据结构和算法，如容器、迭代器、算法和函数对象等，使得C++程序员可以更加方便地进行编程。

STL库的主要组成部分包括以下几个方面：

  1. 容器（Containers）：STL提供了多种容器，如vector、list、deque、set、map等，用于存储和管理不同类型的数据。这些容器实现了各种不同的数据结构，如数组、链表、树等，提供了丰富的接口和算法，方便快捷地进行数据操作。
  2. 迭代器（Iterators）：STL提供了多种迭代器，如输入迭代器、输出迭代器、前向迭代器、双向迭代器、随机访问迭代器等，用于遍历容器中的元素。迭代器提供了一种统一的接口，使得算法和容器之间可以进行无缝协作。
  3. 算法（Algorithms）：STL提供了大量的算法，如排序、查找、拷贝、变换等，用于对容器中的元素进行处理。这些算法实现了各种常用的操作，如查找最大值、计算总和、去重复等，可以大大提高程序的效率和可读性。
  4. 函数对象（Function Objects）：STL提供了多种函数对象，如一元函数对象、二元函数对象、谓词等，用于对容器中的元素进行操作。函数对象提供了一种方便的方式，使得程序员可以自定义算法和操作，从而更好地适应不同的需求。

STL库的使用可以大大提高C++程序的效率和可读性，同时也为程序员提供了更多的便利。在实际编程中，程序员可以根据不同的需求，选择合适的容器、迭代器、算法和函数对象，从而实现高效的数据操作和算法实现。

  1. 饿汉模式：

在程序启动时就创建单例对象，因此也被称为“饱汉模式”。线程安全性较好，但是可能会浪费资源。

  1. 懒汉模式：

只有当需要使用单例对象时才进行创建，因此也被称为“懒汉模式”。需要考虑线程安全问题，否则可能会导致多个线程同时创建单例对象。

线程安全问题可以通过加锁实现，例如使用std::mutex：

  1. 数组（Array）：一组连续的内存单元，用于存储同种类型的数据。
  2. 链表（Linked List）：一组不连续的内存单元，用指针连接起来，可以动态地添加或删除元素。
  3. 栈（Stack）：一种后进先出（LIFO）的数据结构，只能在栈顶进行插入和删除操作。
  4. 队列（Queue）：一种先进先出（FIFO）的数据结构，只能在队尾进行插入操作，在队头进行删除操作。
  5. 树（Tree）：一种非线性数据结构，由节点和边组成，每个节点可以有多个子节点。
  6. 图（Graph）：一种非线性数据结构，由节点和边组成，每个节点可以有多个相邻节点。
  7. 堆（Heap）：一种特殊的树形数据结构，常用于实现优先队列。
  8. 哈希表（Hash Table）：一种通过散列函数将键映射到值的数据结构，可以实现高效的查找和插入操作。

稳定，平均/最差时间复杂度 O(n²)，元素基本有序时最好时间复杂度 O(n)，空间复杂度 O(1)。

每一趟将一个待排序记录按其关键字的大小插入到已排好序的一组记录的适当位置上，直到所有待排序记录全部插入为止。

直接插入没有利用到要插入的序列已有序的特点，插入第 i 个元素时可以通过二分查找找到插入位置 insertIndex，再把 i~insertIndex 之间的所有元素后移一位，把第 i 个元素放在插入位置上。

又称缩小增量排序，是对直接插入排序的改进，不稳定，平均时间复杂度 O(n^1.3^)，最差时间复杂度 O(n²)，最好时间复杂度 O(n)，空间复杂度 O(1)。

把记录按下标的一定增量分组，对每组进行直接插入排序，每次排序后减小增量，当增量减至 1 时排序完毕。

不稳定，时间复杂度 O(n²)，空间复杂度 O(1)。

每次在未排序序列中找到最小元素，和未排序序列的第一个元素交换位置，再在剩余未排序序列中重复该操作直到所有元素排序完毕。

是对直接选择排序的改进，不稳定，时间复杂度 O(nlogn)，空间复杂度 O(1)。

将待排序记录看作完全二叉树，可以建立大根堆或小根堆，大根堆中每个节点的值都不小于它的子节点值，小根堆中每个节点的值都不大于它的子节点值。

以大根堆为例，在建堆时首先将最后一个节点作为当前节点，如果当前节点存在父节点且值大于父节点，就将当前节点和父节点交换。在移除时首先暂存根节点的值，然后用最后一个节点代替根节点并作为当前节点，如果当前节点存在子节点且值小于子节点，就将其与值较大的子节点进行交换，调整完堆后返回暂存的值。

稳定，平均/最坏时间复杂度 O(n²)，元素基本有序时最好时间复杂度 O(n)，空间复杂度 O(1)。

比较相邻的元素，如果第一个比第二个大就进行交换，对每一对相邻元素做同样的工作，从开始第一对到结尾的最后一对，每一轮排序后末尾元素都是有序的，针对 n 个元素重复以上步骤 n -1 次排序完毕。

当序列已经有序时仍会进行不必要的比较，可以设置一个标志记录是否有元素交换，如果没有直接结束比较。

是对冒泡排序的一种改进，不稳定，平均/最好时间复杂度 O(nlogn)，元素基本有序时最坏时间复杂度 O(n²)，空间复杂度 O(logn)。

首先选择一个基准元素，通过一趟排序将要排序的数据分割成独立的两部分，一部分全部小于等于基准元素，一部分全部大于等于基准元素，再按此方法递归对这两部分数据进行快速排序。

快速排序的一次划分从两头交替搜索，直到 low 和 high 指针重合，一趟时间复杂度 O(n)，整个算法的时间复杂度与划分趟数有关。

最好情况是每次划分选择的中间数恰好将当前序列等分，经过 log(n) 趟划分便可得到长度为 1 的子表，这样时间复杂度 O(nlogn)。

最坏情况是每次所选中间数是当前序列中的最大或最小元素，这使每次划分所得子表其中一个为空表 ，这样长度为 n 的数据表需要 n 趟划分，整个排序时间复杂度 O(n²)。

归并排序基于归并操作，是一种稳定的排序算法，任何情况时间复杂度都为 O(nlogn)，空间复杂度为 O(n)。

基本原理：应用分治法将待排序序列分成两部分，然后对两部分分别递归排序，最后进行合并，使用一个辅助空间并设定两个指针分别指向两个有序序列的起始元素，将指针对应的较小元素添加到辅助空间，重复该步骤到某一序列到达末尾，然后将另一序列剩余元素合并到辅助空间末尾。

适用场景：数据量大且对稳定性有要求的情况。

数据量规模较小，考虑直接插入或直接选择。当元素分布有序时直接插入将大大减少比较和移动记录的次数，如果不要求稳定性，可以使用直接选择，效率略高于直接插入。

数据量规模中等，选择希尔排序。

数据量规模较大，考虑堆排序（元素分布接近正序或逆序）、快速排序（元素分布随机）和归并排序（稳定性）。

TCP的Socket套接字是一种可靠的网络通信协议，它可以确保数据的完整性、有序性和可靠性。在C++中实现TCP的Socket套接字的客户端与服务端通信，主要分为以下几个步骤：

  1. 创建Socket：使用socket()函数创建一个Socket对象，指定协议类型和通信方式。
  2. 绑定地址：服务端需要使用bind()函数将Socket对象与一个本地地址绑定，客户端则不需要。
  3. 监听连接：服务端需要使用listen()函数开始监听客户端的连接请求，客户端不需要。
  4. 建立连接：客户端使用connect()函数向服务端发起连接请求，服务端使用accept()函数接受客户端的连接请求。
  5. 通信：客户端和服务端通过send()和recv()函数进行数据的发送和接收。
  6. 关闭连接：客户端和服务端使用close()函数关闭连接。

下面是一个简单的TCP Socket通信的例子，其中包含了客户端和服务端的代码：

服务端代码：

客户端代码：

在上面的例子中，服务端监听本地地址8080端口的连接请求，并在接受到客户端的连接请求后，接收客户端发送的消息，并发送一个回复消息。客户端连接到本地地址为127.0.0.1的8080端口，并发送一条消息给服务端，然后接收服务端发送的回复消息。最后，客户端和服务端都关闭连接。

UDP的Socket套接字是一种无连接的网络通信协议，它不保证数据的可靠性和有序性，但是具有较低的延迟和较高的传输速率。在C++中实现UDP的Socket套接字的客户端与服务端通信，主要分为以下几个步骤：

  1. 创建Socket：使用socket()函数创建一个Socket对象，指定协议类型和通信方式。
  2. 绑定地址：服务端和客户端都可以使用bind()函数将Socket对象与一个本地地址绑定。
  3. 通信：客户端和服务端通过sendto()和recvfrom()函数进行数据的发送和接收。
  4. 关闭Socket：客户端和服务端使用close()函数关闭Socket。

下面是一个简单的UDP Socket通信的例子，其中包含了客户端和服务端的代码：

服务端代码：

客户端代码：

在上面的例子中，服务端监听本地地址8080端口的UDP连接请求，并在接受到客户端的连接请求后，接收客户端发送的消息，并发送一个回复消息。客户端连接到本地地址为127.0.0.1的8080端口，并发送一条消息给服务端，然后接收服务端发送的回复消息。最后，客户端和服务端都关闭Socket。

  1. 连接数据库: mysql -u username -p password -h hostname
  2. 显示数据库列表: show databases;
  3. 创建数据库: create database dbname;
  4. 选择数据库: use dbname;
  5. 显示数据表: show tables;
  6. 创建数据表: create table tablename(column1 datatype, column2 datatype, …);
  7. 插入数据: insert into tablename(column1, column2, …) values(value1, value2, …);
  8. 查询数据: select * from tablename;
  9. 更新数据: update tablename set column1=value1, column2=value2 where condition;
  10. 删除数据: delete from tablename where condition;
  11. 删除数据表: drop table tablename;
  12. 删除数据库: drop database dbname;
  13. 导入数据: source filename.sql;
  14. 导出数据: mysqldump -u username -p password dbname > filename.sql

以下是一个具体的例子，假设我们有一个学生表（students）和一个成绩表（scores），它们的结构如下：

学生表（students）：

成绩表（scores）：

现在我们可以使用以下命令和操作来查询和处理这些数据：现在我们可以使用以下命令和操作来查询和处理这些数据：

  1. 连接数据库: mysql -u root -p password -h localhost
  2. 显示数据库列表: show databases;
  3. 创建数据库: create database mydb;
  4. 选择数据库: use mydb;
  5. 显示数据表: show tables;
  6. 创建数据表:
  1. 插入数据:
  1. 查询数据:
  1. 更新数据:
  1. 删除数据:
  1. 删除数据表:
  1. 删除数据库:
  1. 导入数据:
  1. 导出数据:
  1. Linux是一种开源的、免费的操作系统，其内核由Linus Torvalds在1991年创建，现在已经成为了世界上最流行的操作系统之一。
  2. 常用命令：
  3. ls：列出目录下的文件和子目录。
  4. cd：切换当前目录。
  5. pwd：显示当前所在目录的路径。
  6. mkdir：创建一个新目录。
  7. rm：删除文件或目录。
  8. cp：复制文件或目录。
  9. mv：移动或重命名文件或目录。
  10. cat：查看文件内容。
  11. grep：在文件中查找指定字符串。
  12. chmod：修改文件或目录的权限。

Vim是一款文本编辑器，常用于Linux和Unix系统中。它是Vi编辑器的改进版，具有强大的编辑功能和高度的可定制性。以下是Vim的一些常用命令：

  • i：在当前光标位置插入文本。
  • a：在当前光标位置的下一个字符处插入文本。
  • o：在当前光标行的下一行插入新行。
  • Esc：退出插入模式，回到命令模式。
  • :w：保存文件。
  • :q：退出Vim。
  • :q!：强制退出Vim，不保存修改。
  • :wq：保存文件并退出Vim。
  • yy：复制当前行。
  • p：将复制的文本粘贴到当前光标位置。
  • dd：删除当前行。

除了这些基本命令之外，Vim还有许多其他的高级功能，如宏录制、多窗口编辑、代码折叠等等。Vim的学习曲线可能比较陡峭，但是一旦掌握了它的基本操作，就能够提高文本编辑的效率。

  1. 下面是一个简单的C++程序，使用Vim编辑器进行编辑：
  2. 打开一个终端窗口，输入以下命令启动Vim编辑器：vim hello.cpp这将创建一个名为“hello.cpp”的新文件，并在Vim中打开它。
  3. 进入插入模式，输入以下代码：#include <iostream>int main(){std::cout << \”Hello, world!\” << std::endl;return 0;}这个程序会输出“Hello, world!”，然后返回0。
  4. 保存文件并退出Vim。首先按下Esc键，回到命令模式，然后输入以下命令：:wq这将保存文件并退出Vim。
  5. 使用GCC编译器编译程序。在终端窗口中输入以下命令：g++ -o hello hello.cpp这将生成一个名为“hello”的可执行文件。
  6. 运行程序。在终端窗口中输入以下命令：./hello这将运行程序，并输出“Hello, world!”。

Qt是一种跨平台的GUI应用程序开发框架，提供了一系列的工具和类库，使开发者可以方便地开发高质量的跨平台应用程序。Qt的主要内容包括以下几个方面：

  1. Qt核心模块：提供了Qt的基本功能，包括对象模型、信号和槽机制、容器类、文件和IO操作、多线程等。
  2. Qt Widgets模块：提供了一系列基于QWidget的GUI控件，如按钮、标签、文本框等，用于构建传统的桌面应用程序。
  3. Qt Quick模块：提供了一种基于QML的声明式语言，用于构建现代的用户界面，支持动画、视觉效果等。
  4. Qt网络模块：提供了网络编程相关的类库，如TCP和UDP套接字、HTTP和FTP协议等。
  5. Qt数据库模块：提供了用于访问各种关系型数据库的类库，如MySQL、PostgreSQL、SQLite等。
  6. Qt多媒体模块：提供了音频和视频处理相关的类库，如播放音频和视频、录制音频和视频等。
  7. Qt图形和绘图模块：提供了用于2D和3D图形渲染相关的类库，如OpenGL、QPainter等。
  8. Qt Web模块：提供了用于Web开发相关的类库，如Webkit和WebEngine。

除了以上这些模块之外，Qt还提供了一些其他的工具和类库，如Qt Creator集成开发环境、Qt Quick Controls用于构建移动应用程序等。总的来说，Qt是一个功能强大、可扩展、易于使用的开发框架，适用于开发各种不同类型的跨平台应用程序。

信号和槽机制是Qt框架中的一种事件处理机制，用于在对象之间进行通信。信号是一种特殊的函数，当特定的事件发生时，会自动调用信号，而槽则是一种函数，用于响应信号。

在Qt中，一个对象可以有多个信号和槽，它们可以在不同的对象之间连接起来，实现对象之间的通信。当信号被触发时，与之连接的槽函数会被自动调用，从而实现了对象之间的协作。

使用信号和槽机制可以使代码更加灵活、可维护和可扩展。它可以帮助开发人员更好地组织代码，降低代码的耦合度，并提高程序的可读性和可维护性。

下面是一个简单的例子，演示如何在两个对象之间使用信号和槽机制进行通信。

假设有一个窗口类和一个按钮类，当按钮被点击时，窗口会显示一个消息框。代码如下：

在上面的代码中，我们创建了一个窗口类MyWindow和一个按钮类MyButton。在窗口类的构造函数中，我们创建了一个按钮，并将其连接到窗口类的showMessage()槽函数上。当按钮被点击时，就会触发clicked()信号，进而自动调用showMessage()槽函数，从而显示一个消息框。

这就是一个简单的使用信号和槽机制的例子。通过信号和槽的连接，我们实现了按钮和窗口之间的通信，使程序更加灵活和可扩展。

以下是一个使用Qt5的版本的信号和槽机制的例子：

在这个例子中，我们使用了Qt5的新语法来连接信号和槽。具体来说，我们使用了connect()函数的新语法，将信号和槽通过函数指针连接起来。

在按钮类的构造函数中，我们创建了一个按钮，并将其连接到窗口类的showMessage()槽函数上。当按钮被点击时，就会触发clicked()信号，进而自动调用showMessage()槽函数，从而显示一个消息框。

这个例子和之前的例子类似，只是使用了Qt5的新语法来连接信号和槽。这种新语法更加简洁明了，使代码更加可读性和可维护性。

  1. QMainWindow：主窗口，包括菜单栏、工具栏、状态栏等。例如：Qt Creator的主窗口。
  2. QDialog：对话框窗口，用于显示对话框，例如：文件选择对话框、颜色选择对话框等。
  3. QWidget：基本窗口，用于显示各种控件，例如：按钮、文本框、标签等。
  4. QDockWidget：浮动窗口，可以被拖拽到主窗口的四周，例如：Qt Creator的工程浏览器、属性编辑器等。
  5. QSplashScreen：启动画面，用于显示程序启动时的欢迎画面。例如：各种桌面应用程序的启动画面。

Qt中常用的控件有很多，下面列举一些常用的控件，并给出简单的例子：

  1. QPushButton（按钮控件）
  1. QLabel（标签控件）
  1. QLineEdit（文本框控件）
  1. QTextEdit（多行文本框控件）
  1. QComboBox（下拉框控件）
  1. QSpinBox（数字框控件）
  1. QSlider（滑动条控件）

这些控件只是Qt中的一部分，Qt还提供了很多其他的控件，如QCheckBox、QRadioButton、QTableWidget、QTreeWidget等等。这些控件可以帮助我们快速构建各种类型的界面，提高开发效率。

Qt中的样式表是一种用于定制控件外观的机制，类似于CSS。通过样式表，可以改变控件的颜色、字体、边框等属性，从而实现自定义的外观效果。

以下是一些常用的样式表属性和例子：

  1. background-color：设置控件的背景颜色。例如：QPushButton { background-color: red; }
  2. color：设置控件的前景颜色（即文本颜色）。例如：QLabel { color: blue; }
  3. font-size：设置控件的字体大小。例如：QLineEdit { font-size: 12px; }
  4. border：设置控件的边框。例如：QGroupBox { border: 1px solid black; }
  5. padding：设置控件的内边距（即控件内容与边框之间的距离）。例如：QLineEdit { padding: 5px; }
  6. margin：设置控件的外边距（即控件边框与周围控件之间的距离）。例如：QLabel { margin: 10px; }

这些样式表属性可以组合使用，实现更丰富的外观效果。例如，以下样式表将QPushButton的背景颜色设置为蓝色，边框为圆角，字体为白色，内边距为10px：

QPushButton { background-color: blue; border-radius: 5px; color: white; padding: 10px; }

学习C++不是一蹴而就的，是终身的，基础部分十分的重要，需要反复的学习和体会，学习的过程中，出现了错误才深刻。

本文作者及来源:Renderbus瑞云渲染农场https://www.renderbus.com

点赞 0
收藏 0

文章为作者独立观点不代本网立场，未经允许不得转载。

继续阅读本文相关话题

TAG
全部
行业动态
C4D教程
C4D百科