[C++知识库]游戏客户端春招准备

目录

C++基础

继承

重载、重写（覆盖）、隐藏（重定义）

多态、虚函数（???）

内存管理（内存分配、内存对齐）（???）

类型转换（??）

智能指针（?）

各种关键字

左值右值，右值引用

内联函数与宏

其他杂项

C++基础

• 全局与局部都定义一个静态变量会有什么样的结果

静态变量生存期为整个程序期间，但只能在函数内部被使用，当在函数内部使用全局已有的同名变量时，此时使用的局部静态变量。当在函数外部使用，使用的是外部的全局变量。
可以理解为全局静态变量a为a1，局部静态变量为a2，这两个是互相不会影响对方的值的。

?

继承

• 为什么要自己定义拷贝构造函数？什么是深拷贝和浅拷贝？

（1）拷贝构造函数的作用就是定义了当我们用同类型的另外一个对象初始化本对象的时候做了什么，在某些情况下，如果我们不自己定义拷贝构造函数，使用默认的拷贝构造函数，就会出错。比如一个类里面有一个指针，如果使用默认的拷贝构造函数，会将指针拷贝过去，即两个指针指向同个对象，那么其中一个类对象析构之后，这个指针也会被delete掉，那么另一个类里面的指针就会变成野指针（悬浮指针）；

（2）这也正是深拷贝和浅拷贝的区别，浅拷贝只是简单直接地复制指向某个对象的指针，而不复制对象本身，新旧对象还是共享同一块内存。 但深拷贝会另外创造一个一模一样的对象，新对象跟原对象不共享内存，修改新对象不会改到原对象。

• 继承类型

当一个类派生自基类，该基类可以被继承为?public、protected?或?private?几种类型。继承类型是通过上面讲解的访问修饰符 access-specifier 来指定的。

我们几乎不使用?protected?或?private?继承，通常使用?public?继承。当使用不同类型的继承时，遵循以下几个规则：

• 公有继承（public）：当一个类派生自公有基类时，基类的公有成员也是派生类的公有成员，基类的保护成员也是派生类的保护成员，基类的私有成员不能直接被派生类访问，但是可以通过调用基类的公有和保护成员来访问。
• 保护继承（protected）：?当一个类派生自保护基类时，基类的公有和保护成员将成为派生类的保护成员。
• 私有继承（private）：当一个类派生自私有基类时，基类的公有和保护成员将成为派生类的私有成员。

• 菱形继承的问题？

会存在二义性的问题，子类的两个父类会对公共基类的成员都继承，那子类调用公共基类的成员则会有二义性。

解决方法，子类的两个父类继承时采用virtual修饰，这样就只会创造一份公共基类的实例，不会造成二义性。

举例：

解决方法：

重载、重写（覆盖）、隐藏（重定义）

首先这三种，函数名都必须相同。

重载：参数必须不同，返回值可以不同。都在类内。调用时根据参数不的同，调用不同的同名函数。

重写（覆盖）：又称覆盖override，在c++中必须给基类的函数添加virtual，然后子类重写该虚函数。一般用于实现，使用父类指针去指向不同的子类对象时，可以通过父类指针调用子类中重写的函数，以实现多态。

（返回值、参数必须完全相同，否则会变成隐藏。）

具体：

C++ 多态 | 菜鸟教程 (runoob.com)

隐藏（重定义）：

子类存在和父类一样的同名函数或者变量，此时子类会屏蔽父类的同名变量/函数。

多态、虚函数（???）

• 什么是多态？C++的多态是如何实现的？

答：所谓多态，就是同一个函数名具有多种状态，或者说一个接口具有不同的行为。

C++的多态分为编译时多态和运行时多态：

1. 编译时多态也称为为静态联编，通过重载和模板来实现，在编译时确定。
2. ?运行时多态称为动态联编，通过继承和虚函数来实现，在运行时才确定。

• 虚函数调用是在编译时确定还是运行时确定的？如何确定调用哪个函数？

答：运行时确定，通过查找虚函数表中的函数地址确定。

更正：此处说法不严谨，应该是只有通过指针或者引用的方式调用虚函数是运行时确定，通过值调用的虚函数是编译期就可以确定的，参考这篇文章，虚函数一定是运行期才绑定么？ - 知乎 (zhihu.com)

• 虚函数的实现机制是什么？

虚函数是通过虚函数表来实现的，虚函数表包含了一个类(所有)的虚函数的地址，在有虚函数的类对象中，它内存空间的头部会有一个虚函数表指针(虚表指针)，用来管理虚函数表。当子类对象对父类虚函数进行重写的时候，虚函数表的相应虚函数地址会发生改变，改写成这个虚函数的地址，当我们用一个父类的指针来操作子类对象的时候，它可以指明实际所调用的函数。

举例：

class A {
public:
    virtual void vfunc1();
    virtual void vfunc2();
            void func1();
            void func2();
private:
    int m_data1, m_data1;
};

class B : public A {
public:
    virtual void vfunc1();
            void func2();
private:
    int m_data3;
};

