C++ 手写

手写 shared_ptr 简化版

核心解释

简化版 shared_ptr 的核心是：多个智能指针可以共享同一个对象，内部用“引用计数”记录有多少个 shared_ptr 正在拥有它。拷贝时计数加一，析构时计数减一，减到 0 才真正 delete 对象。

C++ 简化实现

#include <iostream> // 引入输入输出库，方便测试输出。
template <typename T> // 定义模板，让智能指针可以管理任意类型。
class MySharedPtr // 定义一个简化版 shared_ptr 类。
{ // MySharedPtr 类开始。
private: // 私有成员开始。
    struct ControlBlock // 定义控制块，用来保存引用计数。
    { // ControlBlock 结构开始。
        int refCount; // 保存当前有多少个 MySharedPtr 共享同一个对象。
        explicit ControlBlock(int count) : refCount(count) {} // 初始化引用计数。
    }; // ControlBlock 结构结束。
    T* _ptr; // 保存真正被管理的对象指针。
    ControlBlock* _block; // 保存控制块指针。
    void addRef() // 增加引用计数。
    { // addRef 方法开始。
        if (_block != nullptr) // 如果控制块存在。
        { // if 代码块开始。
            ++_block->refCount; // 引用计数加一。
        } // if 代码块结束。
    } // addRef 方法结束。
    void release() // 释放当前持有的引用。
    { // release 方法开始。
        if (_block == nullptr) // 如果没有控制块。
        { // if 代码块开始。
            return; // 直接返回。
        } // if 代码块结束。
        --_block->refCount; // 引用计数减一。
        if (_block->refCount == 0) // 如果已经没有任何智能指针拥有对象。
        { // if 代码块开始。
            delete _ptr; // 释放真正的对象。
            delete _block; // 释放控制块。
        } // if 代码块结束。
        _ptr = nullptr; // 把对象指针置空，避免悬空。
        _block = nullptr; // 把控制块指针置空，避免悬空。
    } // release 方法结束。
public: // 公有成员开始。
    MySharedPtr() : _ptr(nullptr), _block(nullptr) {} // 默认构造一个空智能指针。
    explicit MySharedPtr(T* ptr) : _ptr(ptr), _block(ptr == nullptr ? nullptr : new ControlBlock(1)) {} // 接管裸指针，并创建引用计数为 1 的控制块。
    MySharedPtr(const MySharedPtr& other) : _ptr(other._ptr), _block(other._block) // 拷贝构造，共享同一个对象和控制块。
    { // 拷贝构造函数开始。
        addRef(); // 拷贝后引用计数加一。
    } // 拷贝构造函数结束。
    MySharedPtr& operator=(const MySharedPtr& other) // 拷贝赋值运算符。
    { // 拷贝赋值函数开始。
        if (this == &other) // 如果是自己给自己赋值。
        { // if 代码块开始。
            return *this; // 直接返回当前对象。
        } // if 代码块结束。
        release(); // 先释放自己原来持有的资源。
        _ptr = other._ptr; // 复制对方管理的对象指针。
        _block = other._block; // 复制对方的控制块指针。
        addRef(); // 新资源的引用计数加一。
        return *this; // 返回当前对象，支持连续赋值。
    } // 拷贝赋值函数结束。
    ~MySharedPtr() // 析构函数。
    { // 析构函数开始。
        release(); // 对引用计数减一，必要时释放对象。
    } // 析构函数结束。
    T& operator*() const // 重载解引用运算符。
    { // operator* 方法开始。
        return *_ptr; // 返回被管理对象的引用。
    } // operator* 方法结束。
    T* operator->() const // 重载箭头运算符。
    { // operator-> 方法开始。
        return _ptr; // 返回被管理对象的指针。
    } // operator-> 方法结束。
    T* get() const // 获取内部裸指针。
    { // get 方法开始。
        return _ptr; // 返回对象指针。
    } // get 方法结束。
    int use_count() const // 获取当前引用计数。
    { // use_count 方法开始。
        return _block == nullptr ? 0 : _block->refCount; // 没有控制块返回 0，否则返回引用计数。
    } // use_count 方法结束。
    void reset(T* ptr = nullptr) // 重置当前智能指针管理的新对象。
    { // reset 方法开始。
        if (_ptr == ptr) // 如果新指针和当前指针相同。
        { // if 代码块开始。
            return; // 直接返回，避免重复释放。
        } // if 代码块结束。
        release(); // 释放旧资源引用。
        _ptr = ptr; // 保存新的对象指针。
        _block = ptr == nullptr ? nullptr : new ControlBlock(1); // 如果新指针不为空，就创建新的控制块。
    } // reset 方法结束。
}; // MySharedPtr 类结束。

面试高分回答

TIP

shared_ptr 不是简单保存一个裸指针，它还需要一个控制块。控制块里至少有强引用计数。每次拷贝 shared_ptr，多个智能指针共享同一个对象和同一个控制块，引用计数加一；每个 shared_ptr 析构或 reset 时引用计数减一；只有当引用计数减到 0，才释放真正的对象。

注意点

这个是教学版，不是标准库完整实现。真正的 std::shared_ptr 还会处理线程安全计数、weak_ptr 弱引用计数、自定义删除器、别名构造、make_shared 控制块和对象一起分配等问题。

一句话记忆

shared_ptr = 裸指针 + 控制块；拷贝加计数，析构减计数，计数归零才释放对象。

手写字符串类，包含拷贝构造和赋值

核心解释

手写字符串类的重点不是“能保存字符”，而是自己管理堆内存。只要类里有 char*，就必须注意：析构释放内存、拷贝构造做深拷贝、赋值运算符处理自赋值和旧资源释放。

C++ 代码

#include <cstring> // 引入 strlen 和 memcpy。
#include <cstddef> // 引入 std::size_t。

class MyString // 定义一个简化版字符串类。
{ // 类开始。
private: // 私有成员开始。
    char* _data; // 保存堆上字符数组的首地址。
    std::size_t _size; // 保存字符串长度，不包含 '\0'。

