阿Q技术站

深浅色

美团C++后端二面面经 ​

来源：https://www.nowcoder.com/discuss/794223706988879872

1、在 Lambda 表达式中如何捕获一个 unique_ptr 并在内部使用？ ​

std::unique_ptr 是C++11引入的智能指针，它独占所管理的对象，不允许拷贝，但允许通过移动语义转移所有权。

在Lambda表达式中捕获 unique_ptr 时，由于其不可拷贝的特性，我们不能简单地按值捕获（[ptr]），而需要使用移动捕获（C++14及更高版本）或按引用捕获。

1.1、移动捕获 (C++14 及更高版本) ​

C++14 引入了广义Lambda捕获（Generalized Lambda Capture），允许在捕获列表中使用初始化表达式。这使得我们可以通过 std::move 将 unique_ptr 的所有权转移到 Lambda 表达式内部。

原理： 在捕获列表中，[ptr = std::move(some_unique_ptr)] 会创建一个新的 unique_ptr 变量 ptr，并将 some_unique_ptr 的所有权转移给它。原 some_unique_ptr 将变为 nullptr。

示例：

cpp
#include <iostream>
#include <memory> // For std::unique_ptr
#include <vector>
#include <thread>
#include <functional>

class MyResource {
public:
    int id;
    MyResource(int i) : id(i) { std::cout << "MyResource " << id << " constructed.\n"; }
    ~MyResource() { std::cout << "MyResource " << id << " destroyed.\n"; }
    void do_work() { std::cout << "MyResource " << id << " doing work.\n"; }
};

int main() {
    std::cout << "--- Capturing unique_ptr by move ---\n";
    std::unique_ptr<MyResource> resource_ptr = std::make_unique<MyResource>(100);

    // 使用移动捕获，将 resource_ptr 的所有权转移到 lambda 中
    auto lambda_func = [res_ptr = std::move(resource_ptr)]() {
        if (res_ptr) {
            res_ptr->do_work();
        } else {
            std::cout << "Lambda: resource_ptr is null (ownership was moved).\n";
        }
    };

    // 此时 resource_ptr 已经为空，因为它已经将所有权移动给了 lambda_func 内部的 res_ptr
    if (!resource_ptr) {
        std::cout << "Main: original resource_ptr is now null.\n";
    }

    lambda_func(); // 执行 lambda

    // lambda_func 析构时，其内部的 res_ptr 会被销毁，从而释放 MyResource(100)

    std::cout << "\n--- Capturing unique_ptr by reference ---\n";
    std::unique_ptr<MyResource> another_resource_ptr = std::make_unique<MyResource>(200);

    // 按引用捕获 unique_ptr
    // 注意：如果 lambda 的生命周期超过了 original_ptr，会导致悬空引用
    auto lambda_ref_func = [&another_resource_ptr]() {
        if (another_resource_ptr) {
            another_resource_ptr->do_work();
        } else {
            std::cout << "Lambda (ref): another_resource_ptr is null.\n";
        }
    };

    lambda_ref_func();

    // 此时 original_ptr 仍然有效
    if (another_resource_ptr) {
        std::cout << "Main: original another_resource_ptr is still valid.\n";
    }
    // 可以在 lambda 外部继续使用或转移所有权
    std::unique_ptr<MyResource> moved_out_ptr = std::move(another_resource_ptr);
    std::cout << "Main: moved_out_ptr now owns resource 200.\n";

    lambda_ref_func(); // 此时 lambda 内部的引用将是悬空的，或指向 nullptr

    std::cout << "\n--- Capturing unique_ptr for asynchronous tasks (e.g., thread) ---\n";
    std::unique_ptr<MyResource> thread_resource = std::make_unique<MyResource>(300);
    std::thread t([res_ptr_in_thread = std::move(thread_resource)]() {
        if (res_ptr_in_thread) {
            res_ptr_in_thread->do_work();
        }
        // res_ptr_in_thread 在线程函数退出时自动销毁
    });
    t.join();

    std::cout << "--- End of main ---\n";
    return 0;
}

输出：

输出截图

text
--- Capturing unique_ptr by move ---
MyResource 100 constructed.
Main: original resource_ptr is now null.
MyResource 100 doing work.

--- Capturing unique_ptr by reference ---
MyResource 200 constructed.
MyResource 200 doing work.
Main: original another_resource_ptr is still valid.
Main: moved_out_ptr now owns resource 200.
Lambda (ref): another_resource_ptr is null.

--- Capturing unique_ptr for asynchronous tasks (e.g., thread) ---
MyResource 300 constructed.
MyResource 300 doing work.
MyResource 300 destroyed.
--- End of main ---
MyResource 200 destroyed.
MyResource 100 destroyed.
  • 移动捕获 ([res_ptr = std::move(original_ptr)])：推荐用于将 unique_ptr 的所有权安全地转移到 Lambda 内部，尤其是在 Lambda 的生命周期可能超过原 unique_ptr 的场景（如异步任务、线程）。它确保了资源独占性，避免了悬空指针。
  • 按引用捕获 ([&original_ptr])：如果 Lambda 的生命周期严格短于 original_ptr，或者你需要在 Lambda 内部修改 original_ptr 本身（例如，将其 release()），则可以使用引用捕获。但必须非常小心，避免悬空引用问题。

1.2、C++11 兼容方案 (通过 std::bind 或包装器) ​

在C++11中，由于没有广义Lambda捕获，如果需要将 unique_ptr 移动到 Lambda 中，可以采用 std::bind 结合 std::move，或者自定义一个包装器。

示例 (使用 std::bind)：

cpp
#include <iostream>
#include <memory>
#include <functional>

class MyResource {
public:
    int id;
    MyResource(int i) : id(i) { std::cout << "MyResource " << id << " constructed.\n"; }
    ~MyResource() { std::cout << "MyResource " << id << " destroyed.\n"; }
    void do_work() { std::cout << "MyResource " << id << " doing work.\n"; }
};

int main() {
    std::unique_ptr<MyResource> resource_ptr = std::make_unique<MyResource>(400);

    // 使用 std::bind 和 std::move 将 unique_ptr 移动到可调用对象中
    // std::bind 会拷贝或移动其参数。这里 std::move(resource_ptr) 会触发 unique_ptr 的移动构造函数
    auto bound_func = std::bind([](std::unique_ptr<MyResource> p) {
        if (p) {
            p->do_work();
        } else {
            std::cout << "Bound func: unique_ptr is null.\n";
        }
    }, std::move(resource_ptr));

    if (!resource_ptr) {
        std::cout << "Main: original resource_ptr is now null after std::bind.\n";
    }

    bound_func();
    // 当 bound_func 析构时，其内部持有的 unique_ptr 会被销毁

    return 0;
}

2、unique_ptr 的所有权转移机制是怎样的？ ​

std::unique_ptr 是一种独占式智能指针，它确保在任何时间点只有一个 unique_ptr 实例拥有其所管理的对象。这意味着 unique_ptr 不支持拷贝，但支持通过移动语义转移其所有权。

2.1、所有权转移机制 ​

unique_ptr 的所有权转移主要通过以下两种方式实现：

  1. 移动构造函数：

    • 当使用一个右值（通常是临时 unique_ptr 对象或通过 std::move 转换的 unique_ptr）来初始化另一个 unique_ptr 对象时，会调用移动构造函数。
    • 原理：它将源 unique_ptr 所管理对象的指针直接“窃取”过来，然后将源 unique_ptr 内部的指针设置为 nullptr。这样，新 unique_ptr 获得了所有权，而源 unique_ptr 不再拥有任何资源，其析构函数将不会释放资源。
    • 伪代码：
      cpp
      template <typename T, typename Deleter>
unique_ptr<T, Deleter>::unique_ptr(unique_ptr<T, Deleter>&& other) noexcept
{
    this->ptr_ = other.ptr_; // 窃取资源
    this->deleter_ = std::move(other.deleter_); // 移动deleter
    other.ptr_ = nullptr;     // 源对象置空
}

  2. 移动赋值运算符：

    • 当一个右值 unique_ptr 赋值给一个已存在的 unique_ptr 对象时，会调用移动赋值运算符。
    • 原理：首先，当前 unique_ptr 会释放它自己当前拥有的资源（如果存在）。然后，它执行与移动构造函数类似的操作，从源 unique_ptr “窃取”资源，并将源 unique_ptr 置空。
    • 伪代码：
      cpp
      template <typename T, typename Deleter>
unique_ptr<T, Deleter>& unique_ptr<T, Deleter>::operator=(unique_ptr<T, Deleter>&& other) noexcept
{
    if (this != &other) // 防止自我赋值
    {
        reset(); // 释放当前对象所拥有的资源
        this->ptr_ = other.ptr_; // 窃取资源
        this->deleter_ = std::move(other.deleter_); // 移动deleter
        other.ptr_ = nullptr;     // 源对象置空
    }
    return *this;
}

  3. release() 方法：

    • release() 方法会放弃 unique_ptr 对其管理对象的控制权，并返回原始指针。unique_ptr 自身变为 nullptr，但它管理的资源不会被释放。调用者有责任管理返回的原始指针。
    • 伪代码：
      cpp
      template <typename T, typename Deleter>
T* unique_ptr<T, Deleter>::release() noexcept
{
    T* old_ptr = ptr_;
    ptr_ = nullptr;
    return old_ptr;
}

2.2、示例 ​

cpp
#include <iostream>
#include <memory>
#include <vector>

class MyObject {
public:
    int value;
    MyObject(int v) : value(v) { std::cout << "MyObject " << value << " constructed.\n"; }
    ~MyObject() { std::cout << "MyObject " << value << " destroyed.\n"; }
    void print() const { std::cout << "MyObject value: " << value << "\n"; }
};

// 函数接受 unique_ptr by value (会触发移动构造)
void process_object(std::unique_ptr<MyObject> obj_ptr) {
    if (obj_ptr) {
        obj_ptr->print();
    }
    // obj_ptr 在函数结束时析构，释放资源
}

// 函数返回 unique_ptr (会触发移动构造)
std::unique_ptr<MyObject> create_object(int val) {
    return std::make_unique<MyObject>(val);
}

