当前位置： 首页 > article >正文

C++相关面试题总结一——内存、关键字、STL、指针、排序、Lambda

article 2024/12/30 2:21:47

面试题总结

基础

C++是在C语言的基础上开发的一种面向对象编程语言，应用广泛。C++支持多种编程范式：面向对象编程、泛型编程和过程化编程。其编程领域众广，常用于系统开发，引擎开发等应用领域，是最受广大程序员受用的最强大编程语言之一，支持类：类、封装、重载等特性!

C++在C的基础上增添类，C是一个结构化语言，它的重点在于算法和数据结构。C程序的设计首要考虑的是如何通过一个过程，对输入（或环境条件）进行运算处理得到输出（或实现过程（事务）控制）；而对于C++，首要考虑的是如何构造一个对象模型，让这个模型能够契合与之对应的问题域，这样就可以通过获取对象的状态信息得到输出或实现过程（事务）控制。

面向对象是一种对现实世界理解和抽象的方法、思想，通过将需求要素转化为对象进行问题处理的一种思想。

设计模式（Design pattern）是一套被反复使用、多数人知晓的、经过分类编目的、代码设计经验的总结。

  • 比如单例模式，保证一个类仅有一个实例，并提供一个访问它的全局访问点。
    适用于：当类只能有一个实例而且客户可以从一个众所周知的访问点访问它时；当这个唯一实例应该是通过子类化可扩展的，并且客户应该无需更改代码就能使用一个扩展的实例时。

  • 比如工厂模式，定义一个用于创建对象的接口，让子类决定实例化哪一个类。Factory Method 使一个类的实例化延迟到其子类。
    适用于：当一个类不知道它所必须创建的对象的类的时候；当一个类希望由它的子类来指定它所创建的对象的时候；当类将创建对象的职责委托给多个帮助子类中的某一个，并且你希望将哪一个帮助子类是代理者这一信息局部化的时候。

    大于一个字节的值被称为多字节量，多字节量存在高位有效字节和低位有效字节 (关于高位和低位，我们以十进制的数字来举例，对于数字482来说，4是高位，2是低位），微处理器有两种不同的顺序处理高位和低位字节的顺序：
    ● 小端（little_endian)：低位有效字节存储于较低的内存位置
    ● 大端（big_endian)：高位有效字节存储于较低的内存位置

内存管理

内存布局
如上图（图与本小节内存来源为：内存布局），表示了c++程序的内存分布。

  • Code Segment（代码区）
    也称Text Segment，存放可执行程序的机器码。

  • Data Segment (数据区）
    存放已初始化的全局和静态变量， 常量数据（如字符串常量）。

  • BSS（Block started by symbol)
    存放未初始化的全局和静态变量。（默认设为0）

  • Heap（堆）
    从低地址向高地址增长。容量大于栈，程序中动态分配的内存在此区域。

  • Stack（栈）
    从高地址向低地址增长。由编译器自动管理分配。程序中的局部变量、函数参数值、返回变量等存在此区域。

内存对齐

对于基础类型，如float, double, int, char等，它们的大小和内存占用是一致的。而对于结构体而言，如果我们取得其sizeof的结果，会发现这个值有可能会大于结构体内所有成员大小的总和，这是由于结构体内部成员进行了内存对齐。

为什么要进行内存对齐？？？

  • 内存对齐使数据读取更高效
  • 在某些平台下，不进行内存对齐会崩溃

在硬件设计上，数据读取的处理器只能从地址为k的倍数的内存处开始读取数据。这种读取方式相当于将内存分为了多个"块“，假设内存可以从任意位置开始存放的话，数据很可能会被分散到多个“块”中，处理分散在多个块中的数据需要移除首尾不需要的字节，再进行合并，非常耗时。

为了提高数据读取的效率，程序分配的内存并不是连续存储的，而是按首地址为k的倍数的方式存储；这样就可以一次性读取数据，而不需要额外的操作。

对齐规则：
定义有效对齐值（alignment）为结构体中 最宽成员 和 编译器/用户指定对齐值 中较小的那个。

(1) 结构体起始地址为有效对齐值的整数倍
(2) 结构体总大小为有效对齐值的整数倍
(3) 结构体第一个成员偏移值为0，之后成员的偏移值为 min(有效对齐值, 自身大小) 的整数倍

相当于每个成员要进行对齐，并且整个结构体也需要进行对齐。

struct A
{
    int i;
    char c1;
    char c2;
};
 
struct B
{
    char c1;
    int i;
    char c2;
};
 
