全部栏目

首页 操作系统 后端开发 数据库 前端开发 移动端开发
您的当前位置：首页正文

STL容器类vector,list,deque的比较

2024-11-20 来源：个人技术集锦

STL容器类vector,list,deque的比较

 

转载自：

 

 

C++的STL模板库中提供了3种容器类：vector,list,deque
对于这三种容器，在觉得好用的同时，经常会让我们困惑应该选择哪一种来实现我们的逻辑。
在少量数据操作的程序中随便哪一种用起来感觉差别并不是很大，
但是当数据达到一定数量后，会明显感觉性能上有很大差异。

本文就试图从介绍，以及性能比较两个方面来讨论这个问题。

 

 

vector - 会自动增长的数组

 

list - 擅长插入删除的链表

有黑必有白，世界万物都是成对出现的。
链表对于数组来说就是相反的存在。
数组本身是没有动态增长能力的（程序中也必须重新开辟内存来实现），
而链表强悍的就是动态增长和删除的能力。
但对于数组强悍的随机访问能力来说的话，链表却很弱。

list是一个双向链表的实现。
为了提供双向遍历的能力，list要比一般的数据单元多出两个指向前后的指针。
这也是没办法的，毕竟现在的PC内存结构就是一个大数组，
链表要在不同的环境中实现自己的功能就需要花更多空间。

list提供了push_back，push_front，pop_back，pop_front四个方法
来方便操作list的两端数据的增加和删除，不过少了vector的at和[]运算符的
随机访问数据的方法。并不是不能实现，而是list的设计者
并不想让list去做那些事情，因为他们会做得非常差劲。

对于list来说，清除容器内所有的元素是一件苦力活，
因为所有数据单元的内存都不连续，list只有一个一个遍历来删除。

 

deque - 拥有vector和list两者优点的双端队列

 

性能竞技场

为了能更好地进行比较，我们让静态数组（程序中写死的）和
动态数组（程序中new出来的）也参加了部分竞技。

竞技项目：

  • 　初始化：对于静态和动态数组，逐一赋值，对于容器，push_back插入
  • 前向遍历：从0到n-1，每个数据自加1
  • 后向遍历：从n-1到0，每个数据自减1
  • 随机访问：在0到n-1中，随机抽取一定数量的数据进行读取
  • 后端插入：用push_back在后端插入一定数量的数据
  • 后端移除：用pop_back在后端移除一定数量的数据
  • 前端插入：用push_front在前端插入一定数量的数据
  • 前端移除：用pop_front在前端移除一定数量的数据
  • 中间插入：用insert在中间插入一定数量的数据
  • 中间移除：用erase在中间移除一定数量的数据
  • 反初始化：对于静态和动态数组，ZeroMemory删除所有数据，对于容器，调用clear方法

规则：

  • vector，list，deque都调用默认的构造函数来创建
  • 数组和容器的数据项都是1,000,000个
  • 前端和后端插入的数据项是10,000个
  • 前端和后端删除的数据项是10,000个
  • 随机访问的数据项是10,000个
  • 数据类型采用int型
  • 计时采用RDTSC高精度计时器来计时
  • 随机访问的数据的位置序列在测试前随机生成，所有数组和容器都采用这个序列
  • 测试采用Debug版(Release版会对代码进行优化，可能会对测试产生一定的影响)
  • 测试3次，取平均值

测试机配置：
Intel(R) Core(TM)2 CPU T7400 2.16GHz 2.16GHz
2.00GB内存

测试结果：（单位 秒）

测试项目静态数组动态数组vectorlistdeque备注
　初始化0.005510.004610.2071.300.352list每个数据项都有附加数据，速度稍慢了一些
前向遍历0.003810.005490.07960.07560.0713 
后向遍历0.004220.004780.8850.8790.690 
随机访问0.0003340.0003420.001191480.0115list把时间都耗在了找寻相应数据上
后端插入N/AN/A0.001920.01280.00260 
后端移除N/AN/A0.001310.02930.00194 
前端插入N/AN/A10.20.01280.00547vector对前端操作很苦手啊
前端移除N/AN/A10.30.02970.00135同上
中间插入N/AN/A195187764看似万能的deque的最大弱点，因为复杂的结构导致中间数据操作带来的复杂性大大增加，体现在操作时间是其他两个的几倍
中间移除N/AN/A195209753同上
反初始化0.001390.002900.00001060.6930.305vector貌似是直接抛弃内存的，其他两个就没那么简单了

 