int main() {
    std::cout << "--- Initial unique_ptr creation ---\n";
    std::unique_ptr<MyObject> p1 = std::make_unique<MyObject>(10);
    p1->print();

    std::cout << "\n--- Ownership transfer via move constructor ---\n";
    // p2 通过移动构造函数从 p1 获得所有权
    // p1 变为 nullptr
    std::unique_ptr<MyObject> p2 = std::move(p1);
    if (p1) { p1->print(); } else { std::cout << "p1 is null.\n"; }
    if (p2) { p2->print(); } else { std::cout << "p2 is null.\n"; }

    std::cout << "\n--- Ownership transfer via move assignment operator ---\n";
    std::unique_ptr<MyObject> p3 = std::make_unique<MyObject>(30);
    std::unique_ptr<MyObject> p4 = std::make_unique<MyObject>(40);
    p3->print();
    p4->print();
    std::cout << "Assigning p3 = std::move(p4)...\n";
    // p3 释放其当前资源 (MyObject 30)，然后从 p4 获得所有权
    // p4 变为 nullptr
    p3 = std::move(p4);
    if (p3) { p3->print(); } else { std::cout << "p3 is null.\n"; }
    if (p4) { p4->print(); } else { std::cout << "p4 is null.\n"; }

    std::cout << "\n--- Ownership transfer to function parameter ---\n";
    std::unique_ptr<MyObject> p5 = std::make_unique<MyObject>(50);
    std::cout << "Calling process_object with p5...\n";
    process_object(std::move(p5)); // p5 的所有权转移到函数内部
    if (p5) { p5->print(); } else { std::cout << "p5 is null after move.\n"; }

    std::cout << "\n--- Ownership transfer from function return ---\n";
    std::unique_ptr<MyObject> p6 = create_object(60);
    if (p6) { p6->print(); } else { std::cout << "p6 is null.\n"; }

    std::cout << "\n--- Releasing ownership ---\n";
    std::unique_ptr<MyObject> p7 = std::make_unique<MyObject>(70);
    MyObject* raw_ptr = p7.release(); // p7 放弃所有权，变为 nullptr
    std::cout << "p7 is null: " << (p7 == nullptr ? "true" : "false") << "\n";
    std::cout << "Raw pointer value: " << raw_ptr->value << "\n";
    delete raw_ptr; // 必须手动释放资源

    std::cout << "\n--- End of main ---\n";
    return 0;
}

输出：

输出截图

text
--- Initial unique_ptr creation ---
MyObject 10 constructed.
MyObject value: 10

--- Ownership transfer via move constructor ---
p1 is null.
MyObject value: 10

--- Ownership transfer via move assignment operator ---
MyObject 30 constructed.
MyObject 40 constructed.
MyObject value: 30
MyObject value: 40
Assigning p3 = std::move(p4)...
MyObject 30 destroyed.
MyObject value: 40
p4 is null.

--- Ownership transfer to function parameter ---
MyObject 50 constructed.
Calling process_object with p5...
MyObject value: 50
p5 is null after move.
MyObject 50 destroyed.

--- Ownership transfer from function return ---
MyObject 60 constructed.
MyObject value: 60

--- Releasing ownership ---
MyObject 70 constructed.
p7 is null: true
Raw pointer value: 70
MyObject 70 destroyed.

--- End of main ---
MyObject 60 destroyed.
MyObject 40 destroyed.
MyObject 10 destroyed.

2.3、为什么 unique_ptr 不可拷贝？ ​

unique_ptr 的设计理念是独占所有权。如果允许拷贝，那么多个 unique_ptr 实例将指向同一个资源。

当其中一个 unique_ptr 析构时，它会释放资源，导致其他 unique_ptr 变成悬空指针，再次析构时会造成双重释放，引发程序崩溃。

通过禁止拷贝并强制使用移动语义，unique_ptr 确保了资源在任何时候都只有一个所有者，从而避免了这些问题。

3、什么是万能引用？为什么要使用万能引用？ ​

万能引用（Universal Reference），在C++11中最初被称为“转发引用”（Forwarding Reference），是一种特殊的引用类型。它既可以绑定到左值，也可以绑定到右值，并且在模板编程中表现出独特的类型推导行为。

3.1、形式 ​

万能引用通常出现在以下两种形式中：

  1. 函数模板参数：T&&，其中 T 是一个未推导的模板参数。
  2. auto&&：在 auto 声明中。

关键在于 T 是一个未推导的模板参数。 如果 T 是一个已知类型，那么 T&& 就只是一个普通的右值引用。

3.2、类型推导规则（引用折叠） ​

万能引用之所以能够绑定到左值和右值，是因为C++的**引用折叠（Reference Collapsing）**规则。当 T&& 遇到不同类型的实参时，T 的类型推导和引用折叠规则如下：

  • 如果实参是左值 X，T 会被推导为 X&（左值引用）。此时 X& && 会折叠成 X&（左值引用）。
  • 如果实参是右值 X，T 会被推导为 X（非引用类型）。此时 X&& 保持为 X&&（右值引用）。

这意味着，万能引用 T&& 会根据传入实参的类型，**“变成”**一个左值引用或右值引用，从而实现对左值和右值的通用绑定。

3.3、为什么要使用万能引用？ ​

使用万能引用的主要目的是为了实现完美转发（Perfect Forwarding），即在函数模板中，能够以原始的左值/右值属性将参数转发给另一个函数。

这在编写通用库函数或包装器时非常有用，可以避免不必要的拷贝和类型转换，提高性能并保持语义的正确性。

完美转发的优势：

  1. 避免不必要的拷贝：如果一个参数是右值，万能引用会将其推导为右值引用，并允许通过 std::forward 将其转发为右值，从而触发移动语义，避免深拷贝。
  2. 保持原始值类别：无论是左值还是右值，其原始的“左值性”或“右值性”都能在转发过程中得以保留。
  3. 编写通用代码：允许编写一个函数模板，它能接受任何类型的参数（左值或右值），并将其高效地转发给内部调用的函数，而无需编写多个重载版本。

举例说明：

考虑一个简单的包装函数 wrapper，它接受一个参数并将其传递给 process 函数：

cpp
#include <iostream>
#include <string>
#include <utility>

void process(int& lval) { std::cout << "Processing lvalue: " << lval << "\n"; }
void process(int&& rval) { std::cout << "Processing rvalue: " << rval << "\n"; }

// 没有万能引用和完美转发的问题：
// 如果只接受 int&，不能处理右值
// 如果只接受 int&&，不能处理左值
// 如果按值传递 int，会产生不必要的拷贝
// 如果写两个重载，代码冗余

// 使用万能引用实现完美转发
template <typename T>
void wrapper(T&& arg) { // T&& 是万能引用
    std::cout << "Wrapper received: ";
    process(std::forward<T>(arg)); // 完美转发，保持 arg 的原始值类别
}

int main() {
    int a = 10;
    wrapper(a);       // a 是左值，T被推导为 int&，std::forward<int&>(a) 仍是 int&，调用 process(int&)
    wrapper(20);      // 20 是右值，T被推导为 int，std::forward<int>(20) 是 int&&，调用 process(int&&)

    int b = 30;
    wrapper(std::move(b)); // std::move(b) 是右值，T被推导为 int，std::forward<int>(std::move(b)) 是 int&&，调用 process(int&&)

    return 0;
}

输出：

输出截图

text
Wrapper received: Processing lvalue: 10
Wrapper received: Processing rvalue: 20
Wrapper received: Processing rvalue: 30

如果没有万能引用和 std::forward，我们需要为 wrapper 编写两个重载版本，一个接受左值引用，一个接受右值引用，才能实现相同的效果，这增加了代码的复杂性。

4、实际开发中哪些场景会用到万能引用？标准库（STL）中哪些地方使用了它？ ​

万能引用和完美转发是C++11及更高版本中非常强大的特性，广泛应用于需要编写通用、高效且类型安全的库代码中。

4.1、实际开发中的使用场景 ​

  1. 包装器函数：

    • 当你需要为现有函数添加一些通用逻辑（如日志记录、性能计时、参数验证等），然后将参数转发给原始函数时，万能引用是理想选择。它可以确保原始函数的参数类型（左值/右值）和常量性在转发时得到保留。
    • 示例：一个通用的 log_and_call 函数。

  2. 工厂函数：

    • 创建对象的工厂函数通常需要接受各种参数来构造对象。使用万能引用可以避免为每种构造函数参数组合编写多个重载，从而以最有效的方式（通过移动语义）将参数传递给目标对象的构造函数。
    • 示例：std::make_unique 和 std::make_shared 的实现。

  3. 容器的 emplace 系列方法：

    std::vector::emplace_back、std::map::emplace 等方法使用万能引用来直接在容器内部构造元素，避免了临时对象的创建和拷贝/移动操作，提高了效率。

  4. 智能指针的构造函数：

    std::unique_ptr 和 std::shared_ptr 的构造函数可以接受原始指针，但如果它们需要接受其他智能指针作为参数（例如，从 unique_ptr 构造 shared_ptr），或者在内部转发参数给被管理对象的构造函数时，也会用到完美转发。

  5. 元编程和类型特征：

    在高级模板元编程中，万能引用可以帮助编写能够处理任何值类别的函数，并在此基础上进行类型分析和操作。

  6. 自定义分配器：

    在自定义内存分配器时，通常需要一个 construct 方法来在预分配的内存上构造对象。这个方法会使用万能引用来完美转发构造函数的参数。

4.2、标准库（STL）中的使用 ​

STL中大量使用了万能引用和完美转发来提高效率和通用性。

以下是一些主要例子：

  1. std::forward：

    这是完美转发的核心辅助函数。它本身不是万能引用，但与万能引用 T&& 结合使用，能够根据 T 的推导结果，将 arg 转换为左值引用或右值引用。

  2. std::move：

    虽然 std::move 返回一个右值引用，但它的实现也依赖于模板和引用折叠的原理，尽管它不直接是万能引用。

  3. std::make_unique 和 std::make_shared：

    这两个工厂函数是创建智能指针的首选方式。它们的实现都使用了万能引用来完美转发参数给被管理对象的构造函数。

    cpp
    template<typename T, typename... Args>