int main()
{
    cout << sizeof(A) << endl; // 有效对齐值为4, output : 8
    cout << sizeof(B) << endl; // 有效对齐值为4, output : 12
    return 0;
}

内存碎片

程序的内存往往不是紧凑连续排布的，而是存在着许多碎片。我们根据碎片产生的原因把碎片分为内部碎片和外部碎片两种类型：

(1) 内部碎片：系统分配的内存大于实际所需的内存（由于对齐机制）；

(2) 外部碎片：不断分配回收不同大小的内存，由于内存分布散乱，较大内存无法分配。

垃圾回收机制

三种基本的垃圾收集算法：

  • 引用计数算法
    缺点：1. 无法处理循环引用问题；2. 多线程同时操作引用计数时，可能导致不一致的问题，需要并发控制机制

  • 标记清除算法
    缺点：1. 不能向引用计数对内存进行即时回收；2. 收集垃圾时需要中断正常程序，当内存大、对象多时，中断过程会较长。

  • 节点复制算法
    特点：回收对象越多，开销越小，回收对象越少，开销越大；内存被分为两部分，不能同时使用，内存变小。

分代回收：
通过对这三种方式的融合，出现了一些更加高级的方式。而高级GC技术中最重要的一种为分代回收。它的基本思路是这样的：程序中存在大量的这样的对象，它们被分配出来之后很快就会被释放，但如果一个对象分配后相当长的一段时间内都没有被回收，那么极有可能它的生命周期很长，尝试收集它是无用功。为了让GC变得更高效，我们应该对刚诞生不久的对象进行重点扫描，这样就可以回收大部分的垃圾。为了达到这个目的，我们需要依据对象的”年龄“进行分代，刚刚生成不久的对象划分为新生代，而存在时间长的对象划分为老生代，根据实现方式的不同，可以划分为多个代。

c++ 本身没有垃圾回收机制，但是提供了基于 引用计数算法 的智能指针进行内存管理；同时也有一部分不作为 c++标准的垃圾回收库，如 Boehm 库。

重要关键字

const 的主要作用

  1. 定义只读变量，即常量；
  2. 修饰函数的参数和函数的返回值；
    • const 修饰参数，参数通常为指针或者引用，保护对象的属性；
    • const 修饰返回值，当返回值为引用返回时，可以保护对象不被修改；
  3. 修饰成员变量：需要在构造函数的初始化列表中初始化；
  4. 修饰成员函数：防止成员函数修改成员变量的内容；（使用 mutable 可以强行修改）
  5. 修饰类对象：定义常量对象，只能调用常量函数。

C++中有了 malloc / free , 为什么还需要 new / delete

  1. malloc 与 free 是C++/C语言的标准库函数，new/delete 是C++的运算符。它们都可用于申请动态内存和释放内存。
  2. 对于非内部数据类型的对象而言，光用 maloc/free 无法满足动态对象的要求。
    对象在创建的同时要自动执行构造函数，对象在消亡之前要自动执行析构函数。
    由于 malloc/free 是库函数而不是运算符，不在编译器控制权限之内，不能够把执行构造函数和析构函数的任务强加于 malloc/free。
  3. 因此C++语言需要一个能完成动态内存分配和初始化工作的运算符 new，以及一个能完成清理与释放内存工作的运算符 delete。注意 new/delete 不是库函数。

指针

智能指针

避免申请的空间在函数结束时忘记释放，可以减少野指针（wild）和空指针（dangling），也就是内存泄漏的产生。

野指针：没有被初始化的指针
空指针：指针最初指向的内存已经被释放的指针

  • unique_ptr ：
    保证同一时间只有一个智能指针可以指向该对象，避免空间泄漏
  • shared_ptr ：
    强引用。多个智能指针可以指向相同对象，但是该对象 仅在 “最后一个引用被销毁时” 释放
  • weak_ptr ：
    弱引用。协助 shared_ptr 工作，其构造和析构不会引起引用计数的增加或者减少，防止 两个 shared_ptr 相互引用导致的
    死锁问题（资源永不释放）

智能指针是一个类！类会自动调用析构函数，自动释放内存！

空指针nullptr：替代NULL(0)，类型为nullptr_t，隐式转换为任何指针或成员指针的类型

使用智能指针需要引入头文件 

#include <memory>
#include <iostream>

class C
{
	~C() { std::cout << "destroyed\n" }
};

void test();

void test()
{
	std::shared_ptr<C> ptr1 = new C;
	std::shared_ptr<C> ptr2 = ptr1;
}

