容器使用之multiset

可以理解为小型关联数据库

底层结构:

红黑树

示例代码:

#pragma
#ifndef __MULTISET__
#define __MMULTISE__
​
#include <set>
#include <iostream>
​
using namespace std;
​
namespace MyTestSet {
    void test_set(long& value) {
        multiset<string> c; // 重复值可以插入节点
        char buf[10];
​
        for (long i = 0; i < value; i++)
        {
            try
            {
                snprintf(buf, 10, "%d", rand());
                c.insert(string(buf)); // insert方法自动将元素找到节点插入
            }
            catch (const exception& p)
            {
                cout << p.what() << endl;
                abort();
            }
        }
    }
}
​
#endif // !__MULTISET__

特点:

• 红黑树单节点结构

• key就是vlaue,value就是key

容器使用之multimap

示例代码:

#pragma
#ifndef __MULTIMAP__
#define __MULTIMAP__
​
#include <map>
#include <iostream>
​
using namespace std;
​
namespace MyTestMap {
    void test_multimap(long& value) {
        multimap<long, string> c;
        char buf[10];
​
        for (long i = 0; i < value; i++)
        {
            try
            {
                snprintf(buf, 10, "%d", rand());
                c.insert(pair<long, string>(i, buf)); // 一对一对的插入 -> 标准库提供的结构
            }
            catch (const exception& p)
            {
                cout << p.what() << endl;
                abort();
            }
        }
​
        long target = 23456;
​
        auto pItem = c.find(target);
​
        // 由于map每个节点是一组key和value -> 那么取值的时候就要取到第二个元素
        // 因为放进去的是pair
        cout << "found value:\t" << (*pItem).second << endl;
    }
}
​
#endif // !__MULTIMAP__

使用map

示例代码:

    void test_map(long& value) {
        map<long, string> c;
        char buf[10];
​
        for (long i = 0; i < value; i++)
        {
            try
            {
                snprintf(buf, 10, "%d", rand());
                c[i] = string(buf); // multimap不能用这种赋值方式
                // 这个赋值方式key是不会重复,前面的multimap以pair的方式存入multimap会出现重复值
            }
            catch (const exception& p)
            {
                cout << p.what() << endl;
                abort();
            }
        }
    }

基于hashtable实现的multiset

底层结构是hashtable -> 数组链表

基于hashtable实现的multimap

底层结构是hashtable -> 数组链表

上面的关键点是hashtable后面的链表的散列算法:

• 如果元素>数组长度,那么就会重新声明hashtable的散列表长度

• 所有的multi数据都允许重复的key存在

hash的四个容器:

• hash_Set

• hash_map

• hash_multiset

• hash_multimap