std::unique_ptr<T> make_unique(Args&&... args) {
    return std::unique_ptr<T>(new T(std::forward<Args>(args)...));
}

  4. 容器的 emplace 系列成员函数：

    std::vector::emplace_back、std::list::emplace_front、std::map::emplace 等。这些函数接受可变参数模板，并使用万能引用将这些参数完美转发给元素的构造函数，从而在容器内部直接构造元素，避免了临时对象的创建和拷贝/移动。

    cpp
    template< class... Args >
void emplace_back( Args&&... args ); // 示例：vector::emplace_back

  5. std::function 的构造函数和 operator()：

    std::function 可以包装任何可调用对象。其构造函数和 operator() 的实现也利用了万能引用来高效地处理和转发参数给被包装的可调用对象。

  6. std::thread 的构造函数：

    std::thread 的构造函数接受可调用对象和其参数。它使用万能引用来完美转发这些参数，确保线程函数能够以正确的参数类型被调用。

  7. std::bind：

    std::bind 也是一个复杂的模板函数，其参数绑定和转发机制也大量使用了万能引用和完美转发。

5、emplace_back 与 push_back 的区别与优点是什么？ ​

emplace_back 和 push_back 都是 std::vector（以及其他容器如 std::list, std::deque）用于向容器末尾添加元素的方法。它们的主要区别在于元素的构造方式，这直接影响了性能和效率。

5.1、push_back ​

push_back 接受一个已经存在的对象（或临时对象），然后将其拷贝或移动到容器中。

  • 参数：接受一个 const T&（左值引用）或 T&&（右值引用）。
  • 行为：
    1. 如果传入的是左值，会调用元素的拷贝构造函数在容器内部创建一个新元素。
    2. 如果传入的是右值（包括临时对象），会调用元素的移动构造函数在容器内部创建一个新元素。

示例：

cpp
#include <iostream>
#include <vector>

class Widget {
public:
    int id;
    Widget(int i) : id(i) { std::cout << "Widget(" << id << ") constructed.\n"; }
    Widget(const Widget& other) : id(other.id) { std::cout << "Widget(" << id << ") copied.\n"; }
    Widget(Widget&& other) noexcept : id(other.id) { std::cout << "Widget(" << id << ") moved.\n"; other.id = -1; }
    ~Widget() { std::cout << "Widget(" << id << ") destroyed.\n"; }
};

int main() {
    std::vector<Widget> widgets;
    std::cout << "--- push_back with lvalue ---\n";
    Widget w1(1); // 构造一个临时对象 w1
    widgets.push_back(w1); // w1 是左值，调用拷贝构造函数
    std::cout << "Vector size: " << widgets.size() << ", w1.id: " << w1.id << "\n";

    std::cout << "\n--- push_back with rvalue (temporary object) ---\n";
    widgets.push_back(Widget(2)); // Widget(2) 是临时对象（右值），调用移动构造函数
    std::cout << "Vector size: " << widgets.size() << "\n";

    std::cout << "\n--- push_back with rvalue (std::move) ---\n";
    Widget w3(3);
    widgets.push_back(std::move(w3)); // std::move(w3) 产生右值，调用移动构造函数
    std::cout << "Vector size: " << widgets.size() << ", w3.id: " << w3.id << "\n";

    std::cout << "\n--- End of main (widgets will be destroyed) ---\n";
    return 0;
}

输出：

输出截图

分析：

  • push_back(w1)：先构造 w1，然后将 w1 拷贝到 vector 中。总共发生一次构造和一次拷贝构造。
  • push_back(Widget(2))：先构造临时对象 Widget(2)，然后将该临时对象移动到 vector 中。总共发生一次构造和一次移动构造。
  • push_back(std::move(w3))：先构造 w3，然后将 w3 移动到 vector 中。总共发生一次构造和一次移动构造。

5.2、emplace_back ​

emplace_back 接受用于构造元素的参数，并使用这些参数在容器内部直接构造一个新元素（in-place construction）。

  • 参数：接受可变参数模板 Args&&... args，这些参数会被完美转发给元素的构造函数。
  • 行为：直接在容器预留的内存空间上调用元素的构造函数，避免了创建临时对象，以及随后的拷贝或移动操作。

示例：

cpp
#include <iostream>
#include <vector>

class Widget {
public:
    int id;
    Widget(int i) : id(i) { std::cout << "Widget(" << id << ") constructed.\n"; }
    Widget(const Widget& other) : id(other.id) { std::cout << "Widget(" << id << ") copied.\n"; }
    Widget(Widget&& other) noexcept : id(other.id) { std::cout << "Widget(" << id << ") moved.\n"; other.id = -1; }
    ~Widget() { std::cout << "Widget(" << id << ") destroyed.\n"; }
};

int main() {
    std::vector<Widget> widgets;
    std::cout << "--- emplace_back ---\n";
    widgets.emplace_back(4); // 直接在 vector 内部构造 Widget(4)
    std::cout << "Vector size: " << widgets.size() << "\n";

    std::cout << "\n--- End of main (widgets will be destroyed) ---\n";
    return 0;
}

输出：

输出截图

分析：

emplace_back(4)：直接在 vector 内部调用 Widget(4) 的构造函数。总共只发生一次构造。

5.3、区别与优点 ​

特性push_backemplace_back
参数类型const T& (左值) 或 T&& (右值)Args&&... (可变参数模板，完美转发)
构造过程先在外部构造对象，再拷贝/移动到容器内部直接在容器内部用参数构造对象
临时对象可能创建临时对象（如果传入字面量或表达式）不创建临时对象
效率至少一次构造，可能伴随一次拷贝或移动只有一次构造
主要优点简单直观，适用于所有类型性能优化，特别是对于复杂类型或有昂贵拷贝成本的类型
适用场景任何需要添加元素的情况优先选择，特别是当元素构造函数需要多个参数时

emplace_back 的优点总结：

  1. 减少不必要的拷贝/移动操作：这是最主要的优点。对于没有移动构造函数或移动构造函数开销很大的类型，emplace_back 可以避免这些开销，直接在目标内存上构造对象。
  2. 提高性能：减少了临时对象的创建和销毁，以及数据拷贝的次数，从而提高了程序的运行效率。
  3. 更灵活的构造：可以直接传递构造函数所需的多个参数，而无需先创建一个临时对象。

何时使用？

  • 优先使用 emplace_back：对于大多数情况，尤其是自定义类型，emplace_back 提供了更好的性能。它能够充分利用C++11的完美转发特性。
  • 当 emplace_back 不适用时使用 push_back：例如，你已经有一个现成的对象，并且希望将其添加到容器中，或者当元素的构造函数需要一些复杂的前置处理，不适合直接在 emplace_back 中传递参数时。

6、vector 扩容时是否总是需要拷贝？是否存在其他情况？ ​

std::vector 是C++标准库中的动态数组，其底层通常使用一块连续的内存来存储元素。当 vector 的当前容量不足以容纳新元素时，就需要进行扩容。扩容过程涉及到重新分配内存，并将现有元素转移到新的内存区域。

6.1、扩容机制 ​

当 vector 需要扩容时，通常会执行以下步骤：

  1. 分配更大的内存：vector 会分配一块比当前容量更大的新内存块（通常是当前容量的1.5倍或2倍，具体取决于实现）。
  2. 转移元素：将旧内存块中的所有元素转移到新内存块中。
  3. 释放旧内存：释放旧的内存块。

6.2、转移元素的方式：拷贝或移动 ​

在C++11之前，转移元素总是通过拷贝构造函数完成的，这意味着每个元素都会被完整地复制一份到新内存。这对于包含大量数据或自定义类型且拷贝成本高昂的元素来说，会带来显著的性能开销。

C++11及以后，引入了移动语义，vector 扩容时不再总是需要拷贝，而是会优先尝试使用元素的移动构造函数**。**

  • 移动构造函数 (Move Constructor)：如果元素类型定义了移动构造函数（并且是 noexcept 的），vector 在扩容时会优先调用移动构造函数来转移元素。移动构造函数通常只是“窃取”源对象的资源，并将源对象置空，其开销远小于深拷贝。这显著提高了扩容的效率。
  • 拷贝构造函数 (Copy Constructor)：如果元素类型没有定义移动构造函数，或者移动构造函数不是 noexcept 的，vector 就会退而求其次，调用拷贝构造函数来转移元素。这是为了保证在移动过程中发生异常时，vector 能够保持有效的状态（强异常安全保证）。

总结：

  • vector 扩容时不总是需要拷贝。
  • 如果元素类型支持 noexcept 的移动构造函数，vector 会使用移动构造函数来转移元素。
  • 如果元素类型不支持移动构造函数，或者移动构造函数可能抛出异常，vector 会使用拷贝构造函数来转移元素。

6.3、其他情况（不发生扩容） ​

除了拷贝和移动的情况，还有一些情况可以避免扩容时的元素转移：

  1. 预留足够的容量 (reserve)：

    在向 vector 添加元素之前，如果能预先知道所需的最大元素数量，可以调用 vector::reserve(capacity) 方法预留足够的内存空间。这样在后续添加元素时，只要不超过预留容量，就不会发生扩容，从而避免了任何元素转移。

  2. 使用 std::vector::emplace_back 配合 reserve：

    emplace_back 本身就避免了临时对象的拷贝/移动。如果再配合 reserve 避免扩容，那么元素的构造将直接在最终位置进行，达到最高效率。

  3. 小对象优化 (Small Object Optimization)：

    对于某些自定义类型，如果其大小非常小，编译器或标准库的实现可能会对其进行特殊优化，例如直接存储在 vector 内部而不是动态分配内存。但这通常是底层实现细节，不应依赖。

7、如果不想拷贝元素，该如何避免？（移动语义与优化方法） ​

避免不必要的元素拷贝是C++性能优化的一个重要方面，尤其是在处理大型对象或资源密集型对象时。C++11引入的移动语义是解决这一问题的核心机制。此外，还有一些其他优化方法。

