虾皮高性能C++后端一面

来源：https://www.nowcoder.com/feed/main/detail/17c9377a41754602b32919e053dcb6e4

C++

1、如何解决不同编译单元间 static 变量析构顺序不一致的问题？

在C++中，静态存储期对象（包括全局对象、命名空间作用域的静态对象、类静态成员以及函数内的局部静态对象）的构造顺序在同一个编译单元内是确定的（按定义顺序），但跨编译单元的构造和析构顺序是未定义的。

这种不确定性被称为“静态初始化顺序问题”和“静态析构顺序问题”。当一个静态对象的析构依赖于另一个可能已被析构的静态对象时，就会发生问题，导致程序崩溃或未定义行为。

解决静态变量析构顺序不一致的问题，通常有以下几种策略：

1.1、Meyer's Singleton（局部静态单例）

这是C++中最常用且推荐的解决方案之一。它利用了C++11及更高版本中局部静态变量的特性：局部静态变量的初始化是线程安全的，并且只在首次调用时进行，其析构顺序与构造顺序相反，且在main函数结束后或std::exit调用时进行。

通过将静态对象封装在一个返回其引用的函数中，可以确保该对象在首次需要时才被构造，并且其析构发生在所有依赖它的对象之后。

cpp

// Logger.h
class Logger {
public:
    void log(const std::string& message) { /* ... */ }
    // ...
private:
    Logger() = default;
    ~Logger() = default;
    Logger(const Logger&) = delete;
    Logger& operator=(const Logger&) = delete;
public:
    static Logger& getInstance() {
        static Logger instance; // 局部静态变量，C++11保证线程安全初始化
        return instance;
    }
};

// main.cpp 或其他编译单元
void foo() {
    Logger::getInstance().log("Hello from foo");
}

这种方法确保了Logger实例的生命周期由其首次使用决定，并且在程序结束时正确析构，避免了跨编译单元的顺序问题。

1.2、资源获取即初始化 (RAII) 原则

虽然RAII本身不是直接解决析构顺序的方案，但它是C++管理资源的核心思想。

结合智能指针（如std::unique_ptr或std::shared_ptr）来管理动态分配的资源，可以避免将复杂对象作为全局静态变量。

智能指针的析构是确定的，当其作用域结束时，它所管理的资源会被释放。

1.3、避免全局/跨编译单元静态对象间的依赖

最根本的解决方案是重新设计代码，减少或消除不同编译单元中静态对象之间的依赖关系。如果必须存在依赖，则应将它们集中到同一个编译单元中，并按照正确的顺序定义，以确保构造和析构顺序的确定性。

1.4、`std::atexit`：

std::atexit函数允许注册在程序正常终止时（即main函数返回或调用std::exit时）执行的函数。这些注册的函数会以注册顺序的逆序被调用。

虽然可以用来管理静态资源的释放，但它通常不如Meyer's Singleton方便和安全，因为它需要手动管理资源的生命周期，并且不处理异常安全问题。

2、C++ 中是否有语言特性可以解决上述析构顺序问题？

是的，C++11引入的局部静态变量的线程安全初始化特性在很大程度上解决了静态初始化顺序问题，从而间接解决了析构顺序问题。

对于局部静态变量，标准保证了其初始化只发生一次，并且是线程安全的。

更重要的是，它们的析构顺序是确定的：在main函数结束后，局部静态变量会按照其构造顺序的逆序进行析构。

这使得Meyer's Singleton模式成为一个可靠的解决方案。

此外，C++20引入了constinit关键字，它用于确保具有静态或线程存储期的变量在静态初始化阶段就被完全初始化，而不是在运行时动态初始化。这可以避免静态初始化顺序问题中与动态初始化顺序不确定性相关的问题。

然而，constinit主要关注初始化，对于析构顺序，仍然是局部静态变量的逆序析构规则更为关键。

3、如果在头文件中定义一个 static 变量，会发生什么？

如果在头文件中定义一个非const的static变量（例如 static int counter = 0;），并被多个源文件（.cpp）包含，那么会发生违反“一次定义规则”（One Definition Rule, ODR）的错误，或者导致每个包含该头文件的编译单元都拥有该变量的一个独立副本。

详细分析：

全局或命名空间作用域的static变量：static关键字在全局或命名空间作用域中表示内部链接性。这意味着该变量只在其定义的编译单元内可见。

因此，如果一个头文件中定义了 static int global_static_var;，然后这个头文件被 a.cpp 和 b.cpp 包含，那么 a.cpp 和 b.cpp 将各自拥有一个名为 global_static_var 的独立变量副本。它们之间互不影响。

这通常不是期望的行为，因为开发者可能期望它是一个共享的全局变量。这会导致逻辑错误，因为修改其中一个副本不会影响另一个副本。

cpp

// my_header.h
static int counter = 0; // 定义了一个具有内部链接性的静态变量

// a.cpp
#include "my_header.h"
void increment_a() {
    counter++;
}

// b.cpp
#include "my_header.h"
void increment_b() {
    counter++;
}

// main.cpp
#include <iostream>
extern void increment_a();
extern void increment_b();
// 无法直接访问头文件中的counter，因为它是内部链接性
// 如果在main.cpp中也包含my_header.h，那么main.cpp也会有自己的counter副本
int main() {
    increment_a(); // 修改a.cpp中的counter副本
    increment_b(); // 修改b.cpp中的counter副本
    // 此时a.cpp和b.cpp中的counter都是1，但它们不是同一个变量
    return 0;
}

类中的static成员变量：类中的static成员变量是特殊的。它们是类的所有对象共享的，并且只存在一份。
但它们只能在类定义内部声明，必须在类定义外部（通常在对应的.cpp文件中）进行定义和初始化。
如果在头文件中定义并初始化类静态成员，并且该头文件被多个源文件包含，则会违反ODR，导致链接错误。
cpp
```
// MyClass.h
class MyClass {
public:
    static int s_value; // 声明
};
// 错误：不能在这里定义和初始化，否则会违反ODR
// int MyClass::s_value = 0;

// MyClass.cpp
#include "MyClass.h"
int MyClass::s_value = 0; // 正确：在源文件中定义和初始化
```
const static或constexpr static整型成员变量：对于const static或constexpr static的整型（如int, char, enum等）成员变量，可以在类定义内部直接初始化。
它们是编译期常量，编译器会进行特殊处理，不会导致ODR问题。
然而，如果需要取它们的地址，仍然需要在类外进行定义。

4、如何确保一个全局变量在程序中只有一个实例？

确保一个全局变量在程序中只有一个实例的常见方法是使用单例模式。单例模式是一种创建型设计模式，它保证一个类只有一个实例，并提供一个全局访问点来获取这个实例。

在C++中，实现单例模式有多种方式，其中最推荐的是Meyer's Singleton。

Meyer's Singleton (C++11 局部静态变量)

这种方法利用了C++11标准对局部静态变量的特殊保证：

线程安全初始化：局部静态变量的初始化是线程安全的，即使在多线程环境下，也能保证只初始化一次。
延迟初始化：只有当函数首次被调用时，局部静态变量才会被创建。
确定析构顺序：局部静态变量的析构顺序与构造顺序相反，且在main函数结束后进行，避免了跨编译单元的析构顺序问题。

实现示例：

cpp

// Singleton.h
#include <iostream>
#include <string>

class Singleton {
public:
    // 提供一个全局访问点
    static Singleton& getInstance() {
        static Singleton instance; // 局部静态变量，C++11保证线程安全初始化
        return instance;
    }

    void doSomething() {
        std::cout << "Singleton instance doing something." << std::endl;
    }

private:
    // 私有构造函数，防止外部直接创建实例
    Singleton() {
        std::cout << "Singleton constructor called." << std::endl;
    }
    // 私有析构函数，防止外部直接删除实例
    ~Singleton() {
        std::cout << "Singleton destructor called." << std::endl;
    }
    // 禁用拷贝构造函数和赋值运算符，防止复制实例
    Singleton(const Singleton&) = delete;
    Singleton& operator=(const Singleton&) = delete;
};

// main.cpp
int main() {
    Singleton::getInstance().doSomething();
    Singleton::getInstance().doSomething(); // 再次调用，不会再次构造
    return 0;
}

优点：

简单易用：代码简洁，易于理解和实现。
线程安全：C++11标准保证了局部静态变量的线程安全初始化。
延迟初始化：只有在第一次需要时才创建实例，节省资源。
自动管理生命周期：实例的创建和销毁由C++运行时自动管理，无需手动new/delete。

其他方法（不推荐或有局限性）

饿汉式单例：在程序启动时就创建实例。虽然简单，但可能造成资源浪费，且无法解决跨编译单元的初始化顺序问题。
使用extern和定义在单个.cpp文件：在头文件中使用extern声明一个全局变量，然后在唯一的.cpp文件中定义它。这可以确保只有一个实例，但如果该全局变量是一个复杂对象，其初始化和析构仍然可能面临SIOF问题。
cpp
```
// GlobalVar.h
extern MyObject globalObject; // 声明

// GlobalVar.cpp
#include "GlobalVar.h"
MyObject globalObject; // 定义，确保只有一个实例
```
这种方法对于基本类型或简单对象尚可，但对于具有复杂构造和析构逻辑的对象，仍然推荐Meyer's Singleton。

5、在函数中声明一个对象但不初始化，会有什么问题？

在函数中声明一个对象但不初始化，其行为取决于对象的类型：

5.1、基本数据类型（如 `int`, `double`, `char`, 指针等）

如果未初始化，这些局部变量的值是不确定的，也常被称为“垃圾值”。

这意味着它们的值是内存中该位置上原有的任意数据。使用这些不确定的值会导致未定义行为（Undefined Behavior, UB）。

未定义行为是C++中最严重的错误之一，可能导致程序崩溃、产生错误结果、安全漏洞，甚至在不同编译器或不同运行环境下表现出不同的行为，使得调试极其困难。

cpp

void foo() {
    int x; // 未初始化，x 的值不确定
    std::cout << x << std::endl; // 未定义行为！

    int* ptr; // 未初始化，ptr 的值不确定
    *ptr = 10; // 未定义行为！可能写入非法内存地址
}

5.2、类类型对象：

如果类有默认构造函数：对象会被默认构造函数初始化。例如，std::string s; 会调用std::string的默认构造函数，s会被初始化为空字符串。这种情况下，对象是有效且已初始化的。
如果类没有默认构造函数：尝试声明一个没有默认构造函数的类类型对象而不提供初始化参数，会导致编译错误。编译器无法知道如何构造这个对象。

cpp

class MyClassA {
public:
    MyClassA() { std::cout << "MyClassA default constructor" << std::endl; }
};

class MyClassB {
public:
    MyClassB(int val) { std::cout << "MyClassB constructor with int: " << val << std::endl; }
    // 没有默认构造函数
};

void bar() {
    MyClassA objA; // OK，调用默认构造函数
    // MyClassB objB; // 编译错误：没有合适的默认构造函数
    MyClassB objB(10); // OK，调用带int参数的构造函数
}

6、为什么函数内的局部变量（基本类型）如果不初始化，其值是不确定的？

函数内的局部变量（基本类型）如果不初始化，其值是不确定的，这与C++的存储期和初始化规则有关。

