STL 之 vector 查找性能优化

如果一个数组元素不多，就没必要做优化了。这里要说的是一个大的数组，在进行遍历查找元素的时候，优化和没有优化的效果还是可以用肉眼看得出来的，下面是一个简单的例子：

// vertor_test.cpp : 定义控制台应用程序的入口点。
//

#include "stdafx.h"
#include <iostream>
#include <vector>
#include <string>
#include <sstream>
#include <time.h>

using namespace std;

string int2str(int n)
{
	stringstream ss;
	ss << n;
	string str = "string" + ss.str();
	return str;
}

//class CData
class CData
{
public:
	int id;
	string name;
public:
	CData(int _id,string _name)
	{
		id = _id;
		name = _name;
	}
};

int vector_find(int key, 
		vector<CData>::iterator itrBegin,
		vector<CData>::iterator itrEnd,
		vector<CData>::iterator & itr)
{
	itrEnd -= 1;
	vector<CData>::iterator itrMid = itrBegin + (itrEnd-itrBegin)/2;
	int count = 0;
	while(itrBegin <= itrEnd)
	{
		count++;
		if(itrMid->id == key)
		{
			itr = itrMid;
			cout<<"total search count:"<<count<<endl;
			return true;
		}
		else
		{
			if(itrMid->id < key){
				itrBegin = itrMid + 1;
			}
			else{
				itrEnd = itrMid - 1;
			}
		}
		itrMid = itrBegin + (itrEnd - itrBegin)/2;
	}
	itr = itrEnd;
	return false;
}


int main()
{
	//构建一个大数组
	vector<CData> vect;
	for(int i = 0; i<100000; i++)
	{
		CData test(i, int2str(i));
		vect.push_back(test);
	}
	cout<<"vector has builded!\r\n"<<endl;

	//常规遍历方式耗时统计
	cout << "default find mode:" << endl;
	clock_t start = clock();
	vector<CData>::iterator it = vect.begin();
	while(it != vect.end())
	{
		if(it->id == 9999)
		{
			cout << "id : "<< it->id << "\tname : " << it->name << endl;
			break;
		}
		it++;
	}
	clock_t finish = clock();
	cout << "take time(s):" << (double)(finish-start)/CLOCKS_PER_SEC << "\n";


	//优化后的遍历方式耗时统计
	cout << "\r\nnew find mode:" << endl;	
	clock_t start1 = clock();
	vector<CData>::iterator itr;
	if(vector_find(9999, vect.begin(), vect.end(), itr))
	{
		cout << "id : "<< itr->id << "\tname : " << itr->name << endl;
	}
	else
	{
		cout << "not found!" << endl;
	}
	clock_t finish1 = clock();
	cout << "take time(s):" << (double)(finish1-start1)/CLOCKS_PER_SEC << "\n";

	getchar();
	return 0;
}

打印结果：（常规遍历耗时0.019秒，优化过的耗时：0.003秒）