c++高频总结八

发表于 2025/01/09 更新于 2025/01/09

作者 匆匆那年 28 分钟阅读

map为啥用红黑树不用avl树？

std::map使用红黑树而不是AVL树，主要是基于性能和使用场景的综合权衡。以下是具体原因：

1. 插入与删除操作效率

红黑树: 插入和删除操作的重平衡次数较少，复杂度为 O(log⁡n)，但常数因子更小。红黑树允许最多两次旋转即可完成平衡操作。
AVL树: 插入和删除操作可能触发多次旋转，特别是在删除操作中，需要频繁检查和调整子树的平衡。

为什么选择红黑树:

在std::map的典型使用场景中，插入和删除操作的频率较高，因此红黑树因更少的旋转操作具有更高的总体性能。

2. 查找性能对比

AVL树: 是严格平衡的二叉搜索树，每个节点的左右子树高度差最大为1。因此，AVL树的高度通常更低，查找操作稍微更快。
红黑树: 是一种弱平衡树，允许左右子树高度差较大（最多两倍）。因此，查找性能略逊于AVL树，但差异通常很小。

为什么选择红黑树:

在std::map的应用中，查找操作的性能对比并不会明显落后于AVL树。
红黑树在查找、插入、删除的综合性能更优，适合需要频繁增删的动态场景。

3. 内存使用

AVL树: 需要存储每个节点的高度信息，额外的存储开销较大。
红黑树: 只需要一个颜色位来标识节点的颜色（红或黑），额外的存储开销较小。

为什么选择红黑树:

对于大规模数据结构，红黑树占用的内存较少，更加经济。

4. 实现与维护复杂度

AVL树: 因为需要严格平衡，插入、删除操作的重平衡逻辑更复杂。
红黑树: 平衡条件更宽松，插入和删除的实现相对简单。

为什么选择红黑树:

红黑树的实现更简单，调试和维护成本更低，这对于标准库实现尤为重要。

5. 实际应用场景需求

std::map在许多场景中被用作动态字典，需要频繁地进行插入、删除和查找操作。
红黑树在这些综合操作中表现更均衡，满足大多数使用需求。

为什么选择红黑树:

AVL树适合读操作非常频繁而写操作较少的场景，而红黑树则在读写混合操作中表现更优，适合std::map的使用模式。

总结

红黑树被选择为std::map的底层实现是因为其：

插入与删除效率高：旋转次数少，性能更均衡。
内存开销低：只需额外存储一个颜色位。
实现复杂度低：平衡条件宽松，操作逻辑简单。
综合性能优：在读写混合场景下表现更出色。

虽然AVL树在查找性能上略优，但这一优势通常被红黑树在插入和删除上的高效所抵消，因此红黑树更适合std::map的实际需求。如果查找性能是绝对优先级，可以考虑使用std::unordered_map，其基于哈希表的实现能提供均摊 O(1)的查找效率。

inline失效场景

在C++中，inline关键字用于建议编译器将函数的调用替换为函数体（内联展开），以减少函数调用的开销。然而，inline并不保证一定会被内联，编译器可能基于具体情况决定是否忽略inline建议。以下是一些inline失效的常见场景：

1. 函数体过于复杂

原因: 如果函数体过大，内联展开会导致代码膨胀，从而降低程序性能（例如增加指令缓存压力）。
编译器行为: 大多数现代编译器会忽略inline并按正常方式调用函数。

示例:

  
inline void complex_function() {
    for (int i = 0; i < 10000; ++i) {
        std::cout << i << std::endl;
    }
}

由于函数体过大，编译器可能不会进行内联。

2. 递归函数

原因: 递归函数在调用时本质上需要栈帧支持，无法直接内联。
编译器行为: 即使标记为inline，递归函数通常不会被内联。

示例:

  
inline int factorial(int n) {
    return (n == 0) ? 1 : n * factorial(n - 1);
}