7.1、移动语义 ​

移动语义允许**“窃取”**资源而不是复制资源。它通过右值引用 (&&) 和两个特殊成员函数（移动构造函数和移动赋值运算符）来实现。

核心思想： 当一个对象是一个右值（即将被销毁的临时对象，或通过 std::move 明确标记为可移动的对象）时，我们不再需要对其进行深拷贝，而是可以直接将其内部资源（如指针、文件句柄等）转移给新对象，并将源对象置于有效但未指定的状态（通常是置空）。

实现方式：

  1. 为自定义类型实现移动构造函数和移动赋值运算符：

    • 如果你的类管理着动态资源（如 myString 中的 char* data），你需要显式地实现移动构造函数和移动赋值运算符。它们通常执行浅拷贝，然后将源对象的资源指针置为 nullptr。
    • 示例：
      cpp
      class MyResourceClass {
private:
    int* data_;
    size_t size_;
public:
    // ... 构造函数, 析构函数, 拷贝构造/赋值 ...

    // 移动构造函数
    MyResourceClass(MyResourceClass&& other) noexcept
        : data_(other.data_), size_(other.size_)
    {
        other.data_ = nullptr;
        other.size_ = 0;
        std::cout << "MyResourceClass moved constructed.\n";
    }

    // 移动赋值运算符
    MyResourceClass& operator=(MyResourceClass&& other) noexcept
    {
        if (this != &other) {
            delete[] data_; // 释放当前资源
            data_ = other.data_;
            size_ = other.size_;
            other.data_ = nullptr;
            other.size_ = 0;
            std::cout << "MyResourceClass moved assigned.\n";
        }
        return *this;
    }
};

  2. 使用 std::move 显式转换为右值：

    • 当你想将一个左值对象作为右值传递给函数（从而触发移动语义）时，可以使用 std::move。std::move 本身不执行任何移动操作，它只是将一个左值强制转换为右值引用，告诉编译器“这个对象可以被移动”。
    • 示例：
      cpp
      MyResourceClass obj1;
// ... 对obj1进行操作 ...
MyResourceClass obj2 = std::move(obj1); // 调用移动构造函数

  3. 利用返回值的优化 (Return Value Optimization, RVO / Named Return Value Optimization, NRVO)：

    • 编译器在某些情况下会自动优化，避免返回值的拷贝。当函数返回一个局部对象时，编译器可以直接在调用者的栈帧中构造该对象，从而消除拷贝或移动操作。这通常被称为RVO或NRVO。
    • 示例：
      cpp
      MyResourceClass create_large_object() {
    MyResourceClass obj; // 在函数内部构造
    // ... 填充obj ...
    return obj; // 编译器可能优化掉拷贝/移动
}
MyResourceClass result = create_large_object(); // 直接构造到 result

7.2、其他优化方法 ​

  1. 按常量引用传递参数 (Pass by const&)：

    • 对于函数参数，如果函数不需要修改传入的对象，并且对象较大，应优先使用 const 左值引用 (const T&) 传递。这避免了拷贝，同时保证了对象的只读性。
    • 示例： void func(const MyResourceClass& obj);

  2. 按值返回小对象：

    对于小型对象（如 int, double, std::pair 等），按值返回通常比按引用返回更高效，因为它们可以被编译器优化，直接存储在寄存器中，或者RVO/NRVO可以完全消除拷贝。

  3. 使用 emplace 系列容器方法：

    如前所述，std::vector::emplace_back 等方法允许直接在容器内部构造元素，避免了临时对象的创建和随后的拷贝/移动。

  4. 预留容器容量 (reserve)：

    对于 std::vector，如果能预知其最终大小，使用 reserve() 预先分配内存可以避免多次扩容带来的元素移动开销。

  5. 使用智能指针：

    对于动态分配的对象，使用 std::unique_ptr 或 std::shared_ptr 可以避免手动管理内存和潜在的拷贝问题。unique_ptr 强制使用移动语义来转移所有权。

  6. 避免不必要的临时对象：

    编写代码时注意减少临时对象的创建。例如，链式调用中如果每个中间结果都创建临时对象，可能会导致多次拷贝。合理利用移动语义或直接修改对象可以改善。

通过综合运用移动语义和上述优化方法，可以显著减少C++程序中的不必要拷贝，从而提升性能和资源利用效率。

8、C++ 程序的编译过程是怎样的？ ​

C++ 程序的编译过程是一个多阶段的复杂过程，将人类可读的源代码转换为机器可执行的二进制代码。这个过程通常由编译器驱动程序（如 g++ 或 clang++）协调完成，但它内部可以细分为四个主要阶段：预处理（Preprocessing）、编译（Compilation）、汇编（Assembly）和链接（Linking）。

8.1、预处理 ​

  • 输入：C++ 源代码文件（.cpp, .cxx, .cc 等）。
  • 输出：预处理后的源代码文件（通常是 .i 文件）。
  • 主要任务：
    1. 宏替换：处理 #define 定义的宏，进行文本替换。
    2. 文件包含：处理 #include 指令，将头文件（.h, .hpp 等）的内容插入到当前文件中。
    3. 条件编译：处理 #if, #ifdef, #ifndef, #else, #elif, #endif 等指令，根据条件决定哪些代码段被编译，哪些被忽略。
    4. 删除注释：移除所有的注释（// 和 /* ... */）。
    5. 行号和文件名添加：添加 #line 指令，以便后续阶段报错时能定位到原始源代码行号。
  • 常用命令：g++ -E source.cpp -o source.i

8.2、编译 ​

  • 输入：预处理后的源代码文件（.i 文件）。
  • 输出：汇编代码文件（通常是 .s 文件）。
  • 主要任务：
    1. 词法分析：将源代码分解成一系列的词法单元（tokens），如关键字、标识符、运算符、常量等。
    2. 语法分析：根据语言的语法规则，将词法单元组合成抽象语法树（Abstract Syntax Tree, AST），检查语法错误。
    3. 语义分析：对AST进行语义检查，如类型检查、作用域检查、声明检查等，确保代码的逻辑正确性。
    4. 中间代码生成：将AST转换为与特定机器无关的中间代码（如三地址码）。
    5. 代码优化：对中间代码进行各种优化，如常量折叠、死代码消除、循环优化等，以提高程序运行效率。
    6. 目标代码生成：将优化后的中间代码转换为目标机器的汇编代码。
  • 常用命令：g++ -S source.i -o source.s

8.3、汇编 ​

  • 输入：汇编代码文件（.s 文件）。
  • 输出：目标文件（Object File，通常是 .o 文件或 .obj 文件）。
  • 主要任务：
    1. 将汇编代码翻译成机器指令：汇编器将汇编指令一对一地翻译成机器语言指令。
    2. 生成符号表：记录代码中定义的函数和变量的地址，以及引用的外部函数和变量。
    3. 生成重定位信息：记录代码中需要由链接器在链接阶段进行地址修正的部分。
  • 常用命令：g++ -c source.s -o source.o (或直接 g++ -c source.cpp -o source.o，跳过前两个阶段)

8.4、链接 ​

  • 输入：一个或多个目标文件（.o 文件），以及可能需要的库文件（静态库 .a / .lib，动态库 .so / .dll）。
  • 输出：可执行文件（Executable File，Linux下无扩展名，Windows下 .exe）或共享库文件。
  • 主要任务：

    1. 符号解析（Symbol Resolution）：将各个目标文件中引用的外部符号（函数、全局变量）与它们在其他目标文件或库文件中定义的符号进行匹配。

    2. 地址重定位（Relocation）：根据符号解析的结果，修正目标文件中对外部符号的引用地址，以及调整代码和数据的内存布局。

    3. 库文件合并：

      静态链接：将所有被引用的库函数和全局变量的代码直接复制到最终的可执行文件中。优点是运行时不需要外部库，缺点是可执行文件较大，更新库需要重新编译链接。

      动态链接：在可执行文件中只保留对库函数的引用信息，实际的库代码在程序运行时才加载。优点是可执行文件较小，节省内存，库更新方便，缺点是运行时需要依赖外部库。

  • 常用命令：g++ source.o -o executable (或直接 g++ source.cpp -o executable，完成所有阶段)

编译过程示意图 ​

编译过程

9、操作系统是如何加载可执行文件的？ ​

操作系统加载可执行文件是一个复杂但高效的过程，它涉及将磁盘上的程序指令和数据映射到内存中，并为程序的执行做好准备。这个过程通常由操作系统的**加载器（Loader）**组件完成。

以下是其主要步骤：

9.1、典型的加载过程 ​

  1. 创建新的进程空间：

    • 当用户或另一个进程请求执行一个程序时（例如，通过 execve 系统调用），操作系统首先会创建一个新的进程。这个新进程会获得一个独立的虚拟地址空间。
    • 虚拟地址空间是操作系统为每个进程提供的抽象，它使得每个进程都认为自己拥有完整的内存，而无需关心物理内存的实际布局。

  2. 读取可执行文件头部信息：

    • 加载器会打开磁盘上的可执行文件（例如，Linux下的ELF格式，Windows下的PE格式）。

    • 它会读取文件头部（如ELF Header或PE Header）中的元数据，这些元数据包含了程序运行所需的重要信息，

    • 例如：

      程序入口点（_start 或 main 函数的地址）。

      各个段（代码段 .text、数据段 .data、BSS段 .bss 等）在文件中的偏移量和在内存中的加载地址（虚拟地址）。

      动态链接信息（如果程序是动态链接的）。

      程序所需的内存大小和权限。

  3. 创建虚拟内存区域映射：

    • 加载器根据可执行文件头部的信息，在进程的虚拟地址空间中创建相应的内存区域映射。这些映射将虚拟地址范围与文件中的特定部分关联起来。
    • 例如，代码段会被映射为可读可执行（Read-Execute），数据段会被映射为可读可写（Read-Write）。
    • 注意：此时数据并没有真正从磁盘加载到物理内存中，只是建立了虚拟地址到文件内容的映射关系。 这是一种惰性加载（Lazy Loading）策略，利用了**按需分页（Demand Paging）**技术。

  4. 初始化栈和堆：

    • 为程序的**栈（Stack）**分配并映射内存区域，用于存储函数调用、局部变量等。栈通常从高地址向低地址增长。
    • 为程序的**堆（Heap）**分配并映射内存区域，用于动态内存分配（如 malloc、new）。堆通常从低地址向高地址增长。

  5. 处理动态链接（如果存在）：

    • 如果程序是动态链接的，加载器会调用动态链接器/加载器（Dynamic Linker/Loader）。
    • 动态链接器负责找到程序所需的共享库（.so 或 .dll 文件），将它们加载到进程的虚拟地址空间中，并进行必要的符号解析和地址重定位。这个过程可能涉及多次查找和映射。

  6. 设置程序入口点：

    加载器会将CPU的指令指针（Instruction Pointer，如x86上的EIP/RIP）设置为可执行文件头部指定的程序入口点地址（通常是C运行时库的 _start 函数，它会进一步调用 main 函数）。

  7. 启动执行：

    操作系统将控制权交给新进程，CPU开始从入口点执行指令。当程序访问到尚未加载到物理内存的虚拟地址时，会触发缺页中断（Page Fault），操作系统会捕获中断，将对应的页面从磁盘加载到物理内存中，并更新页表，然后程序继续执行。