    static char* AllocateAndCopy(const char* source, std::size_t length) // 封装申请内存和拷贝字符串的逻辑。
    { // AllocateAndCopy 方法开始。
        char* buffer = new char[length + 1]; // 申请 length + 1 个字符，多出来的 1 个放 '\0'。
        std::memcpy(buffer, source, length); // 拷贝字符串正文内容。
        buffer[length] = '\0'; // 手动补上字符串结束符。
        return buffer; // 返回新申请的字符数组。
    } // AllocateAndCopy 方法结束。

public: // 公有成员开始。
    MyString() // 默认构造函数。
        : _data(AllocateAndCopy("", 0)) // 默认创建一个空字符串。
        , _size(0) // 默认字符串长度是 0。
    { // 默认构造函数开始。
    } // 默认构造函数结束。

    explicit MyString(const char* text) // 通过 C 风格字符串构造 MyString。
    { // 构造函数开始。
        if (text == nullptr) // 如果传入的是空指针。
        { // if 代码块开始。
            text = ""; // 把空指针当成空字符串处理。
        } // if 代码块结束。
        _size = std::strlen(text); // 计算字符串长度。
        _data = AllocateAndCopy(text, _size); // 申请新内存并复制字符串内容。
    } // 构造函数结束。

    MyString(const MyString& other) // 拷贝构造函数，用已有对象创建新对象。
        : _data(AllocateAndCopy(other._data, other._size)) // 为新对象申请独立内存并复制内容。
        , _size(other._size) // 复制字符串长度。
    { // 拷贝构造函数开始。
    } // 拷贝构造函数结束。

    MyString& operator=(const MyString& other) // 拷贝赋值运算符，用已有对象给已有对象赋值。
    { // 赋值运算符开始。
        if (this == &other) // 判断是否自己给自己赋值。
        { // if 代码块开始。
            return *this; // 自赋值时直接返回自己。
        } // if 代码块结束。
        char* newData = AllocateAndCopy(other._data, other._size); // 先申请新内存并复制对方内容。
        delete[] _data; // 释放当前对象原来的旧内存。
        _data = newData; // 让当前对象指向新的字符串内存。
        _size = other._size; // 更新当前对象的字符串长度。
        return *this; // 返回当前对象，支持连续赋值。
    } // 赋值运算符结束。

    ~MyString() // 析构函数。
    { // 析构函数开始。
        delete[] _data; // 释放字符串占用的堆内存。
        _data = nullptr; // 把指针置空，避免悬空指针。
        _size = 0; // 把长度清零。
    } // 析构函数结束。

    const char* c_str() const // 获取内部 C 风格字符串。
    { // c_str 方法开始。
        return _data; // 返回字符数组首地址。
    } // c_str 方法结束。

    std::size_t size() const // 获取字符串长度。
    { // size 方法开始。
        return _size; // 返回字符串长度。
    } // size 方法结束。
}; // 类结束。

为什么不能浅拷贝

如果只写：

_data = other._data; // 只是复制地址，两个对象会指向同一块内存。

两个对象析构时都会 delete[] 同一块内存，容易造成重复释放，程序崩溃。

面试高分回答

TIP

我会说：这个字符串类内部持有 char*，所以需要遵守 Rule of Three：析构函数负责释放内存，拷贝构造函数负责深拷贝，拷贝赋值运算符负责处理自赋值、释放旧资源、复制新资源。拷贝时不能只复制指针地址，否则两个对象会共享同一块内存，析构时会重复释放。

一句话记忆

有 char* 就要深拷贝：构造申请，析构释放，拷贝重新申请，赋值先防自赋值。

手写线程安全队列

核心解释

线程安全队列就是：把普通 std::queue 包起来，所有读写都先加 mutex，避免多个线程同时改队列；如果消费者发现队列为空，就用 condition_variable 睡眠等待，生产者 push 后再唤醒它。

C++ 代码

#include <queue> // 引入 std::queue 容器。
#include <mutex> // 引入 std::mutex、std::lock_guard、std::unique_lock。
#include <condition_variable> // 引入 std::condition_variable 条件变量。
#include <utility> // 引入 std::move 移动语义。
#include <cstddef> // 引入 std::size_t 类型。

template <typename T> // 定义模板，让队列可以保存任意类型。
class ThreadSafeQueue // 定义线程安全队列类。
{ // 类开始。
private: // 私有成员开始。
    mutable std::mutex _mutex; // 定义互斥锁，用来保护队列数据。
    std::queue<T> _queue; // 定义真正存数据的普通队列。
    std::condition_variable _cv; // 定义条件变量，用来阻塞等待和唤醒线程。
    bool _closed = false; // 定义关闭标记，用来通知等待线程退出。
public: // 公有成员开始。
    ThreadSafeQueue() = default; // 使用默认构造函数。
    ThreadSafeQueue(const ThreadSafeQueue&) = delete; // 禁止拷贝构造，避免锁和队列被错误复制。
    ThreadSafeQueue& operator=(const ThreadSafeQueue&) = delete; // 禁止拷贝赋值，避免多个对象共享内部状态。
    bool push(T value) // 向队列中加入一个元素。
    { // push 方法开始。
        { // 创建局部作用域，让锁可以提前释放。
            std::lock_guard<std::mutex> lock(_mutex); // 自动加锁，离开作用域自动解锁。
            if (_closed) // 如果队列已经关闭。
            { // if 代码块开始。
                return false; // 返回 false，表示不能再加入数据。
            } // if 代码块结束。
            _queue.push(std::move(value)); // 把数据移动进队列，减少不必要拷贝。
        } // 局部作用域结束，互斥锁在这里释放。
        _cv.notify_one(); // 唤醒一个正在等待数据的消费者线程。
        return true; // 返回 true，表示入队成功。
    } // push 方法结束。
    bool try_pop(T& out) // 尝试取出一个元素，不阻塞等待。
    { // try_pop 方法开始。
        std::lock_guard<std::mutex> lock(_mutex); // 加锁保护队列访问。
        if (_queue.empty()) // 如果队列为空。
        { // if 代码块开始。
            return false; // 直接返回 false，不等待。
        } // if 代码块结束。
        out = std::move(_queue.front()); // 把队首元素移动到输出参数。
        _queue.pop(); // 删除队首元素。
        return true; // 返回 true，表示取出成功。
    } // try_pop 方法结束。
    bool wait_and_pop(T& out) // 等待并取出一个元素，队列为空时会阻塞。
    { // wait_and_pop 方法开始。
        std::unique_lock<std::mutex> lock(_mutex); // 创建可被条件变量暂时释放的锁。
        _cv.wait(lock, [this]() { return _closed || !_queue.empty(); }); // 队列为空且未关闭时睡眠等待，被唤醒后重新检查条件。
        if (_queue.empty()) // 如果醒来后队列仍然为空。
        { // if 代码块开始。
            return false; // 说明队列已经关闭且没有数据可取。
        } // if 代码块结束。
        out = std::move(_queue.front()); // 把队首元素移动到输出参数。
        _queue.pop(); // 删除队首元素。
        return true; // 返回 true，表示取出成功。
    } // wait_and_pop 方法结束。
    void close() // 关闭队列。
    { // close 方法开始。
        { // 创建局部作用域，让锁可以提前释放。
            std::lock_guard<std::mutex> lock(_mutex); // 加锁保护关闭标记。
            _closed = true; // 设置队列为关闭状态。
        } // 局部作用域结束，互斥锁在这里释放。
        _cv.notify_all(); // 唤醒所有等待线程，让它们有机会退出。
    } // close 方法结束。
    bool empty() const // 判断队列是否为空。
    { // empty 方法开始。
        std::lock_guard<std::mutex> lock(_mutex); // 加锁读取队列状态。
        return _queue.empty(); // 返回队列是否为空。
    } // empty 方法结束。
    std::size_t size() const // 获取队列当前元素数量。
    { // size 方法开始。
        std::lock_guard<std::mutex> lock(_mutex); // 加锁读取队列大小。
        return _queue.size(); // 返回当前队列元素数量。
    } // size 方法结束。
}; // 类结束。

