Halo

A magic place for coding

0%

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

Posted on Edited on Valine:

面试总结之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个元素，倍增m，push_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