std::vector与deque首尾增删及遍历（应用于CListCtrl虚拟列表）混合性能测试

1、简介

  在工作项目中应用MFC类库的CListCtrl刷新加载数据，一开始是用InsertItem()、SetItemText()和DeleteItem()等成员函数来实现数据在列表视图控件中的新增和删除（最多显示500条数据）。在实施运行过程中发现，当数据量较多且显示频率快时，程序占用cpu高达30%以上，且偶尔会出现假面假死问题（其他图标按钮、右键菜单等功能不能使用），于是在网上搜索“MFC CListCtrl占用cpu高”，找到了“虚拟列表”技术支持，经实现、运行、观察，在同样的环境下cpu占用确实减缓了。
  随之而来的问题是虚拟列表需要一个能存储500条数据的数据结构，数据顺序排列（不是sort哦），且数据结构可以在首尾实现增删（项目需求是首部增、尾部删，最新数据在最前面，虚拟列表请求数据并加载在列表控件中时，新数据始终在上方，就像“U”形栈一样）。
  于是想到了标准模板库下vector向量和deque双端队列两个容器满足基本所需，相比较而言，vector遍历（随机访问）性能更高，deque首尾增删性能更高，各有所长。而所要实现的功能是新增一条数据（容器存储上限500），就遍历容器里所有数据（加载到列表控件），既有增删又有遍历，究竟谁的综合性能更高呢（容器满时，增删一次就要遍历取500次数据）？因此决定写一个简单的测试程序看看“增删”及“遍历”混合到一起，两种容器的表现如何。

2、代码

#include <iostream>
#include <Windows.h>
#include <ctime>
#include <deque>
#include <vector>
#include <string>
using namespace std;

#define CNTRSIZE 500 //容器大小（结合项目需求保持不变）
#define AVGCOUNT 5 //平均次数（3、5、7次等均可，次数越大结果越准）
#define LOOPCOUNT 50000 //循环次数（不同大小，混合测试结果也不同）
//int loopArray[6] = {1000, 2000, 5000, 10000, 20000, 50000};

class CListMsg
{
public:
	CListMsg()
	{
		m_strTopic = "";
		m_strData = "";
		m_nImage = 0;
	}

	CListMsg(string strTopic, string strData, short nImage)
	{
		m_strTopic = strTopic;
		m_strData = strData;
		m_nImage = nImage;
	}

	string m_strTopic;
	string m_strData;
	short m_nImage;
};

int main()
{
	string strTopic, strData;
	short nImage;
	time_t tBegin, tEnd, tTotal;//时间戳，计算代码段执行时间
	string strText0 = "(2022-04-27 17:12:41.609) up/9affe44f0000009d/Q6CJwA9U3", strText1 = "[43-54] (177) {\"002\":\"111111\",\"003\":\"18822223333\",\"004\":\"2\",\"001\":\"1\",\"005\":\"22222\",\"006\":\"18811111100\",\"007\":\"3\",\"008\":\"333333\",\"009\":\"18844445555\",\"010\":\"5\",\"011\":\"wyr\",\"012\":\"16178909876\"}";

	//可先单独测试：两种容器“头（增）尾（删）”与“遍历”的耗时时间
	//单独测试结果：据两种容器底层实现及预期结果，vector遍历更快，deque头尾增删更快
	//下面为两种容器的混合测试

	cout << "容器大小：" << CNTRSIZE << "  平均次数：" << AVGCOUNT << "  循环次数：" << LOOPCOUNT <<  endl << endl;

	//向量容器
	tTotal = 0;
	for(UINT nAvg=0; nAvg<AVGCOUNT; nAvg++)
	{
		vector<CListMsg> vecListMsg;//capacity和size都为0

		tBegin = clock();
		for(UINT nLoop=0; nLoop<LOOPCOUNT; nLoop++)
		{
			//插入数据（保证容器大小不超过CNTRSIZE）
			if(vecListMsg.size() >= CNTRSIZE)
			{
				vecListMsg.pop_back();//删除尾部
			}
			vecListMsg.insert(vecListMsg.begin(), CListMsg(strText0, strText1, 2));//头部插入

			//遍历容器所有数据
			for(UINT nSize=0; nSize<vecListMsg.size(); nSize++)
			{
				strTopic = vecListMsg[nSize].m_strTopic;
				strData = vecListMsg[nSize].m_strData;
				nImage = vecListMsg[nSize].m_nImage;
			}
		}
		tEnd = clock();

		time_t tTmp = tEnd - tBegin;
		cout << "vector第" << (nAvg+1) << "次耗时：" << tTmp << "毫秒" << endl;
		tTotal += tTmp;
	}
	double dVagVector = ((double)tTotal) / AVGCOUNT;
	cout << "vector平均耗时：" << dVagVector << "毫秒" << endl << endl;

	//双端队列容器
	tTotal = 0;
	for(UINT nAvg=0; nAvg<AVGCOUNT; nAvg++)
	{
		deque<CListMsg> deqListMsg;

		tBegin = clock();
		for(UINT nLoop=0; nLoop<LOOPCOUNT; nLoop++)
		{
			if(deqListMsg.size() >= CNTRSIZE)
			{
				deqListMsg.pop_back();//删除尾部
			}
			deqListMsg.push_front(CListMsg(strText0, strText1, 2));//头部插入

			for(UINT nSize=0; nSize<deqListMsg.size(); nSize++)
			{
				strTopic = deqListMsg[nSize].m_strTopic;
				strData = deqListMsg[nSize].m_strData;
				nImage = deqListMsg[nSize].m_nImage;
			}
		}
		tEnd = clock();

		time_t tTmp = tEnd - tBegin;
		cout << "deque第" << (nAvg+1) << "次耗时：" << tTmp << "毫秒" << endl;
		tTotal += tTmp;
	}
	double dVagDeque = ((double)tTotal) / AVGCOUNT;
	cout << "deque平均耗时：" << dVagDeque << "毫秒" << endl << endl;

	//测试结果：deque混合测试性能明显优于vector
	double dRatio = dVagVector / dVagDeque;//随LOOPCOUNT增大，dRatio比例变化（越小说明vector相比于deque优势增加/差距减小，越大则说明vector与deque的差距越来越大）
	cout << "dRatio = " << dRatio << endl << endl;
	
	getchar();
	return 0;
}

3、运行结果

  运行环境：Win10-64位 + VS2010-Win32 + Intel® Core™ i5-3470 CPU @ 3.20GHz

4、总结

  通过运行结果可以看出，在混合测试场景下，deque的效率是要远高于vector的。随着时间的推移，数据量增加至容器size预设值后，在每轮增删一次却要完全遍历一次取值的情况下，deque依然占据上风（粗糙的测试：随循环次数增加，vector与deque的平均耗时比值dRatio，并没有出现连续上升或下降）。