面试高分回答

NOTE

我会说：线程安全队列的关键是保护共享数据。内部用 std::queue<T> 保存数据，用 std::mutex 保证同一时刻只有一个线程能修改队列。try_pop 是非阻塞接口，队列空就直接返回失败；wait_and_pop 是阻塞接口，队列空时通过 condition_variable 睡眠等待，生产者 push 数据后调用 notify_one 唤醒消费者。为了让线程能优雅退出，还可以提供 close，关闭后唤醒所有等待线程。

一句话记忆

线程安全队列 = queue 存数据，mutex 防竞争，condition_variable 负责空队列等待和唤醒。

手写对象池

核心解释

对象池就是：对象不用时不销毁，而是放回池子；下次需要时再取出来复用。它常用于子弹、特效、伤害数字、UI Item，因为这些对象创建销毁频率很高。

C# 泛型对象池

using System; // 引入 Func 和 Action 委托类型。
using System.Collections.Generic; // 引入 Stack 集合类型。

public class ObjectPool<T> where T : class // 定义一个只能管理引用类型的泛型对象池。
{ // 类开始。
    private readonly Stack<T> pool; // 保存空闲对象的栈。
    private readonly Func<T> createFunc; // 保存创建对象的方法。
    private readonly Action<T> onGet; // 保存取出对象时执行的回调。
    private readonly Action<T> onRelease; // 保存回收对象时执行的回调。
    private readonly int maxCount; // 保存对象池最大容量。
    public int CountInactive => pool.Count; // 获取当前空闲对象数量。

    public ObjectPool(Func<T> createFunc, Action<T> onGet = null, Action<T> onRelease = null, int preloadCount = 0, int maxCount = 100) // 定义对象池构造函数。
    { // 构造函数开始。
        this.createFunc = createFunc ?? throw new ArgumentNullException(nameof(createFunc)); // 保存创建对象的方法，如果为空就抛异常。
        this.onGet = onGet; // 保存取出对象时的回调。
        this.onRelease = onRelease; // 保存回收对象时的回调。
        this.maxCount = Math.Max(1, maxCount); // 保存最大容量，并保证至少为 1。
        pool = new Stack<T>(this.maxCount); // 创建空闲对象栈。
        for (int i = 0; i < preloadCount && i < this.maxCount; i++) // 按预加载数量提前创建对象。
        { // for 代码块开始。
            T obj = this.createFunc(); // 创建一个新对象。
            this.onRelease?.Invoke(obj); // 执行回收回调，让对象进入初始空闲状态。
            pool.Push(obj); // 把对象放入空闲栈。
        } // for 代码块结束。
    } // 构造函数结束。

    public T Get() // 从对象池中取出一个对象。
    { // Get 方法开始。
        T obj = pool.Count > 0 ? pool.Pop() : createFunc(); // 池里有就取出，没有就创建。
        onGet?.Invoke(obj); // 执行取出回调，比如激活对象。
        return obj; // 返回可用对象。
    } // Get 方法结束。

    public bool Release(T obj) // 把对象回收到对象池。
    { // Release 方法开始。
        if (obj == null) // 如果传入对象为空。
        { // if 代码块开始。
            return false; // 空对象不能回收。
        } // if 代码块结束。
        if (pool.Count >= maxCount) // 如果对象池已经达到最大容量。
        { // if 代码块开始。
            return false; // 不再回收，避免对象池无限变大。
        } // if 代码块结束。
        onRelease?.Invoke(obj); // 执行回收回调，比如清理状态。
        pool.Push(obj); // 把对象放回空闲栈。
        return true; // 返回回收成功。
    } // Release 方法结束。

    public void Clear() // 清空对象池。
    { // Clear 方法开始。
        pool.Clear(); // 清空所有空闲对象引用。
    } // Clear 方法结束。
} // 类结束。

Unity 使用示例

using UnityEngine; // 引入 Unity 引擎命名空间。

public class BulletPoolExample : MonoBehaviour // 定义子弹对象池示例脚本。
{ // 类开始。
    [SerializeField] private GameObject bulletPrefab; // 保存子弹预制体。
    private ObjectPool<GameObject> bulletPool; // 保存 GameObject 类型的对象池。

    private void Awake() // Unity 生命周期函数，脚本加载时调用。
    { // Awake 方法开始。
        bulletPool = new ObjectPool<GameObject>(CreateBullet, OnGetBullet, OnReleaseBullet, 20, 100); // 创建子弹对象池，并预加载 20 个。
    } // Awake 方法结束。