9.2、示意图 ​

程序执行过程

10、可执行文件从磁盘加载到内存的详细过程是怎样的？ ​

可执行文件从磁盘加载到内存的过程，是操作系统虚拟内存管理和文件系统协同工作的体现。这个过程并非简单地将整个文件一次性读入内存，而是采用了**按需分页（Demand Paging）**的策略，以提高效率和减少内存占用。

10.1、核心概念 ​

  • 虚拟内存：操作系统为每个进程提供一个独立的、连续的虚拟地址空间。进程访问的是虚拟地址，由内存管理单元（MMU）将虚拟地址转换为物理地址。
  • 页（Page）/页框：虚拟内存和物理内存都被划分为固定大小的块，虚拟内存的块称为页，物理内存的块称为页框。它们通常大小相同（如4KB）。
  • 页表：每个进程都有一个页表，存储了虚拟页到物理页框的映射关系。页表项还包含访问权限（读/写/执行）和存在位（Present Bit），存在位指示对应的虚拟页是否已加载到物理内存。
  • 可执行文件格式（如ELF）：可执行文件内部被组织成多个段（Segment），如代码段（.text）、数据段（.data）、BSS段（.bss）等。这些段在文件中是连续的，但在内存中可能被映射到不连续的物理页框。

10.2、详细加载步骤 ​

  1. 创建进程和虚拟地址空间：

    • 当用户执行一个程序时（例如，在Shell中输入 ./a.out），操作系统会创建一个新的进程。这个新进程被分配一个独立的虚拟地址空间。
    • 此时，这个虚拟地址空间是空的，没有映射到任何物理内存。

  2. 解析可执行文件头部：

    • 操作系统的加载器（Loader）读取磁盘上可执行文件的头部信息（如ELF Header和Program Header Table）。
    • Program Header Table 描述了可执行文件的各个段（如代码段、数据段）应该如何加载到内存中：它们在文件中的偏移量、大小、在虚拟地址空间中的起始地址、内存权限（读、写、执行）等。

  3. 建立虚拟内存区域（VMA）：

    • 加载器根据Program Header Table中的信息，为进程的虚拟地址空间创建一系列的虚拟内存区域（Virtual Memory Area, VMA）。每个VMA对应文件中的一个可加载段。
    • 这些VMA描述了虚拟地址范围、访问权限以及它们与磁盘上可执行文件相应部分的映射关系。此时，物理内存中并没有实际加载数据，只是建立了映射关系，并将页表中的存在位标记为无效。

  4. 初始化栈和堆 VMA：

    • 除了文件映射的VMA，加载器还会为进程的栈和堆创建独立的VMA。栈通常是向下增长的，堆是向上增长的。
    • 这些区域最初也没有映射到物理内存。

  5. 设置程序入口点并移交控制权：

    • 加载器将CPU的指令指针（PC寄存器）设置为可执行文件指定的程序入口点（通常是C运行时库的 _start 函数）。
    • 然后，操作系统将CPU控制权移交给新创建的进程，程序开始执行。

  6. 按需分页（Demand Paging）和缺页中断（Page Fault）：

    • 当程序开始执行时，它会尝试访问代码段的指令或数据段的变量。由于这些虚拟地址对应的物理页尚未加载到内存中，MMU在进行虚拟地址到物理地址转换时会发现页表项中的存在位是无效的。
    • 这将触发一个缺页中断（Page Fault）。
    • 操作系统内核捕获到缺页中断后，会执行以下操作：
      1. 检查合法性：操作系统首先检查引起缺页的虚拟地址是否属于进程的某个合法VMA。如果不是，则说明是非法内存访问，会发送段错误（Segmentation Fault）信号给进程，导致进程终止。
      2. 查找空闲页框：如果地址合法，操作系统会在物理内存中找到一个空闲的页框。如果没有空闲页框，可能会触发页面置换算法（如LRU、FIFO等），将某个不常用的页从物理内存换出到交换空间（Swap Space）。
      3. 从磁盘加载数据：操作系统将可执行文件中对应虚拟页的数据（例如，代码段或数据段的一部分）从磁盘读取到新分配的物理页框中。
      4. 更新页表：更新进程的页表，将虚拟页映射到新的物理页框，并将页表项中的存在位标记为有效。
      5. 重新执行指令：缺页中断处理完成后，操作系统将控制权返回给进程，CPU重新执行导致缺页的指令。此时，该指令所需的页面已在物理内存中，可以正常执行。

  7. 动态链接库的加载：

    如果程序是动态链接的，在程序执行过程中，当第一次调用某个共享库中的函数时，可能会触发类似的缺页中断机制，由动态链接器将所需的共享库页面加载到内存中。

通过这种按需分页的机制，操作系统只将程序中实际需要的部分加载到物理内存中，而不是一次性加载整个程序，这大大提高了内存利用率，并允许运行比物理内存更大的程序。

10.3、详细加载过程示意图 ​

详细加载过程

11、Linux 创建进程使用了哪些系统调用？ ​

在Linux中，创建新进程主要涉及以下几个核心系统调用，它们通常组合使用以实现不同的进程创建和执行模式。

11.1、fork() ​

  • 功能：fork() 系统调用用于创建一个新进程，这个新进程是调用进程（父进程）的精确副本。

  • 原理：

    当 fork() 被调用时，操作系统会复制父进程的绝大部分资源，包括：

    • 父进程的虚拟地址空间（代码、数据、堆、栈），但通常采用**写时复制（Copy-On-Write, COW）**机制，即父子进程最初共享物理页面，只有当任一进程尝试修改这些页面时，才会进行实际的复制。

    • 文件描述符表（子进程继承父进程打开的所有文件描述符）。

    • 信号处理设置。

    • 当前工作目录。

    • fork() 调用会返回两次：在父进程中返回子进程的PID，在子进程中返回0。

  • 特点：创建的子进程与父进程几乎完全相同，只是PID不同，并且父子进程各自独立运行。

  • 使用场景：通常用于创建子进程来执行与父进程相同的任务，或者在子进程中通过 exec 系列函数加载并执行新的程序。

11.2、exec 系列函数 (execve, execl, execvp 等) ​

  • 功能：exec 系列系统调用用于在当前进程的上下文中加载并执行一个新的程序。它会替换当前进程的代码、数据和堆栈，但进程ID（PID）保持不变。
  • 原理：
    • exec 函数会读取指定的可执行文件，并将其代码、数据等加载到当前进程的虚拟地址空间。
    • 当前进程的内存映像被新程序的内存映像完全覆盖。
    • 文件描述符通常会保持不变（除非设置了 FD_CLOEXEC 标志）。
  • 特点：exec 成功后，原进程的代码将不再执行，新程序从其入口点开始执行。它不会创建新进程，而是“变身”为另一个程序。
  • 使用场景：通常与 fork() 结合使用。父进程 fork() 创建子进程，子进程随后调用 exec 来执行不同的程序，从而实现进程的创建和程序替换。

11.3、vfork() (已弃用或不推荐) ​

  • 功能：vfork() 也是用于创建子进程，但与 fork() 有所不同。
  • 原理：vfork() 创建的子进程与父进程共享地址空间，而不是写时复制。子进程在调用 exec 或 _exit 之前，会阻塞父进程的执行。
  • 特点：由于共享地址空间，vfork() 避免了 fork() 中的页表复制（即使是写时复制也需要复制页表），因此在某些情况下可能更快。但它非常危险，如果子进程在调用 exec 或 _exit 之前修改了共享内存（尤其是栈），可能会导致父进程崩溃。
  • 使用场景：在现代Linux系统中，由于 fork() 的写时复制优化已经非常高效，且 vfork() 存在安全隐患，通常不推荐使用 vfork()。它主要用于嵌入式系统或非常特定的性能敏感场景。

11.4、clone() ​

  • 功能：clone() 是Linux中创建进程（或线程）最底层、最灵活的系统调用。它允许调用者精确控制子进程与父进程共享哪些资源。
  • 原理：clone() 接受一系列标志（flags），这些标志决定了子进程与父进程共享哪些上下文（如内存空间、文件描述符、信号处理、命名空间等）。
  • 特点：
    • 当 clone() 的标志设置为共享所有资源时，它实际上可以创建线程（轻量级进程）。
    • 当 clone() 的标志设置为不共享任何资源时，它行为类似于 fork()。
  • 使用场景：clone() 是 fork() 和线程库（如 pthread）底层实现的基础。普通应用程序开发者通常不会直接使用 clone()，而是使用 fork() 或线程库。

11.5、进程创建的典型模式 ​

最常见的进程创建模式是 fork-exec 模式：

  1. 父进程调用 fork()：创建一个子进程。
  2. 子进程判断返回值：
    • 如果 fork() 返回0，说明是子进程。子进程会调用 exec 系列函数加载并执行新的程序。如果 exec 失败，子进程通常会调用 _exit() 退出。
    • 如果 fork() 返回子进程的PID，说明是父进程。父进程可以继续执行自己的任务，也可以调用 wait() 或 waitpid() 等待子进程结束。

