Halo

A magic place for coding

0%

实习面经 --C/C++ 基础

面试总结之 C 与 C++ 基础

  C 和 C++ 是比较基础编程语言,无论是前端开发或者是后端开发,多多少少都会涉及到 C 和 C++ 的一些基础知识,这里就为大家总结一下常见的考点。总结的部分是结合了教科书、其他面经以及个人的面试经历,相信能够帮助到大家。如果有不足的地方,欢迎大家指出!

   本博客长期更新,欢迎大家收藏、订阅!

vector 扩容原理

  • ** 迭代器失效 **:
    • push_back () 操作时,一旦引起空间重新配置(deep copy),指向原 vector 的迭代器失效;
    • 使用 erase () 函数的时候,也会导致迭代器失效。it 本身失效,it 还可能越界
  • ** 扩容方式 **:不同编译器的扩容方式不同,VS2015 以 1.5 倍扩容,GCC 以 2 倍扩容。
  • ** 为什么成倍增长?**:
    • 一次增加固定值大小:假设有 n 个元素,每次增加 k 个元素,push_back () 操作的复杂度是 $O (n)$
    • 成倍增长:假设有 n 个元素,倍增 mpush_back () 操作的复杂度是 $O (1)$

STL 常用结构总结

map、set、multimap、multiset

  • 底层实现:红黑树(RB Tree)
  • ** 插入 ** 复杂度:$O (logN)$
  • ** 查看 ** 复杂度:$O (logN)$
  • ** 删除 ** 复杂度:$O (logN)$

hash_map、hash_set、hash_multimap、hash_multiset

  • 底层实现:哈希表
  • ** 插入 ** 复杂度:$O (1)$,最坏 $O (N)$
  • ** 查看 ** 复杂度:$O (1)$,最坏 $O (N)$
  • ** 删除 ** 复杂度:$O (1)$,最坏 $O (N)$

各种结构的用途

  • list:支持 ** 快速插入、删除 ($O (1)$), 查找 ** 比较费时($O (N)$)
  • vector:** 查找速度快 插入和删除 ** 比较费时
  • map:查找速度比较快($O (logN)$)
  • hash_map:如果不碰撞的话,** 查找 ** 时间常数级($O (1)$)

虚函数 virtual function

  • ** 作用 **:多态,对象带额外信息,用于在运行时确定该对象调用哪一个虚函数。
  • ** 实现原理 **:每个对象存储一个 vptr(virtual table pointer,虚函数表指针),该指针指向 vtbl(virtual table,虚函数表)的首地址。
  • ** 调用过程 **:调用虚函数时,对象通过本身存储的 vptr,在 vtbl 中找到与调用对象匹配的函数指针,再通过这个函数指针调用该函数,实现运行时多态。
  • ** 细节 **:
    • vtbl 是类共用的,vptr 是对象独享的;
    • 对象的内存空间存储着 vptr(4bytes),指向 vtbl 的地址入口;
    • vtbl 保存该类所有虚函数的地址,是一个 ** 函数指针数组 **。

struct 结构体内存对齐

  • ** 原因 **:不用机器硬件对内存空间的处理不同,因此编译器应该提供统一的内存处理形式。
  • ** 原则 **:
    • 存储地址从 0 开始;
    • 每个成员按其大小和指定参数 n 中较小的一个进行对齐;
    • 结构体总长度必须为所有对齐参数的整数倍。
  • ** 自定义对齐参数 **:加上一行代码 # pragma pack (n)n 为自定义的对齐参数

例子 1:

1
2
3
4
5
6
7
struct A {
short a1;
short a2;
short a3;
} A;

sizeof(A) = 6

** 分析:** 每个 short 类型占 2 个字节大小,A 的内存地址是 0-5,共 6 个字节。

例子 2:

1
2
3
4
5
6
struct B {
long a1;
short a2;
} B;

sizeof(B) = 8

** 分析:**long 类型占 4 个字节,a1 的内存地址是 0-3,short 占两个字节,内存地址是 4-5,因为 ** 结构体总长度必须是所有参数的整数倍,也就是要是 4 的倍数 **,所以结构体的内存地址是 0-7,共 8 个字节

例子 3:

1
2
3
4
5
6
7
struct A {
int a;
char b;
short c;
} A;

sizeof(A) = 8

** 分析:**int 类型占 4 个字节,a 的内存地址是 0-3;char 占 1 个字节,内存地址是 4;short 占 2 个字节,所以 ** 要跳过 5,从 6 开始 **,内存地址是 6-7。整个结构体的内存地址是 0-7,共 8 个字节。