class C : public B {
public:
    virtual void vfunc1();
            void func2();
private:
    int m_data1, m_data4;
};

以上三个类在内存中的排布关系如下图所示：

• 虚函数是存在类中还是类对象中（即是否共享虚表）？

答：存在类中，不同的类对象共享一张虚函数表(为了节省内存空间)。

• 什么是动态绑定？

是指与给定的过程调用相关联的代码，只有在运行期才可知的一种绑定，他是多态实现的具体形式。

在c++中就是指使用父类的指针或者引用调用虚函数时，这个调用可能在运行时，绑定到不同的子类中，产生不同的行为。

• 纯虚函数？

?

• C++和C分别使用什么函数来做内存的分配和释放？有什么区别？

C使用malloc/free，C++使用new/delete。

区别：

（1）new分配内存空间无需指定分配内存大小，malloc需要；

（2）new返回类型指针，类型安全，malloc返回void*，再强制转换成所需要的类型；

（3）对于类对象，new会调用构造函数和析构函数，malloc不会（核心）。

• 什么是内存对齐(字节对齐)，为什么要做内存对齐，如何对齐？

（1）内存对齐的原因：关键在于CPU存取数据的效率问题。为了提高效率，计算机从内存中取数据是按块读取。若不进行对齐，要取出两块地址中的数据，进行掩码和移位等操作，写入目标寄存器内存，效率很低。可以提升数据读取的速度。

内存对齐规则：

以类中最大的变量的字节数来分块，将变量依次放入块中，若剩余内存不足以存放，则存放在新的一块。

（如果class中有自定义类型，则递归的取其中最大的基本类型来参与比较）

类的总大小,,必须是其内部最大成员的"最宽基本类型成员"的整数倍.不足的要补齐。

举例：

#include<iostream>
using namespace std;
class test {
private :
    
    char c='1';//1byte 
    int i;//4byte
    short s=2;//2byte
};

int main(){
    cout << sizeof(test) << endl;
    return 0;
}

输出：12

调换变量顺序：

class test2 {
private:
    int i;//4byte
    char c = '1';//1byte 
    short s = 2;//2byte
};

int main(){
    cout << sizeof(test2) << endl;
    return 0;
}

输出：8

test1：

test2：

下面这两个例子都是按8来作为整数倍

test3：输出48

class BigData
{
    char array[33];
};
 
class Data
{
    BigData bd;
    int integer;
    double d;
};
 
cout << sizeof(BigData) << "   " << sizeof(Data) << endl;
//输出48

test4：输出48

class BigData
{
    char array[33];
};
 
class Data
{
    BigData bd;
    double d;
};
 
cout << sizeof(BigData) << "   " << sizeof(Data) << endl;
//输出48

• c++中类对象的内存模型(布局)是怎么样的？（暂时不太懂，先放着）

【参考资料】：C++内存模型 - MrYun - 博客园 (cnblogs.com)、C++内存布局（上）_qinm的专栏-CSDN博客

答：一般遵循以下几点原则：

（1）如果是有虚函数的话，虚函数表的指针始终存放在内存空间的头部；

（2）除了虚函数之外，内存空间会按照类的继承顺序(父类到子类)和字段的声明顺序布局；