自动存储期（Automatic Storage Duration）：
函数内的局部变量通常具有自动存储期。这意味着它们在函数被调用时在栈（stack）上分配内存，并在函数返回时自动释放。栈上的内存是重复利用的，它可能之前被其他函数或变量使用过。当为新的局部变量分配这块内存时，C++标准规定不会自动将其清零或赋予任何特定值，除非显式初始化。
性能考虑：
C++的设计哲学之一是“不为不需要的特性付出代价”。如果编译器每次为局部变量分配内存时都强制进行零初始化，那么会引入额外的运行时开销。对于许多应用场景，变量很快就会被赋值覆盖，零初始化是多余的。因此，C++将这一责任交给了程序员，允许他们根据需要选择是否初始化，从而优化性能。
“垃圾值”的来源：
当一个未初始化的局部变量被分配内存时，它所占据的内存区域可能包含了之前程序运行留下的数据。这些残留数据就是我们所说的“垃圾值”。这些值可以是任何东西，取决于之前这块内存被如何使用，甚至可能因编译器、操作系统、程序运行时间或程序历史路径而异。

示例：

cpp

#include <iostream>

void func1() {
    int a = 10; // 初始化
    std::cout << "func1: a = " << a << std::endl;
}

void func2() {
    int b; // 未初始化
    std::cout << "func2: b = " << b << std::endl; // b 的值不确定
}

int main() {
    func1();
    func2(); // b 可能会显示之前 func1 中 a 的内存位置上的值，或者其他垃圾值
    func2(); // 再次调用，b 的值可能与上次不同
    return 0;
}

7、函数内的局部变量能否被“移动”到堆上？

从概念上讲，函数内的局部变量（通常分配在栈上）不能直接“移动”到堆上。内存中的一个对象一旦被创建，它的地址就确定了。如果你想让一个对象存在于堆上，你必须在堆上创建它。

然而，这里可能存在一些误解或混淆，我们可以从几个角度来理解这个问题：

对象本身的位置：
- 局部变量：默认情况下，函数内的局部变量（非static）是在栈上分配的，具有自动存储期。它们的生命周期与函数调用绑定。
- 堆上对象：要在堆上创建对象，需要使用new运算符（或malloc），这会返回一个指向堆上新分配内存的指针。这个指针本身可以是一个局部变量（在栈上），但它指向的数据在堆上。
你不能简单地将一个已存在的栈上对象的内存区域“搬迁”到堆上，因为这意味着改变了对象的地址，这在C++中通常是通过创建新对象来实现的。
“移动语义” (Move Semantics)：
C++11引入了移动语义，它允许高效地转移资源所有权，而不是进行深拷贝。这通常用于管理堆上资源的对象（如std::vector, std::string, 智能指针等）。
当一个对象（源对象）的资源被“移动”到另一个对象（目标对象）时，源对象通常会将其内部指向堆上数据的指针或句柄转移给目标对象，然后将自己置于一个有效但未指定的状态（通常是“空”或“默认构造”状态）。这个过程并没有改变资源在堆上的物理位置，只是改变了哪个对象拥有和管理这块堆内存。
例如，你可以创建一个局部std::vector对象，它内部管理着一块堆内存。然后你可以将这个局部std::vector“移动”到一个函数参数、返回值或另一个std::vector对象中。
此时，std::vector内部的堆内存并没有从栈移动到堆，而是其所有权从一个栈上的std::vector实例转移到了另一个std::vector实例（可能在栈上，也可能在堆上，取决于接收它的std::vector实例本身的位置）。
cpp
```
#include <vector>
#include <iostream>

std::vector<int> createVector() {
    std::vector<int> local_vec = {1, 2, 3}; // local_vec 在栈上，但其数据在堆上
    return local_vec; // 返回时，发生移动语义（如果编译器优化或有移动构造函数）
}

int main() {
    std::vector<int> my_vec = createVector(); // my_vec 接收了 local_vec 的堆资源
    // local_vec 的堆数据没有从栈移动到堆，而是其所有权从一个栈对象转移到另一个栈对象
    // 如果 my_vec 是通过 new 创建的，那么它本身就在堆上

    // 假设我们想把一个栈上的基本类型放到堆上，需要显式创建
    int stack_int = 42;
    int* heap_int_ptr = new int(stack_int); // 在堆上创建了一个新的int，并用stack_int的值初始化
    std::cout << "Stack int: " << stack_int << std::endl;
    std::cout << "Heap int: " << *heap_int_ptr << std::endl;
    delete heap_int_ptr;
    return 0;
}
```

严格来说，函数内的局部变量（栈上对象）不能被“移动”到堆上。如果需要对象在堆上，必须使用new等操作符在堆上显式创建。移动语义是关于资源所有权的转移，而不是对象本身内存位置的转移。对于管理堆资源的类（如std::vector），移动语义可以高效地转移其内部的堆资源，而无需重新分配和复制数据。

8、基本数据类型（如 int）是否可以通过 move 操作移动到堆上？

不能。

对于像 int 这样的基本数据类型，std::move操作并不会将其“移动”到堆上，甚至通常不会产生任何实际的“移动”效果，而是退化为一次拷贝。

原因如下：

std::move的本质：std::move本身不执行任何移动操作，它只是一个类型转换函数，将一个左值（lvalue）表达式转换为一个右值引用（rvalue reference）。
这个右值引用可以用来调用对象的移动构造函数或移动赋值运算符。如果一个类型没有定义移动构造函数或移动赋值运算符，那么编译器会退而求其次，调用其拷贝构造函数或拷贝赋值运算符。
基本数据类型没有移动语义：像 int 这样的基本数据类型不拥有任何外部资源（如堆内存、文件句柄等），它们的值就是其本身。
因此，对于基本数据类型，“移动”和“拷贝”在语义上是等价的：都是将一个值从一个位置复制到另一个位置。它们没有定义专门的移动构造函数或移动赋值运算符，所以std::move对它们不起作用，最终会触发拷贝。
堆内存分配：要将一个基本数据类型放到堆上，你必须显式地使用new运算符来分配堆内存，并构造一个对象。std::move与内存分配位置（栈或堆）无关。

示例：

cpp

#include <iostream>
#include <utility> // For std::move

int main() {
    int a = 10; // a 在栈上
    
    // 尝试“移动”a
    int b = std::move(a); // 实际上是拷贝，b 的值是10，a 的值仍然是10
    std::cout << "a: " << a << ", b: " << b << std::endl; // 输出：a: 10, b: 10

    // 如果要在堆上创建int，需要显式使用 new
    int* c_ptr = new int(std::move(a)); // 在堆上创建了一个 int，并用 a 的值初始化（拷贝）
    std::cout << "*c_ptr: " << *c_ptr << std::endl; // 输出：*c_ptr: 10
    delete c_ptr;

    return 0;
}

在这个例子中，std::move(a)只是将a转换为一个右值引用，但由于int没有移动构造函数，int b = std::move(a); 最终调用的是int的拷贝构造（或者说直接赋值），a的值保持不变。new int(std::move(a))也是在堆上创建了一个新的int，并用a的值进行拷贝初始化。

9、对于一个类对象，move 操作会触发什么？

对于一个类对象，move操作（通常通过std::move将左值转换为右值引用，然后匹配到移动语义相关的函数）会触发以下行为，具体取决于类的定义：

移动构造函数（Move Constructor）：

当一个类对象作为右值被初始化另一个同类型对象时，如果该类定义了移动构造函数，则会调用移动构造函数。

移动构造函数通常会从源对象“窃取”资源（例如，将源对象内部指向堆内存的指针直接赋值给新对象，然后将源对象的指针置空），而不是进行深拷贝。

这使得资源转移非常高效，因为避免了昂贵的内存分配和数据复制。

cpp

class MyVector {
public:
    int* data;
    size_t size;

    MyVector(size_t s) : size(s) {
        data = new int[size];
        std::cout << "Constructor: Allocated " << size * sizeof(int) << " bytes" << std::endl;
    }

    // 移动构造函数
    MyVector(MyVector&& other) noexcept : data(other.data), size(other.size) {
        other.data = nullptr; // 源对象资源被“窃取”
        other.size = 0;
        std::cout << "Move Constructor: Resources moved" << std::endl;
    }

    // 拷贝构造函数 (如果存在)
    MyVector(const MyVector& other) : size(other.size) {
        data = new int[size];
        std::copy(other.data, other.data + size, data);
        std::cout << "Copy Constructor: Deep copied" << std::endl;
    }

    ~MyVector() {
        delete[] data;
        std::cout << "Destructor: Deallocated" << std::endl;
    }
};

MyVector createVector() {
    MyVector temp(100); // 构造临时对象
    return temp; // 返回时触发移动构造 (或RVO/NRVO)
}

int main() {
    MyVector v1 = createVector(); // 触发移动构造
    MyVector v2 = std::move(v1); // 显式触发移动构造
    // 此时 v1 处于有效但未指定状态，不应再使用其资源
    return 0;
}

移动赋值运算符（Move Assignment Operator）：

当一个类对象作为右值被赋值给另一个同类型对象时，如果该类定义了移动赋值运算符，则会调用移动赋值运算符。其逻辑与移动构造函数类似，通常会先释放目标对象原有的资源，然后从源对象“窃取”资源。

cpp

class MyString {
public:
    char* data;
    size_t length;

    MyString(const char* s = "") {
        length = strlen(s);
        data = new char[length + 1];
        strcpy(data, s);
        std::cout << "Constructor: " << s << std::endl;
    }

    // 移动赋值运算符
    MyString& operator=(MyString&& other) noexcept {
        if (this != &other) {
            delete[] data; // 释放自己的资源
            data = other.data; // 窃取源对象的资源
            length = other.length;
            other.data = nullptr; // 源对象置空
            other.length = 0;
            std::cout << "Move Assignment: Resources moved" << std::endl;
        }
        return *this;
    }

    // ... 拷贝构造、拷贝赋值、析构函数等
};

int main() {
    MyString s1("hello");
    MyString s2;
    s2 = std::move(s1); // 触发移动赋值
    return 0;
}

拷贝构造函数/拷贝赋值运算符（Copy Constructor/Copy Assignment Operator）：
如果一个类没有定义移动构造函数或移动赋值运算符，但在使用std::move时，编译器会退而求其次，调用其对应的拷贝构造函数或拷贝赋值运算符。
这意味着虽然使用了std::move，但实际上执行的是一次昂贵的深拷贝，失去了移动语义带来的性能优势。对于没有动态资源管理的简单类（如只包含基本数据成员的类），移动操作通常会退化为拷贝，因为没有“资源”可以高效地转移。
编译器优化（RVO/NRVO）：
在某些情况下，即使没有显式地使用std::move，编译器也可能执行返回值优化（Return Value Optimization, RVO）或具名返回值优化（Named Return Value Optimization, NRVO），直接在目标对象的内存中构造返回值，从而完全避免拷贝和移动。
这是一种更高级别的优化，比移动语义更进一步。

10、`const` 和 `constexpr` 有什么区别？

const 和 constexpr 都用于表示常量性，但它们在何时确定值和应用范围上存在显著区别。