    private GameObject CreateBullet() // 创建一个新的子弹对象。
    { // CreateBullet 方法开始。
        GameObject bullet = Instantiate(bulletPrefab); // 实例化子弹预制体。
        bullet.SetActive(false); // 创建后先隐藏。
        return bullet; // 返回新创建的子弹。
    } // CreateBullet 方法结束。

    private void OnGetBullet(GameObject bullet) // 子弹从池子取出时调用。
    { // OnGetBullet 方法开始。
        bullet.SetActive(true); // 激活子弹。
    } // OnGetBullet 方法结束。

    private void OnReleaseBullet(GameObject bullet) // 子弹回收到池子时调用。
    { // OnReleaseBullet 方法开始。
        bullet.SetActive(false); // 隐藏子弹。
        bullet.transform.position = Vector3.zero; // 重置子弹位置。
        bullet.transform.rotation = Quaternion.identity; // 重置子弹旋转。
    } // OnReleaseBullet 方法结束。

    public GameObject SpawnBullet(Vector3 position, Quaternion rotation) // 发射或生成一个子弹。
    { // SpawnBullet 方法开始。
        GameObject bullet = bulletPool.Get(); // 从对象池取出子弹。
        bullet.transform.SetPositionAndRotation(position, rotation); // 设置子弹位置和旋转。
        return bullet; // 返回生成的子弹。
    } // SpawnBullet 方法结束。

    public void RecycleBullet(GameObject bullet) // 回收一个子弹。
    { // RecycleBullet 方法开始。
        bulletPool.Release(bullet); // 把子弹放回对象池。
    } // RecycleBullet 方法结束。
} // 类结束。

面试高分回答

WARNING

我会说：对象池适合高频创建销毁的对象，比如子弹、特效、飘字、怪物、UI Item。核心是提前创建或按需创建对象，用完后不销毁，而是重置状态并放回池子。下次需要时直接取出复用，这样可以减少频繁分配内存、减少 GC、降低 Instantiate 和 Destroy 带来的卡顿。

一句话记忆

对象池 = 用完不销毁，重置后放回池子，下次直接复用。

手写内存池思路

核心解释

内存池的核心思路是：不要每次都向系统 new/malloc，而是一次申请一大块内存，切成很多固定大小的小块。分配时从空闲链表取一块，释放时再把这块挂回空闲链表。

C++ 简化实现

#include <cstdlib> // 引入 std::malloc 和 std::free。
#include <cstddef> // 引入 std::size_t。
#include <stdexcept> // 引入 std::bad_alloc。
#include <algorithm> // 引入 std::max。

class FixedMemoryPool // 定义一个固定块大小的内存池。
{ // 类开始。
private: // 私有成员开始。
    struct FreeNode // 定义空闲链表节点。
    { // FreeNode 结构开始。
        FreeNode* next; // 指向下一个空闲内存块。
    }; // FreeNode 结构结束。

    void* _memory; // 保存整块大内存的起始地址。
    FreeNode* _freeList; // 保存空闲链表头节点。
    std::size_t _blockSize; // 保存每个内存块的大小。
    std::size_t _blockCount; // 保存内存块数量。

public: // 公有成员开始。
    FixedMemoryPool(std::size_t blockSize, std::size_t blockCount) // 定义构造函数。
        : _memory(nullptr) // 初始化大内存指针为空。
        , _freeList(nullptr) // 初始化空闲链表为空。
        , _blockSize(std::max(blockSize, sizeof(FreeNode))) // 保证每个块至少能放下一个 FreeNode 指针。
        , _blockCount(blockCount) // 保存内存块数量。
    { // 构造函数开始。
        std::size_t totalSize = _blockSize * _blockCount; // 计算总共需要申请多少字节。
        _memory = std::malloc(totalSize); // 一次性向系统申请一整块内存。
        if (_memory == nullptr) // 判断内存申请是否失败。
        { // if 代码块开始。
            throw std::bad_alloc(); // 申请失败就抛出内存分配异常。
        } // if 代码块结束。
        char* start = static_cast<char*>(_memory); // 把 void* 转成 char*，方便按字节偏移。
        for (std::size_t i = 0; i < _blockCount; ++i) // 遍历每一个内存块。
        { // for 代码块开始。
            char* blockAddress = start + i * _blockSize; // 计算当前块的起始地址。
            FreeNode* node = reinterpret_cast<FreeNode*>(blockAddress); // 把当前空闲块临时当成链表节点。
            node->next = _freeList; // 让当前节点指向原来的空闲链表头。
            _freeList = node; // 把当前节点挂到空闲链表头部。
        } // for 代码块结束。
    } // 构造函数结束。

    ~FixedMemoryPool() // 定义析构函数。
    { // 析构函数开始。
        std::free(_memory); // 释放整块大内存。
        _memory = nullptr; // 把大内存指针置空。
        _freeList = nullptr; // 把空闲链表头置空。
    } // 析构函数结束。

    FixedMemoryPool(const FixedMemoryPool&) = delete; // 禁止拷贝构造，避免两个池管理同一块内存。
    FixedMemoryPool& operator=(const FixedMemoryPool&) = delete; // 禁止拷贝赋值，避免重复释放同一块内存。

    void* Allocate() // 从内存池分配一个内存块。
    { // Allocate 方法开始。
        if (_freeList == nullptr) // 如果空闲链表为空。
        { // if 代码块开始。
            return nullptr; // 返回空，表示内存池已经没有可用块。
        } // if 代码块结束。
        FreeNode* node = _freeList; // 取出空闲链表头节点。
        _freeList = _freeList->next; // 让链表头移动到下一个空闲块。
        return node; // 返回取出的内存块地址。
    } // Allocate 方法结束。

    void Deallocate(void* ptr) // 把一个内存块归还给内存池。
    { // Deallocate 方法开始。
        if (ptr == nullptr) // 如果传入空指针。
        { // if 代码块开始。
            return; // 空指针不需要释放。
        } // if 代码块结束。
        FreeNode* node = reinterpret_cast<FreeNode*>(ptr); // 把归还的内存块临时当成链表节点。
        node->next = _freeList; // 让这个节点指向原来的空闲链表头。
        _freeList = node; // 把这个节点重新挂到空闲链表头部。
    } // Deallocate 方法结束。
}; // 类结束。

