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

Question

我map在一些代码中使用了一个来存储有序数据.我发现对于巨大的地图,破坏可能需要一段时间.在这段代码我有,取代map通过vector<pair>减少处理时间由10000 ...

最后,我很惊讶我决定将map表演与排序vector或比较pair.

我很惊讶,因为我无法找到的情况下map比排序的更快vector的pair(随机填充后排序)......必须有一些情况下map是快....还有什么是在提供这种类别的点？

这是我测试的:

测试一,比较map填充和破坏与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倍......

然后,我说,"好吧,矢量填充和排序速度更快,但地图搜索会更快"......所以我测试了:

#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(10次搜索map花了将近2秒,并且只用了半秒钟vector)....

所以:

• 我错过了什么？
• 我的测试不正确/准确吗？
• 是map简单的一类,以避免或是否真的在那里的情况下map提供良好的性能？

Answer 1

一般来说，map当您在查找中进行大量插入和删除时， a 会更好。如果您构建一次数据结构，然后只进行查找，那么排序vector几乎肯定会更快，即使只是因为处理器缓存的影响。由于向量中任意位置的插入和删除都是 O(n) 而不是 O(log n)，因此总有一天这些将成为限制因素。