编译器无法将递归调用内联展开。

3. 虚函数

原因: 虚函数的调用通常需要通过虚表（vtable）进行动态绑定，而动态绑定在编译时无法确定具体函数地址。
编译器行为: 虚函数在多态调用时不会被内联。

示例:

  
class Base {
public:
    virtual inline void func() {
        std::cout << "Base function" << std::endl;
    }
};

void call_func(Base* b) {
    b->func(); // 动态绑定，不能内联
}

例外: 如果调用是静态绑定的（如通过对象直接调用），编译器可能会内联。

4. 函数指针或间接调用

原因: 函数指针调用的目标在编译时无法确定。
编译器行为: 间接调用不会内联。

示例:

  
inline void my_function() {
    std::cout << "Hello, inline!" << std::endl;
}

void (*func_ptr)() = my_function;

void call_func() {
    func_ptr(); // 函数指针调用，无法内联
}

5. 跨翻译单元（Translation Unit）调用

原因: 如果一个inline函数的定义和调用分布在不同的翻译单元中，编译器可能无法对其进行内联。
编译器行为: 编译器会将inline函数视为普通函数调用，并在链接时解决。

示例:

  
// File1.cpp
inline void my_function() {
    std::cout << "Inline function in another TU" << std::endl;
}

// File2.cpp
void call_func() {
    my_function(); // 在不同翻译单元中，可能失效
}

解决方法: 确保inline函数定义在头文件中，并在所有需要使用的地方包含。

6. 优化级别限制

原因: 编译器的优化级别会影响inline的行为。如果未启用优化（如-O0），编译器可能忽略inline。
编译器行为: 低优化级别下，inline函数可能被视为普通函数。

示例:

g++ -O0 main.cpp

在这种情况下，inline函数可能不会被内联。

7. 强制忽略内联

原因: 某些编译器选项或特定场景下会强制忽略inline，如调试模式需要保留完整的函数调用信息。
编译器行为: 强制将inline函数视为普通函数。

示例:

使用

-fno-inline

选项：

g++ -fno-inline main.cpp

8. 尾调用优化

原因: 如果函数可以通过尾调用优化（Tail Call Optimization）消除栈帧，编译器可能更倾向于这种优化，而非内联。
编译器行为: 优先进行尾调用优化而不是内联。

总结

inline是对编译器的建议，而非强制要求。编译器决定是否内联时，通常会考虑以下因素：

函数的复杂度。
是否能够静态绑定。
是否需要跨翻译单元。
当前的编译器优化级别。

如果必须确保函数内联，可以使用编译器特定的强制内联指令，例如：

GCC/Clang: __attribute__((always_inline))
MSVC: __forceinline

然而，强制内联可能导致代码膨胀，使用时需要谨慎权衡性能和代码大小。

C++中struct和class区别

在C++中，struct和class是非常相似的，两者都可以用来定义数据结构和成员函数，但它们在语法和默认行为上有一些区别。以下是详细对比：

1. 默认访问权限

struct: 默认成员访问权限是公有的（public）。
class: 默认成员访问权限是私有的（private）。

示例:

  
struct MyStruct {
    int a;       // 默认 public
};

class MyClass {
    int a;       // 默认 private
};

区别:

如果不显式声明public或private，在struct中，成员和继承默认为public；在class中，默认为private。

2. 继承默认访问权限

struct: 默认继承方式是public。
class: 默认继承方式是private。

示例:

  
struct BaseStruct {};
struct DerivedStruct : BaseStruct {};  // 默认 public 继承

class BaseClass {};
class DerivedClass : BaseClass {};    // 默认 private 继承

区别:

在struct中，派生类默认以public继承。
在class中，派生类默认以private继承。

3. 语义意图

struct: 更倾向于用作简单的数据结构（POD：Plain Old Data），主要用于存储数据，没有复杂的行为。
class: 更倾向于定义具有封装、继承、多态等特性的复杂对象。