特性	`const`	`constexpr`
含义	运行时常量性：保证变量在初始化后值不可修改。	编译期常量性：保证变量在编译期就能确定其值，并且值不可修改。
求值时机	可以在编译期或运行时求值。	必须在编译期求值。
修饰对象	变量、函数参数、函数返回值、类成员函数、类成员变量。	变量、函数、类构造函数。
对函数的修饰	表示函数不会修改其参数或对象状态（对于成员函数）。函数本身可以在运行时执行。	表示函数体内的逻辑可以在编译期执行，并且其返回值是一个编译期常量。如果函数不能在编译期求值，则编译失败。
隐式`const`	`constexpr`变量隐式地是`const`的。	无
使用场景	广泛用于表示不可变性，提高代码可读性和安全性。	主要用于需要编译期常量的场合，如数组大小、模板元编程、`case`标签等，可以带来性能优化。
C++版本	C语言开始就有，C++沿用。	C++11引入，C++14、C++17、C++20对其功能进行了扩展。

详细解释

`const` (Constant)

运行时常量性：const表示一个值是常量，一旦初始化后就不能被修改。这个初始化可以在编译时完成，也可以在运行时完成。
灵活性：const变量可以由运行时才能确定的值初始化。
用途：
- 声明常量变量：const int max_size = 100; (编译期) 或 const int user_input = getUserInput(); (运行时)。
- 函数参数：void print(const std::string& s); (防止函数修改传入的引用对象)。
- 成员函数：void MyClass::display() const; (表示该成员函数不会修改对象的状态)。
- 指针和引用：const int* ptr; (指向常量数据的指针)，int* const ptr; (常量指针)。

cpp

const int compile_time_const = 10; // 编译期常量
int runtime_val = 20;
const int runtime_const = runtime_val; // 运行时常量

// compile_time_const = 11; // 错误：不能修改const变量
// runtime_const = 21;    // 错误：不能修改const变量

`constexpr` (Constant Expression)

编译期常量性：constexpr表示一个值或函数的结果必须是编译期常量表达式。这意味着它的值必须在编译时就能完全确定。
强制编译期求值：如果constexpr修饰的表达式不能在编译期求值，编译器会报错。
隐式const：所有constexpr变量都是const的，即它们的值不可修改。
用途：
- 声明编译期常量变量：constexpr int array_size = 50; (可用于定义数组大小)。
- 声明constexpr函数：constexpr int multiply(int x, int y) { return x * y; }。constexpr函数可以在编译期被调用（如果其参数也是编译期常量），也可以在运行时被调用（如果其参数是运行时变量）。
- constexpr构造函数：允许在编译期构造对象。

cpp

constexpr int compile_time_val = 10 * 5; // 编译期求值
// int runtime_val = 20;
// constexpr int invalid_constexpr = runtime_val; // 错误：runtime_val不是编译期常量

constexpr int factorial(int n) {
    return (n <= 1) ? 1 : (n * factorial(n - 1));
}

int arr[factorial(4)]; // OK，factorial(4) 在编译期求值

int main() {
    int x = 5;
    int y = factorial(x); // OK，factorial(x) 在运行时求值
    return 0;
}

11、`#define` 有哪些用法？

#define 是C/C++预处理器指令，用于创建宏（macros）。宏在程序编译的预处理阶段进行文本替换，而不是在编译阶段。

它的主要用法包括：

定义常量：
用一个符号名称来代替一个常量值。这是#define最常见的用法之一，尽管在现代C++中，更推荐使用const或constexpr。
c++
```
#define PI 3.1415926535
#define MAX_SIZE 100

double circle_area(double radius) {
    return PI * radius * radius;
}
```

定义宏函数（带参数的宏）：

用一个宏来模拟函数的功能。宏函数在替换时直接插入代码，避免了函数调用的开销，但可能引入副作用和优先级问题。因此，在现代C++中，通常推荐使用inline函数、模板函数或lambda表达式来代替宏函数。

c++

#define SUM(a, b) ((a) + (b)) // 注意使用括号避免优先级问题
#define SQUARE(x) ((x) * (x))

int main() {
    int result = SUM(10, 20); // 替换为 ((10) + (20))
    int sq = SQUARE(5);       // 替换为 ((5) * (5))
    // 潜在问题：SQUARE(a++) 会被替换为 ((a++) * (a++))，导致a被自增两次
    return 0;
}

条件编译：

根据是否定义了某个宏，来决定是否编译某段代码。这对于跨平台开发、调试代码或包含可选功能非常有用。

c++

#define DEBUG_MODE

#ifdef DEBUG_MODE
    #define LOG(msg) std::cout << "[DEBUG] " << msg << std::endl;
#else
    #define LOG(msg) // 空宏，不生成代码
#endif

int main() {
    LOG("This message appears in debug mode.");
    return 0;
}

相关的预处理指令有：#ifdef, #ifndef, #if, #elif, #else, #endif。

防止头文件重复包含（Include Guards）：
这是#define的一个非常重要的用法，用于确保头文件只被编译一次，避免重复定义错误。
c++
```
// my_header.h
#ifndef MY_HEADER_H
#define MY_HEADER_H

// 头文件内容
class MyClass { /* ... */ };

#endif // MY_HEADER_H
```
现代C++中，#pragma once提供了更简洁的替代方案，且通常由编译器直接支持，效率更高。
字符串化（Stringizing）和连接（Token Pasting）运算符：
- # 运算符（字符串化）：将宏参数转换为字符串字面量。
  c++
```
#define MESSAGE(x) #x
std::cout << MESSAGE(Hello World); // 输出 
"Hello World"
```
- ## 运算符（标记连接）：将两个标记连接成一个。
  c++
```
#define CONCAT(a, b) a##b
int CONCAT(var, 1) = 10; // 替换为 int var1 = 10;
std::cout << var1 << std::endl;
```

12、如何实现一个参数数量和类型都不固定的函数？

在C++中，实现参数数量和类型都不固定的函数主要有以下几种方式：

C风格的可变参数函数：

这是C语言继承下来的方式，使用stdarg.h（C）或cstdarg（C++）头文件中的宏来实现。

这种方式的缺点是类型不安全，需要程序员手动解析参数类型，容易出错。

cpp

#include <cstdarg>
#include <iostream>
#include <string>

void print_args(int count, ...) {
    va_list args; // 定义一个va_list类型的变量
    va_start(args, count); // 初始化va_list，第二个参数是可变参数前的最后一个固定参数

    for (int i = 0; i < count; ++i) {
        // 假设所有参数都是int类型，但这不安全，因为无法在运行时确定类型
        int arg = va_arg(args, int); 
        std::cout << "Arg " << i << ": " << arg << std::endl;
    }
    va_end(args); // 结束va_list的使用
}

// 实际使用时，通常会结合格式字符串来指定类型，类似printf
void my_printf(const char* format, ...) {
    va_list args;
    va_start(args, format);
    // 实际的printf实现会根据format字符串解析参数类型
    vprintf(format, args); // vprintf 是 printf 的变体，接受va_list
    va_end(args);
}

int main() {
    print_args(3, 10, 20, 30);
    my_printf("Hello %s, number %d, float %.2f\n", "World", 123, 4.567);
    return 0;
}

缺点：类型不安全，需要手动管理参数，容易发生类型不匹配的错误导致未定义行为。

C++11 可变参数模板：

这是现代C++中推荐的、类型安全且功能强大的解决方案。它允许函数模板或类模板接受任意数量和任意类型的模板参数。

可变参数模板通常通过递归或包展开（pack expansion）来实现。

递归方式：

通过一个基本情况（base case）函数和一个递归函数模板来处理参数包。

cpp

#include <iostream>
#include <string>

// 基本情况：当参数包为空时调用
void print() {
    std::cout << std::endl;
}

// 递归函数模板：处理一个参数，然后递归调用处理剩余参数
template<typename T, typename... Args>
void print(T first_arg, Args... rest_args) {
    std::cout << first_arg << " ";
    print(rest_arg...); // 递归调用，展开剩余参数包
}

int main() {
    print(1, 2.5, "hello", std::string("world"));
    return 0;
}

包展开方式（C++17 折叠表达式）：

C++17引入了折叠表达式（Fold Expressions），可以更简洁地处理参数包。

cpp

#include <iostream>
#include <string>

template<typename... Args>
void print_fold(Args... args) {
    // (std::cout << ... << args) 会展开成 (std::cout << arg1 << arg2 << ... << argN)
    ((std::cout << args << " "), ...);
    std::cout << std::endl;
}

int main() {
    print_fold(1, 2.5, "hello", std::string("world"));
    return 0;
}

优点：类型安全，编译器会在编译时检查参数类型；性能高，通常可以被编译器优化为内联代码；功能强大，可以处理各种复杂的参数组合。

std::initializer_list (C++11)：

如果所有参数的类型相同，或者可以隐式转换为相同类型，可以使用std::initializer_list。这主要用于初始化列表的场景，例如std::vector<int> v = {1, 2, 3};。

cpp

#include <iostream>
#include <vector>
#include <initializer_list>

void process_numbers(std::initializer_list<int> numbers) {
    long long sum = 0;
    for (int n : numbers) {
        sum += n;
    }
    std::cout << "Sum: " << sum << std::endl;
}

int main() {
    process_numbers({1, 2, 3, 4, 5});
    process_numbers({});
    return 0;
}

优点：类型安全，简洁。缺点：所有参数必须是相同类型（或可隐式转换为相同类型），且参数列表必须在编译时确定。

13、能介绍一下什么是“完美转发”吗？

**完美转发（Perfect Forwarding）是C++11引入的一项重要特性，它允许一个函数模板将其接收到的参数以其原始的类型和值类别（左值或右值）**转发给另一个函数。

这里的“完美”体现在：

保留值类别：如果传入的参数是左值，转发后仍然是左值；如果传入的参数是右值，转发后仍然是右值。
保留const、volatile等修饰符：如果传入的参数是const的，转发后仍然是const的。

完美转发主要用于编写泛型转发函数，这些函数的主要职责是将参数传递给内部调用的另一个函数，而不改变参数的任何属性。

这在实现包装器（wrappers）、工厂函数（factory functions）或任何需要将参数“原样”传递给其他函数的场景中非常有用，尤其是在涉及移动语义时，可以避免不必要的拷贝。

实现完美转发的关键要素

万能引用：
万能引用是形如T&&的模板参数类型，但它只在模板类型推导的特定上下文中表现出特殊行为：
- 当传入左值时，T被推导为X&（左值引用），T&&最终变成X& &&，经过引用折叠规则变成X&（左值引用）。
- 当传入右值时，T被推导为X（非引用类型），T&&最终变成X&&（右值引用）。因此，一个T&&类型的参数可以接受任何类型的左值或右值，并保留其值类别信息。
引用折叠规则：
C++定义了当多个引用符组合在一起时的行为规则：
- & & 变成 &
- & && 变成 &
- && & 变成 &
- && && 变成 && 简单来说，只要有一个左值引用（&），结果就是左值引用；只有当所有都是右值引用（&&）时，结果才是右值引用。
std::forward：
std::forward是一个模板函数，它的作用是有条件地将参数转换为右值引用。它的签名通常是template<typename T> T&& forward(typename std::remove_reference<T>::type& arg) noexcept;。
- 如果T被推导为左值引用类型（例如int&），std::forward会返回一个左值引用（int&）。
- 如果T被推导为非引用类型（例如int），std::forward会返回一个右值引用（int&&）。 std::forward的这种行为使得它能够根据原始传入参数的值类别来决定是将其作为左值转发还是作为右值转发。

完美转发的示例

假设我们有一个wrapper函数，它接受任意参数并将其转发给target函数。

cpp

#include <iostream>
#include <string>
#include <utility> // For std::forward