（3）如果有多继承，每个包含虚函数的父类都会有自己的虚函数表，并且按照继承顺序布局(虚表指针+字段）；如果子类重写父类虚函数，都会在每一个相应的虚函数表中更新相应地址；如果子类有自己的新定义的虚函数或者非虚成员函数，也会加到第一个虚函数表的后面；

（4）如果有钻石继承，并采用了虚继承，则内存空间排列顺序为：各个父类(包含虚表)、子类、公共基类(最上方的父类，包含虚表)，并且各个父类不再拷贝公共基类中的数据成员。

类型转换（??）

数据类型转换：

隐式转换：

高精度和低精度的数据相加会发生转换，结果为高精度：

强制转换：

下面这种情况导致精度丢失?

下面这种情况导致数据截断：

• 四种类型转换

（1）const_cast: 把const属性去掉，即将const转换为非const（也可以反过来），const_cast只能用于指针或引用，并且只能改变对象的底层const（顶层const，本身是const，底层const，指向对象const）；

（2）static_cast: 隐式类型转换，可以实现C++中内置基本数据类型之间的相互转换，enum、struct、 int、char、float等，能进行类层次间的向上类型转换（子类转父类）和向下类型转换（向下不安全，因为没有进行动态类型检查）。它不能进行无关类型(如非基类和子类)指针之间的转换，也不能作用包含底层const的对象；

（3）dynamic_cast：动态类型转换，用于将基类的指针或引用安全地转换成派生类的指针或引用（也可以向上转换），若指针转换失败返回NULL，dynamic_cast是在运行时进行安全性检查；使用dynamic_cast父类一定要有虚函数，否则编译不通过；

（4）reinterpret_cast：reinterpret是重新解释的意思，此标识符的意思即为将数据的二进制形式重新解释，但是不改变其值，有着和C风格的强制转换同样的能力。它可以转化任何内置的数据类型为其他任何的数据类型，也可以转化任何指针类型为其他的类型。它甚至可以转化内置的数据类型为指针，无须考虑类型安全或者常量的情形。不到万不得已绝对不用（比较不安全）

第二第三点的举例：

class Base {
public:
    int _i;
    virtual void foo() {}; //基类必须有虚函数。保持多态特性才能使用dynamic_cast
};

class Sub : public Base {
public:
    char *_name[100];
    void Bar() {};
};

int main() {

    Base* pb = new Sub();
    Sub* ps1 = static_cast<Sub*>(pb);  //子类->父类，静态类型转换，正确但不推荐
    Sub* ps2 = dynamic_cast<Sub*>(pb); //子类->父类，动态类型转换，正确

    Base* pb2 = new Base();
    Sub* ps21 = static_cast<Sub*>(pb2); //父类->子类，静态类型转换，危险！访问子类_name成员越界
    Sub* ps22 = dynamic_cast<Sub*>(pb2);//父类->子类，动态类型转换，安全，但结果为NULL

    return 0;
}

总结：

去const属性用const_cast

基本类型转换用static_cast，可以用于子类转父类但不推荐

多态类之间的类型转换用dynamic_cast，将基类的指针或引用安全地转换成派生类的指针或引用

不同类型的指针类型转换用reinterpret_cast

• static_cast和dynamic_cast的异同点？

答：二者都会做类型安全检查，只是static_cast在编译期进行类型检查，dynamic_cast在运行期进行类型检查。后者需要父类具备虚函数，而前者不需要。

智能指针（?）

智能指针主要解决一个内存泄露的问题，它可以自动地释放内存空间。智能指针分为共享指针(shared_ptr), 独占指针(unique_ptr)和弱指针(weak_ptr)。

（因为它本身是一个类，当函数结束的时候会调用析构函数，并由析构函数释放内存空间。）

• shared_ptr的实现原理是什么？构造函数、拷贝构造函数和赋值运算符怎么写？shared_ptr是不是线程安全的？

（1）shared_ptr是通过引用计数机制实现的，引用计数存储着有几个shared_ptr指向相同的对象，当引用计数下降至0时就会自动销毁这个对象；

（2）具体实现：

1）构造函数：将指针指向该对象，引用计数置为1；

2）拷贝构造函数：将指针指向该对象，引用计数++；

3）赋值运算符：=号左边的shared_ptr的引用计数-1，右边的shared_ptr的引用计数+1，如果左边的引用技术降为0，还要销毁shared_ptr指向对象，释放内存空间。

（3）shared_ptr的引用计数本身是安全且无锁的，但是它指向的对象的读写则不是，因此可以说shared_ptr不是线程安全的

各种关键字

• const作用？

const修饰符用来定义常量，具有不可变性。在类中，被const修饰的成员函数，不能修改类中的数据成员；

• 指针常量和常量指针？

补充一点：

const int* p;

int const* p;

int* const p;

前两个中const形容的是int，代表指针类型是const int的，意思是指向的对象是const int的，意味着指向的对象是常量，而指针p自身可以改变。即常量指针

第三个，const形容的是指针p，代表指针不能变。指针类型是int，代表指向的对象就是可变的int型变量。即指针常量。

• static的作用？static变量什么时候初始化？

static即静态的意思，可以对变量和函数进行修饰。分三种情况：

（1）当用于文件作用域的时候（即在.h/.cpp文件中直接修饰变量和函数），static意味着这些变量和函数只在本文件可见，其他文件是看不到也无法使用的，可以避免重定义的问题。

（2）当用于函数作用域时，即作为局部静态变量时，意味着这个变量是全局的，只会进行一次初始化，不会在每次调用时进行重置，但只在这个函数内可见。

（3）当用于类的声明时，即静态数据成员和静态成员函数，static表示这些数据和函数是所有类对象共享的一种属性，而非每个类对象独有。

（4）static变量在类的声明中不占用内存，因此必须在.cpp文件中定义类静态变量以分配内存。全局变量、文件域的静态变量和类的静态成员变量在main执行之前的静态初始化过程中分配内存并初始化；局部静态变量在第一次使用时分配内存并初始化。

• extern的作用?

答：当它与"C"一起连用时，如: extern "C" void fun(int a, int b);则告诉编译器在编译fun这个函数名时按着C的规则去翻译相应的函数名而不是C++的；当它作为一个对函数或者全局变量的外部声明，提示编译器遇到此变量或函数时，在其它模块中寻找其定义。

• auto和deltype的作用和区别？

答：用于实现类型自动推导，让编译器来操心变量的类型；auto不能用于函数传参和推导数组类型，但deltype可以解决这个问题。

• typedef的作用

定义一种类型的别名，而不只是简单的宏替换。可以用作同时声明指针型的多个对象。

比如：

char* pa, pb; // 这多数不符合我们的意图，它只声明了一个指向字符变量的指针， 和一个字符变量；

以下则可行：

typedef char* PCHAR; // 一般用大写
PCHAR pa, pb; // 可行，同时声明了两个指向字符变量的指针

虽然：

char *pa, *pb;

也可行，但相对来说没有用typedef的形式直观，尤其在需要大量指针的地方，typedef的方式更省事。

左值右值，右值引用

• 左值右值是什么？

可以取地址的，有名字的，非临时的就是左值；

不能取地址的，没有名字的，临时的就是右值；

• 右值引用的作用？

参考文章：c++ 左值引用与右值引用 - 知乎 (zhihu.com)

举例：

先看一下传统的左值引用。

int a = 10;
int &b = a;  // 定义一个左值引用变量
b = 20;      // 通过左值引用修改引用内存的值

左值引用在汇编层面其实和普通的指针是一样的；定义引用变量必须初始化，因为引用其实就是一个别名，需要告诉编译器定义的是谁的引用。

int &var = 10;

上述代码是无法编译通过的，因为10无法进行取地址操作，无法对一个立即数取地址，因为立即数并没有在内存中存储，而是存储在寄存器中，可以通过下述方法解决：

const int &var = 10;

使用常引用来引用常量数字10，因为此刻内存上产生了临时变量保存了10，这个临时变量是可以进行取地址操作的，因此var引用的其实是这个临时变量，相当于下面的操作：

const int temp = 10; 
const int &var = temp;

根据上述分析，得出如下结论：

• 左值引用要求右边的值必须能够取地址，如果无法取地址，可以用常引用；
  但使用常引用后，我们只能通过引用来读取数据，无法去修改数据，因为其被const修饰成常量引用了。

那么C++11 引入了右值引用的概念，使用右值引用能够很好的解决这个问题。

右值引用可以进行读写操作，而常引用只能进行读操作。

定义右值引用的格式如下：

类型 && 引用名 = 右值表达式;

右值引用是C++ 11新增的特性，所以C++ 98的引用为左值引用。右值引用用来绑定到右值，绑定到右值以后本来会被销毁的右值的生存期会延长至与绑定到它的右值引用的生存期。

int &&var = 10;

右值引用的存在并不是为了取代左值引用，而是充分利用右值(特别是临时对象)的构造来减少对象构造和析构操作以达到提高效率的目的。

使用右值引用的移动操作可以避免无谓的拷贝，提高性能。

右值引用用来绑定到右值，绑定到右值以后本来会被销毁的右值的生存期会延长至与绑定到它的右值引用的生存期。

• 右值引用只能对右值进行引用吗？能不能对左值引用？

右值引用独立于左值和右值。意思是右值引用类型的变量可能是左值也可能是右值。比如：

内联函数与宏

• 内联函数有什么作用？存不存在什么缺点？

（1）作用是使编译器在函数调用点上展开函数，可以避免函数调用的开销；

（2）内联函数的缺点是可能造成代码膨胀，尤其是递归的函数，会造成大量内存开销，exe太大，占用CPU资源。此外，内联函数不方便调试，每次修改会重新编译头文件，增加编译时间。

• 内联函数和宏有什么区别，有了宏为什么还需要内联函数?

（1）define宏命令是在预处理阶段对命令进行替换，inline是在编译阶段在函数调用点处直接展开函数，节省了函数调用的开销；

（2）define的话是不会对参数的类型进行检查的，因此会出现类型安全的问题，比如定义一个max命令，但是传递的时候可能会传递一个整数和一个字符串，就会出错，但是内联函数在编译阶段会进行类型检查；

其他杂项

• C++11的新特性

（1）auto关键字，可以自动推断出变量的类型；

（2）nullptr来代替NULL，可以避免重载时出现的问题（一个是int，一个是void*）;

为什么建议使用nullptr代替NULL呢？

这是因为在C++中，NULL是被定义为0的常量，当遇到函数重载时，就会出现问题。

比如有下面两个函数时：

• void foo(int n)
• void foo(char* s)

函数重载：C++允许在同一作用域中声明多个类似的同名函数，这些同名函数的形参列表（参数个数，类型，顺序）必须不同。

#include <iostream>
using namespace std;

void foo(int n) {
    cout << "foo(int n)" << endl;
}

void foo(char* s) {
    cout << "foo(char* s)" << endl;
}

int main()
{
    foo(NULL);

    return 0;
}

编译上述代码，结果如下图所示，编译器提示有两个函数都可能匹配，产生二义性。

（3）智能指针，那三个智能指针，对内存进行管理；

（4）右值引用，基于右值引用可以实现移动语义和完美转发，消除两个对象交互时不必要的对象拷贝，节省运算存储资源，提高效率；

（5）lambda表达式，可以理解为一个匿名的函数，有些函数我们只关心它的功能不需要有它的名字，甚至可以是临时的，这时候可以使用匿名函数。

另一方面，lambda表达式可以使得代码更加简洁易懂。

参考：C++中的Lambda表达式 - 简书 (jianshu.com)

例如：

bool cmp(int &a, int &b);

int main() {
    vector<int> data;
    for (int i = 0; i < 10; ++i)
        data.push_back(i);
    sort(data.begin(), data.end(), cmp);
    for (int i = 0; i < data.size(); ++i)
        cout << data[i] << endl;
    return 0;
}

bool cmp(int &a, int &b) {
    return a > b;
}

在定义了函数bool cmp(int &a, int &b)后，相同的函数签名变得不可用，我不能再用bool cmp(int &a, int &b)这个签名定义一个别的比较函数：

问题是排序这件事通常不会反复做，那么用cmp比较大小是个一次性的临时需求，排序之后它的任务就已经完成了。所以给它特意起个名字污染命名空间似乎有点不太合算，可不可以不给它起cmp这个名字，又能使用比较大小的功能呢？答案当然是可以的，通过与cmp等价的匿名函数：

int main() {
    vector<int> data;
    for (int i = 0; i < 10; ++i)
        data.push_back(i);
    sort(data.begin(), data.end(), [](int &a, int &b)->bool {
         return a > b;
         });
    for (int i = 0; i < data.size(); ++i)
        cout << data[i] << endl;
    return 0;
}

即

[](int &a, int &b)->bool {
         return a > b;
}

就是传说中的Lambda表达式了，先不管[]部分，(int &a, int &b)->bool表示接受两个int引用类型的参数，返回值是bool类型，{}里是函数体，是不是很简单？

[ capture-list ] ( params ) -> ret { body }

其中( params ) -> ret定义了这个匿名函数的参数和返回类型， { body }定义了这个匿名函数的功能，捕捉列表[ capture-list ]是做什么的呢？概括地讲，它使这个匿名函数可以访问外部（父作用域）变量。

STL

STL各种容器的底层实现？（???）

（1）vector，底层是一块具有连续内存的数组，vector的核心在于其长度自动可变。vector的数据结构主要由三个迭代器(指针)来完成：指向首元素的start，指向尾元素的finish和指向内存末端的end_of_storage。vector的扩容机制是：当目前可用的空间不足时，分配目前空间的两倍或者目前空间加上所需的新空间大小（取较大值），容量的扩张必须经过“重新配置、元素移动、释放原空间”等过程。

（2）list，底层是一个循环双向链表，链表结点和链表分开独立定义的，结点包含pre、next指针和data数据。

（3）deque（double-ended queue），双向队列，由分段连续空间构成，每段连续空间是一个缓冲区，由一个中控器来控制。它必须维护一个map指针（中控器指针），还要维护start和finish两个迭代器，指向第一个缓冲区，和最后一个缓冲区。deque可以在前端或后端进行扩容，这些指针和迭代器用来控制分段缓冲区之间的跳转。

（4）stack和queue，栈和队列。它们都是由由deque作为底层容器实现的，他们是一种容器配接器，修改了deque的接口，具有自己独特的性质（此二者也可以用list作为底层实现）；stack是deque封住了头端的开口，先进后出，queue是deque封住了尾端的开口，先进先出。

（5）priority_queue，优先队列。是由以vector作为底层容器，以heap作为处理规则，heap的本质是一个完全二叉树。

（6）set和map。底层都是由红黑树实现的。红黑树是一种二叉搜索树，但是它多了一个颜色的属性。红黑树的性质如下：1）每个结点非红即黑；2）根节点是黑的；3）如果一个结点是红色的，那么它的子节点就是黑色的；4）任一结点到树尾端（NULL）的路径上含有的黑色结点个数必须相同。通过以上定义的限制，红黑树确保没有一条路径会比其他路径多出两倍以上；因此，红黑树是一种弱平衡二叉树，相对于严格要求平衡的平衡二叉树来说，它的旋转次数少，所以对于插入、删除操作较多的情况下，通常使用红黑树。

补充：平衡二叉树(AVL)和红黑树的区别：AVL 树是高度平衡的，频繁的插入和删除，会引起频繁的rebalance（旋转操作），导致效率下降；红黑树不是高度平衡的，算是一种折中，插入最多两次旋转，删除最多三次旋转。

STL各种容器的查找、删除和插入的时间复杂度（性能比较）？（??）

【参考资料】：C++STL各种容器的性能比较、【C++】STL各容器的实现，时间复杂度，适用情况分析_Y先森0.0-CSDN博客

（1）vector，vector支持随机访问(通过下标），时间复杂度是O(1)；如果是无序vector查找的时间复杂度是O(n)，如果是有序vector，采用二分查找则是O(log n)；对于插入操作，在尾部插入最快，中部次之，头部最慢，删除同理。vector占用的内存较大，由于二倍扩容机制可能会导致内存的浪费，内存不足时扩容的拷贝也会造成较大性能开销；

（2）list由于底层是链表，不支持随机访问，只能通过扫描的方式查找，复杂度为O(n)，但是插入和删除的速度快，只需要调整指针的指向。（有一种说法是链表每次插入和删除都需要分配和释放内存，会造成较大的性能开销，所以如果频繁地插入和删除，list性能并不好，但很多地方都说list插入删除性能好，这点我还没有验证，希望有人能指出）；list不会造成内存的浪费，占用内存较小；

（3）deque支持随机访问，但性能比vector要低；支持双端扩容，因此在头部和尾部插入和删除元素很快，为O(1)，但是在中间插入和删除元素很慢；

（4）set和map，底层基于红黑树实现，增删查改的时间复杂度近似O(log n)，红黑树又是基于链表实现，因此占用内存较小；

（5）unordered_set和unordered_map，底层是基于哈希表实现的，是无序的。理论上增删查改的时间复杂度是O(1)（最差时间复杂度O(n))，实际上数据的分布是否均匀会极大影响容器的性能。

STL的排序用到了哪种算法，具体如何执行？

答：快速排序、插入排序和堆排序；当数据量很大的时候用快排，划分区段比较小的时候用插入排序，当划分有导致最坏情况的倾向的时候使用堆排序。

数据结构

排序算法

（1）快排：一轮划分，选择一个基准值，小于该基准值的元素放到左边，大于的放在右边，此时该基准值在整个序列中的位置就确定了，接着递归地对左边子序列和右边子序列进行划分。时间复杂度o(nlogn)，最坏的时间复杂度是o(n2)；

（2）堆排序：参考：图解排序算法(三)之堆排序 - dreamcatcher-cx - 博客园 (cnblogs.com)

分为大顶堆和小顶堆，大顶堆就是根节点必须要大于左右子树的结点。

构造方法：以大顶堆为例，先按顺序将其用树的形式存放，然后从最后一个非叶子结点开始（从左至右，从下至上），看其是否满足其值大于左右子树，如果不满足则将其与小的那个做替换，一直替换直到满足这个条件为止。（这样即可实现大的元素上浮，小的元素下沉）。

这一步做完之后，最大的数将会位于最顶端，然后将该元素与最后一个元素做交换即可实现最大的元素位于最后。

接下来按照上面的步骤循环直到使整个序列有序。

具体例子看上面的博客。

时间复杂度O(nlogn)；

（3）冒泡排序：从前往后两两比较，逆序则交换，不断重复直到有序；时间复杂度O(n2），最好情况O(n)；

（4）插入排序，类似打牌，从第二个元素开始，把每个元素插入前面有序的序列中；时间复杂度O(n2），最好情况O(n)；

（5）选择排序，每次选择待排序列中的最小值和未排序列中的首元素交换；时间复杂度O(n2）；

（6）归并排序，将整个序列划分成最小的>=2的等长序列，排序后再合并，再排序再合并，最后合成一个完整序列。时间复杂度O(nlogn)。

（7）希尔排序，是插入排序的改进版，取一个步长划分为多个子序列进行排序，再合并(如135一个序列，246一个序列），时间复杂度O(n1.3)，最好O(n)，最坏O(n2)；

（8）桶排序，将数组分到有限数量的桶里。每个桶再个别排序，最后依次把各个桶中的记录列出来记得到有序序列。桶排序的平均时间复杂度为线性的O(N+C)，其中C=N*(logN-logM)，M为桶的数量。最好的情况下为O(N)。

?如何在一个序列中求前k个最大或者最小的数？（TOP K问题）

思想：将全局排序优化为局部排序，非TopK的元素是不需要排序的。除此之外，只需要找出前K个，对这K个内部也不需要排序。

（1）基于快排，每轮划分选择一个基准值，把比它小的数放在左边，大的放在右边，函数返回基准值的位置，如果该位置恰好是K，就说明了这是第K小的数，所以从0-基准值位置的数是序列中的前K小数。若返回基准值的位置小于或者大于K，再进行相应调整：如果返回的基准值大于k，在基准值左边序列查找，如果大于，在基准值右边进行查找。递归地进行快排，直到返回的结果=K；时间复杂度为O(n)。

举例：

算法必学：经典的 Top K 问题 - 简书 (jianshu.com)

（2）基于堆排序，求前K个最小的数用最大顶堆，求前K个最大的数用最小顶堆。以最大顶堆为例，要维护一个大小为K的顶堆，就是先将K个数插入堆中，随后，对每一个数，与堆顶的最大元素比较，若该数比堆顶元素小，则替换掉堆顶元素，然后调整堆，若大于堆顶元素，则不管，那么将所有元素比较和插入后，该堆维护的就是最小的K个数。求前k小的数用最大顶堆的目的(原理）：这是一种局部淘汰的思想，尽量的把小的数都放在堆中，最后使得即使堆中最大的数，也比外界的所有数都小，就达到了目的。

• 怎样判断单链表是否存在回环

最简单的方法, 用一个指针遍历链表,
每遇到一个节点就把他的内存地址做为key放在一个map中.
这样当map中出现重复key的时候说明此链表上有环. 这个方法的时间复杂度为O(n), 空间同样为O(n).

判断单链表是否存在回环原理很简单，即假设有两个指针p1，p2。在每次循环的时候，p1先走一步，p2走两步，直到p2碰到空指针或两者相等时循环结束，如果两个指针相等则说明存在回环。
?

对象池思想

对于那些需要频繁创建和销毁的对象，对象池的思想是，首先从对象池中寻找有没有可用的对象，如果没有，就创建对象来使用，然后当一个对象不使用的时候，不是把它删除，而是将它设置为不激活的状态并放入对象池中，等待需要使用的时候再去对象池中寻找，并把它激活。

例如：子弹思想、使用对象池实现2d跳跃的残影效果。

计算机组成

编译链接原理，从C++源文件到可执行文件的过程？（??）

答：包括四个阶段：预处理阶段、编译阶段、汇编阶段、连接阶段。

（1）预处理阶段处理头文件包含关系，对预编译命令进行替换，生成预编译文件；

（2）编译阶段将预编译文件编译，生成汇编文件（编译的过程就是把预处理完的文件进行一系列的词法分析，语法分析，语义分析及优化后生成相应的汇编代码)；

（3）汇编阶段将汇编文件转换成机器码，生成可重定位目标文件（.obj文件）（汇编器是将汇编代码转变成机器可以执行的命令，每一个汇编语句几乎都对应一条机器指令。汇编相对于编译过程比较简单，根据汇编指令和机器指令的对照表一一翻译即可）；

（4）链接阶段，将多个目标文件和所需要的库连接成可执行文件（.exe文件）。

• 什么是缓存(Cache)？为什么需要缓存？如何提高缓存的命中率？缓存是不是最快的？（??）

（1）Cache即CPU的高速缓冲存储器，是一种是用于减少处理器访问内存所需平均时间的部件；

（2）由于CPU的计算速度远远大于从CPU向内存取数据的速度，如果每次都让CPU去内存取数据，会导致CPU计算能力的浪费，所以人们设计了缓存，CPU通过读写缓存来获取操作数，结果也通过缓存写入内存；

（3）注意程序的局部性原理，在遍历数组时按照内存顺序访问；充分利用CPU分支预测功能，将预测的指令放到缓存中执行；此外缓存的容量和块长是影响缓存效率的重要因素。如何提升CPU的缓存命中率？ - 知乎 (zhihu.com)

（4）缓存不是最快的，寄存器更快。

• C++函数调用机制？

局部变量占用的内存是在程序执行过程中“动态”地建立和释放的。这种“动态”是通过栈由系统自动管理进行的。当任何一个函数调用发生时，系统都要作以下工作：
（1）建立栈空间；
（2）保护现场：主调函数运行状态和返回地址入栈；
（3）为被调函数中的局部变量分配空间，完成参数传递；
（4）执行被调函数函数体；
（5）释放被调函数中局部变量占用的栈空间；
（6）回复现场：取主调函数运行状态及返回地址，释放栈空间；
（7）继续主调函数后续语句。
?

举例：

◆?函数调用过程中的内存使用：通过下面例子来看函数调用时内存的变化情况。

void fun1(int, int);
void fun2(float);
int main()
{
    int x=1;y=2;
    fun1(x, y);
    return 0;
}
void fun1(int a,int b)
{
    float x=3;
    fun2(x);
}
void fun2(float y) 
{
    int x;
    …
}

内存管理（内存分配、内存对齐）（???）

• C++是如何做内存管理的（有哪些内存区域）?

堆 heap ：

堆，使用new、delete动态分配和释放空间，能分配较大的内存；
如果程序员没有释放掉，在程序结束时OS会自动回收。涉及的问题：“缓冲区溢出”、“内存泄露”

栈 stack ：

存放局部变量、函数参数。
是那些编译器在需要时分配，在不需要时自动清除的存储区。
存放在栈中的数据只在当前函数及下一层函数中有效，一旦函数返回了，这些数据也就自动释放了。
全局/静态存储区?
存储全局和静态变量
常量存储区
存放常量
代码区
存放代码

设计模式

在面向对象编程领域中，开闭原则规定“软件中的对象（类，模块，函数等等）应该对于扩展是开放的，但是对于修改是封闭的”。

其含义是说一个软件实体应该通过扩展来实现变化，而不是通过修改已有的代码来实现变化的

工厂模式：

设计模式之工厂模式（factory pattern） - alpha_panda - 博客园 (cnblogs.com)

该模式用来封装和管理类的创建，终极目的是为了解耦，实现创建者和调用者的分离。

工厂模式分为三种：

1）简单工厂，一个工厂生产多种产品，要指定产品的名字进行生产；

2）普通工厂，将产品生产分配给多个工厂，但是每个工厂只生产一种产品；

3）抽象工厂，将产品生产分配给多个工厂，每个工厂可以生产多种产品；

操作系统

• 堆和栈的内存有什么区别？

（1）堆中的内存需要手动申请和手动释放，栈中内存是由OS自动申请和自动释放；

（2）堆能分配的内存较大（4G(32位机器)），栈能分配的内存较小（1M）；

（3）在堆中分配和释放内存会产生内存碎片，栈不会产生内存碎片；

（4）堆的分配效率低，栈的分配效率高；

（5）堆地址从低向上，栈由高向下。

• 进程和线程的区别？

（1）进程是运行时的程序，是系统进行资源分配和调度的基本单位，它实现了系统的并发；

（2）线程是进程的子单位，也称为轻量级进程，它是CPU进行分配和调度的基本单位，也是独立运行的基本单位，它实现了进程内部的并发；

（3）一个程序至少拥有一个进程，一个进程至少拥有一个线程，线程依赖于进程而存在；

（4）进程拥有独立的内存空间，而线程是共享进程的内存空间的，自己不占用资源；

（5）线程的优势：线程之间的信息共享和通讯比较方便，不需要资源的切换等.

• 什么是死锁，死锁的条件以及如何防止？

（1）死锁就是多个进程并发执行，在各自占有一定资源的情况下，希望获得其他进程占有的资源以推进执行，但是其他资源同样也期待获得另外进程的资源，大家都不愿意释放自己的资源，从而导致了相互阻塞、循环等待，进程无法推进的情况。

（2）死锁条件：1）互斥条件（一个资源每次只能被一个进程使用）；2）请求并保持条件（因请求资源而阻塞时，对已获得的资源保持不放）；3）不剥夺条件（在未使用完之前，不能剥夺，只能自己释放）；4）循环等待（若干进程之间形成一种头尾相接的循环等待资源关系）。

（3）死锁防止：1）死锁预防，打破四个死锁条件；2）死锁避免，使用算法来进行资源分配，防止系统进入不安全状态，如银行家算法；3）死锁检测和解除，抢占资源或者终止进程；

什么是银行家算法？（??）

（4）银行家算法是一种最有代表性的避免死锁的算法。在避免死锁方法中允许进程动态地申请资源，但系统在进行资源分配之前，应先计算此次分配资源的安全性，若分配不会导致系统进入不安全状态，则分配，否则等待。为实现银行家算法，系统必须设置若干数据结构。安全的状态指的是一个进程序列{P1,P2,...Pn}，对于每一个进程Pi，它以后尚需要的资源不大于当前资源剩余量和其余进程所占有的资源量之和。

• 操作系统如何管理内存，什么是虚拟内存？

通过一种分页管理机制来进行内存管理。分页管理机制将程序的逻辑地址划分为固定大小的页，而物理内存划分为同样大小的帧，程序加载时，可以将任意一页放入内存中任意一个帧，这些帧不必连续，从而实现了离散分离。虚拟内存是基于分页存储管理机制的，它允许程序不必将所有的页都放入内存中，而只是将一部分页映射到内存中，另一部分页放在外存上(如磁盘、软盘、USB），当引用到不在内存中的页时，系统产生缺页中断，并从外存中调入该部分页进来，从而产生一种逻辑上内存得到扩充的感觉，实际上内存并没有增大。

• 什么是内存碎片，内存碎片是在虚拟内存还是物理内存？

采用分区式存储管理的系统，在储存分配过程中产生的、不能供用户作业使用的主存里的小分区称成“内存碎片”。内存碎片分为内部碎片和外部碎片。内存碎片只存在于虚拟内存上。

哈希表的长度为什么要是质数？

哈希表的长度使用质数，可以降低发生冲突的概率，使哈希后的数据更加均匀，如果使用合数，可能会导致很多数据集中分布到一个点上，造成冲突；

计算机网络

• TCP和UDP的区别？

（1）TCP是传输控制协议，UDP是用户数据报协议；

（2）TCP是面向连接的，可靠的数据传输协议，它要通过三次握手来建立连接，UDP是无连接的，不可靠的数据传输协议，采取尽力而为的策略，不保证接收方一定能收到正确的数据；

（3）TCP面向的是字节流，UDP面向的是数据报；

（4）TCP只支持点对点，UDP支持一对一，一对多和多对多；

（5）TCP有拥塞控制机制，UDP没有。

• OSI七层模型和TCP/IP五层模型

（物联网淑慧试用）

?

• TCP三次握手？四次挥手？

面试回答：这个问题我是清楚的，TCP/IP是传输层面向连接的可靠协议，三次握手的机制是为了保证安全可靠的连接。第一次由客户端向服务器发送报文，这个报文的SYN位置一，代表请求建立连接，并包含seq报文表示请求服务器发送的报文序列号，服务器收到报文后会知道客户端请求建立连接，于是向客户端发送确认消息报，SYN置1表示建立连接，ACK置一，并且ack设置为第一次握手中的seq+1。
在服务器发送报文后，服务器方不知道自己的报文是否发送成功，因此此时需要第三次握手，客户端发送报文，并且ACK位置1，表示客户端已经收到服务器端的确认报文了。
在三次握手结束后，双方都知道了可以发送和接受到对方的消息，此时连接成功建立，接下来双方就可以进行数据的发送了。

四次挥手：
首先由客户端发起，表示请求断开连接，此时客户端发送请求断开连接的报文，FIN置一，当服务器端收到报文后，此时可能还没准备好断开连接，此时可能还有需要继续发送的报文。
当服务器准备好的时候，服务器向客户端发送请求断开连接的报文，FIN置1，但是服务器并不知道自己是否发送成功，于是最后还需要一次挥手，就是让客户端向服务器发送收到断开信息的报文。
?