stl 容器 分类 效率

STL容器效率

容器分类

有序容器

• array
• vector
• deque
• forward_list 单向/转发列表
• list

容器适配器

• stack
• queue
• priority_queue 优先队列

无序容器(关联容器)

• set
• multiset
• map
• multimap

哈希实现的

• unordered_set
• unordered_multiset
• unordered_map
• unordered_multimap

链接

容器效率

#include <iostream>
#include <ctime>
#include <algorithm>

const unsigned int  MAXSIZE = 5000000;

#include <vector>

bool  FuncFindiIf(int val)
{
    return val > 10000;
}

bool  FuncFindiIfPair(std::pair<int,int> val)
{
    return val.second > 10000;
}

void TestVector()
{
    std::cout << "--------------------" << std::endl;
    std::cout << "vector测试结果:" << std::endl;
    std::vector<int> test;
    std::clock_t start = std::clock();
    for (size_t i=0;i<MAXSIZE;++i)
        test.push_back(rand());
    
    std::clock_t end = std::clock();
    std::cout << "写入(push_back)数据时间:" << end - start << std::endl;
    start = std::clock();
    std::sort(test.begin(), test.end());
    end = std::clock();
    std::cout << "排序(sort)时间:" << end - start << std::endl;
    start = std::clock();
    std::count_if(test.begin(), test.end(), FuncFindiIf);
    end = std::clock();
    std::cout << "查找(count_if)时间:" << end - start << std::endl;
    start = std::clock();
    for (int i=0;i<10;++i)
        test.insert(test.begin() + 10*i, 10);

    end = std::clock();
    std::cout << "插入(insert)时间:" << end - start << std::endl;

    start = std::clock();
    for (int i = 0; i < 10; ++i)
        test.erase(test.begin() + 2 * i);

    end = std::clock();
    std::cout << "删除(erase)时间:" << end - start << std::endl;
}

#include <array>
std::array<int, MAXSIZE> test;
void TestArry()
{
    std::cout << "--------------------" << std::endl;
    std::cout << "array测试结果：" << std::endl;
    
    std::clock_t start = std::clock();
    for (size_t i = 0; i < MAXSIZE; ++i)
        test[i] = rand();

    std::clock_t end = std::clock();
    std::cout << "写入(push_back)数据时间:" << end - start << std::endl;
    start = std::clock();
    std::sort(test.begin(), test.end());
    end = std::clock();
    std::cout << "排序(sort)时间:" << end - start << std::endl;
    start = std::clock();
    std::count_if(test.begin(), test.end(), FuncFindiIf);
    end = std::clock();
    std::cout << "查找(count_if)时间:" << end - start << std::endl;
}


#include <deque>
void TestDeque()
{
    std::cout << "--------------------" << std::endl;
    std::cout << "deque测试结果：" << std::endl;
    std::deque<int> test;
    std::clock_t start = std::clock();
    for (size_t i = 0; i < MAXSIZE; ++i)
        test.push_back(rand());

    std::clock_t end = std::clock();
    std::cout << "写入(push_back)数据时间:" << end - start << std::endl;
    start = std::clock();
    std::sort(test.begin(), test.end());
    end = std::clock();
    std::cout << "排序(sort)时间:" << end - start << std::endl;
    start = std::clock();
    std::count_if(test.begin(), test.end(), FuncFindiIf);
    end = std::clock();
    std::cout << "查找(count_if)时间:" << end - start << std::endl;

    start = std::clock();
    for (int i = 0; i < 10; ++i)
        test.insert(test.begin() + 10 * i, 10);

    end = std::clock();
    std::cout << "插入(insert)时间:" << end - start << std::endl;

    start = std::clock();
    for (int i = 0; i < 10; ++i)
        test.erase(test.begin() + 2 * i);

    end = std::clock();
    std::cout << "删除(erase)时间:" << end - start << std::endl;
}

