阿里C++研发一面准备

阿里C++面试文档

4月8做完笔试，做的稀烂，还以为直接凉凉了，就没管这事了，没想到今天接到约面试的电话，约到了明天下午，然鹅我已经半年多没写过C++了，于是今天下午赶紧恶补一下，许个愿，等过几天看看能不能回来还愿。

先说结果： 我是18级的，他们不招，所以这些准备的今年是用不上了，但是还是可以分享一下的。

NULL 和 nullptr

参考资料： this one

nullptr是在C++11中才出现的，首先我们来看一下nullptr解决了什么问题：

#ifdef __cplusplus
#define NULL 0
#else
#define NULL ((void *)0)
#endif

在C++中不允许(void*)类型进行隐式转换，所以在C语言中，NULL被定义为(void*)0,而在C++语言中，NULL则被定义为整数0，也就是说，NULL是一个整型变量，这样的设计带来了如下的问题:

• ```C++ char* a =" Hello"; void foo(void* p){} foo(a);

    上方这种调用会出现问题
  
  * ```C++
    void func(int data);
     
    void func(char* data);

  在上面这种情况中，无法将NULL和整形区分，调用的结果与想象中不符。

nullptr在C++11被引入用于解决这一问题，nullptr可以明确区分整型和指针类型，能够根据环境自动转换成相应的指针类型，但不会被转换为任何整型，所以不会造成参数传递错误。

深拷贝与浅拷贝

• 浅拷贝下：

  A复制了B，那么A和B是共用同一片内存区域的，也就是说，A和B中任何一个发生变化，他们两个都会发生变化。

• 深拷贝下:

  A复制了B，A和B除了内容相同之外，相互独立。

堆区与栈区

参考资料：this one

申请方式的区别

堆区存放的是new、malloc出的变量，由程序员自己定义大小。

栈由系统自动分配，我们直接int出来的局部变量就在栈区。

系统的响应

• 堆:操作系统有一个记录空闲内存地址的链表，系统收到程序的申请时，会遍历该链表，寻找第一个空间大于所申请空间的堆结点，然后将该结点从空闲结点链表中删除，并将该结点的空间分配给程序。会在这块内 存空间中的首地址处记录本次分配的大小，这样，代码中的delete语句才能正确的释放本内存空间。另外，由于找到的堆结点的大小不一定正好等于申请的大 小，系统会自动的将多余的那部分重新放入空闲链表中。

• 栈:只要栈的剩余空间大于所申请空间，系统将为程序提供内存，否则将报异常提示栈溢出。

能申请的空间的大小

• 栈：能从栈获得的空间较小。
• 堆：堆获得的空间比较灵活，也比较大。

申请效率

• 栈由系统自动分配，速度较快。但程序员是无法控制的。

• 堆是由new分配的内存，一般速度比较慢，而且容易产生内存碎片,不过用起来最方便.

inline 和 普通函数

inline VS 普通函数

参考资料：this one

内联函数有一些限制：

• 内联函数体不能包含循环语句、switch语句。
• 内联函数要先定义、后调用，不能先声明内联函数原型，再定义、调用。

内联函数实际上是省去了跳转的步骤，在速度层面有一定的加强，但同时也增大了内存的开销。

inline VS 宏定义

宏定义直接就是代码替换，与inline有本质上的区别，如果直接用宏定义来替代inline可能还会导致逻辑错误。

static

来源

静态局部变量

刚才在讲堆栈的时候，有一点是没有讲到的，C++程序在内存中，除了占用堆栈区域外，还有一种区域是：静态内存区域，它负责存储全局变量和静态变量，初始化的全局变量和静态变量在一块区域，未初始化的全局变量和未初始化的静态变量在相邻的另一块区域。程序结束释放。当然，还有代码区，这里不展开讲。

static是在全局数据区分配的,那么它存在的意思是什么？又是什么时候初始化的呢？

• 它存在的意义就是随着第一次函数的调用而初始化，却不随着函数的调用结束而销毁，所以它只会初始化一次。

静态局部变量的特点：

