面试题：C++内存池设计与数据结构性能优化

1. C++ 内存池设计

#include <iostream>
#include <vector>
#include <cassert>

class MemoryPool {
private:
    const size_t blockSize;
    const size_t initialBlocks;
    std::vector<char*> blocks;
    char* freeList;

public:
    MemoryPool(size_t blockSize, size_t initialBlocks = 10)
        : blockSize(blockSize), initialBlocks(initialBlocks), freeList(nullptr) {
        for (size_t i = 0; i < initialBlocks; ++i) {
            char* block = new char[blockSize];
            blocks.push_back(block);
            // 初始化空闲链表
            for (size_t j = 0; j < blockSize - sizeof(char*); j += sizeof(char*)) {
                reinterpret_cast<char**>(block + j)[0] = block + j + sizeof(char*);
            }
            reinterpret_cast<char**>(block + blockSize - sizeof(char*))[0] = freeList;
            freeList = block;
        }
    }

    ~MemoryPool() {
        for (char* block : blocks) {
            delete[] block;
        }
    }

    void* allocate() {
        if (freeList == nullptr) {
            char* newBlock = new char[blockSize];
            blocks.push_back(newBlock);
            // 初始化新块的空闲链表
            for (size_t j = 0; j < blockSize - sizeof(char*); j += sizeof(char*)) {
                reinterpret_cast<char**>(newBlock + j)[0] = newBlock + j + sizeof(char*);
            }
            reinterpret_cast<char**>(newBlock + blockSize - sizeof(char*))[0] = freeList;
            freeList = newBlock;
        }
        void* result = freeList;
        freeList = *reinterpret_cast<char***>(freeList)[0];
        return result;
    }

    void deallocate(void* ptr) {
        assert(ptr != nullptr);
        *reinterpret_cast<char***>(ptr)[0] = freeList;
        freeList = reinterpret_cast<char*>(ptr);
    }
};

2. 结合内存池优化自定义双向链表节点性能

假设双向链表节点定义如下：

struct DoublyLinkedListNode {
    int data;
    DoublyLinkedListNode* prev;
    DoublyLinkedListNode* next;
};

使用内存池优化性能：

class DoublyLinkedList {
private:
    MemoryPool pool;
    DoublyLinkedListNode* head;
    DoublyLinkedListNode* tail;

public:
    DoublyLinkedList() : pool(sizeof(DoublyLinkedListNode), 10), head(nullptr), tail(nullptr) {}

    ~DoublyLinkedList() {
        while (head != nullptr) {
            DoublyLinkedListNode* temp = head;
            head = head->next;
            pool.deallocate(temp);
        }
    }

    void push_back(int value) {
        DoublyLinkedListNode* newNode = static_cast<DoublyLinkedListNode*>(pool.allocate());
        newNode->data = value;
        newNode->prev = tail;
        newNode->next = nullptr;
        if (tail != nullptr) {
            tail->next = newNode;
        } else {
            head = newNode;
        }
        tail = newNode;
    }
};

3. 可能遇到的问题及解决方案

内存池大小问题：
- 问题：如果内存池初始大小设置过小，频繁分配可能导致频繁扩展内存池，增加开销；如果设置过大，可能浪费内存。
- 解决方案：可以根据应用场景估算合适的初始大小，并且提供动态调整内存池大小的机制，例如在内存池耗尽一定比例时，按照一定策略（如倍增）扩展内存池。
内存对齐问题：
- 问题：不同平台和编译器对内存对齐要求不同，如果分配的内存块没有正确对齐，可能导致程序崩溃或性能问题。
- 解决方案：在内存池分配时，使用 alignas 关键字确保内存块对齐，或者使用标准库中的 aligned_alloc 函数来分配内存。
线程安全问题：
- 问题：如果在多线程环境下使用内存池，同时进行分配和释放操作可能导致数据竞争。
- 解决方案：可以使用互斥锁（如 std::mutex）保护内存池的分配和释放操作，确保同一时间只有一个线程可以访问内存池。也可以考虑使用无锁数据结构来实现线程安全的内存池，提高并发性能。

星途面试题库

面试题：C++内存池设计与数据结构性能优化

知识考点

面试题答案

1. C++ 内存池设计

2. 结合内存池优化自定义双向链表节点性能

3. 可能遇到的问题及解决方案