使用方式

struct Bullet // 定义一个示例对象。
{ // Bullet 结构开始。
    int damage; // 保存伤害值。
    float speed; // 保存速度。
}; // Bullet 结构结束。

FixedMemoryPool pool(sizeof(Bullet), 100); // 创建一个能放 100 个 Bullet 的固定块内存池。
void* memory = pool.Allocate(); // 从内存池申请一块原始内存。
Bullet* bullet = new (memory) Bullet{10, 20.0f}; // 使用 placement new 在这块内存上构造 Bullet。
bullet->~Bullet(); // 手动调用析构函数。
pool.Deallocate(bullet); // 把这块内存还给内存池。

面试高分回答

CAUTION

我会说：内存池主要是为了减少频繁 new/delete 或 malloc/free 带来的系统调用开销和内存碎片。简单固定块内存池会一次申请一大块连续内存，然后切成多个固定大小的小块。空闲块用链表串起来，分配时从链表头取一块，释放时再放回链表头，所以分配和释放都可以做到 O(1)。

一句话记忆

内存池 = 大块内存切小块，空闲链表管复用，分配取头，释放还头。

手写 LRU 缓存

核心解释

LRU 缓存的核心是：容量满时淘汰“最久没有被使用”的数据。标准手写方案是 Dictionary + 双向链表：字典负责 O(1) 查找，链表负责 O(1) 调整新旧顺序。

C# 代码

using System; // 引入异常类型。 
using System.Collections.Generic; // 引入 Dictionary 集合。 
public class LruCache<TKey, TValue> // 定义泛型 LRU 缓存类。 
{ // 类开始。 
    private class Node // 定义双向链表节点。 
    { // 节点类开始。 
        public TKey Key; // 保存缓存 key。 
        public TValue Value; // 保存缓存 value。 
        public Node Prev; // 指向前一个节点。 
        public Node Next; // 指向后一个节点。 
        public Node(TKey key, TValue value) // 定义节点构造函数。 
        { // 构造函数开始。 
            Key = key; // 初始化 key。 
            Value = value; // 初始化 value。 
        } // 构造函数结束。 
    } // 节点类结束。 
    private readonly int capacity; // 保存缓存容量。 
    private readonly Dictionary<TKey, Node> map; // 保存 key 到节点的映射。 
    private readonly Node head; // 虚拟头节点，头部表示最新使用。 
    private readonly Node tail; // 虚拟尾节点，尾部表示最久未使用。 
    public LruCache(int capacity) // 定义 LRU 构造函数。 
    { // 构造函数开始。 
        if (capacity <= 0) // 如果容量不合法。 
        { // if 开始。 
            throw new ArgumentException("capacity 必须大于 0"); // 抛出参数异常。 
        } // if 结束。 
        this.capacity = capacity; // 保存容量。 
        map = new Dictionary<TKey, Node>(); // 创建哈希表。 
        head = new Node(default(TKey), default(TValue)); // 创建虚拟头节点。 
        tail = new Node(default(TKey), default(TValue)); // 创建虚拟尾节点。 
        head.Next = tail; // 让头节点指向尾节点。 
        tail.Prev = head; // 让尾节点指向头节点。 
    } // 构造函数结束。 
    public bool TryGet(TKey key, out TValue value) // 尝试读取缓存。 
    { // TryGet 开始。 
        if (!map.TryGetValue(key, out Node node)) // 如果字典中没有这个 key。 
        { // if 开始。 
            value = default(TValue); // 输出默认值。 
            return false; // 返回读取失败。 
        } // if 结束。 
        MoveToHead(node); // 命中后把节点移动到头部。 
        value = node.Value; // 输出缓存值。 
        return true; // 返回读取成功。 
    } // TryGet 结束。 
    public void Put(TKey key, TValue value) // 添加或更新缓存。 
    { // Put 开始。 
        if (map.TryGetValue(key, out Node node)) // 如果 key 已经存在。 
        { // if 开始。 
            node.Value = value; // 更新缓存值。 
            MoveToHead(node); // 更新后也算刚使用，移动到头部。 
            return; // 结束方法。 
        } // if 结束。 
        Node newNode = new Node(key, value); // 创建新节点。 
        map[key] = newNode; // 把新节点加入字典。 
        AddToHead(newNode); // 把新节点加入链表头部。 
        if (map.Count > capacity) // 如果超过容量。 
        { // if 开始。 
            Node oldNode = RemoveTail(); // 删除尾部最旧节点。 
            map.Remove(oldNode.Key); // 从字典中删除旧节点 key。 
        } // if 结束。 
    } // Put 结束。 
    private void MoveToHead(Node node) // 把节点移动到头部。 
    { // MoveToHead 开始。 
        RemoveNode(node); // 先从原位置摘掉节点。 
        AddToHead(node); // 再插入到头部。 
    } // MoveToHead 结束。 
    private void AddToHead(Node node) // 把节点插入到 head 后面。 
    { // AddToHead 开始。 
        node.Prev = head; // 新节点前驱指向 head。 
        node.Next = head.Next; // 新节点后继指向原第一个节点。 
        head.Next.Prev = node; // 原第一个节点前驱改成新节点。 
        head.Next = node; // head 后继改成新节点。 
    } // AddToHead 结束。 
    private void RemoveNode(Node node) // 从链表中移除节点。 
    { // RemoveNode 开始。 
        node.Prev.Next = node.Next; // 前一个节点跳过当前节点。 
        node.Next.Prev = node.Prev; // 后一个节点跳过当前节点。 
    } // RemoveNode 结束。 
    private Node RemoveTail() // 删除尾部最旧节点。 
    { // RemoveTail 开始。 
        Node oldNode = tail.Prev; // tail 前面的真实节点就是最旧节点。 
        RemoveNode(oldNode); // 从链表中移除旧节点。 
        return oldNode; // 返回被删除的旧节点。 
    } // RemoveTail 结束。 
} // 类结束。

面试高分回答

IMPORTANT