性能总结与使用建议

测试项目静态数组动态数组vectorlistdeque
　初始化★★★★★★★★★★★★★★☆★★★☆☆★★★★☆
前向遍历★★★★★★★★★★★★★★☆★★★★☆★★★★☆
后向遍历★★★★★★★★★★★★★★☆★★★★☆★★★★☆
随机访问★★★★★★★★★★★★★★☆★☆☆☆☆★★★☆☆
后端插入N/AN/A★★★★★★★★★☆★★★★★
后端移除N/AN/A★★★★★★★★★☆★★★★★
前端插入N/AN/A★★☆☆☆★★★★☆★★★★★
前端移除N/AN/A★★☆☆☆★★★★☆★★★★★
中间插入N/AN/A★★☆☆☆★★☆☆☆★☆☆☆☆
中间移除N/AN/A★★☆☆☆★★☆☆☆★☆☆☆☆
反初始化★★★★★★★★★★★★★★★★★★★☆★★★★☆

一些使用上的建议：
Level 1 - 仅仅作为Map使用：采用静态数组
Level 2 - 保存定长数据，使用时也是全部遍历：采用动态数组（长度一开始就固定的话静态数组也行）
Level 3 - 保存不定长数组，需要动态增加的能力，侧重于寻找数据的速度：采用vector
Level 3 - 保存不定长数组，需要动态增加的能力，侧重于增加删除数据的速度：采用list
Level 4 - 对数据有复杂操作，即需要前后增删数据的能力，又要良好的数据访问速度：采用deque
Level 5 - 对数据中间的增删操作比较多：采用list，建议在排序的基础上，批量进行增删可以对运行效率提供最大的保证
Level 6 - 上述中找不到适合的：组合STL容器或者自己建立特殊的数据结构来实现

 

#include <string>

#include <iostream>

#include <iomanip>

#include <vector>

#include <list>

#include <set>

#include <map>

#include <deque>

#include <algorithm>

#include <windows.h>

 

using namespace std;

 

inline unsigned __int64 GetTick()

{

    __asm RDTSC

}

 

// 定数の定義

const int ARRAY_SIZE = 1000 * 1000 * 1;

const int INSERT_NUM = 1000 * 10;

const int DELETE_NUM = INSERT_NUM;

const int READ_RANDOM_NUM = 1000 * 10;

const int VALUE_OFFSET = 0;

typedef int TARGET_TYPE;

typedef void (*FUNC)();

 

 

// グローバル変数の定義

__int64 g_second;

int g_rand_list[READ_RANDOM_NUM];

TARGET_TYPE g_static_array[ARRAY_SIZE];

TARGET_TYPE* g_dynamic_array;

TARGET_TYPE stub;

std::vector <TARGET_TYPE> g_vector;

std::list <TARGET_TYPE> g_list;

std::deque <TARGET_TYPE> g_deque;

 

 

// 関数定義

__int64 GetPerSecondTick();

double GetSecond(__int64 beginTick);

void init();

void uninit();

void start();

void clear();

void check();

void calctime(FUNC f, string msg);

void DebugOut(string str);

void AddOneBySelf(TARGET_TYPE& tt);

void SubOneBySelf(TARGET_TYPE& tt);

 

 

void StaticArrayCheck();

void DynamicArrayCheck();

void VectorCheck();

void ListCheck();

void DequeCheck();

 

 

void StaticArrayInit();

void DynamicArrayInit();

void VectorInit();

void ListInit();

void DequeInit();

 

 

void StaticArrayUninit();

void DynamicArrayUninit();

void VectorUninit();

void ListUninit();

void DequeUninit();

 

 

