c++ - 我在哪种情况下 std::map<A,B> 比排序的 std::vector<std::pair<A,B>> 更快？

Question

我用的是 map在一些代码中存储有序数据。我发现对于巨大的 map ，销毁可能需要一段时间。在我的这段代码中，替换了 map通过 vector<pair>处理时间减少 10000...

最后，我很惊讶，我决定比较map排序的表演vector或 pair .

我很惊讶，因为我找不到 map 的情况比排序的 vector 快的 pair (随机填充，然后排序)...一定有一些情况 map更快....否则提供此类的意义何在？

这是我测试过的:

测试一，比较map填充和销毁 vs vector填充、排序(因为我想要一个排序的容器)和销毁:

#include <iostream>
#include <time.h>
#include <cstdlib>
#include <map>
#include <vector>
#include <algorithm>

int main(void)
{

    clock_t tStart = clock();

    {
        std::map<float,int> myMap;
        for ( int i = 0; i != 10000000; ++i )
        {
            myMap[ ((float)std::rand()) / RAND_MAX ] = i;
        }
    }

    std::cout << "Time taken by map: " << ((double)(clock() - tStart)/CLOCKS_PER_SEC) << std::endl;

    tStart = clock();

    {
        std::vector< std::pair<float,int> > myVect;
        for ( int i = 0; i != 10000000; ++i )
        {
            myVect.push_back( std::make_pair( ((float)std::rand()) / RAND_MAX, i ) );
        }

        // sort the vector, as we want a sorted container:
        std::sort( myVect.begin(), myVect.end() );
    }

    std::cout << "Time taken by vect: " << ((double)(clock() - tStart)/CLOCKS_PER_SEC) << std::endl;

    return 0;
}

编译自g++ main.cpp -O3 -o main并得到:

Time taken by map: 21.7142
Time taken by vect: 7.94725

map慢了 3 倍...

然后，我说，“好吧， vector 的填充和排序速度更快，但是使用 map 搜索会更快”……所以我测试了:

#include <iostream>
#include <time.h>
#include <cstdlib>
#include <map>
#include <vector>
#include <algorithm>

int main(void)
{
    clock_t tStart = clock();

    {
        std::map<float,int> myMap;
        float middle = 0;
        float last;
        for ( int i = 0; i != 10000000; ++i )
        {
            last = ((float)std::rand()) / RAND_MAX;
            myMap[ last ] = i;
            if ( i == 5000000 )
                middle = last; // element we will later search
        }

        std::cout << "Map created after " << ((double)(clock() - tStart)/CLOCKS_PER_SEC) << std::endl;

        float sum = 0;
        for ( int i = 0; i != 10; ++i )
            sum += myMap[ last ]; // search it

        std::cout << "Sum is " << sum << std::endl;
    }

    std::cout << "Time taken by map: " << ((double)(clock() - tStart)/CLOCKS_PER_SEC) << std::endl;

    tStart = clock();

    {
        std::vector< std::pair<float,int> > myVect;
        std::pair<float,int> middle;
        std::pair<float,int> last;
        for ( int i = 0; i != 10000000; ++i )
        {
            last = std::make_pair( ((float)std::rand()) / RAND_MAX, i );
            myVect.push_back( last );
            if ( i == 5000000 )
                middle = last; // element we will later search
        }

        std::sort( myVect.begin(), myVect.end() );

        std::cout << "Vector created after " << ((double)(clock() - tStart)/CLOCKS_PER_SEC) << std::endl;

        float sum = 0;
        for ( int i = 0; i != 10; ++i )
            sum += (std::find( myVect.begin(), myVect.end(), last ))->second; // search it

        std::cout << "Sum is " << sum << std::endl;
    }

    std::cout << "Time taken by vect: " << ((double)(clock() - tStart)/CLOCKS_PER_SEC) << std::endl;

    return 0;
}

编译自g++ main.cpp -O3 -o main并得到:

Map created after 19.5357
Sum is 1e+08
Time taken by map: 21.41
Vector created after 7.96388
Sum is 1e+08
Time taken by vect: 8.31741

使用 vector 显然搜索速度更快(用 map 搜索 10 次用了将近 2 秒，而用 vector 只用了半秒)...

所以:

• 我错过了什么吗？
• 我的测试不正确/不准确吗？
• 是map只是一个要避免的类，还是真的存在map提供良好的性能？

Answer 1

通常，map 会更好地执行大量插入和删除操作，并穿插在查找操作中。如果您构建一次数据结构然后只进行查找，那么排序的 vector 几乎肯定会更快，如果只是因为处理器缓存效应的话。由于 vector 中任意位置的插入和删除操作的复杂度为 O(n) 而不是 O(log n)，因此最终会成为限制因素。