示例:

  
struct Point {
    int x, y;  // 用于简单数据表示
};

class Shape {
    virtual void draw() = 0;  // 用于定义复杂的行为
};

区别:

这是约定俗成的用法，而非强制。struct和class实际上都可以互换使用。

4. C兼容性

struct: 与C语言中的struct完全兼容。
class: 是C++特有的，不与C语言兼容。

区别:

如果需要与C代码交互，必须使用struct。

5. 模板特化的偏好

在模板的偏特化和偏向表示数据时，开发者倾向于使用struct。

示例:

  
template<typename T>
struct Traits {
    static const bool is_pointer = false;
};

template<typename T>
struct Traits<T*> {
    static const bool is_pointer = true;
};

区别:

struct更常用作元编程工具，因为它默认是public的，且多用于数据特性描述。

6. 构造函数和成员函数

struct和class都支持构造函数、析构函数、成员函数、静态成员、运算符重载等特性。

示例:

  
struct MyStruct {
    int a;
    MyStruct(int x) : a(x) {} // 构造函数
};

class MyClass {
    int a;
public:
    MyClass(int x) : a(x) {}  // 构造函数
};

区别:

功能上没有区别，仅是默认访问权限不同。

7. 多态性和继承

struct和class都支持继承、多态和虚函数。

示例:

  
struct Base {
    virtual void func() {
        std::cout << "Base struct" << std::endl;
    }
};

class Derived : public Base {
    void func() override {
        std::cout << "Derived class" << std::endl;
    }
};

区别:

无本质区别，struct和class都支持面向对象特性。

8. 代码风格约定

struct: 通常用于仅包含数据的简单结构体。
class: 通常用于表示复杂的类和对象，强调封装和行为。

总结对比表

特性	`struct`	`class`
默认成员访问权限	`public`	`private`
默认继承方式	`public`	`private`
面向用途	简单数据结构（POD）	复杂对象（封装、继承、多态）
C语言兼容性	是	否
模板元编程偏好	常用	较少用
支持面向对象特性	支持	支持

总结

struct和class的功能几乎完全相同，主要区别在于默认访问权限和默认继承方式。在实践中，struct更倾向于表示简单的数据结构，而class则用于实现具有复杂行为的对象。但这只是惯例，选择哪一种完全取决于开发者的代码风格和语义表达的需要。

如何防止一个头文件include多次

在C++中，为了防止一个头文件被多次包含，通常使用头文件保护措施。这可以避免重复定义的问题，如multiple definition或redefinition错误。

以下是防止头文件多次包含的两种主要方法：

1. 使用 Include Guard（包含保护宏）

Include Guard 是一种传统且常用的方式，通过定义一个唯一的宏来防止头文件的重复包含。

示例：

  
#ifndef HEADER_FILE_NAME_H
#define HEADER_FILE_NAME_H

// 头文件的内容
class MyClass {
public:
    void doSomething();
};

#endif // HEADER_FILE_NAME_H

原理：

第一次包含头文件时：
- 宏HEADER_FILE_NAME_H尚未定义，因此定义它并处理头文件的内容。
第二次及之后的包含：
- 宏HEADER_FILE_NAME_H已经定义，编译器跳过整个头文件内容。

注意：

宏名称应该唯一，通常使用头文件名并加后缀 _H 或 _HPP。
如果有多个项目或头文件路径复杂，建议在宏名称中加上命名空间或路径标识符。

2. 使用 `#pragma once`

#pragma once 是一种更现代的方式，它告诉编译器只处理该头文件一次，无需显式定义和检查宏。

示例：

  
#pragma once

// 头文件的内容
class MyClass {
public:
    void doSomething();
};

原理：

编译器会自动确保该文件只被包含一次，无需显式检查宏。
它是编译器的指令，与宏定义方式相比更简洁。

优势：