// target 函数重载，用于演示不同值类别的行为
void target(int& x) {
    std::cout << "target(int&): lvalue ref, x = " << x << std::endl;
}

void target(int&& x) {
    std::cout << "target(int&&): rvalue ref, x = " << x << std::endl;
}

void target(const std::string& s) {
    std::cout << "target(const std::string&): const lvalue ref, s = " << s << std::endl;
}

void target(std::string&& s) {
    std::cout << "target(std::string&&): rvalue ref, s = " << s << std::endl;
}

// 泛型转发函数
template<typename T>
void wrapper(T&& arg) { // T&& 是万能引用
    std::cout << "  In wrapper: ";
    target(std::forward<T>(arg)); // 使用 std::forward 进行完美转发
}

int main() {
    int a = 10;
    std::cout << "Calling wrapper with lvalue int:";
    wrapper(a); // a 是左值，T 被推导为 int&，std::forward<int&>(a) 返回 int&，调用 target(int&)

    std::cout << "\nCalling wrapper with rvalue int:";
    wrapper(20); // 20 是右值，T 被推导为 int，std::forward<int>(20) 返回 int&&，调用 target(int&&)

    std::string s1 = "hello";
    std::cout << "\nCalling wrapper with lvalue string:";
    wrapper(s1); // s1 是左值，T 被推导为 std::string&，std::forward<std::string&>(s1) 返回 std::string&，调用 target(const std::string&)

    std::cout << "\nCalling wrapper with rvalue string:";
    wrapper(std::string("world")); // std::string("world") 是右值，T 被推导为 std::string，std::forward<std::string>(std::string("world")) 返回 std::string&&，调用 target(std::string&&)

    return 0;
}

为什么需要完美转发？

如果没有完美转发，泛型函数在传递参数时会遇到“引用丢失”的问题。

例如，如果wrapper函数参数是T arg（按值传递），那么每次调用都会发生拷贝。如果参数是T& arg（左值引用），则无法接受右值。如果参数是const T& arg，则无法将参数作为右值转发（例如，无法调用移动构造函数）。

完美转发解决了这些问题，使得泛型函数能够以最高效的方式传递参数，同时保持类型和值类别的完整性。

操作系统

1、对操作系统比较熟悉，能介绍一下存储器的层次结构吗？（从速度高到低）

存储器层次结构是现代计算机系统设计中的一个核心概念，旨在平衡存储器的速度、容量和成本。

它将不同类型和性能的存储设备组织成一个金字塔形的结构，CPU倾向于访问速度更快、容量更小、成本更高的存储器，而将不常用的数据存储在速度较慢、容量更大、成本更低的存储器中。

通过这种分层结构，系统能够以接近最快存储器的速度运行，同时拥有接近最慢存储器的容量和成本效益。

以下是存储器层次结构从速度高到低（通常也是成本高到低、容量小到大）的排序：

CPU 寄存器：
- 速度：最快，通常在CPU的一个时钟周期内完成访问。
- 容量：最小，通常只有几十到几百字节，直接集成在CPU内部。
- 功能：用于存储CPU当前正在处理的数据、指令地址、通用计算结果等。它们是CPU直接操作的数据存储单元，是CPU执行指令的必要组成部分。
高速缓存：高速缓存是位于CPU和主内存之间的小容量、高速存储器，用于存储CPU频繁访问的数据和指令。它分为多级，以进一步优化性能。
L1 Cache（一级缓存）：
- 速度：非常快，通常在几个CPU时钟周期内访问。
- 容量：小，通常为几十到几百KB。每个CPU核心独有。
- 功能：存储最近或最频繁使用的数据和指令，通常分为指令缓存（L1i）和数据缓存（L1d）。
L2 Cache（二级缓存）：
- 速度：比L1慢，但比主内存快，通常在几十个CPU时钟周期内访问。
- 容量：中等，通常为几百KB到几MB。可以是每个CPU核心独有，也可以是多个核心共享。
- 功能：作为L1缓存的补充，存储更多的数据和指令。
L3 Cache（三级缓存）：
- 速度：比L2慢，但仍比主内存快，通常在几百个CPU时钟周期内访问。
- 容量：较大，通常为几MB到几十MB。通常由所有CPU核心共享。
- 功能：作为L2缓存的补充，进一步提高缓存命中率。
主内存：
- 速度：比高速缓存慢，但比磁盘存储快，通常在几十到几百纳秒内访问。
- 容量：大，通常为几GB到几百GB。
- 功能：用于存储当前正在运行的程序指令和数据。是CPU可以直接寻址和访问的主要工作存储器。RAM是易失性存储器，断电后数据丢失。
固态硬盘：
- 速度：比传统机械硬盘快得多，但比RAM慢，通常在几十到几百微秒内访问。
- 容量：大，通常为几百GB到几TB。
- 功能：作为持久性存储，用于存储操作系统、应用程序和用户数据。它使用闪存（NAND Flash）技术，无机械部件，读写速度快，但成本高于机械硬盘。
机械硬盘：
- 速度：慢，访问时间通常在几毫秒到几十毫秒。
- 容量：最大，通常为几TB到几十TB。
- 功能：最主要的持久性存储设备，用于长期存储大量数据。它通过旋转盘片和读写磁头工作，具有机械部件，读写速度相对较慢，但成本低廉。
辅助存储器/离线存储：
- 速度：最慢，访问时间可能从几秒到几分钟甚至更长。
- 容量：理论上无限。
- 功能：用于数据备份、归档和不常用数据的长期存储。包括磁带库、光盘（CD/DVD/蓝光）、网络存储（云存储、NAS）等。

存储器层次结构图

这种层次结构通过局部性原理（Temporal Locality 和 Spatial Locality）来工作，即程序倾向于在短时间内重复访问相同的数据（时间局部性），以及访问相邻的数据（空间局部性）。

当CPU需要数据时，它首先在最快的存储器中查找，如果命中则直接使用；如果未命中，则从下一级存储器中获取数据，并将其复制到当前级存储器中，以备将来快速访问。这样，大部分时间CPU都能从高速存储器中获取数据，从而提高整体系统性能。

2、请将存储器的访问速度进行排序。

根据上一题的存储器层次结构，存储器的访问速度从高到低排序如下：

CPU 寄存器
L1 Cache
L2 Cache
L3 Cache
主内存 (RAM)
固态硬盘 (SSD)
机械硬盘 (HDD)
辅助存储器 / 离线存储 (如磁带、光盘)

3、有没有比 L1 Cache 还快的存储器？

有，CPU寄存器比L1 Cache更快。

CPU 寄存器：是CPU内部最快的存储单元，它们直接集成在CPU芯片内部，并且是CPU执行指令时直接操作的数据存储区域。访问寄存器通常只需要一个CPU时钟周期，甚至更短（在某些流水线设计中，数据可能在指令解码阶段就已从寄存器中读取）。
L1 Cache：虽然L1 Cache也非常快，但它通常需要几个CPU时钟周期才能完成访问。L1 Cache虽然也是集成在CPU芯片内部，但其访问路径和逻辑比直接访问寄存器要复杂一些。

4、线程间如何进行通信？

线程间通信（Inter-Thread Communication, ITC）是指在同一进程中运行的不同线程之间交换信息或同步操作的过程。由于线程共享同一进程的地址空间，它们的通信方式通常比进程间通信（IPC）更直接和高效。

线程间通信的主要目的是数据共享和同步。

以下是线程间通信的几种主要方式：

共享内存：
- 原理：由于同一进程内的所有线程共享相同的地址空间，它们可以直接访问和修改相同的全局变量、静态变量或堆上的数据。这是最直接、最高效的通信方式。
- 挑战：直接共享数据会导致竞态条件（Race Condition），即多个线程同时访问和修改共享数据时，结果取决于线程执行的相对时序。为了避免竞态条件，必须使用同步机制来保护共享数据的访问。
- 示例：一个线程写入全局变量，另一个线程读取全局变量。
互斥量：
- 原理：互斥量是一种同步原语，用于保护共享资源，确保在任何时刻只有一个线程可以访问被保护的代码段（临界区）。当一个线程锁定互斥量时，其他尝试锁定该互斥量的线程将被阻塞，直到持有锁的线程释放它。
- 用途：防止竞态条件，保护共享数据的完整性。
- 示例：std::mutex（C++11），pthread_mutex_t（POSIX）。
条件变量：
- 原理：条件变量通常与互斥量一起使用，用于线程间的等待和通知机制。一个线程可以等待某个条件成立，而另一个线程在条件成立时通知等待的线程。等待线程会释放互斥量并进入睡眠状态，直到被唤醒；唤醒线程在通知前需要持有互斥量。
- 用途：实现线程间的协调和同步，例如生产者-消费者模型。
- 示例：std::condition_variable（C++11），pthread_cond_t（POSIX）。
信号量：
- 原理：信号量是一个计数器，用于控制对共享资源的访问。它维护一个非负整数值。当线程需要访问资源时，它会尝试对信号量执行“P”操作（等待或减一）；当线程释放资源时，它会执行“V”操作（发送信号或加一）。如果信号量的值为零，P操作会阻塞线程。
- 用途：控制同时访问某个资源的线程数量，实现资源池管理。
- 示例：std::counting_semaphore（C++20），sem_t（POSIX）。
读写锁：
- 原理：读写锁允许多个线程同时读取共享资源，但只允许一个线程写入共享资源。当有线程持有写锁时，所有读写请求都会被阻塞；当有线程持有读锁时，其他读请求可以继续，但写请求会被阻塞。
- 用途：在读多写少的场景下，提高并发性能。
- 示例：std::shared_mutex（C++17），pthread_rwlock_t（POSIX）。
消息队列：
- 原理：线程可以将消息发送到队列中，其他线程可以从队列中接收消息。这提供了一种解耦的通信方式，发送方和接收方不需要直接交互。
- 用途：实现任务分发、事件通知等。
- 示例：通常需要自定义实现或使用第三方库，如boost::interprocess::message_queue。
原子操作：
- 原理：对于简单的共享数据（如整数、布尔值），可以使用原子操作来确保其读写是不可中断的。原子操作在硬件层面保证了操作的完整性，无需使用锁。
- 用途：实现无锁编程（Lock-Free Programming），提高对简单共享变量的访问效率。
- 示例：std::atomic<int>（C++11）。
线程局部存储：
- 原理：每个线程都拥有自己独立的数据副本，而不是共享数据。这样可以完全避免线程间的数据竞争，但这不是严格意义上的“通信”，更像是避免通信。
- 用途：存储线程私有的数据，例如错误码、日志句柄等。
- 示例：thread_local关键字（C++11）。

5、除了加锁，线程间通信还有哪些无锁的方式？

除了传统的加锁（互斥量、读写锁、信号量等）方式，线程间通信还存在一些无锁（Lock-Free）或无等待（Wait-Free）的方式。这些方式旨在减少或消除锁带来的开销（如上下文切换、死锁、优先级反转等），从而提高并发性能和实时性。无锁编程通常依赖于原子操作和内存屏障。