LRU 不能只用 Dictionary，因为字典不知道谁最久没用；也不能只用链表，因为查找 key 会变成 O(n)。所以用 Dictionary 快速定位节点，用双向链表维护访问顺序。每次 Get 或更新都把节点移动到头部，容量满时删除尾部节点。

复杂度

Get 平均 O(1)。

Put 平均 O(1)。

空间复杂度 O(n)。

一句话记忆

LRU = 字典负责快速找到节点，双向链表负责快速移动和淘汰最旧节点。

手写快排

核心解释

快排的核心是“分区”：选一个基准值 pivot，把比它小的放左边，比它大的放右边。这样 pivot 就到了最终位置，然后递归排序左右两边。

C# 代码

using System; // 引入基础命名空间。

public static class QuickSortDemo // 定义快速排序工具类。
{ // 类开始。
    public static void QuickSort(int[] nums) // 对外提供快速排序入口。
    { // QuickSort 入口方法开始。
        if (nums == null || nums.Length <= 1) // 如果数组为空或长度小于等于 1。
        { // if 代码块开始。
            return; // 不需要排序，直接返回。
        } // if 代码块结束。

        QuickSort(nums, 0, nums.Length - 1); // 从整个数组区间开始递归排序。
    } // QuickSort 入口方法结束。

    private static void QuickSort(int[] nums, int left, int right) // 对指定区间执行快速排序。
    { // QuickSort 递归方法开始。
        if (left >= right) // 如果区间里没有元素或只有一个元素。
        { // if 代码块开始。
            return; // 这个区间天然有序，直接返回。
        } // if 代码块结束。

        int pivotIndex = Partition(nums, left, right); // 对当前区间分区，并得到基准值最终位置。
        QuickSort(nums, left, pivotIndex - 1); // 递归排序基准值左边的区间。
        QuickSort(nums, pivotIndex + 1, right); // 递归排序基准值右边的区间。
    } // QuickSort 递归方法结束。

    private static int Partition(int[] nums, int left, int right) // 对数组区间进行分区。
    { // Partition 方法开始。
        int pivot = nums[right]; // 选择最右边元素作为基准值。
        int storeIndex = left; // storeIndex 表示下一个小元素应该放的位置。

        for (int i = left; i < right; i++) // 从 left 遍历到 right 前一个位置。
        { // for 代码块开始。
            if (nums[i] <= pivot) // 如果当前元素小于等于基准值。
            { // if 代码块开始。
                Swap(nums, i, storeIndex); // 把当前元素交换到左侧小元素区域。
                storeIndex++; // 小元素区域向右扩大一格。
            } // if 代码块结束。
        } // for 代码块结束。

        Swap(nums, storeIndex, right); // 把基准值交换到中间最终位置。
        return storeIndex; // 返回基准值最终下标。
    } // Partition 方法结束。

    private static void Swap(int[] nums, int a, int b) // 交换数组中的两个元素。
    { // Swap 方法开始。
        if (a == b) // 如果两个下标相同。
        { // if 代码块开始。
            return; // 不需要交换，直接返回。
        } // if 代码块结束。

        int temp = nums[a]; // 临时保存 a 位置的值。
        nums[a] = nums[b]; // 把 b 位置的值放到 a 位置。
        nums[b] = temp; // 把临时保存的值放到 b 位置。
    } // Swap 方法结束。
} // 类结束。

怎么背 Partition

storeIndex 左边都是已经确认“小于等于 pivot”的元素。

遍历时发现 nums[i] <= pivot，就把它交换到 storeIndex 的位置。

遍历结束后，把 pivot 交换到 storeIndex。

这样：

左边都 <= pivot。

右边都 > pivot。

pivot 自己已经在最终位置。

复杂度

平均时间复杂度：O(n log n)。

最坏时间复杂度：O(n²)，比如每次都选到最大或最小元素做基准。

空间复杂度：平均 O(log n)，来自递归调用栈；最坏 O(n)。

稳定性：通常不稳定，因为交换可能改变相等元素的原始顺序。

面试高分回答

NOTE

快排使用分治思想。每次选一个基准值，通过 Partition 把数组分成左右两部分，使左边元素小于等于基准，右边元素大于基准。此时基准值已经在最终位置，再递归排序左右区间。快排平均性能很好，原地排序，平均时间复杂度是 O(n log n)，但如果基准选择很差，最坏会退化到 O(n²)。

一句话记忆

快排 = 选基准，做分区，基准归位，递归左右。

手写二叉树遍历

核心解释

二叉树遍历就是按规则访问每个节点一次。前序、中序、后序属于 DFS，区别是“根节点什么时候访问”；层序遍历属于 BFS，用队列一层一层访问。

遍历顺序

前序：根 -> 左 -> 右。

中序：左 -> 根 -> 右。

后序：左 -> 右 -> 根。

层序：从上到下、从左到右。

C# 代码