例子 4:

1
2
3
4
5
6
7
struct B {
char b;
int a;
short c;
} B;

sizeof(B) = 12

** 分析:char 类型占 1 个字节,b 的内存地址是 0;int 类型占 4 个字节,所以要跳过 1-3,从 4 开始,内存地址是 4-7;short 类型占 2 个字节,内存地址是 8-9。 因为结构体总长度必须为所有对其参数的整数倍,所以必须是 4 的倍数 **。即结构体的内存地址是 0-11,共 12 个字节。

   可以看出,例子 3 和例子 4 两个结构存储的内容都是一样的,但是由于声明的顺序不同,导致结构体最终的大小是不一样的,因此我们在编程的过程中,定义 struct 的时候应该将内存较大的元素放在靠前的位置,尽可能地节省空间。


new 和 malloc 的区别

** 最本质区别 **:new 是运算符(operator),而 malloc 是函数(function)。

  • 分配内存的区域
    • new:从自由存储区(free store)中分配内存,自由存储区可以是堆(heap),也可以是静态存储区(static area)
    • malloc:只能从堆(heap)中分配内存
  • 返回类型的安全性
    • new:返回对象类型的指针,类型严格与对象匹配,类型安全
    • malloc:返回 void*,要强制类型转换
  • 内存分配失败
    • new:抛出 bac_alloc 异常,不会返回 NULL
    • malloc:返回 NULL,需要用户做判断
  • 指定内存大小
    • new:用户不需要制定内存块的大小,编译器会根据类型信息自行计算
    • malloc:用户需要显式地指出所需内存的尺寸
  • 构造和析构
    • new 操作符:
      1. 调用 operator new () 函数,分配内存空间
      2. 调用对象构造函数,传入初值
      3. 返回指向该对象的指针
    • delete 操作符:
      1. 调用对象的析构函数
      2. 调用 operator delete () 函数,释放内存空间
    • malloc 函数:只分配内存空间,返回 void*
    • free 函数:只释放内存空间
  • 支持数组
    • new、delete 支持数组格式,会对数组中每一个对象进行构造或析构
    • malloc、free 不支持构造或析构
  • new,malloc 调用
    • new 的实现可基于 malloc
  • 重载
    • new、delete:可重载
    • malloc、free:不可重载
  • 重新分配内存
    • malloc 分配后,可以用 realloc 进行内存重新分配。先判断当前指针所指向的空间是否有足够的连续空间:
      • 如果有,在原地址的基础上扩大内存地址,返回原指针
      • 如果没有,分配新的空间,将原数据 copy 到新的空间中,然后释放掉原来的空间,返回新地址的指针。

智能指针 shared_prt 和 unique_ptr

  • ** 作用 **:更好的内存管理,防止指针问题带来的内存泄露。

  • ** 重点 **:智能指针是一个类(class),而不是一种新的数据类型(type)。

  • ** 共同点 **:

    • 可以为空,两者都可以直接声明,而不给任何初值。
    • 都有判断条件,给定智能指针 p,通过如果 p 指向了对象,则为 true
    • 通过解引用获得数据,给定智能指针 p,通过 *p 获得所指对象
    • 访问成员变量:给定智能指针 p,通过 p->mem(*p).mem 访问成员变量
    • 获得保存的指针:给定智能指针 p,通过 p.get () 获取 p 中保存的指针
    • 交换两个指针
      • share_ptr:swap (p, q)
      • unique_ptr:p.swap (p, q)

static 的作用

  • 隐藏:在一个文件中定义的 static 变量,在其他源文件中无法访问,实现了对其他源文件的隐藏,因此可以在不同的源文件使用同名的变量。
  • 变量内容持久:类似于声明了一个全局的变量。
  • 默认初始化为 0:static 变量的声明默认值是 0(NULL)

const 成员函数

类中的每一个成员函数前实际上都有一个 this 指针,在一个类的成员函数后加 const 关键字,表明这个函数不能改变类中的成员变量,实际上这个 const 是对 this 修饰的。


explicit 关键字

修饰构造函数,防止由构造函数定义的隐式转换。


Reference

  1. STL 的 vector 为什么成倍扩容
  2. C++ 智能指针用法详解
  3. C++ 中 static 的作用
  4. C++const 成员函数详解
  5. C++explict 关键字作用

Welcome to my other publishing channels