更简单，不需要显式定义宏。
避免了因手动命名宏而引入的错误（如命名冲突）。

缺点：

兼容性较差，虽然大多数现代编译器（如 GCC、Clang、MSVC）都支持，但某些老旧或特定的编译器可能不支持。

两种方法的对比

特性	Include Guard	`#pragma once`
简洁性	较繁琐，需要定义宏	非常简洁
编译器支持	所有标准编译器支持	大多数现代编译器支持
兼容性	完全兼容，跨平台无问题	可能不被部分老旧编译器支持
编译性能	宏检查略低效（需要预处理）	性能稍优（直接由编译器处理）

实际建议

如果项目需要支持广泛的编译器（包括老旧版本），使用 Include Guard，因为它是标准做法，兼容性最好。
如果只需要支持现代编译器（如 GCC、Clang、MSVC 的最新版本），可以使用更简洁的 #pragma once。

这两种方法也可以结合使用，例如：

  
#ifndef HEADER_FILE_NAME_H
#define HEADER_FILE_NAME_H
#pragma once

// 头文件内容

#endif // HEADER_FILE_NAME_H

这样既兼容老旧编译器，又在现代编译器上更高效。

lambda表达式的理解，它可以捕获哪些类型

在C++中，lambda表达式是一种简洁的语法，用于定义匿名函数。它可以通过捕获机制访问上下文中的变量。以下是对lambda表达式及其捕获机制的详细理解，包括可以捕获哪些类型的变量。

1. Lambda表达式的基本结构

Lambda表达式的基本形式如下：

  
[capture_list] (parameters) -> return_type {
    // Function body
};

capture_list: 捕获上下文变量的方式。
parameters: 函数参数。
return_type: 返回类型（可省略，由编译器推导）。
函数体: Lambda的逻辑。

2. 捕获的方式

捕获上下文变量的方式：

值捕获（capture by value）:

将上下文中的变量复制一份，Lambda 内部使用的是该副本。
原始变量的修改不会影响 Lambda 内的变量，反之亦然。
捕获到的值在 Lambda 生命周期内固定。

示例:

  
int x = 10;
auto lambda = [x]() { return x + 5; }; // 捕获 x 的值
x = 20;                               // 不影响 lambda 中的 x
std::cout << lambda();                // 输出 15

引用捕获（capture by reference）:

捕获上下文变量的引用，Lambda 内部直接操作原始变量。
Lambda 生命周期内，外部变量的变化会影响 Lambda 内部变量，反之亦然。

示例:

  
int x = 10;
auto lambda = [&x]() { return x + 5; }; // 捕获 x 的引用
x = 20;                                // 影响 lambda 中的 x
std::cout << lambda();                 // 输出 25

值与引用混合捕获:

可以同时捕获某些变量的值，某些变量的引用。

示例:

  
int x = 10, y = 20;
auto lambda = [x, &y]() { return x + y; }; // x 值捕获，y 引用捕获
y = 30;
std::cout << lambda();                     // 输出 40

捕获列表的特殊符号：

[=]: 默认值捕获，将上下文中所有变量按值捕获。
[&]: 默认引用捕获，将上下文中所有变量按引用捕获。
[this]: 捕获当前对象的指针。
- 如果在类的成员函数中使用 Lambda，可以通过捕获this访问成员变量。
[x, this]: 捕获特定变量和当前对象指针。
[x, &y]: 捕获特定变量的值和引用。

示例:

  
class MyClass {
    int value = 42;
public:
    void print() {
        auto lambda = [this]() { std::cout << value << std::endl; };
        lambda();
    }
};

3. 捕获的类型

Lambda 可以捕获以下类型的变量：

3.1 普通变量

值捕获：复制变量。
引用捕获：操作变量的引用。

3.2 指针

Lambda 直接捕获指针并使用，但不会捕获指针所指向的对象。

示例:

  
int x = 10;
int* ptr = &x;

