对象池

对象池是为了解决容器内对象被频繁的开辟释放空间而被提出的。在开始了解对象池之前我们来看下面一个代码示例

queue.cpp

#pragma once

template <typename T>
class Queue {
public:
    Queue() { _head = _rear = new QueueItem(); }

    // API
    bool empty() const { return _head == _rear; }
    void push(const T &value) {
        QueueItem *item = new QueueItem(value);
        _rear->_next = item;
        _rear = item;
    }
    void pop() {
        if (empty()) {
            return;
        }

        QueueItem *first = _head->_next;
        _head->_next = first->_next;
        if (_head->_next == nullptr) {
            _rear = _head;
        }
        delete first;
        first = nullptr;
    }

private:
    // 节点
    class QueueItem {
    public:
        QueueItem(T data = T()) : _data(data), _next(nullptr) {}

    public:
        T _data;
        QueueItem *_next;
    };

private:
    QueueItem *_head; // 头节点
    QueueItem *_rear; // 尾节点
};

main.cpp

#include "queue.hpp"


int main(){
    Queue<int> q;

    for(int i =0; i < 100000000; ++i){
        q.push(i);
        q.pop();
    }

    return 0;
}

运行结果

$ g++ main.cpp -o main
$ time ./main 

real    0m2.619s
user    0m2.614s
sys     0m0.002s

现在我们来对上面的代码进行改造，增加对象池

#pragma once

#include <iostream>

template <typename T>
class Queue {
public:
    Queue() { _head = _rear = new QueueItem(); }

    // API
    bool empty() const { return _head == _rear; }
    void push(const T &value) {
        QueueItem *item = new QueueItem(value);
        _rear->_next = item;
        _rear = item;
    }
    void pop() {
        if (empty()) {
            return;
        }

        QueueItem *first = _head->_next;
        _head->_next = first->_next;
        if (_head->_next == nullptr) {
            _rear = _head;
        }
        delete first;
        first = nullptr;
    }

private:
    // 节点
    class QueueItem {
    public:
        QueueItem(T data = T()) : _data(data), _next(nullptr) {}

        // 增加对象池
        void *operator new(size_t size) {
            if (_itemPool == nullptr) {
                _itemPool = (QueueItem *)new char[POOL_ITEM_SIZE * sizeof(QueueItem)];
                QueueItem *p = _itemPool;
                for (; p < _itemPool + POOL_ITEM_SIZE - 1; ++p) {
                    p->_next = p + 1;
                }
                p->_next = nullptr;
            }
            QueueItem *p = _itemPool;
            _itemPool = _itemPool->_next;
            return (void *)p;
        }
        void operator delete(void *ptr) {
            QueueItem *p = (QueueItem *)ptr;
            p->_next = _itemPool;
            _itemPool = p;
        }

    public:
        T _data;
        QueueItem *_next;
        static QueueItem *_itemPool;              // 对象池
        static const int POOL_ITEM_SIZE = 100000; // 池的大小
    };

private:
    QueueItem *_head; // 头节点
    QueueItem *_rear; // 尾节点
};

template <typename T>
typename Queue<T>::QueueItem *Queue<T>::QueueItem::_itemPool = nullptr;

运行结果

$ g++ main.cpp -o main
$ time ./main 

real    0m2.676s
user    0m2.674s
sys     0m0.001s

在我测试时池的大小为100000时为最优，后续有时间再进行测试。