10--STL无序容器(Unordered Containers)

一:无序容器简介

10--STL无序容器(Unordered Containers)

Unordered Containers也是一种关联式容器。其中元素是分散,没有定性的排列(不是图中那样松散)。其中元素可能在某一次操作后改变原来的位置。

10--STL无序容器(Unordered Containers)

哈希表的链地址法,更能表现其内部实现结构。其中哈希表中表长可以改变,其实现用分配器实现,
为了防止链表过程,效率减低,设置一个值,当链表长度过长时,打散哈希表,重新设置表长,分配位置。

二:性能测试

10--STL无序容器(Unordered Containers)
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <stdio.h>
#include <cstring>

#if _MSC_VER
#define snprintf _snprintf
#endif

using namespace std;

long get_a_target_long()
{
    /******变量声明********/
    long target = 0;
    /**********************/

    cout << "targer (0~" << RAND_MAX << "):";
    cin >> target;
    return target;
}

string get_a_target_string()
{
    /******变量声明********/
    long target = 0;
    char buf[10];
    /**********************/

    cout << "targer (0~" << RAND_MAX << "):";
    cin >> target;

    snprintf(buf, 10, "%d", target);
    return string(buf);
}

//与后面的比较函数中回调参数对应
int compareLongs(const void* l1, const void* l2)
{
    return (*(long*)l1 - *(long*)l2);
}

int compareStrings(const void* s1, const void* s2)
{
    if (*(string*)s1 > *(string*)s2)
        return 1;
    if (*(string*)s1 < *(string*)s2)
        return -1;
    return 0;
}
公共函数

(一)unordered_multiset测试

#include <unordered_set>
//测试unordered_multiset-->元素可以重复
namespace jj12
{
    void test_unordered_multiset(long& us_size)
    {
        cout << "\ntest_unordered_multiset()*******" << endl;

        /******变量声明:数组初始********/
        char buf[10];

        /******变量声明:unordered_multiset初始********/
        unordered_multiset<string> ums;

        /******变量声明:记录时间********/
        clock_t timeStart = clock();    //开始时间
        for (long i = 0; i < us_size; i++)
        {
            try
            {
                snprintf(buf, 10, "%d", rand());
                ums.insert(string(buf));
            }
            catch (exception& e)
            {
                cout << e.what() << endl;
                cout << "Max_size:" << i << endl;
                abort();    //终止
            }
        }

        cout << "inti unordered_multiset use milli-seconds:" << (clock() - timeStart) << endl;    //获取初始化数组耗时
        cout << "unordered_multiset.size:" << ums.size() << endl;    //获取unordered_multiset大小
        cout << "unordered_multiset.max_size:" << ums.max_size() << endl;    //获取unordered_multiset允许最大长度
        cout << "unordered_multiset.bucket_count:" << ums.bucket_count() << endl;    //获取篮子数--表长
        cout << "unordered_multiset.load_factor:" << ums.load_factor() << endl;    //获取加载因子
        cout << "unordered_multiset.max_load_factoe:" << ums.max_load_factor() << endl;    //获取最大加载因子--1
        cout << "unordered_multiset.max_bucket_count:" << ums.max_bucket_count() << endl;    //获取存在最大篮子数--表长

        //打印前20个篮子
        for (int i = 0; i < 20; i++)
            cout << "Key #" << i << " has " <<
            ums.bucket_size(i)    //该篮子中有几个元素
            << " elements" << endl;

        /******变量声明:获取我们要查询的数********/
        string target = get_a_target_string();


        //使用::find方法进行查找
        timeStart = clock();

        auto pI = find(ums.begin(), ums.end(), target);

        cout << "::find(),milli-seconds:" << clock() - timeStart << endl;
        if (pI != ums.end())
            cout << "found:" << *pI << endl;
        else
            cout << "not found!" << endl;

        //使用unordered_multiset.find查找
        timeStart = clock();

        pI = ums.find(target);    //比::find块得多,直接定位查询,

        cout << "unordered_multiset.find(),milli-seconds:" << clock() - timeStart << endl;
        if (pI != ums.end())
            cout << "found:" << *pI << endl;
        else
            cout << "not found!" << endl;

    }
}

