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

本文主要是介绍手写单向队列性能秒杀std::queue，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

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::queuetestIOQueue(requests);  // 测试IORequestQueuereturn a.exec();
}