示意图 ​

Fork() 和 Exec() 进程创建流程

13、进程之间有哪些通信方式？ ​

进程间通信（Inter-Process Communication, IPC）是指不同进程之间进行数据交换和同步的机制。由于进程拥有独立的虚拟地址空间，它们不能直接访问彼此的内存，因此需要操作系统提供的特定机制来协调和通信。Linux/Unix 系统提供了多种IPC方式，每种方式都有其特点和适用场景。

13.1、管道 ​

  • 原理：管道是半双工的，数据只能单向流动。它是一个内核缓冲区，进程通过读写文件描述符来访问。管道分为匿名管道和命名管道。

    匿名管道 (Anonymous Pipe)：

    • 特点：只能用于具有亲缘关系的进程（如父子进程）。生命周期随进程。通常通过 pipe() 系统调用创建。
    • 使用场景：父子进程之间传递数据。

    命名管道 (Named Pipe / FIFO)：

    • 特点：可以在文件系统中创建一个特殊的文件（FIFO文件），允许不相关的进程通过文件路径进行通信。生命周期独立于进程，直到被删除。通过 mkfifo() 系统调用创建。
    • 使用场景：不相关的进程之间传递数据，例如Shell中的 | 命令。

  • 优点：简单易用，适用于单向数据流。

  • 缺点：半双工，数据量有限，匿名管道限制亲缘进程。

13.2、消息队列 ​

  • 原理：消息队列是存放在内核中的消息链表。进程可以向消息队列中添加消息，也可以从消息队列中读取消息。每条消息都有一个类型，可以实现消息的随机读取。
  • 特点：消息具有格式，可以克服管道无格式字节流的缺点。消息队列的生命周期独立于发送和接收进程，即使发送进程终止，消息仍然保留在队列中。
  • 优点：解耦发送方和接收方，消息持久化，支持消息优先级和随机读取。
  • 缺点：每次读写都需要进行用户态和内核态的切换，以及数据拷贝，效率相对较低。
  • 使用场景：客户端-服务器模型中，需要异步通信和消息缓冲的场景。

13.3、共享内存 ​

  • 原理：共享内存是效率最高的IPC方式。它允许不同进程直接访问同一块物理内存区域。操作系统将一块物理内存映射到多个进程的虚拟地址空间中，进程可以直接读写这块内存，无需通过内核。
  • 特点：一旦映射完成，数据交换不再需要系统调用，也不需要数据拷贝，直接在内存中操作。
  • 优点：速度快，效率高。
  • 缺点：不提供任何同步机制，需要配合信号量或互斥锁等其他IPC机制来保证数据一致性。
  • 使用场景：大数据量传输，高性能要求高的场景。

13.4、信号量 ​

  • 原理：信号量是一个计数器，用于控制多个进程对共享资源的访问。它主要用于进程间的同步，而不是数据传输。
    • P (wait) 操作：信号量值减1，如果值为负，则阻塞。
    • V (signal) 操作：信号量值加1，如果值为非负，则唤醒一个等待进程。
  • 特点：可以用于实现互斥（二值信号量）或控制并发进程的数量（计数信号量）。
  • 优点：灵活，可以用于多种同步场景。
  • 缺点：只能用于同步，不能传输数据。
  • 使用场景：控制对共享资源的访问，如共享内存的同步访问。

13.5、信号 ​

  • 原理：信号是一种异步通知机制，用于通知进程发生了某种事件。它类似于硬件中断，但发生在软件层面。
  • 特点：信号没有数据传输能力，只能传递少量信息（信号类型）。进程可以捕获、忽略或默认处理信号。
  • 优点：简单，适用于异步事件通知。
  • 缺点：只能传递少量信息，不可靠（信号可能丢失或合并）。
  • 使用场景：进程终止、键盘中断、定时器到期等事件通知。

13.6、套接字 ​

  • 原理：套接字是一种更通用的通信机制，可以用于同一台机器上的进程间通信（IPC），也可以用于网络上不同机器间的进程通信。它支持TCP/UDP等多种协议。
  • 特点：全双工通信，可以传输大量数据，支持多种通信模式（流式、数据报式）。
  • 优点：通用性强，支持网络通信，接口标准化。
  • 缺点：相对复杂，需要进行网络协议栈的处理，效率不如共享内存。
  • 使用场景：网络服务（Web服务器、数据库）、分布式系统、本地进程间复杂通信。

13.7、文件锁 ​

  • 原理：通过对文件进行加锁，来协调多个进程对同一个文件的访问。可以实现读共享、写独占。
  • 特点：基于文件系统，简单易用。
  • 优点：实现简单，适用于文件资源的同步。
  • 缺点：只能对文件进行同步，不能用于其他共享资源。
  • 使用场景：多个进程并发读写同一个文件。

14、malloc 的底层实现原理是什么？ ​

malloc 是C标准库中用于动态内存分配的函数。它从堆（Heap）中分配指定大小的内存块。malloc 的底层实现是一个复杂的过程，它通常依赖于操作系统提供的内存管理系统调用，并在用户态维护一个高效的内存分配器。这里主要介绍其在Linux系统下的典型实现。

14.1、操作系统层面的内存分配 ​

malloc 最终需要向操作系统请求内存。在Linux中，主要有两种系统调用用于分配内存：

  1. brk() / sbrk()：

    • 原理：brk() 和 sbrk() 系统调用用于调整进程**数据段（data segment）**的结束位置，即堆的顶部（或称为“program break”）。brk() 将 program break 设置为指定地址，sbrk() 增加或减少 program break 的大小。
    • 特点：这种方式分配的内存是连续的，并且位于进程的堆区。当分配小块内存时，malloc 通常会优先使用 brk()/sbrk() 来扩展堆。
    • 缺点：只能在堆的末尾进行扩展或收缩，无法方便地释放堆中间的内存块。

  2. mmap() / munmap()：

    • 原理：mmap() 系统调用用于在进程的虚拟地址空间中映射文件或匿名内存区域。当 malloc 请求分配较大块内存时，它会直接使用 mmap(NULL, size, PROT_READ|PROT_WRITE, MAP_PRIVATE|MAP_ANONYMOUS, -1, 0) 来分配一块匿名的、私有的、可读写的内存区域。
    • 特点：mmap() 分配的内存是页对齐的，并且可以独立于堆进行管理。munmap() 可以精确地释放通过 mmap() 分配的内存块，即使这些块位于虚拟地址空间的中间。
    • 缺点：每次 mmap() 调用都会产生系统调用开销，且分配的内存大小是页的整数倍，可能存在内部碎片。

14.2、用户态的内存分配器 ​

直接使用 brk() 或 mmap() 进行每次内存分配和释放的效率非常低，因为系统调用开销大。因此，malloc 的核心在于其用户态的内存分配器（如 glibc 中的 ptmalloc，或 jemalloc, tcmalloc 等）。

用户态内存分配器的工作原理是：

  1. 预先向操作系统申请大块内存：当程序第一次调用 malloc 或请求的内存块较大时，malloc 会通过 brk() 或 mmap() 向操作系统申请一大块内存（例如，几MB）。
  2. 在用户态管理这些大块内存：分配器将这些从操作系统获得的内存块划分为更小的、可管理的单元（称为chunk或arena），并维护一个复杂的内部数据结构（如空闲链表、bin、tree等）来管理这些空闲和已分配的内存块。
  3. 满足用户请求：当用户再次调用 malloc 请求小块内存时，分配器会优先从其内部管理的空闲内存块中查找合适的块返回给用户，而不需要每次都进行系统调用。
  4. 内存回收和合并：当用户调用 free 释放内存时，分配器不会立即将内存归还给操作系统，而是将其标记为空闲，并尝试与相邻的空闲块合并，形成更大的空闲块，以便后续的 malloc 请求可以重用。只有当空闲块非常大，并且位于堆的顶部或可以通过 munmap 释放时，分配器才会考虑将其归还给操作系统。

14.3、ptmalloc (glibc 默认分配器) 的一些机制 ​

ptmalloc 是 glibc 库中 malloc 的默认实现，它非常复杂且高效，主要包含以下机制：

  • Arena (内存池)：ptmalloc 支持多线程，每个线程可以有自己的主 arena 或非主 arena。这减少了多线程下的锁竞争。
  • Bins (空闲链表)：ptmalloc 将空闲内存块（chunk）组织成不同大小的链表（bins）。
    • Fast Bins：用于非常小的、经常被分配和释放的内存块。
    • Small Bins：用于小块内存。
    • Large Bins：用于大块内存。
    • Unsorted Bin：当内存块被释放时，首先进入这个bin，然后根据大小重新分配到其他bin。
  • Top Chunk：堆的顶部未分配内存块，当没有合适的空闲块时，会从Top Chunk中分割，如果Top Chunk不足，则通过 sbrk() 扩展堆。
  • mmap 阈值：ptmalloc 有一个阈值（通常是128KB）。当请求的内存大小超过这个阈值时，malloc 会直接使用 mmap() 系统调用来分配内存，而不是通过 brk() 扩展堆。这是因为大块内存通过 mmap() 分配可以更容易地被 munmap() 释放，避免堆碎片化。

14.4、malloc 底层原理示意图 ​

malloc底层原理

15、用户态是如何管理堆内存的？（堆的实现机制） ​

用户态的堆内存管理主要是由C/C++运行时库中的内存分配器（如 glibc 的 ptmalloc、jemalloc、tcmalloc 等）实现的。

这些分配器在操作系统提供的基本内存分配机制（如 brk() 和 mmap()）之上，构建了一套高效、复杂的内存管理系统。其核心目标是减少系统调用次数、提高分配速度、减少内存碎片。