10--STL无序容器(Unordered Containers)

(二)unordered_multimap测试

#include <unordered_map>
//测试unordered_multimap-->元素可以重复
namespace jj13
{
    void test_unordered_multimap(long& mm_size)
    {
        cout << "\ntest_unordered_multimap()*******" << endl;

        /******变量声明:数组初始********/
        char buf[10];

        /******变量声明:unordered_multimap初始********/
        unordered_multimap<long, string> umm;

        /******变量声明:记录时间********/
        clock_t timeStart = clock();    //开始时间
        for (long i = 0; i < mm_size; i++)
        {
            try
            {
                snprintf(buf, 10, "%d", rand());
                umm.insert(pair<long, string>(i, string(buf)));
            }
            catch (exception& e)
            {
                cout << e.what() << endl;
                cout << "Max_size:" << i << endl;
                abort();    //终止
            }
        }

        cout << "inti unordered_multimap use milli-seconds:" << (clock() - timeStart) << endl;    //获取初始化数组耗时
        cout << "unordered_multimap.size:" << umm.size() << endl;    //获取unordered_multimap大小
        cout << "unordered_multimap.max_size:" << umm.max_size() << endl;    //获取unordered_multimap所允许最大
        cout << "unordered_multimap.bucket_count:" << umm.bucket_count() << endl;    //获取篮子数--表长
        cout << "unordered_multimap.load_factor:" << umm.load_factor() << endl;    //获取加载因子
        cout << "unordered_multimap.max_load_factoe:" << umm.max_load_factor() << endl;    //获取最大加载因子--1
        cout << "unordered_multimap.max_bucket_count:" << umm.max_bucket_count() << endl;    //获取存在最大篮子数--表长

        //打印前20个篮子
        for (int i = 0; i < 20; i++)
            cout << "Key #" << i << " has " <<
            umm.bucket_size(i)    //该篮子中有几个元素
            << " elements" << endl;


        /******变量声明:获取我们要查询的数********/
        long target = get_a_target_long();    //根据key查找


        //unordered_multimap没有全局::find方法可用,::find找值,multimap找键,两者不同,不可以混用


        //使用unordered_multimap.find查找
        timeStart = clock();

        auto pI = umm.find(target);

        cout << "unordered_multimap.find(),milli-seconds:" << clock() - timeStart << endl;
        if (pI != umm.end())
            cout << "found:" << (*pI).first << ":" << (*pI).second << endl;
        else
            cout << "not found!" << endl;

    }
}

10--STL无序容器(Unordered Containers)

(三)unordered_set测试

