面试题：C++ 优化自定义队列的内存管理

优化思路

智能指针：使用unique_ptr或shared_ptr替代原始指针来管理链表节点。unique_ptr适合于独占所有权的情况，能确保节点在不再被使用时自动释放内存；shared_ptr用于共享所有权场景，通过引用计数管理内存释放。在队列中，每个节点的内存管理可以交给智能指针，这样能避免手动释放内存导致的内存泄漏等问题。
内存池技术：创建一个内存池，预先分配一块较大的内存空间。当需要创建新的链表节点时，从内存池中获取内存，而不是每次都调用new运算符向系统申请内存。当节点不再使用时，将其内存归还到内存池中，而不是直接释放给系统。这样可以减少内存碎片的产生，因为内存池内部的内存分配和回收相对有序，避免了频繁的小块内存申请和释放。

关键代码片段

定义链表节点和内存池

#include <memory>
#include <vector>

// 链表节点结构
template <typename T>
struct QueueNode {
    T data;
    std::unique_ptr<QueueNode<T>> next;
    QueueNode(const T& value) : data(value), next(nullptr) {}
};

// 内存池类
template <typename T>
class MemoryPool {
private:
    std::vector<char> pool;
    size_t blockSize;
    size_t currentIndex;

public:
    MemoryPool(size_t numBlocks, size_t blockSize) : blockSize(blockSize), currentIndex(0) {
        pool.resize(numBlocks * blockSize);
    }

    T* allocate() {
        if (currentIndex >= pool.size()) {
            return nullptr;
        }
        T* ptr = reinterpret_cast<T*>(&pool[currentIndex]);
        currentIndex += blockSize;
        return ptr;
    }

    void deallocate(T* ptr) {
        // 简单处理，这里可以添加更复杂的回收逻辑
        // 确保ptr在pool范围内
        // 这里不做实际操作，因为在智能指针管理下，节点释放时不会调用此函数
        // 内存池的释放由内存池对象生命周期结束时进行
    }
};

基于智能指针和内存池的队列实现

template <typename T>
class Queue {
private:
    std::unique_ptr<QueueNode<T>> front;
    std::unique_ptr<QueueNode<T>> rear;
    MemoryPool<QueueNode<T>> memoryPool;

public:
    Queue(size_t numBlocks = 100) : memoryPool(numBlocks, sizeof(QueueNode<T>)) {}

    void enqueue(const T& value) {
        auto newNode = std::unique_ptr<QueueNode<T>>(memoryPool.allocate()? new (memoryPool.allocate()) QueueNode<T>(value) : nullptr);
        if (!newNode) {
            throw std::bad_alloc();
        }
        if (!rear) {
            front = std::move(newNode);
            rear = std::move(front);
        } else {
            rear->next = std::move(newNode);
            rear = std::move(rear->next);
        }
    }

    void dequeue() {
        if (!front) {
            throw std::runtime_error("Queue is empty");
        }
        front = std::move(front->next);
        if (!front) {
            rear.reset();
        }
    }

    T& peek() {
        if (!front) {
            throw std::runtime_error("Queue is empty");
        }
        return front->data;
    }

    bool isEmpty() const {
        return!front;
    }
};

性能对比分析方法

测试场景：创建两个队列，一个是原始的基于链表的队列（使用原始指针管理内存），另一个是优化后的基于智能指针和内存池的队列。
性能指标：
- 时间：记录在相同的操作序列下（如大量的入队和出队操作），两个队列完成操作所需的时间。可以使用std::chrono库来获取高精度的时间测量。
- 内存占用：在操作系统层面观察程序运行过程中的内存使用情况，例如在Linux下可以使用ps命令查看进程的内存占用。在程序内部，可以使用malloc_usable_size（在<malloc.h>中，仅适用于glibc）等函数来获取动态分配内存的实际大小，从而分析内存碎片情况。
测试代码示例

#include <iostream>
#include <chrono>
// 原始队列实现（假设已存在）
// class OriginalQueue { /*... */ }; 

int main() {
    const int numOperations = 1000000;
    {
        auto start = std::chrono::high_resolution_clock::now();
        OriginalQueue originalQueue;
        for (int i = 0; i < numOperations; ++i) {
            originalQueue.enqueue(i);
        }
        for (int i = 0; i < numOperations; ++i) {
            originalQueue.dequeue();
        }
        auto end = std::chrono::high_resolution_clock::now();
        auto duration = std::chrono::duration_cast<std::chrono::milliseconds>(end - start).count();
        std::cout << "Original Queue time: " << duration << " ms" << std::endl;
    }
    {
        auto start = std::chrono::high_resolution_clock::now();
        Queue<int> optimizedQueue;
        for (int i = 0; i < numOperations; ++i) {
            optimizedQueue.enqueue(i);
        }
        for (int i = 0; i < numOperations; ++i) {
            optimizedQueue.dequeue();
        }
        auto end = std::chrono::high_resolution_clock::now();
        auto duration = std::chrono::duration_cast<std::chrono::milliseconds>(end - start).count();
        std::cout << "Optimized Queue time: " << duration << " ms" << std::endl;
    }
    return 0;
}

通过上述测试，可以对比出优化前后队列在时间和内存占用方面的性能差异，直观地看到智能指针和内存池技术对性能的提升。

星途面试题库

面试题：C++ 优化自定义队列的内存管理

知识考点

面试题答案

优化思路

关键代码片段

性能对比分析方法