原子操作：
- 原理：利用CPU提供的原子指令（如CAS - Compare-And-Swap，Fetch-And-Add等）来对共享变量进行读-改-写操作，确保这些操作是不可中断的。C++11引入了std::atomic模板类，提供了对各种基本类型进行原子操作的封装。
- 用途：更新计数器、标志位、指针等简单共享变量。例如，实现一个无锁的计数器：std::atomic<int> counter; counter.fetch_add(1);。
- 优点：粒度最小，效率高，不会导致死锁。
- 缺点：仅适用于简单数据类型，复杂数据结构需要精心设计。
无锁数据结构：
- 原理：通过巧妙地设计数据结构和使用原子操作，使得多个线程可以并发地访问和修改数据结构，而无需使用互斥锁。
  常见的无锁数据结构包括：
  无锁队列（Lock-Free Queue）：例如，单生产者-单消费者（SPSC）队列、多生产者-多消费者（MPMC）队列。它们通常使用原子操作来更新头尾指针，实现数据的入队和出队。
  无锁栈（Lock-Free Stack）：通常使用CAS操作来实现栈顶指针的更新。
  无锁哈希表、链表等。
- 优点：高并发性能，避免锁带来的开销和问题。
- 缺点：设计和实现非常复杂，容易出错，调试困难。需要深入理解内存模型和原子操作。
内存屏障/内存栅栏：
- 原理：内存屏障是一种CPU指令，用于强制处理器和编译器对内存操作进行排序，防止指令重排。在无锁编程中，它与原子操作结合使用，以确保不同线程之间内存操作的可见性和顺序性，从而保证数据一致性。
- 用途：在原子操作不足以保证内存顺序时，显式地插入内存屏障。C++11的std::memory_order枚举值（如memory_order_acquire, memory_order_release, memory_order_seq_cst等）在原子操作中提供了内存排序语义，通常无需手动插入独立的内存屏障指令。
线程局部存储：
- 原理：如前所述，TLS为每个线程提供独立的变量副本。虽然不是直接的“通信”方式，但它通过避免共享来消除竞争，从而达到“无锁”访问的效果。每个线程只访问自己的数据，因此无需同步。
- 用途：存储线程私有的状态、上下文信息等。
消息传递：
- 原理：线程之间不直接共享内存，而是通过发送和接收消息进行通信。每个线程都有自己的私有数据，并通过明确的消息传递机制（如队列）来交换数据。如果消息队列本身是无锁实现的，那么整个通信过程可以认为是无锁的。
- 用途：Actor模型、CSP（Communicating Sequential Processes）等并发范式。

6、原子变量（Atomic Variables）都有哪些？

C++11标准库通过<atomic>头文件提供了std::atomic模板类，用于创建原子变量。std::atomic可以特化（instantiate）为多种基本类型和用户定义类型，从而使这些类型的操作具有原子性。并非所有类型都可以直接特化为std::atomic。

std::atomic支持的常见原子变量类型包括：

布尔类型：
std::atomic<bool>：用于原子地存储和操作布尔值。常用于实现标志位、自旋锁等。
整数类型：
- std::atomic<char>
- std::atomic<signed char>
- std::atomic<unsigned char>
- std::atomic<short>
- std::atomic<unsigned short>
- std::atomic<int>
- std::atomic<unsigned int>
- std::atomic<long>
- std::atomic<unsigned long>
- std::atomic<long long>
- std::atomic<unsigned long long>
- 以及固定宽度整数类型，如std::atomic<int8_t>, std::atomic<uint32_t>等。这些类型支持原子地加载、存储、交换、比较并交换（CAS）以及算术操作（如fetch_add, fetch_sub, operator++, operator--等）。
指针类型：
std::atomic<T*>：用于原子地存储和操作指针。支持加载、存储、交换、比较并交换以及指针算术（fetch_add, fetch_sub）。
std::atomic_flag：
这是一个最简单的原子布尔标志，只支持两个操作：test_and_set()（原子地设置标志并返回旧值）和clear()（原子地清除标志）。它通常用于实现自旋锁，并且是唯一保证**无等待（wait-free）**的原子类型。
用户定义类型（User-Defined Types）：
std::atomic<MyStruct>：理论上，任何用户定义类型T都可以用于std::atomic<T>。但前提是该类型必须是**平凡可复制（TriviallyCopyable）**的，并且其大小适合平台上的原子操作（通常是CPU字长或更小）。
如果std::atomic<T>不能被实现为无锁的（std::atomic<T>::is_lock_free返回false），那么它将使用内部互斥锁来实现原子性，从而退化为有锁操作。因此，通常只对简单、小型的用户定义类型使用std::atomic，或者确保is_lock_free为true。

std::atomic的特化和通用形式：

除了std::atomic<T>的通用模板，标准库还提供了针对某些常用类型的特化，例如：

std::atomic_bool (等同于 std::atomic<bool>)
std::atomic_char (等同于 std::atomic<char>)
std::atomic_schar (等同于 std::atomic<signed char>)
std::atomic_uchar (等同于 std::atomic<unsigned char>)
std::atomic_short (等同于 std::atomic<short>)
std::atomic_ushort (等同于 std::atomic<unsigned short>)
std::atomic_int (等同于 std::atomic<int>)
std::atomic_uint (等同于 std::atomic<unsigned int>)
std::atomic_long (等同于 std::atomic<long>)
std::atomic_ulong (等同于 std::atomic<unsigned long>)
std::atomic_llong (等同于 std::atomic<long long>)
std::atomic_ullong (等同于 std::atomic<unsigned long long>)
std::atomic_wchar_t (等同于 std::atomic<wchar_t>)
std::atomic_char8_t (等同于 std::atomic<char8_t>, C++20)
std::atomic_char16_t (等同于 std::atomic<char16_t>)
std::atomic_char32_t (等同于 std::atomic<char32_t>)
std::atomic_intmax_t (等同于 std::atomic<intmax_t>)
std::atomic_uintmax_t (等同于 std::atomic<uintmax_t>)
std::atomic_ptrdiff_t (等同于 std::atomic<ptrdiff_t>)
std::atomic_size_t (等同于 std::atomic<size_t>)

这些特化类型提供了与std::atomic<T>相同的接口，只是名称更简洁。

7、原子变量修改值时，有哪些接口可以使用？

std::atomic模板类提供了多种接口来原子地修改其存储的值，并且这些接口通常都接受一个可选的std::memory_order参数，用于指定内存同步和可见性规则。理解内存序对于编写正确的无锁并发代码至关重要。

以下是std::atomic常用的修改值接口及其内存序：

store(Desired, MemoryOrder = std::memory_order_seq_cst)：
功能：原子地将Desired的值写入原子变量。
内存序：
- std::memory_order_relaxed：最宽松的内存序。不保证任何内存同步，只保证原子操作本身是原子的。其他线程可能在任意时间点看到写入的值。
- std::memory_order_release：释放语义。保证store操作之前的所有内存写入都在store操作完成之前对其他线程可见。通常与acquire配对使用。
- std::memory_order_seq_cst（默认）：顺序一致性。这是最严格的内存序，保证所有seq_cst操作在所有线程中都以相同的总顺序执行，并且具有释放和获取语义。开销最大。
operator=(Desired)：
功能：原子地将Desired的值赋给原子变量。这是store操作的重载形式。
内存序：默认使用std::memory_order_seq_cst。
exchange(Desired, MemoryOrder = std::memory_order_seq_cst)：
功能：原子地将Desired的值写入原子变量，并返回原子变量的旧值。
内存序：可以指定任何std::memory_order，具有释放和获取语义的组合。
compare_exchange_weak(Expected, Desired, SuccessOrder, FailureOrder) 和 compare_exchange_strong(Expected, Desired, SuccessOrder, FailureOrder)：
功能：**比较并交换（Compare-And-Swap, CAS）**操作。如果原子变量的当前值等于Expected，则原子地将其值更新为Desired，并返回true；否则不修改原子变量，将Expected更新为原子变量的当前值，并返回false。
weak版本可能在值相等时仍然返回false（虚假失败，spurious failure），通常用于循环中，可能在某些平台上效率更高。
strong版本保证只有在值不相等时才返回false。
内存序：
- SuccessOrder：当操作成功时使用的内存序，可以指定acquire, release, acq_rel, seq_cst或relaxed。
- FailureOrder：当操作失败时使用的内存序，可以指定acquire, acq_rel或relaxed。FailureOrder不能比SuccessOrder更强，通常是SuccessOrder的acquire版本或relaxed。
算术操作（仅适用于整数和指针特化）：
- fetch_add(Arg, MemoryOrder = std::memory_order_seq_cst)：原子地将Arg加到原子变量上，并返回原子变量的旧值。
- fetch_sub(Arg, MemoryOrder = std::memory_order_seq_cst)：原子地从原子变量中减去Arg，并返回原子变量的旧值。
- fetch_and(Arg, MemoryOrder = std::memory_order_seq_cst)：原子地对原子变量和Arg执行按位与操作，并返回原子变量的旧值。
- fetch_or(Arg, MemoryOrder = std::memory_order_seq_cst)：原子地对原子变量和Arg执行按位或操作，并返回原子变量的旧值。
- fetch_xor(Arg, MemoryOrder = std::memory_order_seq_cst)：原子地对原子变量和Arg执行按位异或操作，并返回原子变量的旧值。
- operator++() / operator++(int) / operator--() / operator--(int)：原子地递增/递减原子变量。前缀版本返回新值，后缀版本返回旧值。
- operator+=() / operator-=() / operator&=() / operator|=() / operator^=()：复合赋值运算符，原子地执行相应的算术/位操作。
- 内存序：这些操作都可以接受std::memory_order参数，默认是std::memory_order_seq_cst。

内存序（std::memory_order）的类型：

std::memory_order_relaxed：不施加任何同步或排序约束。只保证操作是原子的。读写可以被编译器和CPU随意重排。
std::memory_order_consume：消费语义。读取操作会“消费”某个值，并建立一个依赖关系。在该读取操作之后，依赖于该值的后续内存访问不会被重排到该读取操作之前。通常用于依赖链，比acquire更宽松。
std::memory_order_acquire：获取语义。在该操作之后的所有内存读取和写入操作都不会被重排到该操作之前。它“获取”了在release操作之前发生的内存写入的可见性。
std::memory_order_release：释放语义。在该操作之前的所有内存写入操作都不会被重排到该操作之后。它“释放”了在acquire操作之后发生的内存读取的可见性。
std::memory_order_acq_rel：获取-释放语义。结合了acquire和release的特性，用于读-改-写（RMW）操作，如exchange或fetch_add，既能看到之前的写入，又能让之后的写入可见。
std::memory_order_seq_cst：顺序一致性。最强的内存序。所有seq_cst操作在所有线程中都以相同的总顺序执行，并且具有获取-释放语义。它提供了一种直观的内存模型，但通常开销最大。

8、多线程发生死锁应如何避免？

死锁（Deadlock）是多线程编程中一个常见且难以调试的问题，当两个或多个线程在等待彼此释放资源时，导致所有线程都无法继续执行。避免死锁的关键在于破坏死锁产生的四个必要条件中的至少一个。

以下是避免死锁的几种常用策略：