int main()
{
	test();
	// 等到两个shared_ptr均失效，new获得的指针就会自动被释放。
	std::cin.get(); // 回车键退出
}
  • 缺点：不能释放循环引用

引用和指针

  1. 引用的变量的一个别名，内部实现是只读指针；
  2. 引用只能在初始化时被赋值，其他时候值不能被改变，指针的值可以在任何时候被改变；
  3. 引用不能为 NULL，指针可以为 NULL；
  4. 引用变量内存单元保存的是被引用变量的地址；
  5. ”sizeof 引用“ = 指向变量的大小； ”sizeof 指针“ = 指针本身的大小；
  6. 指针和引用的自增（++）运算意义不一样；
  7. 指针可以有多级指针，但是引用只能是一级的；
  8. 引用可以取地址操作，返回的是被引用变量本身所在的内存单元地址；
  9. 从内存分配上，程序为指针变量分配内存区域，而引用不需要分配内存区域；
  10. 引用使用在源代码级相当于普通的变量一样使用，做函数参数时，内部传递的实际是变量地址。

参数传递

形参：在函数定义时出现的参数
实参：函数实际调用的参数

  • 指针：形参为指向实参地址的指针。对指针进行地址操作时，会改变实参。编译时将“指针变量名-指针变量的地址”添加到符号表中；
  • 引用：形参是实参的别名，不可修改，必须初始化。在栈中开辟形参的空间，存放的是实参的地址。编译时将“引用变量名-引用对象的地址”添加到符号表中；
  • 值：形参是实参的拷贝。在栈中开辟了空间，将实参复制给形参，改变形参不会修改实参。

指针参数传递&引用参数传递：指针传参的本质是值传递，传递地址值 / 引用传参是地址传递，传递引用变量

编译的角度：指针在符号表上对应的地址值为指针变量的地址（可修改指向的对象），引用在符号表上对应的地址值为引用对象的地址（不可修改被引用的对象）

其他

Lambda 表达式

类似匿名函数（需要函数体，不需要函数名），可以理解为简易版函数。
基本格式： [捕获方式] (参数) -> 返回值类型 {函数体}（可以忽略返回类型，lambda自动推断出返回类型）。
[ ]：闭包形式(closure type)，即定义一个lambda表达式后，编译器会自动生成一个重载()运算符的匿名类。优势在于可以通过传值或引用的方式捕获其封装作用域内的变量（即捕获方式中存在的变量）

  • 捕获方式：
    [ ]：不捕获任何变量
    [=]：值捕获所有变量
    [&]：引用捕获所有变量
    [x]：值捕获 x 变量，其他变量不捕获
    [&x]：引用捕获 x 变量，其他变量不捕获
    [=,&x]：以值捕获所有变量，除 x 用引用捕获
    [&,x]：以引用捕获所有变量，除 x 用值捕获
    [this]：引用捕获当前对象（复制指针）
    [*this]：传值方式捕获当前对象

lambda 的性能优势：
1. 内联函数：
编译器自动将 lambda 表达式内联，这意味着代码直接插入到调用函数中。
可以减少函数调用的开销，并提高性能。
2. 避免命名函数的开销：
lambda 表达式没有名称，因此不必被声明和存储在符号表中，
可以减少开销，并提高性能。
3. 改善高速缓存局部性：
lambda 表达式可以在同一个函数中定义和使用，这意味着 lambda 使用的代码和数据
存储在与调用代码相同的高速缓存行中。
可以改善高速缓存局部性并降低高速缓存失效的成本。
4. 减小代码大小：
lambda 表达式通常比命名函数小，并不需要外部函数调用，
这可以减小编译代码的大小并提高性能。
5. 增加灵活性：
lambda 表达式可以用来将函数作为参数传递给其他函数，
这提高了灵活性、可以改善性能、减少重复代码的需求。

	vector<int> numbers = { 1, 2, 3, 4, 5, 6 };
	// lambda , 用于查找两个数字的和
	auto sum = [](int a, int b) {return a + b; };
	int result = accumulate(numbers.begin(), numbers.end(), 0, sum);
	cout << "sum of elements in the vector: " << result << endl;

	int sum_c = 0;
	for_each(numbers.begin(), numbers.end(), [&sum_c](int x) {sum_c += x; });
	cout << "the sum is: " << sum_c << endl;

	// capturing default
	auto square = [](int x) {return x * x; };
	cout << "The square of 5 is: " << square(5) << endl;

	// capturing by value
	int x = 42;
	auto f = [x]() {cout << "x = " << x << endl; };
	f();
	auto fp1 = [x](int y) {cout << "x + y = " << x+y << endl; };
	fp1(1);

	// capturing by reference
	auto fbyref = [&x]() {cout << "x = " << x << endl; };
	fbyref();
	auto addOne = [&x]() {++x; };
	addOne();
	cout << "after addOne x = " << x << endl;

	// mutable lambda
	auto fmutable = [x]() mutable { cout << "++x, x = " << ++x << endl; };
	fmutable();