using System.Collections.Generic; // 引入 List 和 Queue 集合类型。
public class TreeNode // 定义二叉树节点类。
{ // TreeNode 类开始。
    public int Value; // 保存当前节点的值。
    public TreeNode Left; // 保存左子节点引用。
    public TreeNode Right; // 保存右子节点引用。
    public TreeNode(int value) // 定义节点构造函数。
    { // 构造函数开始。
        Value = value; // 初始化节点值。
    } // 构造函数结束。
} // TreeNode 类结束。
public static class BinaryTreeTraversal // 定义二叉树遍历工具类。
{ // 工具类开始。
    public static List<int> Preorder(TreeNode root) // 前序遍历入口。
    { // Preorder 方法开始。
        List<int> result = new List<int>(); // 创建结果列表。
        PreorderDfs(root, result); // 从根节点开始递归前序遍历。
        return result; // 返回遍历结果。
    } // Preorder 方法结束。
    private static void PreorderDfs(TreeNode node, List<int> result) // 前序遍历递归函数。
    { // PreorderDfs 方法开始。
        if (node == null) // 如果当前节点为空。
        { // if 代码块开始。
            return; // 空节点直接返回。
        } // if 代码块结束。
        result.Add(node.Value); // 前序第一步：访问根节点。
        PreorderDfs(node.Left, result); // 前序第二步：递归访问左子树。
        PreorderDfs(node.Right, result); // 前序第三步：递归访问右子树。
    } // PreorderDfs 方法结束。
    public static List<int> Inorder(TreeNode root) // 中序遍历入口。
    { // Inorder 方法开始。
        List<int> result = new List<int>(); // 创建结果列表。
        InorderDfs(root, result); // 从根节点开始递归中序遍历。
        return result; // 返回遍历结果。
    } // Inorder 方法结束。
    private static void InorderDfs(TreeNode node, List<int> result) // 中序遍历递归函数。
    { // InorderDfs 方法开始。
        if (node == null) // 如果当前节点为空。
        { // if 代码块开始。
            return; // 空节点直接返回。
        } // if 代码块结束。
        InorderDfs(node.Left, result); // 中序第一步：递归访问左子树。
        result.Add(node.Value); // 中序第二步：访问根节点。
        InorderDfs(node.Right, result); // 中序第三步：递归访问右子树。
    } // InorderDfs 方法结束。
    public static List<int> Postorder(TreeNode root) // 后序遍历入口。
    { // Postorder 方法开始。
        List<int> result = new List<int>(); // 创建结果列表。
        PostorderDfs(root, result); // 从根节点开始递归后序遍历。
        return result; // 返回遍历结果。
    } // Postorder 方法结束。
    private static void PostorderDfs(TreeNode node, List<int> result) // 后序遍历递归函数。
    { // PostorderDfs 方法开始。
        if (node == null) // 如果当前节点为空。
        { // if 代码块开始。
            return; // 空节点直接返回。
        } // if 代码块结束。
        PostorderDfs(node.Left, result); // 后序第一步：递归访问左子树。
        PostorderDfs(node.Right, result); // 后序第二步：递归访问右子树。
        result.Add(node.Value); // 后序第三步：访问根节点。
    } // PostorderDfs 方法结束。
    public static List<int> LevelOrder(TreeNode root) // 层序遍历入口。
    { // LevelOrder 方法开始。
        List<int> result = new List<int>(); // 创建结果列表。
        if (root == null) // 如果根节点为空。
        { // if 代码块开始。
            return result; // 空树直接返回空列表。
        } // if 代码块结束。
        Queue<TreeNode> queue = new Queue<TreeNode>(); // 创建队列保存待访问节点。
        queue.Enqueue(root); // 先把根节点放入队列。
        while (queue.Count > 0) // 只要队列里还有节点就继续遍历。
        { // while 代码块开始。
            TreeNode node = queue.Dequeue(); // 取出队首节点。
            result.Add(node.Value); // 访问当前节点。
            if (node.Left != null) // 如果左子节点不为空。
            { // if 代码块开始。
                queue.Enqueue(node.Left); // 把左子节点加入队列。
            } // if 代码块结束。
            if (node.Right != null) // 如果右子节点不为空。
            { // if 代码块开始。
                queue.Enqueue(node.Right); // 把右子节点加入队列。
            } // if 代码块结束。
        } // while 代码块结束。
        return result; // 返回层序遍历结果。
    } // LevelOrder 方法结束。
} // 工具类结束。

复杂度

时间复杂度都是 O(n)，因为每个节点都访问一次。

DFS 递归空间复杂度是 O(h)，h 是树高。

BFS 层序空间复杂度是 O(w)，w 是某一层最大节点数。

面试高分回答

IMPORTANT

二叉树遍历分 DFS 和 BFS。前序、中序、后序都是 DFS，区别在于访问根节点的位置：前序先访问根，中序中间访问根，后序最后访问根。层序遍历是 BFS，需要用队列，先把根节点入队，每次出队一个节点，再把它的左右孩子入队。

一句话记忆

前中后序看“根”的位置，层序遍历靠队列一层层扫。

手写生产者消费者

核心解释

生产者消费者模型就是：生产者线程负责生成数据，消费者线程负责处理数据，中间用一个线程安全队列做缓冲。队列为空时消费者等待；生产者放入数据后通知消费者。

C++ 代码

#include <iostream> // 引入输入输出库。
#include <queue> // 引入队列容器。
#include <mutex> // 引入互斥锁。
#include <condition_variable> // 引入条件变量。
#include <thread> // 引入线程。
#include <chrono> // 引入时间工具。

class BlockingQueue // 定义阻塞队列类。
{ // 类开始。
private: // 私有成员开始。
    std::queue<int> _queue; // 保存真正的数据队列。
    std::mutex _mutex; // 保存互斥锁，保护队列。
    std::condition_variable _cv; // 保存条件变量，用于等待和唤醒。
    bool _closed = false; // 保存队列是否关闭。

public: // 公有成员开始。
    void push(int value) // 生产者调用，用来放入数据。
    { // push 方法开始。
        { // 创建局部作用域，让锁提前释放。
            std::lock_guard<std::mutex> lock(_mutex); // 自动加锁，离开作用域自动解锁。
            if (_closed) // 如果队列已经关闭。
            { // if 开始。
                return; // 不再允许放入数据。
            } // if 结束。
            _queue.push(value); // 把数据放入队列。
        } // 局部作用域结束，锁在这里释放。
        _cv.notify_one(); // 唤醒一个正在等待的消费者。
    } // push 方法结束。

    bool wait_pop(int& value) // 消费者调用，用来等待并取出数据。
    { // wait_pop 方法开始。
        std::unique_lock<std::mutex> lock(_mutex); // 创建可以配合条件变量使用的锁。
        _cv.wait(lock, [this]() { return _closed || !_queue.empty(); }); // 队列为空且未关闭时等待。
        if (_queue.empty()) // 如果醒来后队列还是空。
        { // if 开始。
            return false; // 表示队列关闭并且没有数据了。
        } // if 结束。
        value = _queue.front(); // 取出队首数据。
        _queue.pop(); // 删除队首数据。
        return true; // 返回取出成功。
    } // wait_pop 方法结束。

    void close() // 关闭队列。
    { // close 方法开始。
        { // 创建局部作用域，让锁提前释放。
            std::lock_guard<std::mutex> lock(_mutex); // 加锁保护关闭标记。
            _closed = true; // 设置队列为关闭状态。
        } // 局部作用域结束，锁在这里释放。
        _cv.notify_all(); // 唤醒所有等待中的消费者，让它们退出。
    } // close 方法结束。
}; // BlockingQueue 类结束。