auto lambda = [ptr]() { return *ptr + 5; }; // 捕获指针 ptr 的值
x = 20;
std::cout << lambda();                     // 输出 25

3.3 类的成员变量

通过捕获this指针，Lambda 可以访问类的成员变量。

示例:

  
class MyClass {
    int value = 10;
public:
    void process() {
        auto lambda = [this]() { value += 5; }; // 捕获 this
        lambda();
        std::cout << value << std::endl;       // 输出 15
    }
};

3.4 静态变量

静态变量不需要捕获，可以直接在 Lambda 内部访问。

示例:

  
static int x = 10;
auto lambda = []() { return x + 5; };
std::cout << lambda(); // 输出 15

3.5 全局变量

全局变量和静态变量一样，不需要捕获，可以直接使用。

示例:

  
int global_var = 10;
auto lambda = []() { return global_var + 5; };
std::cout << lambda(); // 输出 15

4. 捕获列表中的限制

4.1 不允许重复捕获：

捕获列表中的变量不能同时按值和按引用捕获。

错误示例:

  
int x = 10;
auto lambda = [x, &x]() { return x; }; // 错误，重复捕获

4.2 动态分配的内存捕获：

Lambda 只能捕获变量本身，如果是动态分配的内存，需小心管理其生命周期。

示例:

  
int* ptr = new int(10);
auto lambda = [ptr]() { return *ptr; };
// 需要手动管理内存
delete ptr;

5. 注意事项

5.1 生命周期问题

引用捕获的变量如果在 Lambda 使用时已经销毁，会引发未定义行为。

示例:

  
auto lambda = []() -> int& {
    int x = 10;  // x 在 lambda 外已销毁
    return x;    // 未定义行为
};
// 注意看是返回的引用，而x在lambda结束后就会销毁，所以会导致未定义的行为

5.2 线程安全

值捕获和引用捕获可能导致线程安全问题，尤其是引用捕获可能在多线程中引发数据竞争。

总结

Lambda 表达式的捕获机制是其灵活性的核心，可以捕获：

局部变量（按值或引用）。
指针（但不捕获指针所指向的对象）。
类的成员变量（通过捕获this）。
静态变量和全局变量（无需捕获直接访问）。

选择捕获方式时，应根据需要权衡性能与安全性，特别是值捕获和引用捕获的选择对代码行为有重要影响。

C++, C++面经

C++ 面经

本文由作者按照 CC BY 4.0 进行授权

map为啥用红黑树不用avl树？

1. 插入与删除操作效率

2. 查找性能对比

3. 内存使用

4. 实现与维护复杂度

5. 实际应用场景需求

总结

inline失效场景

1. 函数体过于复杂

2. 递归函数

3. 虚函数

4. 函数指针或间接调用

5. 跨翻译单元（Translation Unit）调用

6. 优化级别限制

7. 强制忽略内联

8. 尾调用优化

总结

C++中struct和class区别

1. 默认访问权限

2. 继承默认访问权限

3. 语义意图

4. C兼容性

5. 模板特化的偏好

6. 构造函数和成员函数

7. 多态性和继承

8. 代码风格约定

总结对比表

总结

如何防止一个头文件include多次

1. 使用 Include Guard（包含保护宏）

原理：

注意：

2. 使用 #pragma once

原理：

优势：

缺点：

两种方法的对比

实际建议

lambda表达式的理解，它可以捕获哪些类型

1. Lambda表达式的基本结构

2. 捕获的方式

捕获上下文变量的方式：

捕获列表的特殊符号：

3. 捕获的类型

3.1 普通变量

3.2 指针

3.3 类的成员变量

3.4 静态变量

3.5 全局变量

4. 捕获列表中的限制

4.1 不允许重复捕获：

4.2 动态分配的内存捕获：

5. 注意事项

5.1 生命周期问题

5.2 线程安全

总结

热门标签

2. 使用 `#pragma once`