在写代码的时候，即使编程老手经常会遇到一个不知道如何抉择的事情，面对查询的需求如何选择容器，容器的大小等因素也会困扰我们的选择。为什么呢？新手面对查询往往会直接选择
map
，因为
map
是内部是支持查询函数的
,
但老手知道
map
是通过复杂性换取查询的性能的（
map
的实现往往是红黑树），那如果要保存的数据个数不多呢，是否值得使用
map
这样的容器呢？
最近两天写了几行短小的代码，针对这个问题进行了一测试，测试对
vector,map,hash_map
三种有代表性的容器进行了测试，测试容器的长度为
10
，
50
，
100
，
200
，
500
，
1000.
测试的方法是使用
int
作为测试对象，
vector
的查询使用顺序查找，
map
和
hash_map
的查询使用容器的
find
函数。为了能表现出测试结果，查询测试了
1000000
次，开始时，查询的数据我用
rand
函数产生随机数作为查询对象，后来发现好像对查询干扰过大，最后还是使用了顺序数据作为查询对象。
由于测试结果数据枯燥，我在后面再附录上测试的程序。每个测试都作了
3
次，取平均值给大家看看结果。测试使用的是
STLPort
，
Visual Studio 2003
的
DEBUG
版本。测试结果如下：
表1
各种容器的耗时
|
容器容纳的尺寸 |
vector(ms) |
map(ms) |
hash_map(ms) |
|
10 |
578 |
1333 |
1333 |
|
20 |
1078 |
1562 |
1328 |
|
50 |
2520 |
1921 |
1328 |
|
100 |
4953 |
2176 |
1328 |
|
200 |
9806 |
2422 |
1322 |
|
500 |
24437 |
2739 |
1323 |
|
1000 |
48827 |
2942 |
1317 |
在容器的数量小于
20
个的时候，
vector
的还表现良好，即使有查询的需求，也可以考虑直接选择
vector
，但当容器的数据超过
50
个以后、，
map
的优势就显示出来了。而且当容器的容量继续增大后，
map
的查询速度增加也很平稳，当然这和
map
的实现是采取红黑树，查询的时间复杂度是
log2(N)
有关。而且
hash_map
（
unorder_map
）表现只能用稳定高效形容。所以在大部分时候
hash_map
是我们的首选。
由于测试中有其他的干扰信息，所以测试数据不等于实际效率。这个数据只是一个参考数据。但是我们大致可以得到一些感觉，容器的尺寸小于
20
时，我们大可以选择
vector
作为容器。不用选择更加复杂的容器。如果要容纳的对象个数大于
50
而且需要查询的时候，
vector
就不要选择了。用更快的容器。对于
map
和
hash_map
，优先选择
hash_map
。当然我说的是
STLport
的
hash_map
，不是微软默认的。我在前面《
慎用
Visual Studio C++
默认的
hash_map
》的文章说明过这个问题了。在此不复述了。
同时测试的是很我还测试一个其他问题，就是
swtich case
的性能，发现
swtich case
的性能基本不会随
case
的条件增加而增加耗时（懂汇编的要笑话我了，哈哈），而且非常非常非常非常快，所以，如果有时候你追求的极限性能的目标，而且可以用
swtich case
的时候，可以考虑用这个比较“丑陋”一点的写法。
BTW:
《
c++
编程规范》一书的第
76
条是，默认使用
vector,
否则使用其他容器。其中提到了选择容器的
3
个原则：
1.
正确性事，简单，清晰是第一位的
2.
在必要时考虑效率
3.
尽可能编写事务安全的代码。（注意插入和删除的迭代器失效问题的影响）
附录测试代码如下，我懒得写注释了。偷懒。
#include <stdio.h>
#include <string.h>
#include <time.h>
#include <math.h>
#include <stdlib.h>
#include <conio.h>
#include <iostream>
#include <fstream>
#include <memory.h>
#include <map>
#include <hash_map>
#include <ace/OS.h>
#include <ace/Time_Value.h>
#include <ace/SString.h>
#include <ace/Shared_Memory_MM.h>
#include <ace/Shared_Memory_SV.h>
#include <ace/Mem_Map.h>
#include <ace/SV_Shared_Memory.h>
using namespace std;
const size_t TEST_NUMBER = 100000*10;
void test_findwith_container(size_t container_len)
{
vector<int> int_vector;
map<int,int> int_map;
hash_map<int,int> int_hash;
int_vector.resize(container_len);
int_hash.resize(container_len);
//
for(size_t i = 0;i<container_len;i++)
{
int_vector[i]=i;
int_map[i] = i;
int_hash[i]=i;
}
ACE_Time_Value tvStart(0);
ACE_Time_Value tvEnd(0);
ACE_Time_Value tvPassTime(0);
tvStart = ACE_OS::gettimeofday();
for (size_t i= 0;i<TEST_NUMBER;++i)
{
int find_number = i%container_len;
//
for(size_t j = 0;j<container_len;j++)
{
if (int_vector[j]==find_number)
{
break;
}
}
}
tvEnd = ACE_OS::gettimeofday();
tvPassTime = tvEnd - tvStart;
cout<<"test vector gettimeofday :"<<tvPassTime.msec()<<" "<<endl;
tvStart = ACE_OS::gettimeofday();
for (size_t i= 0;i<TEST_NUMBER;++i)
{
int find_number = i%container_len;
int_map.find(find_number);
}
tvEnd = ACE_OS::gettimeofday();
tvPassTime = tvEnd - tvStart;
cout<<"test map gettimeofday :"<<tvPassTime.msec()<<" "<<endl;
tvStart = ACE_OS::gettimeofday();
for (size_t i= 0;i<TEST_NUMBER;++i)
{
int find_number = i%container_len;
int_hash.find(find_number);
}
tvEnd = ACE_OS::gettimeofday();
tvPassTime = tvEnd - tvStart;
cout<<"test hash gettimeofday :"<<tvPassTime.msec()<<" "<<endl;
}
//
int main(int argc, ACE_TCHAR* argv[])
{
for (int j=0;j<3;++j)
{
cout<<"container length = 10 "<<endl;
test_findwith_container(10);
cout<<"container length = 20 "<<endl;
test_findwith_container(20);
cout<<"container length = 50 "<<endl;
test_findwith_container(50);
cout<<"container length = 100 "<<endl;
test_findwith_container(100);
cout<<"container length = 200 "<<endl;
test_findwith_container(200);
cout<<"container length = 500 "<<endl;
test_findwith_container(500);
cout<<"container length = 1000 "<<endl;
test_findwith_container(1000);
}
_getch();
return 0;
}
http://blog.csdn.net/fullsail/archive/2009/06/27/4303758.aspx