void StaticArrayForEach();

void DynamicArrayForEach();

void VectorForEach();

void ListForEach();

void DequeForEach();

 

 

void StaticArrayForEachRight();

void DynamicArrayForEachRight();

void VectorForEachRight();

void ListForEachRight();

void DequeForEachRight();

 

 

void StaticArrayForEachRandom();

void DynamicArrayForEachRandom();

void VectorForEachRandom();

void ListForEachRandom();

void DequeForEachRandom();

 

 

void VectorInsertAtBack();

void ListInsertAtBack();

void DequeInsertAtBack();

 

 

void VectorDeleteAtBack();

void ListDeleteAtBack();

void DequeDeleteAtBack();

 

 

void VectorInsertAtFront();

void ListInsertAtFront();

void DequeInsertAtFront();

 

 

void VectorDeleteAtFront();

void ListDeleteAtFront();

void DequeDeleteAtFront();

 

 

 

void VectorInsertAtMiddle();

void ListInsertAtMiddle();

void DequeInsertAtMiddle();

 

 

void VectorDeleteAtMiddle();

void ListDeleteAtMiddle();

void DequeDeleteAtMiddle();

 

 

void init()

{

    g_second = GetPerSecondTick();

    g_dynamic_array = new TARGET_TYPE[ARRAY_SIZE];

    srand((int)GetTick());

    for (int i = 0; i < READ_RANDOM_NUM; i++)

    {

        g_rand_list[i] = MulDiv(ARRAY_SIZE - 1, rand(), RAND_MAX);

    }

 

    calctime(StaticArrayInit, "StaticArrayInit: ");

    calctime(DynamicArrayInit, "DynamicArrayInit: ");

    calctime(VectorInit, "VectorInit: ");

    calctime(ListInit, "ListInit: ");

    calctime(DequeInit, "DequeInit: ");

    cout << endl;

}

 

void uninit()

{

    calctime(StaticArrayUninit, "StaticArrayUninit: ");

    calctime(DynamicArrayUninit, "DynamicArrayUninit: ");

    calctime(VectorUninit, "VectorUninit: ");

    calctime(ListUninit, "ListUninit: ");

    calctime(DequeUninit, "DequeUninit: ");

    cout << endl;

}

 

void check()

{

    StaticArrayCheck();

    DynamicArrayCheck();

    VectorCheck();

    ListCheck();

    DequeCheck();    

}

 

void start()

{

    calctime(StaticArrayForEach, "StaticArrayForEach: ");

    calctime(DynamicArrayForEach, "DynamicArrayForEach: ");

    calctime(VectorForEach, "VectorForEach: ");

    calctime(ListForEach, "ListForEach: ");

    calctime(DequeForEach, "DequeForEach: ");

    cout << endl;

    

    calctime(StaticArrayForEachRight, "StaticArrayForEachRight: ");

    calctime(DynamicArrayForEachRight, "DynamicArrayForEachRight: ");

    calctime(VectorForEachRight, "VectorForEachRight: ");

    calctime(ListForEachRight, "ListForEachRight: ");

    calctime(DequeForEachRight, "DequeForEachRight: ");

    cout << endl;

    

    calctime(StaticArrayForEachRandom, "StaticArrayForEachRandom: ");

    calctime(DynamicArrayForEachRandom, "DynamicArrayForEachRandom: ");

    calctime(VectorForEachRandom, "VectorForEachRandom: ");

    calctime(ListForEachRandom, "ListForEachRandom: ");

    calctime(DequeForEachRandom, "DequeForEachRandom: ");

    cout << endl;

    

    

    calctime(NULL, "");

    calctime(NULL, "");

    calctime(VectorInsertAtBack, "VectorInsertAtBack: ");

    calctime(ListInsertAtBack, "ListInsertAtBack: ");

    calctime(DequeInsertAtBack, "DequeInsertAtBack: ");

    cout << endl;

    

    

    calctime(NULL, "");

    calctime(NULL, "");

    calctime(VectorDeleteAtBack, "VectorDeleteAtBack: ");

    calctime(ListDeleteAtBack, "ListDeleteAtBack: ");

    calctime(DequeDeleteAtBack, "DequeDeleteAtBack: ");

    cout << endl;

    

    

    

    calctime(NULL, "");

    calctime(NULL, "");

    calctime(VectorInsertAtFront, "VectorInsertAtFront: ");

    calctime(ListInsertAtFront, "ListInsertAtFront: ");

    calctime(DequeInsertAtFront, "DequeInsertAtFront: ");

    cout << endl;

    

    

    calctime(NULL, "");

    calctime(NULL, "");

    calctime(VectorDeleteAtFront, "VectorDeleteAtFront: ");

    calctime(ListDeleteAtFront, "ListDeleteAtFront: ");

    calctime(DequeDeleteAtFront, "DequeDeleteAtFront: ");

    cout << endl;

    

    

    

    calctime(NULL, "");

    calctime(NULL, "");

    calctime(VectorInsertAtMiddle, "VectorInsertAtMiddle: ");

    calctime(ListInsertAtMiddle, "ListInsertAtMiddle: ");

    calctime(DequeInsertAtMiddle, "DequeInsertAtMiddle: ");

    cout << endl;

    

    

    calctime(NULL, "");

    calctime(NULL, "");

    calctime(VectorDeleteAtMiddle, "VectorDeleteAtMiddle: ");

    calctime(ListDeleteAtMiddle, "ListDeleteAtMiddle: ");

    calctime(DequeDeleteAtMiddle, "DequeDeleteAtMiddle: ");

    cout << endl;

}

 

 

