手写单向队列性能秒杀std::queue

程序员文章站 2022-03-14 15:05:15

...

std::queue即单向队列，是一种先入先出的FIFO队列。具有以下特点：

只允许从队尾插入元素，从队头删除元素
先进先出(First In First Out)
不允许在中间部位进行操作

一共6个函数front()、back()、push()、pop()、empty()、size()，自己手写实现，也是比较简单的。

接下来，我们就手写实现一个定制的queue队列，然后将其与std::queue性能进行对比。

一、IORequestQueue队列类实现

IORequestQueue.h

#ifndef IOREQUESTQUEUE_H
#define IOREQUESTQUEUE_H

#include <assert.h>

struct IORequest
{
    IORequest* p;
    int data;
    int ioType;
    unsigned int requestIndex;
};

class IORequestQueue
{
public:
    IORequestQueue()
        : pHead(nullptr),
          pTail(nullptr),
          count(0)
    {}

    // 队列是否为空
    bool empty() const
    {
        return (pHead == nullptr);
    }

    // 返回队列中元素个数
    size_t size() const
    {
        return count;
    }

    // 返回队头元素
    IORequest* front()
    {
        assert(!empty());
        return pHead;
    }

    // 返回队尾元素
    IORequest* back()
    {
        assert(!empty());
        return pTail;
    }

    // 将变量request从队列尾入队
    void push(IORequest* request)
    {
        request->p = nullptr;
        if (pHead == nullptr)
        {
            assert(pTail == nullptr);
            pHead = request;
        }
        else
        {
            assert(pTail != nullptr);
            pTail->p = request;
        }
        pTail = request;
        count++;
    }

    // 将队头元素弹出
    void pop()
    {
        assert(!empty());
        pHead = pHead->p;
        if (pHead == nullptr)
        {
            pTail = nullptr;
        }
        count--;
    }

private:
    IORequest* pHead;
    IORequest* pTail;
    size_t count;
};

#endif // IOREQUESTQUEUE_H

struct IORequest结构体是需要加入到队列中的元素类型，其中IORequest* p为指向下一个元素的指针，其余均为测试成员变量。

IORequestQueue类是队列实现，分别参考std::queue实现了6个函数，基本原理是记录首尾元素的地址，其间各元素之间依靠IORequest* p进行连接。

二、IORequestQueue与std::queue性能对比

对IORequestQueue与std::queue进行测试，main.cpp如下：

#include <QCoreApplication>
#include <queue>
#include <QDebug>
#include "IORequestQueue.h"
#include "CTimer.h"

void testStdQueue(std::vector<IORequest>& requests)
{
    /***********************测试入队*************************/
    CTimer timer;
    timer.reset();
    std::queue<IORequest*> stdQueue;
    for (unsigned int i = 0; i < requests.size(); i++) // 将IO请求添加到std::queue队列中
    {
        stdQueue.push(&requests[i]);
    }
    double elapsed = timer.end();
    qDebug() << "std::queue push:" << elapsed << "us";

    /***********************测试出队*************************/
    timer.reset();
    for (unsigned int i = 0; i < requests.size(); i++) // 从std::queue出队列
    {
        IORequest* req = stdQueue.front(); // 返回队头元素
        stdQueue.pop(); // 将队头元素弹出
    }
    elapsed = timer.end();
    qDebug() << "std::queue pop:" << elapsed << "us";
}

void testIOQueue(std::vector<IORequest>& requests)
{
    /***********************测试入队*************************/
    CTimer timer;
    timer.reset();
    IORequestQueue ioQueue;
    for (unsigned int i = 0; i < requests.size(); i++) // 将IO请求添加到IORequestQueue队列中
    {
        ioQueue.push(&requests[i]);
    }
    double elapsed = timer.end();
    qDebug() << "IORequestQueue push:" << elapsed << "us";

    /***********************测试出队*************************/
    timer.reset();
    for (unsigned int i = 0; i < requests.size(); i++) // 从IORequestQueue出队列
    {
        IORequest* req = ioQueue.front(); // 返回队头元素
        ioQueue.pop(); // 将队头元素弹出
    }
    elapsed = timer.end();
    qDebug() << "IORequestQueue pop:" << elapsed << "us";
}

int main(int argc, char *argv[])
{
    QCoreApplication a(argc, argv);

    // 准备测试元素10000个
    std::vector<IORequest> requests;
    for (unsigned int index = 0; index < 10000; index++)
    {
        IORequest req;
        req.data = 0;
        req.ioType = 0;
        req.requestIndex = index;
        requests.push_back(req);
    }

    testStdQueue(requests); // 测试std::queue
    testIOQueue(requests);  // 测试IORequestQueue

    return a.exec();
}