• （1）该变量在全局数据区分配内存(局部变量在栈区分配内存);
• （2）静态局部变量在程序执行到该对象的声明处时被首次初始化，即以后的函数调用不再进行初始化(局部变量每次函数调用都会被初始化);
• （3）静态局部变量一般在声明处初始化，如果没有显式初始化，会被程序自动初始化为0(局部变量不会被初始化);
• （4）它始终驻留在全局数据区，直到程序运行结束。但其作用域为局部作用域，也就是不能在函数体外面使用它(局部变量在栈区，在函数结束后立即释放

静态全局变量

static int i = 1;  //note:3
//int i = 1;  //note:4
 
 
int foo()
{
	i += 1;
	return i;
}

静态全局变量不能被其它文件所用(全局变量可以);

静态函数：和静态全局变量类似

静态数据成员：被定义在类里面的静态成员

特点：与普通的成员不一样，普通的类成员是一个实例一个。而静态成员是每个类一个的，这个可以用来统计一些累计的东西，也可以用来做公有的东西。

静态成员函数：类里面的静态函数

• 1.静态成员之间可以相互访问，包括静态成员函数访问静态数据成员和访问静态成员函数;
• 2.非静态成员函数可以任意地访问静态成员函数和静态数据成员;
• 3.静态成员函数不能访问非静态成员函数和非静态数据成员;
• 4.调用静态成员函数，可以用成员访问操作符(.)和(->)为一个类的对象或指向类对象的指针调用静态成员函数,也可以用类名::函数名调用(因为他本来就是属于类的，用类名调用很正常)

虚函数和多态

一、子类对象可以被当作父类对象。

• 派生类的对象可以隐含的转换成基类对象。
• 派生类对象可以初始化基类的引用。
• 派生类指针可以隐含转换为基类的指针

说人话就是：

• 父类指针可以指向子类对象

那么虚函数有什么用处呢？这里我们和java对比着来说，众所周知，Java中可以override，也就是说将函数重写，这样来达到多态。父类指针指向的子类，可以调用子类中重写过的方法。但是C++在默认情况下不可以，所以C++引入了virtual。

多态:

不同类的对象堆同一消息的不同响应。俺会了，⑧谈了

动态绑定

可以说是多态的实际应用

实现动态绑定的要点（多态）

• 具有类的继承关系图，这个继承关系中每个类都可以调用一个虚函数
• 基础类的指针指向子类的对象
• 通过基础类的指针调用虚函数

虚析构函数

在析构函数定义为虚函数，这样就可以根据子类的不同特性对析构函数进行重写。

虚函数表

有无虚函数的类的内存布局的区别‘

无虚函数：类的实例化中仅有成员占用空间。

有虚函数：虚函数指针同时占用空间，该虚函数指针指向一个虚函数表。

虚函数表保存了一个函数的地址，也就是函数指针。

再来捋一遍：

• 含有虚函数的类进行实例化：
• 编译器给类的实例化分配一个虚函数指针
• 虚函数指针指向虚函数表
• 虚函数表里面有虚函数

子类不重写父类的虚函数的情况：

假设现在有一个父类一个子类，父类中定义类一个虚函数，子类在继承父类后，并没有重写该函数。

这种情况下，父类和子类的内存布局中仍然都有虚函数指针，指向虚函数表。为避免套娃，不讲了。

一句话来说:我爸爸有虚函数，我直接继承了， 那我的虚函数指针就指向我爸爸在虚函数表里的虚函数。反之我的虚函数指针就指向我重写的虚函数在虚函数表里的位置。

补充

看后面看到的，塞过来

子类的虚函数被放在声明的第一个基类的虚函数表中。

c++经典继承，多态，封装

封装

• 好处：安全，方便简单
• 封装的层次：
  • 方法封装了功能
  • 类封装了数据和功能
• 如何实现封装
  • 使用private修饰属性，不能直接给属性赋值
  • 提供public的方法完成对属性的赋值set和取值get操作
  • 在set方法中添加控制语句
• 类的成员使用的修饰符：
  • private 默认 protected public
• 类只能用public和默认来修饰

继承

• 父类、子类。就是子类继承父类的属性和行为，使得子类对象具有与父类相同的属性、相同的行为。子类可以直接 访问父类中的非私有的属性和行为

• 好处：
  • 避免代码重复，提高代码的复用性。
  • 类与类之间产生了关系，是多态的前提。
  • 修改父类，影响所有的子类（好处：便于修改，修改一次接口。不足：增加了耦合性）

多态

已经说完了

引用VS指针

https://blog.csdn.net/tch918/article/details/7401351

引用：

• 是一块内存区域的别名
• 必须被初始化
• 初始化后不能被更改（绑定）
• 他不是一个对象

指针：

• 他记录一块内存区域的地址
• 定义时可以不被初始化
• 可以指向不同的对象（不绑定）
• 它是一个对象

虚函数VS纯虚函数

首先书虚函数和纯虚函数的定义：

virtual void func(){} // 虚函数
virtual void fly() = 0{} // 纯虚函数

虚函数：虚函数是多态的基础，我们在上面已经有所涉及，基类中含有一个虚函数，派生类可以对该函数进行重写，这一过程就实现了多态。

纯虚函数：和虚函数有很大的相似性，但是纯虚函数多了一个限制，那就是派生类必须重写该函数。

不管是虚函数还是纯虚函数，基类都可以为提供他们的实现（implementation），如果有的话子类可以调用基类的这些实现。

子类可自主选择是否要提供一份属于自己的个性化虚函数实现。

子类必须提供一份属于自己的个性化纯虚函数实现。

抽象类

　C++中包含纯虚函数的类，被称为是“抽象类”。抽象类不能使用new出对象，只有实现了这个纯虚函数的子类才能new出对象。

C++中的纯虚函数更像是“只提供申明，没有实现”，是对子类的约束，是“接口继承”。

C++中的纯虚函数也是一种“运行时多态”。

const

常量表示一种定义后就不能再修改的量

• 最简单的用法： const修饰普通类型的变量

  const int MAX_N = 500;

• const 修饰指针变量，分为三种情况：

  • const 修饰指针指向的内容，则内容为不可变量，人话就是：const修饰的指针指向的东东，那么就只能访问不能更改
  • const 修饰指针，则指针为不可变量，人话：const修饰指针本身，指针指向的区域不能变化
  • const 修饰指针和指针指向的内容，则指针和指针指向的内容都为不可变量，就是第一种加第二种

  对于第一种：

  const int *p = 8;

  第二种：

  int a = 8;
   int* const p = &a;
  
   *p = 9; //it’s right
  
   int  b = 7;
   p = &b; //it’s wrong

  第三种：

  int a = 8;
  const int * const  p = &a;

const 修饰传递参数

void Cpf(const int a)
{
    cout<<a; 
    // ++a;  it's wrong, a can't is changed
}

值传递的const修饰传递，一般这种情况不需要const修饰，因为函数会自动产生临时变量复制实参值。

void Cpf(int *const a) 
{ 
    cout<<*a<<" ";
    *a = 9;
}

当const参数为指针时，可以防止指针被意外篡改。

void Cmf(const Test& _tt)
{
    cout<<_tt.get_cm(); 
}

自定义类型的参数传递，需要临时对象复制参数，对于临时对象的构造，需要调用构造函数，比较浪费时间，因此我们采取const外加引用传递的方法。

const修饰函数的返回值

const修饰内置类型的返回值，修饰与不修饰返回值作用一样。

const int Cmf()

{

    return 1;

}

const 修饰自定义类型的作为返回值，此时返回的值不能作为左值使用，既不能被赋值，也不能被修改。

const 修饰返回的指针或者引用，是否返回一个指向const的指针，取决于我们想让用户干什么。

const修饰类成员函数.

onst 修饰类成员函数，其目的是防止成员函数修改被调用对象的值，如果我们不想修改一个调用对象的值，所有的成员函数都应当声明为const成员函数。注意：const关键字不能与static关键字同时使用，因为static关键字修饰静态成员函数，静态成员函数不含有this指针，即不能实例化，const成员函数必须具体到某一实例。

class test
{
public:
    void func(){}
    int getNum(void) const // const 成员函数
    {
        ++num;     // 编译错误，企图修改数据成员m_num
        func();     // 编译错误，企图调用非const函数
        return num;
    }
private:
    int num;
};

智能指针

链接：https://zhuanlan.zhihu.com/p/78123220

由于 C++ 语言没有自动内存回收机制，程序员每次 new 出来的内存都要手动 delete。程序员忘记 delete，流程太复杂，最终导致没有 delete，异常导致程序过早退出，没有执行 delete 的情况并不罕见。——解决了忘了delete的问题。

智能指针实际上是一个栈对象，并非指针类型，在栈对象生命期即将结束时，智能指针通过析构函数释放有它管理的堆内存。所有智能指针都重载了“operator->”操作符，直接返回对象的引用，用以操作对象。访问智能指针原来的方法则使用“.”操作符。

访问智能指针包含的裸指针则可以用 get() 函数。

std::auto_ptr

从C++98开始便推出了auto_ptr，对裸指针进行封装，让程序员无需手动释放指针指向的内存区域，在auto_ptr生命周期结束时自动释放，由于auto_ptr在转移指针所有权后会产生野指针，导致程序运行时crash，如下面示例代码所示。

auto_ptr<int> p1(new int(10));
auto_ptr<int> p2 = p1; //转移控制权
*p1 += 10; //crash，p1为空指针，可以用p1->get判空做保护

unique_ptr

unique_ptr是auto_ptr的继承者，对于同一块内存只能有一个持有者，而unique_ptr和auto_ptr唯一区别就是unique_ptr不允许赋值操作，也就是不能放在等号的右边（函数的参数和返回值例外），这一定程度避免了一些误操作导致指针所有权转移，然而，unique_str依然有提供所有权转移的方法move，调用move后，原unique_ptr就会失效，再用其访问裸指针也会发生和auto_ptr相似的crash，如下面示例代码，所以，即使使用了unique_ptr，也要慎重使用move方法，防止指针所有权被转移。

shared_ptr

shared_ptr 是一个标准的共享所有权的智能指针，允许多个 shared_ptr 智能指针指向同一个指针对象，shared_ptr 利用引用计数的方式实现了对所管理的对象的所有权的分享，即允许多个 shared_ptr 共同管理同一个对象

weak_ptr

weak_ptr 是为了配合 shared_ptr 而引入的一种智能指针，它更像是 shared_ptr 的一个助手而不是智能指针，因为它不具有普通指针的行为，没有重载解引用运算符"*"和运算符"->"，它的最大作用在于协助 shared_ptr 工作，像旁观者那样观测资源的使用情况

graph LR
普通指针 --自动delete--> auto_ptr
auto_ptr --禁止所有权转移-->unique_ptr-治标不治本
unique_ptr-治标不治本 --共享所有权--> shared_ptr

map&set的底层

空间占用率高

红黑树：

• 根节点必须为黑色
• 父子不能同为红色
• 从任何一个节点出发，到叶子节点经过的黑色节点数量一致

操作：

• 搜索：和二叉搜索树一样
• 插入：以红色作为默认插入颜色，插入后进行修复：
  • 一、变色
  • 二、旋转

vector底层

数组，

访问：O(1)

扩容：新建vector会分配连续内存空间，通过push_back增加元素时，如果初始分分配空间满了，那么久扩容，扩容到原来的两倍。

unordered_map 底层

哈希表，查找速度非常的快

哈希表的建立比较耗费时间

对于查找问题，unordered_map会更加高效一些

哈希：

• 开散列
• 闭散列

C++11

• nullptr
• auto：自动推导类型，但不能用于传参和数组
• 基于范围的for循环
• 初始化列表
• tuple元组

项目

什么是立体匹配？

立体匹配解决的科学问题是：

• 给出两张图片，这两张图片是由两个平行的摄像机向同一方向拍摄得到的。
• 使用这两张图片，得到一张深度图（深度图中每一个点的值表示左右图中在现实世界中的同一点相差的距离）
• 根据深度图可以重建出三维世界

基本流程：

图割立体匹配

• 匹配代价计算
• 视差计算

相当于是构建了一个全局的函数，深度图构成的序列是函数的自变量，求函数的最优解的问题。

作者用的方法是：使用最大流最小割定理。

建边方法：

假设(i,j,k)代表i，j节点取k深度

随机生成

• 一个像素点位置上：不同深度取值建边，成为深度边。
  
• 交换深度