15.1、核心思想 ​

  1. 大块申请，小块管理：分配器不会每次用户请求都向操作系统申请内存。它会一次性向操作系统申请一大块内存（通常是多个页），然后在用户态将这块大内存划分为小块，供用户程序使用。
  2. 空闲链表/数据结构：分配器维护一个或多个数据结构来跟踪和管理所有空闲的内存块。当用户请求内存时，分配器会从这些空闲块中选择一个合适的，并将其标记为已使用。当用户释放内存时，分配器会将其标记为空闲，并尝试与相邻的空闲块合并。
  3. 减少碎片：通过合并空闲块、使用不同大小的空闲链表等策略，尽量减少内存碎片（外部碎片和内部碎片）。

15.2、常见的堆管理机制 ​

以 glibc 的 ptmalloc 为例，其堆管理机制主要包括：

  1. Arena (内存区)：

    • ptmalloc 引入了 Arena 的概念，即内存池。每个进程可以有一个主 Arena，也可以有多个非主 Arena。在多线程环境中，为了减少锁竞争，每个线程可以尝试使用自己的非主 Arena。如果线程没有自己的 Arena 或其 Arena 已满，则会尝试使用其他 Arena。
    • Arena 内部管理着从操作系统获得的内存块，通常通过 brk() 或 mmap() 获得。

  2. Chunk (内存块)：

    • Arena 中的内存被划分为一个个 chunk。每个 chunk 包含用户数据区和分配器维护的一些元数据（如大小、是否空闲等）。
    • 当用户请求内存时，分配器会返回一个 chunk 的用户数据区地址。

  3. Bins (空闲链表)：

    • 为了快速查找合适大小的空闲 chunk，ptmalloc 将空闲 chunk 组织成不同类型的链表，称为 Bins。
    • Fast Bins：用于管理非常小的 chunk。这些 chunk 被释放后，不会立即合并，而是放入 Fast Bins。再次请求相同大小的内存时，可以直接从 Fast Bins 中快速取出，减少合并和分割的开销。
    • Small Bins：用于管理小尺寸的 chunk。这些 bin 中的 chunk 都是相同大小的。当 chunk 释放时，会尝试与相邻的空闲 chunk 合并，然后放入对应的 Small Bin。
    • Large Bins：用于管理大尺寸的 chunk。这些 bin 中的 chunk 大小不一，通常按大小排序，以方便查找最合适的 chunk。
    • Unsorted Bin：所有被释放的 chunk 都会先进入 Unsorted Bin。当需要分配内存时，分配器会首先检查 Unsorted Bin，并将其中的 chunk 移动到对应的 Fast, Small 或 Large Bin 中。

  4. Top Chunk：

    • 每个 Arena 都有一个 Top Chunk，它是 Arena 中最高地址处未使用的连续内存块。当所有 Bins 中都没有合适的空闲 chunk 时，分配器会尝试从 Top Chunk 中分割出所需大小的内存。
    • 如果 Top Chunk 也不足，ptmalloc 就会通过 brk() 系统调用来扩展堆，将新获得的内存添加到 Top Chunk 中。

  5. mmap 分配大内存：

    对于非常大的内存请求（通常大于128KB），ptmalloc 会直接使用 mmap() 系统调用向操作系统申请内存，而不是通过 brk() 扩展堆。这是因为 mmap() 分配的内存可以独立于堆的其余部分进行 munmap() 释放，避免了大块内存释放时造成的堆碎片化问题。

16、TCP 拥塞控制的流程与核心机制是什么？ ​

TCP（Transmission Control Protocol）的拥塞控制是其核心机制之一，旨在防止过多的数据注入到网络中，从而避免网络中的路由器或链路过载，导致数据包丢失、延迟增加，甚至网络崩溃。

拥塞控制通过动态调整发送方的发送速率来实现，主要包括以下四种核心算法：慢启动（Slow Start）、拥塞避免（Congestion Avoidance）、快速重传（Fast Retransmit）和快速恢复（Fast Recovery）。

TCP拥塞控制引入了一个重要的状态变量：拥塞窗口（Congestion Window, cwnd）。发送方实际能够发送的数据量是拥塞窗口和接收方通告的接收窗口（rwnd，流量控制）中的较小值。即 min(cwnd, rwnd)。

16.1、核心机制 ​

  1. 拥塞窗口 (cwnd)：

    发送方维护的一个状态变量，表示在不引起网络拥塞的情况下，发送方可以向网络中发送的最大未确认数据量。cwnd 的大小动态变化，是拥塞控制算法的核心。

  2. 慢启动阈值 (ssthresh)：

    一个阈值，用于区分慢启动阶段和拥塞避免阶段。当 cwnd 小于 ssthresh 时，进入慢启动；当 cwnd 大于或等于 ssthresh 时，进入拥塞避免。

16.2、拥塞控制的四个阶段/算法 ​

1. 慢启动 ​
  • 目的：在TCP连接建立之初，探测网络的承载能力，避免一开始就向网络注入大量数据导致拥塞。
  • 流程：
    1. 连接建立后，cwnd 初始化为一个较小的值（通常是1或2个MSS，最大报文段长度）。
    2. 每当发送方收到一个确认（ACK），cwnd 就指数级增长。具体来说，每收到一个ACK，cwnd 增加1个MSS。这意味着每经过一个RTT（往返时间），cwnd 就会翻倍。
    3. 当 cwnd 达到 ssthresh 时，慢启动阶段结束，进入拥塞避免阶段。
2. 拥塞避免 ​
  • 目的：在网络承载能力范围内，逐步增加发送速率，避免再次引起拥塞。
  • 流程：

    1. 当 cwnd 达到 ssthresh 后，cwnd 的增长方式变为线性增长（加性增，Additive Increase）。

    2. 每经过一个RTT，cwnd 增加1个MSS（或者说，每收到一个ACK，cwnd 增加 MSS*MSS/cwnd，当 cwnd 较大时，这近似于每RTT增加1个MSS）。

    3. 拥塞判断：如果在拥塞避免阶段发生丢包，TCP会认为网络发生了拥塞，并采取相应的措施：

      超时重传：如果发送方等待ACK超时，这通常意味着网络发生了严重的拥塞。此时，ssthresh 会被设置为当前 cwnd 的一半，cwnd 重新设置为1个MSS，然后再次进入慢启动阶段（乘性减，Multiplicative Decrease）。

      快速重传：如果发送方收到三个重复的ACK，这表明网络中可能只是少量丢包（通常是单个报文段丢失），而不是严重的拥塞。此时，ssthresh 会被设置为当前 cwnd 的一半，cwnd 设置为 ssthresh + 3 * MSS，然后进入快速恢复阶段。

3. 快速重传 ​
  • 目的：在不等待重传定时器超时的情况下，尽快重传丢失的报文段，提高传输效率。
  • 流程：
    1. 发送方发送数据包1、2、3、4、5。
    2. 接收方收到1、2、4、5，但3丢失。
    3. 接收方为1、2发送ACK，当收到4时，由于期望的是3，所以再次发送对2的ACK（重复ACK）。当收到5时，再次发送对2的ACK（第三个重复ACK）。
    4. 发送方收到三个重复的ACK（对2的ACK），立即判断报文段3可能丢失，不等定时器超时就重传报文段3。
  • 触发条件：收到3个重复ACK。
4. 快速恢复 ​
  • 目的：在快速重传后，避免 cwnd 骤降（像超时重传那样降到1），从而保持较高的传输速率，因为三个重复ACK表明网络并非严重拥塞。
  • 流程：
    1. 进入快速恢复阶段时，ssthresh 被设置为当前 cwnd 的一半。
    2. cwnd 被设置为 ssthresh + 3 * MSS（这3个MSS代表了已经离开网络但尚未被确认的重复ACK所携带的数据）。
    3. 每收到一个重复ACK，cwnd 增加1个MSS（模拟数据包已经离开网络）。
    4. 当收到对重传报文段的ACK时（表示丢失的报文段已成功到达），cwnd 被设置为 ssthresh，然后进入拥塞避免阶段。

16.3、拥塞控制流程图 ​

拥塞控制流程图

17、TCP 在三次重传后，窗口阈值应该设为多少？为什么？ ​

这里的问题“三次重传后”可能存在歧义，通常TCP的拥塞控制中，我们谈论的是收到三次重复ACK后（触发快速重传/快速恢复）和重传定时器超时后（触发慢启动）。这两种情况对拥塞窗口阈值（ssthresh）的设置是不同的。

17.1、收到三次重复ACK后 (ssthresh 的设置) ​

当TCP发送方收到三个重复的ACK时，这表明网络中可能只丢失了少数报文段，而不是发生了严重的网络拥塞。在这种情况下，TCP会触发快速重传和快速恢复算法。

  • ssthresh 的设置：ssthresh 会被设置为当前拥塞窗口 cwnd 的一半。

    ssthresh = cwnd / 2

  • cwnd 的设置：cwnd 会被设置为 ssthresh + 3 * MSS。

  • 为什么：

    • 将 ssthresh 减半是为了对网络拥塞做出适度的反应，但又不至于过于激进地降低发送速率。
    • 将 cwnd 设置为 ssthresh + 3 * MSS 是因为收到了三个重复ACK，这表示有三个数据包已经离开了网络（因为接收方收到了后续数据才发送重复ACK），所以 cwnd 可以适当增大，而不是直接降到 ssthresh。这有助于在网络状况不是特别糟糕时，维持较高的传输效率。
    • 之后进入快速恢复阶段。

17.2、重传定时器超时后 (ssthresh 的设置) ​

当TCP发送方等待一个报文段的ACK超时，这通常被认为是网络发生了严重拥塞的信号，因为数据包可能在网络中丢失或延迟严重。在这种情况下，TCP会采取更保守的策略。

  • ssthresh 的设置：ssthresh 会被设置为当前拥塞窗口 cwnd 的一半。

    ssthresh = cwnd / 2

  • cwnd 的设置：cwnd 会被重置为1个MSS。

  • 为什么：

    • 超时被认为是更严重的拥塞事件，因此需要更大幅度地降低发送速率。将 cwnd 降到1个MSS，并重新进入慢启动阶段，是为了从头开始探测网络的承载能力，以避免进一步加剧拥塞。
    • ssthresh 仍然设置为 cwnd 的一半，作为下一次进入拥塞避免阶段的阈值。

总结 ​