按顺序加锁：
- 原理：为程序中所有的互斥量（或锁）定义一个全局的获取顺序。所有线程在获取多个锁时，都必须严格按照这个预定义的顺序进行。如果一个线程需要获取锁A和锁B，并且约定A在B之前，那么线程必须先尝试获取A，再尝试获取B。
- 破坏条件：破坏了循环等待条件。
- 优点：简单易行，如果能明确定义锁的顺序，是一种非常有效的策略。
- 缺点：在复杂系统中，维护一个全局的锁顺序可能很困难，或者不切实际。
cpp
```
std::mutex mtx1, mtx2;

void func1() { // 总是先锁mtx1，再锁mtx2
    std::lock_guard<std::mutex> lock1(mtx1);
    std::lock_guard<std::mutex> lock2(mtx2);
    // ... 访问共享资源
}

void func2() { // 同样先锁mtx1，再锁mtx2
    std::lock_guard<std::mutex> lock1(mtx1);
    std::lock_guard<std::mutex> lock2(mtx2);
    // ... 访问共享资源
}
```
使用std::lock（C++11）：
- 原理：std::lock是一个函数模板，可以一次性锁定多个互斥量，并且保证原子性（要么全部锁定成功，要么全部不锁定）和无死锁（它会使用一种算法来避免死锁，例如通过尝试锁定、回退、重试）。
- 破坏条件：破坏了请求和保持以及循环等待条件。
- 优点：方便且安全，是处理多个锁的推荐方式。
- 示例：
cpp
```
std::mutex mtxA, mtxB;

void transfer(int from_account, int to_account, double amount) {
    std::unique_lock<std::mutex> lockA(mtxA, std::defer_lock);
    std::unique_lock<std::mutex> lockB(mtxB, std::defer_lock);

    std::lock(lockA, lockB); // 原子地锁定两个互斥量，避免死锁

    // ... 执行转账操作
}
```
加锁时限/尝试加锁：
- 原理：在尝试获取锁时设置一个超时时间，或者使用非阻塞的try_lock()方法。如果无法在指定时间内获取到锁，或者try_lock()失败，线程会放弃获取该锁，并可以执行其他操作或稍后重试。
- 破坏条件：破坏了不可剥夺条件（虽然不是直接剥夺，但线程可以主动放弃等待）。
- 优点：提高了程序的响应性，避免线程无限期等待。
- 缺点：增加了代码复杂性，需要设计回退和重试逻辑。
cpp
```
std::mutex mtx;

void do_something_with_timeout() {
    if (mtx.try_lock()) { // 尝试获取锁
        std::cout << "Got lock!" << std::endl;
        // ... 访问共享资源
        mtx.unlock();
    } else {
        std::cout << "Failed to get lock, doing something else..." << std::endl;
        // ... 执行其他操作或稍后重试
    }
}
```
避免持有多个锁：
- 原理：尽量减少单个线程同时持有的锁的数量。如果一个线程只需要一个锁就能完成操作，那么死锁的可能性就大大降低。
- 破坏条件：间接减少了请求和保持以及循环等待的发生机会。
细粒度锁 vs 粗粒度锁：
- 原理：根据共享资源的访问粒度来选择锁的范围。细粒度锁（保护小块数据）可以提高并发性，但增加了锁管理的复杂性；粗粒度锁（保护大块数据）简化了管理，但可能降低并发性。
- 优点：合理选择粒度可以平衡性能和死锁风险。
资源一次性分配：
- 原理：在进程（或线程）开始执行之前，一次性请求所有需要的资源。如果所有资源都能满足，则分配给它；否则，不分配任何资源，并让进程等待。这是一种预防死锁的算法。
- 破坏条件：破坏了请求和保持条件。
- 优点：理论上可以完全避免死锁。
- 缺点：实际应用中很难预知所有需要的资源，且可能导致资源利用率低下和饥饿。
死锁检测与恢复：
- 原理：不尝试预防死锁，而是允许死锁发生，然后通过算法检测死锁的发生，并采取措施（如终止进程、剥夺资源）来恢复系统。
- 优点：不需要严格的预防措施，提高了资源利用率。
- 缺点：检测和恢复的开销较大，且可能导致数据丢失或系统不稳定。

9、死锁产生的条件有哪些？

死锁的发生需要同时满足以下四个必要条件，它们被称为Coffman条件：

互斥条件：
- 定义：至少有一个资源是非共享的，即在任何一个时刻，只能有一个线程（或进程）占用该资源。如果另一个线程请求该资源，它必须等待，直到该资源被释放。
- 解释：这是锁机制的本质。如果资源可以被多个线程同时访问，就不会有竞争，也就不会有死锁。例如，打印机、文件句柄、互斥量本身都是互斥资源。
请求和保持条件：
- 定义：一个线程（或进程）已经持有了至少一个资源，但又提出了新的资源请求。它会阻塞等待新的资源，同时不释放自己已经持有的资源。
- 解释：线程在等待新资源的同时，仍然占用着旧资源。这使得旧资源无法被其他等待它的线程获取，从而加剧了资源竞争。
不剥夺条件：
- 定义：线程（或进程）已经获得的资源在未使用完之前，不能被系统或任何其他线程强行剥夺，只能由持有该资源的线程自愿释放。
- 解释：资源一旦被分配给一个线程，就不能被强制收回。如果可以强制剥夺资源，那么当一个线程等待另一个线程的资源时，系统可以强制释放等待线程的资源，从而打破死锁。
循环等待条件：
- 定义：存在一个线程（或进程）的循环链，链中的每一个线程都在等待下一个线程所持有的资源，从而形成一个循环等待的闭环。
- 解释：例如，线程A等待线程B的资源，线程B等待线程C的资源，而线程C又等待线程A的资源。这种循环依赖是死锁的直接原因。

只有当这四个条件同时满足时，才会发生死锁。如果能够破坏其中任何一个条件，就可以避免死锁的发生。

10、针对死锁的各个条件，除了按顺序加锁外，还有哪些解决方案？

除了“按顺序加锁”这种主要针对循环等待条件的解决方案外，还可以通过破坏死锁的其他必要条件来避免死锁。

以下是针对死锁各个条件的解决方案（包括预防和避免）：

1. 破坏互斥条件

方法：将互斥资源改造为可共享资源，或者尽量减少对互斥资源的需求。

具体措施：

使用无锁数据结构和算法：对于某些数据结构（如计数器、队列），可以使用原子操作（std::atomic）或无锁算法（如无锁队列）来允许多个线程并发访问，而无需互斥锁。这直接消除了对互斥条件的依赖。

读写锁（Read-Write Locks）：允许多个读线程并发访问，只在写操作时才互斥。这在读多写少的场景下提高了并发性，但写操作仍然是互斥的。
线程局部存储（Thread-Local Storage, TLS）：为每个线程提供一份数据的独立副本，从而消除共享数据的需要，也就消除了互斥。
局限性：并非所有资源都能被改造为共享资源。例如，打印机等物理设备本质上是互斥的。

2. 破坏请求和保持条件

方法：要求线程一次性地请求所有需要的资源，或者在请求新资源时释放所有已持有的资源。

具体措施：

一次性分配所有资源：线程在开始执行前，必须一次性申请所有它在整个执行过程中可能需要的资源。如果不能一次性获取所有资源，就不能开始执行，也不能持有任何资源。这也被称为静态资源分配。
- 优点：简单有效，可以预防死锁。
- 缺点：可能导致资源利用率低（资源被长时间占用但未被使用），以及饥饿问题（如果某个线程总是无法一次性获取所有资源）。
释放已持有资源：当一个线程请求新资源但无法立即获得时，它必须释放所有当前持有的资源。然后，它重新尝试获取所有资源（包括之前释放的和新请求的）。
- 优点：提高了资源利用率。
- 缺点：实现复杂，可能导致数据回滚或状态恢复的开销。

3. 破坏不剥夺条件

方法：允许系统在必要时从持有资源的线程那里“剥夺”资源。

具体措施：

抢占式资源分配：当一个线程请求的资源被另一个线程持有且该线程正在等待其他资源时，系统可以强制从后者手中剥夺资源，分配给前者。被剥夺资源的线程需要回滚到之前的状态，并稍后重新尝试获取资源。
加锁时限（Lock Timeout）：前面提到，当线程尝试获取锁时，可以设置一个超时时间。如果超时仍未获得锁，线程就放弃等待，并释放自己持有的所有锁（如果存在），然后重试。这是一种“软剥夺”机制。
局限性：剥夺资源通常会带来很大的复杂性，例如需要实现状态保存和恢复机制。对于某些资源（如打印机正在打印的文档），剥夺是不可行的。

4. 破坏循环等待条件

方法：通过对资源进行排序，并强制线程按照这个顺序获取资源。

具体措施：

按顺序加锁：这是最常用和推荐的方法，前面已详细介绍。为所有锁分配一个唯一的顺序号，线程在获取多个锁时必须按照递增的顺序获取。
std::lock：C++11提供的std::lock函数可以原子地锁定多个互斥量，并内部实现了一种无死锁的算法来获取这些锁，从而避免了循环等待。
资源分配图算法：更高级的操作系统层面算法，通过分析资源分配图来检测是否存在循环，并在分配资源前进行预防。

算法与数据结构

1、简单介绍一下数组和链表的区别。

数组（Array）和链表（Linked List）是两种最基本、最常用的线性数据结构，它们在内存存储、访问方式、增删操作等方面存在显著差异。

特性	数组（Array）	链表（Linked List）
存储方式	连续内存：元素在内存中是连续存储的。	非连续内存：元素（节点）在内存中可以不连续存储，通过指针连接。
访问方式	随机访问（Random Access）：可以通过索引`O(1)`时间直接访问任意元素。	顺序访问（Sequential Access）：只能从头节点开始，通过指针逐个遍历访问元素，时间复杂度为`O(n)`。
元素大小	所有元素类型相同，大小固定。	节点大小可能不同（如果存储不同类型的数据），但通常节点结构（数据+指针）固定。
插入/删除	慢：在中间位置插入或删除元素需要移动大量后续元素，时间复杂度为`O(n)`。在末尾插入/删除（如果容量允许）为`O(1)`。	快：只需修改少量指针即可，时间复杂度为`O(1)`（如果已知插入/删除位置的前一个节点），或`O(n)`（如果需要查找位置）。
内存利用率	高：没有存储额外指针的开销，但可能存在空间浪费（如果预分配过大）或需要重新分配（如果容量不足）。	低：每个节点都需要额外的空间存储指针，导致内存开销较大。
空间分配	静态或动态一次性分配一块连续内存。	动态按需分配，每个节点单独分配。
缓存友好性	高：由于内存连续，CPU缓存命中率高。	低：由于内存不连续，CPU缓存命中率低。

详细解释

数组：
- 优点：访问速度快（随机访问），缓存友好，结构简单。
- 缺点：插入和删除效率低，大小固定（静态数组）或需要重新分配和拷贝（动态数组如std::vector），可能导致内存碎片（重新分配时）。
- 适用场景：数据量固定或变化不大，需要频繁随机访问的场景，如查找、排序等。
链表：
- 优点：插入和删除效率高（O(1)），大小动态可变，没有内存碎片问题（每个节点独立分配）。
- 缺点：访问速度慢（顺序访问），内存利用率低（需要额外存储指针），缓存不友好。
- 适用场景：数据量频繁变化，需要频繁插入和删除操作的场景，如实现队列、栈、哈希表的链式冲突解决等。

2、从内存利用率角度看，数组和链表哪个更高？

从内存利用率角度看，数组通常比链表更高。

原因如下：