#include <list>
void TestList()
{
    typedef std::list<int>::iterator iterator;
    std::cout << "--------------------" << std::endl;
    std::cout << "list测试结果：" << std::endl;
    std::list<int> test;
    std::clock_t start = std::clock();
    for (size_t i = 0; i < MAXSIZE; ++i)
        test.push_back(rand());
    
    std::clock_t end = std::clock();
    //std::cout << "写入(push_back)数据时间:" << end - start << std::endl;
    //start = std::clock();
    //std::sort(test.begin(), test.end());
    //end = std::clock();
    //std::cout << "排序(sort)时间:" << end - start << std::endl;
    //_Sort_unchecked1(_First, _Last, _Last - _First, _Pred);确实需要做的话，尝试自己算出距离
    start = std::clock();
    std::count_if(test.begin(), test.end(), FuncFindiIf);
    end = std::clock();
    std::cout << "查找(count_if)时间:" << end - start << std::endl;
    iterator it1[10];
    iterator it = test.begin();
    for (int Index = 0; Index < 10; ++Index)
    {
        it1[Index] = it; 
        for (int i=0;i<10;++i)
            it++;
    }
    start = std::clock();
    for (int i = 0; i < 10; ++i)
        test.insert(it1[i], 10);

    end = std::clock();
    std::cout << "插入(insert)时间:" << end - start << std::endl;

    start = std::clock();
    for (int i = 0; i < 10; ++i)
        test.erase(it1[i]);

    end = std::clock();
    std::cout << "删除(erase)时间:" << end - start << std::endl;
}


#include <forward_list>
void TestForwardList()
{
    std::cout << "--------------------" << std::endl;
    std::cout << "forward_list测试结果：" << std::endl;
    std::forward_list<int> test;
    typedef std::forward_list<int>::iterator iterator;
    std::clock_t start = std::clock();
    for (size_t i = 0; i < MAXSIZE; ++i)
        test.push_front(rand());
    
    std::clock_t end = std::clock();
    std::cout << "写入(push_front)数据时间:" << end - start << std::endl;
    //start = std::clock();
    //std::sort(test.begin(), test.end());
    //end = std::clock();
    //std::cout << "排序(sort)时间:" << end - start << std::endl;
    //_Sort_unchecked1(_First, _Last, _Last - _First, _Pred);确实需要做的话，尝试自己算出距离
    start = std::clock();
    std::count_if(test.begin(), test.end(), FuncFindiIf);
    end = std::clock();
    std::cout << "查找(count_if)时间:" << end - start << std::endl;

    iterator it1[10];
    iterator it = test.begin();
    for (int Index = 0; Index < 10; ++Index)
    {
        it1[Index] = it;
        for (int i = 0; i < 10; ++i)
            it++;
    }
    start = std::clock();
    for (int i = 0; i < 10; ++i)
        test.insert_after(it1[i], 10);

    end = std::clock();
    std::cout << "插入(insert)时间:" << end - start << std::endl;

    start = std::clock();
    for (int i = 0; i < 10; ++i)
        test.erase_after(it1[i]);

    end = std::clock();
    std::cout << "删除(erase)时间:" << end - start << std::endl;
}

#include <set>
void TestSet()
{
    std::cout << "--------------------" << std::endl;
    std::cout << "set测试结果：" << std::endl;
    std::set<int> test;
    std::clock_t start = std::clock();
    for (size_t i = 0; i < MAXSIZE; ++i)
    {
        test.insert(rand());
    }
    std::clock_t end = std::clock();
    std::cout << "写入(insert)数据时间:" << end - start << std::endl;
    //start = std::clock();
    //std::sort(test.begin(), test.end());
    //end = std::clock();
    //std::cout << "排序(sort)时间:" << end - start << std::endl;
    start = std::clock();
    std::count_if(test.begin(), test.end(), FuncFindiIf);
    end = std::clock();
    std::cout << "查找(count_if)时间:" << end - start << std::endl;
}

void TestMultiSet()
{
    std::cout << "--------------------" << std::endl;
    std::cout << "multiset测试结果：" << std::endl;
    std::multiset<int> test;
    std::clock_t start = std::clock();
    for (size_t i = 0; i < MAXSIZE; ++i)
    {
        test.insert(rand());
    }
    std::clock_t end = std::clock();
    std::cout << "写入(insert)数据时间:" << end - start << std::endl;
    //start = std::clock();
    //std::sort(test.begin(), test.end());
    //end = std::clock();
    //std::cout << "排序(sort)时间:" << end - start << std::endl;
    start = std::clock();
    std::count_if(test.begin(), test.end(), FuncFindiIf);
    end = std::clock();
    std::cout << "查找(count_if)时间:" << end - start << std::endl;
}


#include <map>
void TestMap()
{
    std::cout << "--------------------" << std::endl;
    std::cout << "map测试结果：" << std::endl;
    std::map<int,int> test;
    std::clock_t start = std::clock();
    for (size_t i = 0; i < MAXSIZE; ++i)
    {
        test.insert(std::pair<int,int>(i,rand()));
    }
    std::clock_t end = std::clock();
    std::cout << "写入(insert)数据时间:" << end - start << std::endl;
    //start = std::clock();
    //std::sort(test.begin(), test.end());
    //end = std::clock();
    //std::cout << "排序(sort)时间:" << end - start << std::endl;
    start = std::clock();
    std::count_if(test.begin(), test.end(), FuncFindiIfPair);
    end = std::clock();
    std::cout << "查找(count_if)时间:" << end - start << std::endl;
}