情况拥塞窗口 cwnd 变化慢启动阈值 ssthresh 变化后续阶段
三次重复ACKcwnd = ssthresh + 3 * MSSssthresh = cwnd / 2 (拥塞发生时的 cwnd)快速恢复
超时重传cwnd = 1 * MSSssthresh = cwnd / 2 (拥塞发生时的 cwnd)慢启动

TCP拥塞控制的目标是在网络拥塞时降低发送速率，在网络空闲时增加发送速率。

当发生拥塞时，将 ssthresh 减半是一种通用的惩罚机制，表示网络承载能力下降。

而 cwnd 的具体调整则根据拥塞的严重程度（通过超时或重复ACK判断）来决定，以在可靠性和效率之间取得平衡。

18、为什么 TCP 拥塞控制的阈值要设为当前窗口大小的一半？ ​

TCP 拥塞控制中，当检测到网络拥塞时（无论是通过超时还是收到三个重复ACK），慢启动阈值 ssthresh 通常会被设置为当前拥塞窗口 cwnd 的一半。

这个“减半”策略是一个经验性的设计选择，旨在在网络拥塞后，既能快速降低发送速率以缓解拥塞，又能避免过于保守导致网络带宽利用率不足。

18.1、核心原因 ​

  1. 快速缓解拥塞：

    • 当网络发生拥塞时，表明当前发送方的数据注入速率超过了网络的承载能力。将 ssthresh 减半，意味着发送方将立即进入一个更保守的发送模式。
    • 如果拥塞非常严重（如超时），cwnd 会直接降到1个MSS，强制进入慢启动，从头开始探测网络。
    • 如果拥塞不是特别严重（如收到重复ACK），cwnd 会降到 ssthresh + 3*MSS，然后进入快速恢复，但整体发送速率仍然大幅下降。
    • 这种减半策略能够迅速减少网络中的数据量，从而缓解拥塞，防止情况恶化。

  2. 避免过于保守，保持一定利用率：

    • 如果将 ssthresh 降得太低（例如，直接降到1个MSS），每次拥塞都会导致发送速率大幅下降，使得网络需要很长时间才能重新达到高利用率，这会降低整体吞吐量。
    • 减半策略是一种折衷方案。它假设当前 cwnd 接近网络的实际承载能力，或者至少是网络发生拥塞时的最大承载能力。因此，将 ssthresh 设为 cwnd 的一半，意味着新的“安全”发送速率应该在这个值附近，使得TCP能够再次以较快的速度（慢启动）探测到这个新的 ssthresh，然后进入线性增长的拥塞避免阶段，逐步提高发送速率，最终再次达到网络的承载能力。

  3. 公平性：

    这种减半策略也有助于实现TCP连接之间的公平性。当多个TCP流共享同一个拥塞链路时，如果它们都采用类似的减半策略，那么在拥塞发生后，它们都有机会重新争夺带宽，而不是某个流一直霸占带宽。

  4. 历史经验和实践验证：

    TCP拥塞控制算法（特别是TCP Reno和Tahoe）是经过长期实践和理论研究演化而来的。将 ssthresh 减半，cwnd 线性增长（AIMD: Additive Increase, Multiplicative Decrease）被证明是一种有效且相对公平的拥塞控制策略。

当拥塞发生时，cwnd 减半是为了快速响应拥塞，而 ssthresh 减半则为下一次探测网络容量设定了一个新的、更保守的起点。这个机制使得TCP能够在网络带宽和延迟之间找到一个动态平衡，既能充分利用网络资源，又能避免网络崩溃。

19、手撕算法题：求一棵树的最长直径 ​

19.1、问题描述 ​

给定一棵无向树，求其最长直径（Longest Diameter）。树的直径定义为树中任意两个节点之间最长路径的长度。

示意图：

树的直径

19.2 解题思路 ​

求解树的直径有两种常用的方法：

方法一：两次深度优先搜索（DFS）或广度优先搜索（BFS） ​

这是最经典且高效的方法。

  1. 第一次搜索：从树中任意一个节点（例如节点A）开始，进行一次DFS或BFS，找到距离节点A最远的节点，记为节点P。
  2. 第二次搜索：从节点P开始，再进行一次DFS或BFS，找到距离节点P最远的节点，记为节点Q。节点P到节点Q的路径长度就是树的直径。

为什么这个方法是正确的？

  • 证明：设树的直径的两个端点是 U 和 V。从任意节点 A 开始进行第一次搜索，找到距离 A 最远的节点 P。可以证明，P 必然是 U 和 V 中的一个（或者说，P 必然是直径的一个端点）。
    • 情况1：如果 A 位于直径 U-V 上，那么 P 必然是 U 或 V 中距离 A 更远的那一个。
    • 情况2：如果 A 不在直径 U-V 上，那么从 A 到 U-V 路径上最近的点 X，再到 U 或 V。P 仍然是 U 或 V 中距离 A 更远的那一个。如果 P 不是 U 或 V，那么就会存在一条比 U-V 更长的路径，与直径的定义矛盾。
  • 因此，从 P 开始的第二次搜索，找到的最远节点 Q，必然是直径的另一个端点，P 到 Q 的路径长度即为直径。
方法二：动态规划（DFS） ​

对于树中的每个节点，计算以该节点为根的子树中，从该节点出发的最长路径和次长路径。树的直径就是所有节点的最长路径和次长路径之和的最大值。

  1. 定义 dp[u]：表示从节点 u 出发，向下（远离父节点）的最长路径长度。这个路径可以是 u 到其某个叶子节点的路径。
  2. DFS 遍历：从任意节点开始DFS。对于当前节点 u：
    • 递归计算其所有子节点 v 的 dp[v]。
    • dp[u] 等于 max(dp[v] + edge_weight(u,v))，其中 v 是 u 的子节点。
    • 在计算 dp[u] 的过程中，可以同时计算以 u 为“拐点”的直径。即找到 u 的两个子节点 v1, v2，使得 dp[v1] + edge_weight(u,v1) 和 dp[v2] + edge_weight(u,v2) 分别是最大和次大值。那么以 u 为拐点的直径就是这两者之和。
    • 全局维护一个最大直径 max_diameter。

方法一通常更直观和易于实现。

这里我们主要以方法一为例进行手撕。

19.3 算法实现 (C++) ​

我们将使用邻接表来表示树，并使用BFS进行两次搜索。

cpp
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>

// 结构体表示图的边
struct Edge {
    int to;       // 边的终点
    int weight;   // 边的权重
};

// 第一次BFS/DFS，从起点start_node找到最远的节点及其距离
std::pair<int, int> bfs(int start_node, int num_nodes, const std::vector<std::vector<Edge>>& adj) {
    std::vector<int> dist(num_nodes + 1, -1); // 存储距离，-1表示不可达
    std::queue<int> q;

    q.push(start_node);
    dist[start_node] = 0;

    int farthest_node = start_node;
    int max_dist = 0;

    while (!q.empty()) {
        int u = q.front();
        q.pop();

        // 更新最远节点和最大距离
        if (dist[u] > max_dist) {
            max_dist = dist[u];
            farthest_node = u;
        }

        for (const auto& edge : adj[u]) {
            int v = edge.to;
            int w = edge.weight;
            if (dist[v] == -1) { // 如果v未被访问
                dist[v] = dist[u] + w;
                q.push(v);
            }
        }
    }
    return {farthest_node, max_dist};
}

// 求树的直径
int get_tree_diameter(int num_nodes, const std::vector<std::vector<Edge>>& adj) {
    if (num_nodes == 0) return 0;
    if (num_nodes == 1) return 0; // 单个节点，直径为0

    // 1. 从任意节点（这里选择节点1）开始，找到距离它最远的节点P
    std::pair<int, int> result1 = bfs(1, num_nodes, adj);
    int node_p = result1.first;

    // 2. 从节点P开始，找到距离它最远的节点Q及其距离
    std::pair<int, int> result2 = bfs(node_p, num_nodes, adj);
    int diameter = result2.second;

    return diameter;
}

int main() {
    // 示例树结构：
    // 1 --(1)-- 2 --(2)-- 3 --(3)-- 4
    //         |           |
    //         (4)         (5)
    //         |           |
    //         5           6
    // 最长路径可能是 5-2-3-4 (4+2+3=9) 或 5-2-3-6 (4+2+5=11)
    // 节点数量
    int num_nodes = 6;
    // 邻接表表示图 (节点从1开始编号)
    std::vector<std::vector<Edge>> adj(num_nodes + 1);

    // 添加边
    adj[1].push_back({2, 1});
    adj[2].push_back({1, 1});

    adj[2].push_back({3, 2});
    adj[3].push_back({2, 2});

    adj[3].push_back({4, 3});
    adj[4].push_back({3, 3});

    adj[2].push_back({5, 4});
    adj[5].push_back({2, 4});

    adj[3].push_back({6, 5});
    adj[6].push_back({3, 5});

    int diameter = get_tree_diameter(num_nodes, adj);
    std::cout << "树的最长直径是: " << diameter << "\n"; // 预期输出 11 (路径 5-2-3-6)

    // 另一个例子：一条链
    // 1 --(1)-- 2 --(1)-- 3 --(1)-- 4
    num_nodes = 4;
    std::vector<std::vector<Edge>> adj2(num_nodes + 1);
    adj2[1].push_back({2, 1}); adj2[2].push_back({1, 1});
    adj2[2].push_back({3, 1}); adj2[3].push_back({2, 1});
    adj2[3].push_back({4, 1}); adj2[4].push_back({3, 1});
    diameter = get_tree_diameter(num_nodes, adj2);
    std::cout << "链的最长直径是: " << diameter << "\n"; // 预期输出 3

    return 0;
}

输出：

输出

19.4、算法复杂度 ​

  • 时间复杂度：两次BFS（或DFS）遍历。对于邻接表表示的图，BFS/DFS的时间复杂度是 O(V + E)，其中 V 是节点数，E 是边数。由于树的边数 E = V - 1，所以总时间复杂度为 O(V)。
  • 空间复杂度：O(V + E) 用于存储邻接表和距离数组，即 O(V)。