#include <unordered_set>
//测试unordered_set-->元素不可以重复
namespace jj14
{
    void test_unordered_set(long& us_size)
    {
        cout << "\ntest_unordered_set()*******" << endl;

        /******变量声明:数组初始********/
        char buf[10];

        /******变量声明:unordered_set初始********/
        unordered_set<string> us;

        /******变量声明:记录时间********/
        clock_t timeStart = clock();    //开始时间
        for (long i = 0; i < us_size; i++)
        {
            try
            {
                snprintf(buf, 10, "%d", rand());
                us.insert(string(buf));
            }
            catch (exception& e)
            {
                cout << e.what() << endl;
                cout << "Max_size:" << i << endl;
                abort();    //终止
            }
        }

        cout << "inti unordered_multiset use milli-seconds:" << (clock() - timeStart) << endl;    //获取初始化数组耗时
        cout << "unordered_set.size:" << us.size() << endl;    //获取unordered_set大小
        cout << "unordered_set.max_size:" << us.max_size() << endl;    //获取unordered_set允许最大
        cout << "unordered_set.bucket_count:" << us.bucket_count() << endl;    //获取篮子数--表长
        cout << "unordered_set.load_factor:" << us.load_factor() << endl;    //获取加载因子
        cout << "unordered_set.max_load_factoe:" << us.max_load_factor() << endl;    //获取最大加载因子--1
        cout << "unordered_set.max_bucket_count:" << us.max_bucket_count() << endl;    //获取存在最大篮子数--表长

        //打印前20个篮子
        for (int i = 0; i < 20; i++)
            cout << "Key #" << i << " has " <<
            us.bucket_size(i)    //该篮子中有几个元素
            << " elements" << endl;

        /******变量声明:获取我们要查询的数********/
        string target = get_a_target_string();


        //使用::find方法进行查找
        timeStart = clock();

        auto pI = find(us.begin(), us.end(), target);

        cout << "::find(),milli-seconds:" << clock() - timeStart << endl;
        if (pI != us.end())
            cout << "found:" << *pI << endl;
        else
            cout << "not found!" << endl;

        //使用unordered_set.find查找
        timeStart = clock();

        pI = us.find(target);    //比::find块得多,直接定位查询,

        cout << "unordered_set.find(),milli-seconds:" << clock() - timeStart << endl;
        if (pI != us.end())
            cout << "found:" << *pI << endl;
        else
            cout << "not found!" << endl;

    }
}

10--STL无序容器(Unordered Containers)

(四)unordered_map测试

#include <unordered_map>
//测试unordered_map-->元素不可以重复
namespace jj15
{
    void test_unordered_map(long& um_size)
    {
        cout << "\ntest_unordered_map()*******" << endl;

        /******变量声明:数组初始********/
        char buf[10];

        /******变量声明:unordered_multimap初始********/
        unordered_map<long, string> um;

        /******变量声明:记录时间********/
        clock_t timeStart = clock();    //开始时间
        for (long i = 0; i < um_size; i++)
        {
            try
            {
                snprintf(buf, 10, "%d", rand());
                um.insert(pair<long, string>(i, string(buf)));
            }
            catch (exception& e)
            {
                cout << e.what() << endl;
                cout << "Max_size:" << i << endl;
                abort();    //终止
            }
        }

        cout << "inti unordered_map use milli-seconds:" << (clock() - timeStart) << endl;    //获取初始化数组耗时
        cout << "unordered_map.size:" << um.size() << endl;    //获取unordered_map大小
        cout << "unordered_map.max_size:" << um.max_size() << endl;    //获取unordered_map允许最大
        cout << "unordered_map.bucket_count:" << um.bucket_count() << endl;    //获取篮子数--表长
        cout << "unordered_map.load_factor:" << um.load_factor() << endl;    //获取加载因子
        cout << "unordered_map.max_load_factoe:" << um.max_load_factor() << endl;    //获取最大加载因子--1
        cout << "unordered_map.max_bucket_count:" << um.max_bucket_count() << endl;    //获取存在最大篮子数--表长

        //打印前20个篮子
        for (int i = 0; i < 20; i++)
            cout << "Key #" << i << " has " <<
            um.bucket_size(i)    //该篮子中有几个元素
            << " elements" << endl;


        /******变量声明:获取我们要查询的数********/
        long target = get_a_target_long();    //根据key查找


        //unordered_map没有全局::find方法可用,::find找值,unordered_map找键,两者不同,不可以混用


        //使用unordered_map.find查找
        timeStart = clock();

        auto pI = um.find(target);

        cout << "unordered_map.find(),milli-seconds:" << clock() - timeStart << endl;
        if (pI != um.end())
            cout << "found:" << (*pI).first << ":" << (*pI).second << endl;
        else
            cout << "not found!" << endl;

    }
}

10--STL无序容器(Unordered Containers)

 

上一篇:【LeetCode 217、219、220】存在重复元素、存在重复元素 II、存在重复元素 III


下一篇:error:control reaches end of non-void function [-Werror=return-type]