void TestMultiMap()
{
    std::cout << "--------------------" << std::endl;
    std::cout << "multimap测试结果：" << std::endl;
    std::multimap<int, int> test;
    std::clock_t start = std::clock();
    for (size_t i = 0; i < MAXSIZE; ++i)
    {
        test.insert(std::pair<int, int>(i, rand()));
    }
    std::clock_t end = std::clock();
    std::cout << "写入(insert)数据时间:" << end - start << std::endl;
    //start = std::clock();
    //std::sort(test.begin(), test.end());
    //end = std::clock();
    //std::cout << "排序(sort)时间:" << end - start << std::endl;
    start = std::clock();
    std::count_if(test.begin(), test.end(), FuncFindiIfPair);
    end = std::clock();
    std::cout << "查找(count_if)时间:" << end - start << std::endl;
}


#include <unordered_set>
void TestUnOrderedSet()
{
    std::cout << "--------------------" << std::endl;
    std::cout << "unordered_set测试结果：" << std::endl;
    std::unordered_set<int> test;
    std::clock_t start = std::clock();
    for (size_t i = 0; i < MAXSIZE; ++i)
    {
        test.insert(rand());
    }
    std::clock_t end = std::clock();
    std::cout << "写入(insert)数据时间:" << end - start << std::endl;
    //start = std::clock();
    //std::sort(test.begin(), test.end());
    //end = std::clock();
    //std::cout << "排序(sort)时间:" << end - start << std::endl;
    start = std::clock();
    std::count_if(test.begin(), test.end(), FuncFindiIf);
    end = std::clock();
    std::cout << "查找(count_if)时间:" << end - start << std::endl;
}

void TestUnOrderedMultiSet()
{
    std::cout << "--------------------" << std::endl;
    std::cout << "unordered_multiset测试结果：" << std::endl;
    std::unordered_multiset<int> test;
    std::clock_t start = std::clock();
    for (size_t i = 0; i < MAXSIZE; ++i)
    {
        test.insert(rand());
    }
    std::clock_t end = std::clock();
    std::cout << "写入(insert)数据时间:" << end - start << std::endl;
    //start = std::clock();
    //std::sort(test.begin(), test.end());
    //end = std::clock();
    //std::cout << "排序(sort)时间:" << end - start << std::endl;
    start = std::clock();
    std::count_if(test.begin(), test.end(), FuncFindiIf);
    end = std::clock();
    std::cout << "查找(count_if)时间:" << end - start << std::endl;
}

#include <unordered_map>
void TestUnOrderMap()
{
    std::cout << "--------------------" << std::endl;
    std::cout << "unordered_map测试结果：" << std::endl;
    std::unordered_map<int, int> test;
    std::clock_t start = std::clock();
    for (size_t i = 0; i < MAXSIZE; ++i)
    {
        test.insert(std::pair<int, int>(i, rand()));
    }
    std::clock_t end = std::clock();
    std::cout << "写入(insert)数据时间:" << end - start << std::endl;
    //start = std::clock();
    //std::sort(test.begin(), test.end());
    //end = std::clock();
    //std::cout << "排序(sort)时间:" << end - start << std::endl;
    start = std::clock();
    std::count_if(test.begin(), test.end(), FuncFindiIfPair);
    end = std::clock();
    std::cout << "查找(count_if)时间:" << end - start << std::endl;
}

int main()
{
    std::cout << "序列式容器:" << std::endl;
    TestArry();
    TestVector();
    TestDeque();
    TestList();
    TestForwardList();
    std::cout << "" << std::endl << std::endl;
    std::cout << "关联式容器:" << std::endl;
    TestSet();
    TestMultiSet();
    TestMap();
    TestMultiMap();
    TestUnOrderedSet();
    TestUnOrderedMultiSet();
    TestUnOrderMap();

    return 0;
}

未完待续...

如有错误,请提出指正!谢谢.

本文由 花心胡萝卜 创作，采用 知识共享署名4.0 国际许可协议进行许可
本站文章除注明转载/出处外，均为本站原创或翻译，转载前请务必署名
最后编辑时间为: 2017-04-14 at 04:12 pm