void producer(BlockingQueue& queue) // 定义生产者函数。
{ // producer 函数开始。
    for (int i = 1; i <= 5; ++i) // 生产 5 个任务。
    { // for 开始。
        queue.push(i); // 把任务放进阻塞队列。
        std::cout << "生产任务: " << i << std::endl; // 输出生产日志。
        std::this_thread::sleep_for(std::chrono::milliseconds(200)); // 模拟生产任务需要时间。
    } // for 结束。
    queue.close(); // 生产结束后关闭队列。
} // producer 函数结束。

void consumer(BlockingQueue& queue) // 定义消费者函数。
{ // consumer 函数开始。
    int value = 0; // 保存取出的任务数据。
    while (queue.wait_pop(value)) // 持续等待并消费任务，直到队列关闭。
    { // while 开始。
        std::cout << "消费任务: " << value << std::endl; // 输出消费日志。
        std::this_thread::sleep_for(std::chrono::milliseconds(300)); // 模拟处理任务需要时间。
    } // while 结束。
    std::cout << "消费者退出" << std::endl; // 输出消费者退出日志。
} // consumer 函数结束。

int main() // 程序入口函数。
{ // main 函数开始。
    BlockingQueue queue; // 创建一个阻塞队列。
    std::thread producerThread(producer, std::ref(queue)); // 创建生产者线程。
    std::thread consumerThread(consumer, std::ref(queue)); // 创建消费者线程。
    producerThread.join(); // 等待生产者线程结束。
    consumerThread.join(); // 等待消费者线程结束。
    return 0; // 返回 0，表示程序正常结束。
} // main 函数结束。

面试高分回答

NOTE

生产者消费者模型解决的是线程之间的协作问题。生产者不直接调用消费者，而是把任务放到共享队列里；消费者从队列里取任务处理。共享队列必须用 mutex 保护，避免多个线程同时读写造成数据竞争。队列为空时，消费者不要死循环浪费 CPU，而是用 condition_variable 阻塞等待；生产者放入新数据后调用 notify_one 唤醒消费者。

一句话记忆

生产者消费者 = 生产者 push，消费者 pop，中间队列用锁保护，没数据就等待，有数据就唤醒。

手写 A* 伪代码

核心解释

A* 的核心是：每次从 Open 表 中选 f = g + h 最小的节点来扩展。g 是起点到当前点的真实代价，h 是当前点到终点的预估代价。找到终点后，用 parent 一路回溯出完整路径。

A* 伪代码

function AStar(start, end) // 定义 A* 寻路函数，传入起点和终点。
    openSet = PriorityQueue() // 创建 Open 表，用优先队列保存待探索节点。
    closedSet = HashSet() // 创建 Closed 表，用来保存已经处理过的节点。
    start.g = 0 // 起点到自己的真实代价是 0。
    start.h = Heuristic(start, end) // 计算起点到终点的预估代价。
    start.f = start.g + start.h // 计算起点的总代价。
    start.parent = null // 起点没有父节点。
    openSet.Push(start, start.f) // 把起点加入 Open 表。
    while openSet is not empty // 只要还有节点可以探索，就继续循环。
        current = openSet.PopMinF() // 取出 f 值最小的节点。
        if current == end // 如果当前节点就是终点。
            return BuildPath(current) // 从终点沿 parent 回溯出路径。
        closedSet.Add(current) // 把当前节点加入 Closed 表，表示它已经处理过。
        for each neighbor in GetNeighbors(current) // 遍历当前节点周围可以到达的邻居。
            if neighbor is wall // 如果邻居是墙。
                continue // 跳过这个邻居。
            if neighbor in closedSet // 如果邻居已经处理过。
                continue // 跳过这个邻居。
            newG = current.g + MoveCost(current, neighbor) // 计算从起点经过 current 再到 neighbor 的新代价。
            if neighbor not in openSet // 如果邻居还不在 Open 表中。
                neighbor.g = newG // 记录邻居的真实代价。
                neighbor.h = Heuristic(neighbor, end) // 计算邻居到终点的预估代价。
                neighbor.f = neighbor.g + neighbor.h // 计算邻居总代价。
                neighbor.parent = current // 记录邻居是从 current 走过来的。
                openSet.Push(neighbor, neighbor.f) // 把邻居加入 Open 表。
            else if newG < neighbor.g // 如果邻居已经在 Open 表中，但新路径更短。
                neighbor.g = newG // 更新邻居的真实代价。
                neighbor.f = neighbor.g + neighbor.h // 更新邻居的总代价。
                neighbor.parent = current // 更新邻居的父节点。
                openSet.UpdatePriority(neighbor, neighbor.f) // 更新 Open 表里的优先级。
    return empty path // Open 表空了还没找到终点，说明没有可达路径。

回溯路径伪代码

function BuildPath(endNode) // 定义路径回溯函数。
    path = List() // 创建路径列表。
    current = endNode // 从终点开始回溯。
    while current is not null // 只要当前节点存在，就继续往父节点走。
        path.Add(current) // 把当前节点加入路径。
        current = current.parent // 移动到父节点。
    path.Reverse() // 因为是从终点回到起点，所以需要反转路径。
    return path // 返回从起点到终点的完整路径。

怎么理解 Open 和 Closed

Open 表：还没最终确定，但值得继续探索的点。

Closed 表：已经处理过，不需要再处理的点。

每一轮从 Open 表 里拿 f 最小的点，因为它看起来“从起点走到这里，再从这里走到终点”的总代价最低。

面试高分回答

CAUTION

我会说：A* 是在 Dijkstra 的基础上加了启发式估价。它维护一个 Open 表和一个 Closed 表。Open 表保存待探索节点，并按 f = g + h 排序；Closed 表保存已经处理过的节点。每次取 f 最小的节点扩展相邻格子，如果找到更短路径，就更新邻居的 g、f 和 parent。当终点被取出时，通过 parent 回溯得到最终路径。

一句话记忆

A* = 每次选 g + h 最小的点继续走，找到终点后靠 parent 倒着拼路径。