额外开销：
- 数组：除了存储实际数据外，几乎没有额外的内存开销。对于动态数组（如C++的std::vector），可能有一些管理容量和大小的额外开销，但每个数据元素本身没有额外的开销。
- 链表：每个节点除了存储数据本身，还需要额外存储一个或多个指针（例如，单向链表需要一个next指针，双向链表需要next和prev两个指针）。这些指针会占用额外的内存空间。在存储大量小数据元素时，指针的开销可能会非常显著。
例如，在一个存储int类型数据的链表中，一个int可能占用4字节，而一个指针在64位系统上可能占用8字节。这意味着每个节点为了存储一个int数据，需要额外付出8字节（甚至更多）的指针开销，使得内存利用率大大降低。
内存碎片：
- 数组：通常是连续分配的内存块。虽然动态数组在扩容时可能需要重新分配更大的内存块并拷贝数据，这可能导致原内存块的碎片化，但数组本身内部是紧凑的。
- 链表：由于每个节点是独立分配的，它们在内存中可能分散在各个位置。这虽然避免了整体内存块的重新分配，但长期运行可能导致堆内存的严重碎片化，使得分配大块连续内存变得困难，并且可能降低CPU缓存的效率。

3、数组和链表在增删改查操作上的时间复杂度有何区别？

数组和链表在常见的增删改查（CRUD）操作上的时间复杂度有显著区别，这直接影响了它们在不同应用场景下的性能表现。

操作类型	数组（Array）	链表（Linked List）
查找	按索引查找：`O(1)`（随机访问）	按值查找：`O(n)`（需要遍历）
	按值查找：`O(n)`（需要遍历，无序）或`O(log n)`（有序，二分查找）	按索引查找：`O(n)`（需要遍历）
插入	头部/中间插入：`O(n)`（需要移动后续所有元素）	头部插入：`O(1)`
	尾部插入：`O(1)`（如果容量足够，否则可能`O(n)`扩容）	中间/尾部插入：`O(1)`（如果已知前一个节点），`O(n)`（如果需要查找位置）
删除	头部/中间删除：`O(n)`（需要移动后续所有元素）	头部删除：`O(1)`
	尾部删除：`O(1)`	中间/尾部删除：`O(1)`（如果已知前一个节点），`O(n)`（如果需要查找位置）
修改	按索引修改：`O(1)`（随机访问）	按索引修改：`O(n)`（需要遍历）
	按值修改：`O(n)`（需要查找，然后修改）	按值修改：`O(n)`（需要查找，然后修改）

详细解释

查找：
- 数组：由于元素在内存中是连续存储的，并且可以通过索引直接计算出元素的内存地址，因此按索引访问（例如 arr[i]）的时间复杂度是O(1)，即随机访问。按值查找则需要遍历，时间复杂度为O(n)。如果数组有序，可以使用二分查找，时间复杂度为O(log n)。
- 链表：元素在内存中是不连续的，只能通过指针从头节点开始逐个遍历。因此，无论是按索引查找还是按值查找，都需要遍历链表，时间复杂度都是O(n)。
插入：
- 数组：在数组的头部或中间插入一个元素，需要将插入位置之后的所有元素向后移动一位，以腾出空间。这个操作的时间复杂度是O(n)。在数组尾部插入，如果当前容量足够，则为O(1)；如果容量不足，需要重新分配更大的内存并拷贝所有元素，时间复杂度为O(n)。
- 链表：在链表的头部插入一个元素，只需创建一个新节点，并更新头指针，时间复杂度是O(1)。在链表的中间或尾部插入，如果已知要插入位置的前一个节点，也只需修改两个指针，时间复杂度是O(1)。但如果需要先查找插入位置，那么查找的时间复杂度**O(n)**会主导整个操作。
删除：
- 数组：在数组的头部或中间删除一个元素，需要将删除位置之后的所有元素向前移动一位，以填补空缺。这个操作的时间复杂度是O(n)。在数组尾部删除，时间复杂度为O(1)。
- 链表：在链表的头部删除一个元素，只需更新头指针，时间复杂度是O(1)。在链表的中间或尾部删除，如果已知要删除位置的前一个节点，也只需修改两个指针，时间复杂度是O(1)。但如果需要先查找删除位置，那么查找的时间复杂度**O(n)**会主导整个操作。
修改：
- 数组：通过索引直接访问元素并修改，时间复杂度是O(1)。按值查找并修改则为O(n)。
- 链表：无论是按索引还是按值修改，都需要先遍历找到目标元素，因此时间复杂度都是O(n)。

4、堆排序可以用什么数据结构实现？

堆排序（Heap Sort）是一种基于比较的排序算法，它利用了**堆（Heap）**这种数据结构。

堆排序的核心思想是：

将待排序的序列构建成一个大顶堆（或小顶堆）。
将堆顶元素（最大或最小）与堆的最后一个元素交换。
将剩余的n-1个元素重新调整为堆。
重复步骤2和3，直到堆中只剩下一个元素。

因此，堆排序主要使用堆数据结构实现。

堆通常可以被看作是一个完全二叉树，同时满足堆的性质（父节点的值总是大于或等于其子节点的值，称为大顶堆；或者父节点的值总是小于或等于其子节点的值，称为小顶堆）。

最常见的、也是最方便实现堆的数据结构是数组（Array）。

数组实现堆的原理：

由于完全二叉树的特性，可以使用一个一维数组来存储堆中的所有元素，而无需存储显式的指针。

对于数组中索引为 i 的节点：

其父节点的索引是 (i-1)/2（向下取整）。
其左子节点的索引是 2*i + 1。
其右子节点的索引是 2*i + 2。这种映射关系使得数组能够高效地模拟完全二叉树的结构，从而实现堆的各种操作（如插入、删除、堆化）。

所以，堆排序通常使用数组来作为底层数据结构实现堆。

5、除了数组（vector），还可以用什么数据结构实现堆？

除了最常用的数组（或C++中的std::vector）来实现堆之外，理论上任何能够表示完全二叉树的数据结构都可以用来实现堆。

以下是一些可能的替代数据结构：

显式链式二叉树：
- 原理：每个节点包含数据以及指向其左子节点和右子节点的指针。这种方式能够表示任意二叉树。
- 实现堆：要用链式二叉树实现堆，需要额外的逻辑来确保它始终保持完全二叉树的结构（即从左到右填充，没有空洞），并且满足堆的性质。这会比数组实现复杂得多，因为需要手动管理节点的连接和查找最后一个节点的位置。
- 优缺点：
  优点：动态性强，插入和删除节点不需要移动大量数据，理论上可以支持非完全二叉树的结构（但实现堆时仍需保持完全二叉树特性）。
  缺点：内存开销大（每个节点需要额外的指针存储空间），缓存不友好（节点不连续），实现复杂，尤其是要维护完全二叉树的结构。
双端队列：
- 原理：双端队列是一种支持两端插入和删除的序列容器。C++的std::deque内部通常实现为多个固定大小的块，这些块通过指针连接，逻辑上是连续的。
- 实现堆：std::deque可以作为std::priority_queue的底层容器，因为它可以高效地在两端添加和移除元素，并且支持随机访问（尽管不如std::vector高效）。因此，它也可以用来模拟数组实现堆，只是性能可能略低于std::vector。
- 优缺点：
  优点：相比std::vector，在头部插入/删除元素时可能更高效（不需要移动所有元素），内存使用更灵活。
  缺点：随机访问性能略低于std::vector，内存开销可能略大。
其他支持随机访问的序列容器：
任何支持O(1)随机访问和O(1)在末尾添加/删除元素的序列容器，理论上都可以作为堆的底层实现。例如，如果自定义一个基于连续内存的动态数组类，也可以用来实现堆。

6、如果用数组（vector）和二叉树（如红黑树）来实现堆，它们各自的优缺点是什么？

这里需要澄清一个概念：**堆（Heap）本身是一种特殊的完全二叉树，它满足堆的性质。而红黑树（Red-Black Tree）**是一种自平衡二叉搜索树（Self-Balancing Binary Search Tree），它满足二叉搜索树的性质（左子节点小于父节点，右子节点大于父节点），并且通过颜色标记和旋转来保持平衡，以保证O(log n)的查找、插入和删除时间复杂度。

所以，用红黑树来实现“堆”是不准确的说法。红黑树通常用来实现有序集合（Set）或映射（Map），而不是堆。堆的主要操作是找到最大/最小元素（O(1)）和插入/删除元素（O(log n)），但它不保证元素的整体有序性，只保证堆性质。红黑树则保证元素的整体有序性。

这里比较使用数组实现堆和使用红黑树实现优先级队列（因为优先级队列可以用堆实现，也可以用其他有序数据结构实现，如红黑树）

1. 使用数组（`std::vector`）实现堆（即 `std::priority_queue` 的默认底层实现）

优点：
- 空间效率高：数组存储紧凑，没有额外的指针开销（除了vector自身管理开销），内存利用率高。
- 缓存友好：元素在内存中连续存储，CPU缓存命中率高，访问速度快。
- 实现简单：父子节点索引关系计算简单，易于实现。
- O(1)访问堆顶元素：最大/最小元素总是位于数组的第一个位置。
- O(log n)插入/删除：维护堆性质（上浮/下沉）操作的时间复杂度为对数级别。
- 建堆效率高：从无序数组建堆的时间复杂度为O(n)。
缺点：
- 容量固定或扩容开销：如果底层是固定大小数组，则容量固定；如果使用std::vector，当容量不足时需要重新分配内存并拷贝所有元素，可能导致O(n)的开销。
- 非完全有序：只保证堆性质，不保证所有元素的全局有序性。如果需要遍历所有元素并按顺序获取，需要进行完整的堆排序。

2. 使用二叉搜索树（如红黑树）实现优先级队列

优点：
- O(log n)查找、插入、删除：所有操作（包括查找任意元素）的时间复杂度都是对数级别，且保证平衡，性能稳定。
- 有序性：存储的元素始终保持有序，可以方便地进行范围查询或遍历所有元素。
- 动态性：不需要预先分配容量，可以动态增长和收缩。
缺点：
- 空间效率低：每个节点需要额外的指针（通常是左右子节点指针和父节点指针）以及颜色信息，内存开销大。
- 缓存不友好：节点在内存中不连续，导致CPU缓存命中率低，访问速度相对较慢。
- 实现复杂：需要复杂的平衡逻辑（旋转和颜色调整），实现难度远高于数组堆。
- O(log n)访问最大/最小元素：虽然可以快速找到最大/最小元素（通常是树的最左/最右节点），但不如数组堆的O(1)。

总结：

特性	数组（`std::vector`）实现堆	红黑树实现优先级队列
数据结构	完全二叉树的数组表示	自平衡二叉搜索树
查找堆顶	`O(1)`	`O(log n)` (需要遍历到最左/最右节点)
插入元素	`O(log n)` (可能伴随 `O(n)` 的扩容)	`O(log n)`
删除堆顶	`O(log n)`	`O(log n)`
查找任意元素	`O(n)`	`O(log n)`
内存效率	高，存储紧凑	低，每个节点有额外指针和颜色信息开销
缓存友好性	高，内存连续	低，内存分散
实现复杂度	相对简单	复杂，需要平衡操作
主要用途	优先级队列、堆排序	有序集合、映射（`std::map`, `std::set`）

7、删除堆中一个中间元素会发生什么？底层如何调整？

在标准的堆数据结构（通常是基于数组实现的完全二叉树）中，删除一个任意的中间元素（即非堆顶元素）的操作相对复杂，并且不如删除堆顶元素高效。

一般而言，堆主要设计用于快速访问和删除最大/最小元素（堆顶），以及插入元素。删除任意中间元素不是堆的常见或高效操作。如果需要频繁删除任意元素，可能需要考虑其他数据结构（如使用红黑树实现的优先级队列）。