void clear()

{

    delete g_dynamic_array;

}

 

 

 

 

 

void StaticArrayInit()

{

    for (int i = 0; i < ARRAY_SIZE; i++) g_static_array[i] = i;

}

 

void DynamicArrayInit()

{

    for (int i = 0; i < ARRAY_SIZE; i++) g_dynamic_array[i] = i;

}

 

void VectorInit()

{

    for (int i = 0; i < ARRAY_SIZE; i++) g_vector.push_back(i);

}

 

void ListInit()

{

    for (int i = 0; i < ARRAY_SIZE; i++) g_list.push_back(i);

}

 

void DequeInit()

{

    for (int i = 0; i < ARRAY_SIZE; i++) g_deque.push_back(i);

}

 

 

 

 

 

void StaticArrayUninit()

{

    ZeroMemory(g_static_array, ARRAY_SIZE * sizeof(TARGET_TYPE));

}

 

void DynamicArrayUninit()

{

    ZeroMemory(g_dynamic_array, ARRAY_SIZE * sizeof(TARGET_TYPE));

}

 

void VectorUninit()

{

    g_vector.clear();

}

 

void ListUninit()

{

    g_list.clear();

}

 

void DequeUninit()

{

    g_deque.clear();

}

 

void StaticArrayForEach()

{

    for (int i = 0; i < ARRAY_SIZE; i++) ++g_static_array[i];

}

 

void DynamicArrayForEach()

{

    for (int i = 0; i < ARRAY_SIZE; i++) ++g_dynamic_array[i];

}

 

void VectorForEach()

{

    for_each(g_vector.begin(), g_vector.end(), AddOneBySelf);

}

 

void ListForEach()

{

    for_each(g_list.begin(), g_list.end(), AddOneBySelf);

}

 

void DequeForEach()

{

    for_each(g_deque.begin(), g_deque.end(), AddOneBySelf);

}

 

void StaticArrayForEachRight()

{

    for (int i = ARRAY_SIZE; i > 0; i--) --g_static_array[i - 1];

}

 

void DynamicArrayForEachRight()

{

    for (int i = ARRAY_SIZE; i > 0; i--) --g_dynamic_array[i - 1];

}

 

void VectorForEachRight()

{

    for_each(g_vector.rbegin(), g_vector.rend(), SubOneBySelf);

}

 

void ListForEachRight()

{

    for_each(g_list.rbegin(), g_list.rend(), SubOneBySelf);

}

 

