C++ vector unordered_map速度对比（含迭代器）

下面这段程序是我进行的一个对比实验，数组的维数是3000，重复500000次，统计总耗时（使用Release模式，开启O2优化）。

#include<iostream>
#include<vector>
#include<ctime>
#include<unordered_set>

#pragma GCC optimize(2)
using namespace std;

int main()
{
    int vector_size = 3000;
    int loop_size = 500000;
    int seed = (unsigned)time(NULL);
    srand(seed);

    int array_a[vector_size];
    for(int i = 0; i < vector_size;i++ )
    {
        array_a[i] = 0;
    }
    for(int i = 1; i < vector_size; i = i + 10 )
    // 有10%的元素为1，90%的元素为0
    {
        array_a[i] = 1;
    }
    vector<int> vector_array(vector_size, 0);
    unordered_set<int> unordered_array;
    for(int i = 0; i < vector_size; i++)
    {
        vector_array[i] = array_a[i];
        if(array_a[i] == 1)
        {
            unordered_array.insert(i);
        }
    }


    clock_t start_time1 = clock();
    for(int j = 0; j < loop_size; j++)
    for(int i = 0; i < vector_size; i++)
    {
        if(vector_array[i] == 1)
        {
            int a = 1;
//            vector_array[i]++;
            vector_array[i]+=1;
//            ++vector_array[i];
            //cout<<1;
        }
    }
    clock_t end_time1 = clock();

    clock_t start_time2 = clock();
//    for(int j = 0; j < loop_size; j++)
//    for(int i = 0; i < vector_size; i++)
//    {
//        if(unordered_array.find(i) != unordered_array.end())
//        {
//            int b = 1;
//            //very time-consuming
//            //cout<<2;
//        }
//    }
    clock_t end_time2 = clock();

    clock_t start_time3 = clock();
    for(int j = 0; j < loop_size; j++)
    for(auto iter = unordered_array.begin(); iter != unordered_array.end(); iter++)
    {
        int c = 1;
        //*iter += 1;
        //cout<<3;
    }
    clock_t end_time3 = clock();

    clock_t start_time4 = clock();
    for(int j = 0; j < loop_size; j++)
        for(auto iter = vector_array.begin(); iter != vector_array.end(); iter++)
        {
            int d = 1;
            distance(vector_array.begin(),iter);
            *iter+=1;
        }
    clock_t end_time4 = clock();

    cout<<endl;
    cout<<(double)(end_time1-start_time1)<<endl;
    cout<<(double)(end_time2-start_time2)<<endl;
    cout<<(double)(end_time3-start_time3)<<endl;
    cout<<(double)(end_time4-start_time4)<<endl;
}

result：

1530
0
210
618

其中

第一个部分是对vector中的元素使用数组下标进行访问并更改；

第二个部分是将vector中值为1的数组下标值存进unordered_set中，然后通过find进行访问；

第三个部分是使用迭代器对unordered_set进行访问；

第四个部分是使用迭代器对vector中的元素进行访问并更改。

从结果上看，虽然unordered_set查找的平均时间复杂度是O(1)，但是在实际操作时，耗时相比数组会多几百倍（这个原因我也不是很清楚，反正就是我做的这个简单的实验得出的结论）；

而使用迭代器对vector进行修改元素的速度相对于使用数组下标速度会更快。

注意事项：

1.c++ 迭代器iterator在改变访问的元素时不能用*iter++的操作，要用 *iter+=1

*iter++会造成指针错乱

2.unordered_set/map的迭代器是只读的，因为如果改变了它的值那么哈希就会发生改变

3.这是从其它博客上看到的，STL重载迭代器的++运算符时，前置形式要快于后置形式

CDemo CDemo::operator++ ()
{  //前置++
    ++n;
    return *this;
}
CDemo CDemo::operator ++(int k)
{  //后置++
    CDemo tmp(*this);  //记录修改前的对象
    n++;
    return tmp;  //返回修改前的对象
}

实验设置可能不够严谨，如有不合理之处希望各位大佬能够评论私信我指出，欢迎交流！

最后

以上就是野性烧鹅为你收集整理的C++ vector unordered_map速度对比（含迭代器）C++ vector unordered_map速度对比（含迭代器）的全部内容，希望文章能够帮你解决C++ vector unordered_map速度对比（含迭代器）C++ vector unordered_map速度对比（含迭代器）所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。