面试题：C++ 中自定义内存分配器与标准库内存分配的协同及优化

1. 设计自定义内存分配器与C++标准库协同工作

在C++中，可以通过重载operator new和operator delete来实现自定义内存分配器。以下是一个简单示例：

#include <iostream>
#include <cstdlib>

class MyAllocator {
public:
    void* allocate(size_t size) {
        return std::malloc(size);
    }

    void deallocate(void* ptr) {
        std::free(ptr);
    }
};

class MyClass {
public:
    void* operator new(size_t size) {
        return MyAllocator().allocate(size);
    }

    void operator delete(void* ptr) {
        MyAllocator().deallocate(ptr);
    }
};

这样，当创建MyClass对象时，就会使用自定义的内存分配器。如果要让自定义分配器与标准库容器协同工作，可以实现一个符合std::allocator接口的自定义分配器类，如下：

template <typename T>
class MyStdAllocator {
public:
    using value_type = T;
    using pointer = T*;
    using const_pointer = const T*;
    using reference = T&;
    using const_reference = const T&;
    using size_type = size_t;
    using difference_type = ptrdiff_t;

    template <typename U>
    struct rebind {
        using other = MyStdAllocator<U>;
    };

    MyStdAllocator() noexcept = default;
    MyStdAllocator(const MyStdAllocator&) noexcept = default;
    template <typename U>
    MyStdAllocator(const MyStdAllocator<U>&) noexcept {}
    ~MyStdAllocator() noexcept = default;

    pointer address(reference x) const noexcept { return &x; }
    const_pointer address(const_reference x) const noexcept { return &x; }

    pointer allocate(size_type n, const void* hint = nullptr) {
        return static_cast<pointer>(MyAllocator().allocate(n * sizeof(T)));
    }

    void deallocate(pointer p, size_type n) {
        MyAllocator().deallocate(p);
    }

    size_type max_size() const noexcept {
        return static_cast<size_type>(-1) / sizeof(T);
    }

    template <typename U, typename... Args>
    void construct(U* p, Args&&... args) {
        ::new((void*)p) U(std::forward<Args>(args)...);
    }

    template <typename U>
    void destroy(U* p) {
        p->~U();
    }
};

然后可以这样使用：

#include <vector>
int main() {
    std::vector<int, MyStdAllocator<int>> vec;
    vec.push_back(1);
    return 0;
}

2. 优化小块内存分配和释放场景

减少内存碎片：
- 对象池：对于频繁分配和释放的小块内存，可以使用对象池技术。预先分配一大块内存，将其分割成多个小块，当需要分配时直接从对象池中获取，释放时再放回对象池。例如：

class SmallObjectPool {
private:
    const size_t blockSize;
    const size_t poolSize;
    char* pool;
    bool* used;
public:
    SmallObjectPool(size_t blockSize, size_t poolSize)
        : blockSize(blockSize), poolSize(poolSize) {
        pool = new char[blockSize * poolSize];
        used = new bool[poolSize]();
    }

    ~SmallObjectPool() {
        delete[] pool;
        delete[] used;
    }

    void* allocate() {
        for (size_t i = 0; i < poolSize; ++i) {
            if (!used[i]) {
                used[i] = true;
                return pool + i * blockSize;
            }
        }
        return nullptr;
    }

    void deallocate(void* ptr) {
        size_t index = (reinterpret_cast<char*>(ptr) - pool) / blockSize;
        if (index < poolSize) {
            used[index] = false;
        }
    }
};

- **伙伴系统**：这是一种更复杂但高效的内存管理算法。它将内存空间看作是一个树形结构，大块内存可以分裂成两个相等的小块（伙伴），当两个伙伴都空闲时可以合并成一个大块。这样可以有效减少外部碎片。

提高整体性能：
- 减少系统调用：标准库的malloc和free通常会涉及系统调用，频繁调用会带来较大开销。自定义分配器通过对象池等技术，可以在用户空间内完成大部分分配和释放操作，减少系统调用次数。
- 预分配：在应用启动时，预先分配一定量的内存供后续使用，避免在运行过程中频繁分配新内存。

3. 多线程环境下的线程安全性问题及解决方案

线程安全性问题：
- 资源竞争：多个线程同时访问和修改内存分配器的内部数据结构（如对象池的使用状态）时，可能会导致数据不一致。
- 内存损坏：例如，一个线程释放了内存，另一个线程同时尝试分配相同的内存，可能导致内存损坏。
解决方案：
- 互斥锁（Mutex）：在关键代码段（如分配和释放内存的函数）前后加锁，保证同一时间只有一个线程能执行这些操作。例如：

#include <mutex>
class ThreadSafeAllocator {
private:
    std::mutex mtx;
    SmallObjectPool pool;
public:
    ThreadSafeAllocator(size_t blockSize, size_t poolSize) : pool(blockSize, poolSize) {}

    void* allocate() {
        std::lock_guard<std::mutex> lock(mtx);
        return pool.allocate();
    }

    void deallocate(void* ptr) {
        std::lock_guard<std::mutex> lock(mtx);
        pool.deallocate(ptr);
    }
};

- **读写锁（Read - Write Lock）**：如果读操作（如获取已分配内存块的信息）远多于写操作（分配和释放内存），可以使用读写锁。读操作时允许多个线程同时进行，写操作时则独占锁。
- **无锁数据结构**：设计无锁的数据结构来管理内存分配，避免锁带来的性能开销。但这种方法实现复杂，需要仔细处理原子操作和内存屏障等问题。

面试题：C++ 中自定义内存分配器与标准库内存分配的协同及优化

知识考点

面试题答案

1. 设计自定义内存分配器与C++标准库协同工作

2. 优化小块内存分配和释放场景

3. 多线程环境下的线程安全性问题及解决方案