void DequeForEachRight()

{

    for_each(g_deque.rbegin(), g_deque.rend(), SubOneBySelf);

}

 

 

void StaticArrayForEachRandom()

{

    for (int i = 0; i < READ_RANDOM_NUM; i++) stub = g_static_array[g_rand_list[i]];

}

 

void DynamicArrayForEachRandom()

{

    for (int i = 0; i < READ_RANDOM_NUM; i++) stub = g_dynamic_array[g_rand_list[i]];

}

 

void VectorForEachRandom()

{

    for (int i = 0; i < READ_RANDOM_NUM; i++) stub = g_vector[g_rand_list[i]];

}

 

void ListForEachRandom()

{

    list<TARGET_TYPE>::iterator iter;

 

    for (int i = 0; i < READ_RANDOM_NUM; i++)

    {

        iter = g_list.begin();

        for (int j = 0; j < g_rand_list[i]; j++) ++iter;

        stub = (*iter);

    }

}

 

void DequeForEachRandom()

{

    for (int i = 0; i < READ_RANDOM_NUM; i++) stub = g_deque[g_rand_list[i]];

}

 

 

 

void StaticArrayCheck()

{

    for (int i = 0; i < ARRAY_SIZE; i++)

    {

        if (g_static_array[i] != (i + VALUE_OFFSET))

        {

            cerr << "StaticArrayCheck NG:" << i << " = " << g_static_array[i] << endl;

            return;

        }

    }

}

 

void DynamicArrayCheck()

{

    for (int i = 0; i < ARRAY_SIZE; i++)

    {

        if (g_dynamic_array[i] != (i + VALUE_OFFSET))

        {

            cerr << "DynamicArrayCheck NG:" << i << " = " << g_dynamic_array[i] << endl;

            return;

        }

    }

}

 

void VectorCheck()

{

    vector<TARGET_TYPE>::iterator iter;

    int i = 0;

 

    for (iter = g_vector.begin(); iter != g_vector.end(); ++iter, ++i)

    {

        if ((*iter) != (i + VALUE_OFFSET))

        {

            cerr << "VectorCheck NG:" << i << " = " << (*iter) << endl;

            return;

        }

    }

}

 

void ListCheck()

{

    list<TARGET_TYPE>::iterator iter;

    int i = 0;

 

    for (iter = g_list.begin(); iter != g_list.end(); ++iter, ++i)

    {

        if ((*iter) != (i + VALUE_OFFSET))

        {

            cerr << "ListCheck NG:" << i << " = " << (*iter) << endl;

            return;

        }

    }

}

 

void DequeCheck()

{

    deque<TARGET_TYPE>::iterator iter;

    int i = 0;

 

    for (iter = g_deque.begin(); iter != g_deque.end(); ++iter, ++i)

    {

        if ((*iter) != (i + VALUE_OFFSET))

        {

            cerr << "DequeCheck NG:" << i << " = " << (*iter) << endl;

            return;

        }

    }

}

 

 

 

void VectorInsertAtBack()

{

    for (int i = 0; i < INSERT_NUM; i++) g_vector.push_back((TARGET_TYPE)0);

}

 

void ListInsertAtBack()

{

    for (int i = 0; i < INSERT_NUM; i++) g_list.push_back((TARGET_TYPE)0);

}

 

void DequeInsertAtBack()

{

    for (int i = 0; i < INSERT_NUM; i++) g_deque.push_back((TARGET_TYPE)0);

}

 

void VectorDeleteAtBack()

{

    for (int i = 0; i < DELETE_NUM; i++) g_vector.pop_back();

}

 

void ListDeleteAtBack()

{

    for (int i = 0; i < DELETE_NUM; i++) g_list.pop_back();

}

 

void DequeDeleteAtBack()

{

    for (int i = 0; i < DELETE_NUM; i++) g_deque.pop_back();

}

 

 

 

 

void VectorInsertAtFront()

{

    for (int i = 0; i < INSERT_NUM; i++) g_vector.insert(g_vector.begin(), (TARGET_TYPE)0);

}

 