然而，如果确实需要删除堆中的一个中间元素，底层调整过程通常如下：

查找目标元素：
首先，需要找到要删除的中间元素。由于堆不保证除堆性质外的任何特定顺序，所以查找一个特定值或特定索引的元素需要遍历堆，时间复杂度为O(n)。
替换目标元素：
找到目标元素后，为了保持完全二叉树的结构，通常会用堆的最后一个元素来替换要删除的元素。然后，将堆的大小减一，逻辑上移除了最后一个元素。
为什么是最后一个元素？
因为最后一个元素是完全二叉树中最容易移除而不会破坏其结构完整性的元素。
重新堆化（Heapify）：
替换操作后，新的元素（原先的最后一个元素）可能不满足堆的性质。因此，需要对这个新位置的元素进行堆化操作，以恢复堆的性质。
这通常涉及到两种情况：
- 向下调整：如果替换后的元素比其子节点小（在大顶堆中）或大（在小顶堆中），则需要将其与最大的（或最小的）子节点交换，并递归地向下调整，直到满足堆性质或到达叶子节点。这个过程的时间复杂度是O(log n)。
- 向上调整：如果替换后的元素比其父节点大（在大顶堆中）或小（在小顶堆中），则需要将其与父节点交换，并递归地向上调整，直到满足堆性质或到达堆顶。这个过程的时间复杂度也是O(log n)。
具体是向上调整还是向下调整，取决于替换后的元素与周围元素的关系。通常，由于替换元素来自堆的末尾，它可能比其父节点小，也可能比其子节点小，所以可能需要同时考虑向上和向下调整，或者选择一个方向进行调整（例如，先向上调整，如果仍然不满足，再向下调整）。
更常见的做法是，直接进行向下调整，因为替换上来的元素通常较小，需要“下沉”。

操作步骤总结（以大顶堆为例）：

找到要删除的元素（假设其索引为 idx）。O(n)
将堆的最后一个元素与 idx 位置的元素交换。O(1)
将堆的大小减一（逻辑上移除最后一个元素）。O(1)
对 idx 位置的新元素进行向下调整（Heapify-down），使其满足大顶堆性质。O(log n)

8、动态规划（DP）和分治法有什么不一样？

动态规划（Dynamic Programming, DP）和分治法（Divide and Conquer）都是解决复杂问题的算法思想，它们都将问题分解为子问题，但它们的分解方式、子问题间的关系以及解决子问题的方法有本质区别。

特性	动态规划（Dynamic Programming, DP）	分治法（Divide and Conquer）
子问题关系	子问题重叠（Overlapping Subproblems）：	子问题独立（Independent Subproblems）：
	存在大量相同的子问题，需要重复计算。	子问题之间相互独立，不包含重复的子子问题。
解决方式	自底向上（Bottom-Up）或记忆化搜索（Memoization / Top-Down with Caching）：	自顶向下（Top-Down）：
	- 自底向上：先解决最小的子问题，然后逐步构建解决更大的子问题，直到解决原问题。	- 将原问题分解为若干个规模较小但相互独立、与原问题形式相同的子问题。
	- 记忆化搜索：递归地解决问题，但会存储已解决的子问题结果，避免重复计算。	- 递归地解决这些子问题。
		- 将子问题的解合并成原问题的解。
适用问题	优化问题、计数问题，通常涉及求最优解或最值。	适用于可以分解为独立子问题的问题，如排序、查找。
典型问题	背包问题、最长公共子序列、斐波那契数列、矩阵链乘法、最短路径（如Floyd-Warshall）	归并排序、快速排序、二分查找、大整数乘法、汉诺塔

详细解释：

分治法（Divide and Conquer）

核心思想：将一个大的问题分解成若干个相互独立、规模较小的子问题，然后递归地解决这些子问题，最后将子问题的解合并起来得到原问题的解。
子问题特点：子问题之间是独立的，即解决一个子问题不需要另一个子问题的结果，也不会产生重复计算。
解决过程：
1. 分解（Divide）：将原问题分解为若干个子问题。
2. 解决（Conquer）：递归地解决这些子问题。如果子问题足够小，直接解决。
3. 合并（Combine）：将子问题的解合并成原问题的解。
示例：归并排序（将数组分成两半，分别排序，然后合并）、快速排序（选择一个基准，将数组分成两部分，分别排序）、二分查找。

图示（归并排序）：

归并排序

动态规划（Dynamic Programming, DP）

核心思想：当一个问题可以分解成重叠的子问题，并且具有最优子结构（即原问题的最优解包含子问题的最优解）时，动态规划通过存储子问题的解来避免重复计算，从而提高效率。
子问题特点：子问题是重叠的，即在解决原问题的过程中，同一个子问题会被多次计算。DP通过存储这些子问题的解来避免重复计算。
解决过程：
1. 识别最优子结构：原问题的最优解可以通过子问题的最优解来构造。
2. 识别重叠子问题：存在需要重复计算的子问题。
3. 定义状态：用一个或多个变量来表示子问题的解，通常用数组或表格来存储。
4. 建立状态转移方程：描述如何从已知的子问题解推导出更大子问题的解。
5. 计算顺序：通常采用自底向上（迭代）的方式，先计算最小的子问题，然后逐步填充状态表；或者采用自顶向下（递归+记忆化搜索）的方式。
示例：斐波那契数列（F(n) = F(n-1) + F(n-2)，F(n-1)和F(n-2)是重叠子问题）、背包问题、最长公共子序列、最短路径问题。

图示（斐波那契数列）

斐波那契数列

总结区别：

最核心的区别在于子问题是否重叠：

分治法：子问题相互独立，适合并行处理。
动态规划：子问题重叠，通过存储中间结果避免重复计算。

因此，如果一个问题分解后子问题是独立的，用分治法；如果子问题有重叠，并且具备最优子结构，那么动态规划是更合适的选择。

算法

模拟斗地主出牌。给定一副手牌（如17张），要求计算出清所有手牌所需的最少出牌次数。牌型包括单张、对子、顺子、三带一、三带二等，其中组合牌型（如顺子、三带）可以减少出牌次数。

一个经典的搜索/动态规划问题，大家可以采用广度优先搜索 (BFS) 或深度优先搜索 (DFS) 结合剪枝优化来解决。

这里不提供参考解法。

微服务

文档

基础

虾皮高性能C++后端一面 ​

C++ ​

1、如何解决不同编译单元间 static 变量析构顺序不一致的问题？ ​

1.1、Meyer's Singleton（局部静态单例） ​

1.2、资源获取即初始化 (RAII) 原则 ​

1.3、避免全局/跨编译单元静态对象间的依赖 ​

1.4、std::atexit： ​

2、C++ 中是否有语言特性可以解决上述析构顺序问题？ ​

3、如果在头文件中定义一个 static 变量，会发生什么？ ​

4、如何确保一个全局变量在程序中只有一个实例？ ​

Meyer's Singleton (C++11 局部静态变量) ​

其他方法（不推荐或有局限性） ​

5、在函数中声明一个对象但不初始化，会有什么问题？ ​

5.1、基本数据类型（如 int, double, char, 指针等） ​

5.2、类类型对象： ​

6、为什么函数内的局部变量（基本类型）如果不初始化，其值是不确定的？ ​

7、函数内的局部变量能否被“移动”到堆上？ ​

8、基本数据类型（如 int）是否可以通过 move 操作移动到堆上？ ​

9、对于一个类对象，move 操作会触发什么？ ​

10、const 和 constexpr 有什么区别？ ​

详细解释 ​

const (Constant) ​

constexpr (Constant Expression) ​

11、#define 有哪些用法？ ​

12、如何实现一个参数数量和类型都不固定的函数？ ​

13、能介绍一下什么是“完美转发”吗？ ​

实现完美转发的关键要素 ​

完美转发的示例 ​

为什么需要完美转发？ ​

操作系统 ​

1、对操作系统比较熟悉，能介绍一下存储器的层次结构吗？（从速度高到低） ​

存储器层次结构图 ​

2、请将存储器的访问速度进行排序。 ​

3、有没有比 L1 Cache 还快的存储器？ ​

4、线程间如何进行通信？ ​

5、除了加锁，线程间通信还有哪些无锁的方式？ ​

6、原子变量（Atomic Variables）都有哪些？ ​

7、原子变量修改值时，有哪些接口可以使用？ ​

8、多线程发生死锁应如何避免？ ​

9、死锁产生的条件有哪些？ ​

10、针对死锁的各个条件，除了按顺序加锁外，还有哪些解决方案？ ​

1. 破坏互斥条件 ​

2. 破坏请求和保持条件 ​

3. 破坏不剥夺条件 ​

4. 破坏循环等待条件 ​

算法与数据结构 ​

1、简单介绍一下数组和链表的区别。 ​

详细解释 ​

2、从内存利用率角度看，数组和链表哪个更高？ ​

3、数组和链表在增删改查操作上的时间复杂度有何区别？ ​

详细解释 ​

4、堆排序可以用什么数据结构实现？ ​

虾皮高性能C++后端一面

C++

1、如何解决不同编译单元间 static 变量析构顺序不一致的问题？

1.1、Meyer's Singleton（局部静态单例）

1.2、资源获取即初始化 (RAII) 原则

1.3、避免全局/跨编译单元静态对象间的依赖

1.4、`std::atexit`：

2、C++ 中是否有语言特性可以解决上述析构顺序问题？

3、如果在头文件中定义一个 static 变量，会发生什么？

4、如何确保一个全局变量在程序中只有一个实例？

Meyer's Singleton (C++11 局部静态变量)

其他方法（不推荐或有局限性）

5、在函数中声明一个对象但不初始化，会有什么问题？

5.1、基本数据类型（如 `int`, `double`, `char`, 指针等）

5.2、类类型对象：

6、为什么函数内的局部变量（基本类型）如果不初始化，其值是不确定的？

7、函数内的局部变量能否被“移动”到堆上？

8、基本数据类型（如 int）是否可以通过 move 操作移动到堆上？

9、对于一个类对象，move 操作会触发什么？

10、`const` 和 `constexpr` 有什么区别？

详细解释

`const` (Constant)

`constexpr` (Constant Expression)

11、`#define` 有哪些用法？

12、如何实现一个参数数量和类型都不固定的函数？

13、能介绍一下什么是“完美转发”吗？

实现完美转发的关键要素

完美转发的示例

为什么需要完美转发？

操作系统

1、对操作系统比较熟悉，能介绍一下存储器的层次结构吗？（从速度高到低）

存储器层次结构图

2、请将存储器的访问速度进行排序。

3、有没有比 L1 Cache 还快的存储器？

4、线程间如何进行通信？

5、除了加锁，线程间通信还有哪些无锁的方式？

6、原子变量（Atomic Variables）都有哪些？

7、原子变量修改值时，有哪些接口可以使用？

8、多线程发生死锁应如何避免？

9、死锁产生的条件有哪些？

10、针对死锁的各个条件，除了按顺序加锁外，还有哪些解决方案？

1. 破坏互斥条件

2. 破坏请求和保持条件

3. 破坏不剥夺条件

4. 破坏循环等待条件

算法与数据结构

1、简单介绍一下数组和链表的区别。

详细解释

2、从内存利用率角度看，数组和链表哪个更高？

3、数组和链表在增删改查操作上的时间复杂度有何区别？

详细解释

4、堆排序可以用什么数据结构实现？