深拷贝&浅拷贝

浅拷贝：系统默认的拷贝函数；
深拷贝：在堆内存中另外申请空间来存储数据。
当数据成员中有指针时，必须用深拷贝，否则会造成野指针等空间泄露的问题。

同步IO和异步IO

A. 同步：
所谓同步，就是在发出一个功能调用时，在没有得到结果之前，该调用就不返回。
按照这个定义，其实绝大多数函数都是同步调用（例如sin isdigit等）。
但是一般而言，我们在说同步、异步的时候，特指那些需要其他部件协作或者需要一定时间完成的任务。
最常见的例子就是 SendMessage。
该函数发送一个消息给某个窗口，在对方处理完消息之前，这个函数不返回。
当对方处理完毕以后，该函数才把消息处理函数所返回的值返回给调用者。

B. 异步：
异步的概念和同步相对。
当一个异步过程调用发出后，调用者不会立刻得到结果。
实际处理这个调用的部件是在调用发出后，通过状态、通知来通知调用者，或通过回调函数处理这个调用。

STL

序列式容器

元素在容器中的位置顺序存储和访问。
vector：高效的随机存取；
list：大量的插入和删除；
deque：即要求高效的随机存取，有需要数据两端的插入和删除。

关联式容器

  • 红黑树：
    set / map / multiset / multimap
  • 哈希表：
    unordered_set / unordered_map / unordered_multiset / unordered_multimap
带 unordered = 无序
带 multi = 允许键(key)重复
insert_equal：允许键值重复
insert_unique：不允许键值重复

Set
Map

排序算法

排序算法

冒泡排序

void BubbleSort(int arr[], int n)
{
    for (int i = 0; i < n - 1; i++) {
        for (int j = 0; j < n - i - 1; j++) {
            if (arr[j] > arr[j + 1]) { // 相邻元素比较
                int temp = arr[j]; 
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;  //交换两个元素
            }
        }
    }
}

选择排序

void SelectSort(int arr[], int n)
{
	int i, j, min; //min = 最小元素
	int t = 1;
	for (i = 0; i < m - 1; i++) { //共有m个元素，只需要比m-1次
		min = i;
		for (j = i + 1; j < m; j++) {
			if (arr[j] < arr[min])
				min = j; //下标变化，一直是比较后目前最小的数的下标
		}
		if (min != i) { //如果最小数下标改变了，进行数的交换
			t = arr[min];
			arr[min] = arr[i];
			arr[i] = t;
		}
	}
}

插入排序


http://www.kler.cn/a/6236.html

相关文章：

  • JVM学习-内存结构（二）
  • 【Elasticsearch】DSL查询文档
  • 芯科科技蓝牙、Wi-Fi、Wi-SUN产品广获业界认可，技术创新引领行业潮流
  • 基于Bregman的交替方向乘子法
  • LeetCode：3159. 查询数组中元素的出现位置（hash Java）
  • arcface
  • 【iOS】—— 类和对象底层探索
  • SpringBoot国际化配置
  • 通过 NFTScan 追踪 NFT 钻石手持仓
  • mysql binlog 一直追加写，磁盘满了怎么办？
  • Win11启用IE方法
  • 超详细WindowsJDK1.8与JDK11版本切换教程
  • PCB模块化设计11——VGA高速PCB布局布线设计规范
  • nanovg绘图库的编译与使用
  • 【Python】数据容器--列表常用方法
  • 23种Java设计模式知识要点
  • （1）深入解析图像字幕生成数据集———Coco dataset
  • Scala的数组，元组，列表，集，映射（Map），迭代器(iterator)
  • LC-831. 隐藏个人信息（字符串模拟）
  • 深度解析Python函数的使用与实现
  • 【C++从0到1】4.程序的注释
  • 为社会开发，无障碍开发，开发人员的公益时间
  • 【面试】Raft算法详解
  • JavaScript 获取时间范围（当天，本月（30天间隔），momentJS基本使用）
  • 【EHub_tx1_tx2_E100】 WLR-720多线激光 雷达在Ubuntu18.04 + ROS_ Melodic 环境评测
  • Linux之父：连你自己都懒得解释，那这就是一堆垃圾！