void ListInsertAtFront()

{

    for (int i = 0; i < INSERT_NUM; i++) g_list.push_front((TARGET_TYPE)0);

}

 

void DequeInsertAtFront()

{

    for (int i = 0; i < INSERT_NUM; i++) g_deque.push_front((TARGET_TYPE)0);

}

 

 

 

void VectorDeleteAtFront()

{

    for (int i = 0; i < DELETE_NUM; i++) g_vector.erase(g_vector.begin());

}

 

void ListDeleteAtFront()

{

    for (int i = 0; i < DELETE_NUM; i++) g_list.pop_front();

}

 

void DequeDeleteAtFront()

{

    for (int i = 0; i < DELETE_NUM; i++) g_deque.pop_front();

}

 

 

void VectorInsertAtMiddle()

{

    vector<TARGET_TYPE>::iterator iter;

    for (int i = 0; i < INSERT_NUM; i++)

    {

        iter = g_vector.begin();

        for (unsigned int j = 0; j < g_vector.size() / 2; j++) ++iter;

        g_vector.insert(iter, (TARGET_TYPE)0);

    }

}

 

void ListInsertAtMiddle()

{

    list<TARGET_TYPE>::iterator iter;

    for (int i = 0; i < INSERT_NUM; i++)

    {

        iter = g_list.begin();

        for (unsigned int j = 0; j < g_list.size() / 2; j++) ++iter;

        g_list.insert(iter, (TARGET_TYPE)0);

    }

}

 

void DequeInsertAtMiddle()

{

    deque<TARGET_TYPE>::iterator iter;

    for (int i = 0; i < INSERT_NUM; i++)

    {

        iter = g_deque.begin();

        for (unsigned int j = 0; j < g_deque.size() / 2; j++) ++iter;

        g_deque.insert(iter, (TARGET_TYPE)0);

    }

}

 

 

void VectorDeleteAtMiddle()

{

    vector<TARGET_TYPE>::iterator iter;

    for (int i = 0; i < DELETE_NUM; i++)

    {

        iter = g_vector.begin();

        for (unsigned int j = 0; j < g_vector.size() / 2; j++) ++iter;

        g_vector.erase(iter);

    }

}

 

void ListDeleteAtMiddle()

{

    list<TARGET_TYPE>::iterator iter;

    for (int i = 0; i < DELETE_NUM; i++)

    {

        iter = g_list.begin();

        for (unsigned int j = 0; j < g_list.size() / 2; j++) ++iter;

        g_list.erase(iter);

    }

}

 

void DequeDeleteAtMiddle()

{

    deque<TARGET_TYPE>::iterator iter;

    for (int i = 0; i < DELETE_NUM; i++)

    {

        iter = g_deque.begin();

        for (unsigned int j = 0; j < g_deque.size() / 2; j++) ++iter;

        g_deque.erase(iter);

    }

}

 

 

 

 

void calctime(FUNC f, string msg)

{

    __int64 t1;

    

    if (f != NULL)

    {

        t1 = GetTick();

        (*f)();

        // cerr << msg << GetSecond(t1) << endl;

        cout << GetSecond(t1) << ", ";

    }

    else

    {

        // cerr << msg << "N/A" << endl;

        cout << "N/A, ";

    }

}

 

__int64 GetPerSecondTick()

{

    __int64 t1;

    

    t1 = GetTick();

    Sleep(1000);

    return (GetTick() - t1);

}

 

double GetSecond(__int64 beginTick)

{

    return (double)(GetTick() - beginTick) / (double)g_second;

}

 

void AddOneBySelf(TARGET_TYPE& tt)

{

    ++tt;

}

 

void SubOneBySelf(TARGET_TYPE& tt)

{

    --tt;

}

 

void DebugOut(string str)

{

    cerr << str << endl;

}

 

 

int main(char** argv, int argc)

{

    // 初期化

    init();

 

    // 実行開始

    start();

    

    // チェック

    check();

    

    // 資源回収

    uninit();

    

    // クリア

    clear();

 

    return 0;

}

 
显示全文