C++STL之hash_table，hash_map与hash_multimap，hash_set与hash_multiset的使用

学习别人的哈，特此声明。


hash_table是STL中hash_map 和 hash_set 的内部数据结构，hash_table的插入 / 删除 / 查找的时间复杂度都为O(1),
是查找速度最快的一种数据结构，但是hash_table中的数据是无序的，一般也只有在数据不需要排序，
只需要满足快速查找 / 插入 / 删除的时候使用hash_table。hash_table的扩展是将原hash_table中的数据摘下来插入
到一个临时的hash_table中，因为每个桶都使用list来实现的，因此插入删除都不存在内存copy，所以也是很高效的，
最后再将临时hash_table和原来的hash_table（此时已经为空）交换。

//SGI STL中的map底层以红黑树实现，hash_map以hash table实现。
//hash_map不允许插入重新键值，hash_multimap允许插入重复键值。
//这两者的关系就像map和multimap的关系。底层的hash table提供的大部分的操作，
//hash_map(hash_multimap)大部分都是直接调用hash table的函数。
//
//hash_multimap和hash_map的区别就像multimap与map的区别一样，
//hash_multimap的底层机制是基于hash table，它可以存在重复的键值，
//所以插入函数使用insert_equal()，hash_multimap和hash_map一样，容器的内容不自动排序。
#include<iostream>
#include<hash_map>
using namespace std;
//using namespace _gnu_cxx;
int main()
{
    hash_map<char, int, hash<char>, equal_to<char> > m;//char是键值类型，int是实值类型。
    m['a'] = 10;
    m['b'] = 2;
    cout << m.size() << endl;//输出2.
    cout << m.find('a')->second << endl;
    cout << m.count('a') << endl;

    system("pause");
    return 0;
}

/*
hash_set与hash_multiset：
实值就是键值
以hashtable为底层机制，所以几乎所有的hash_set行为，都是转调hashtable的操作行为。

与set、multiset相比，hash_set、hash_multiset没有自动排序功能。

hash_set与set一样，实值就是键值。使用方式与set完全相同

插入元素操作采用底层机制hashtable的insert_unique()。
hash_multiset与multiset一样，键值可以重复，使用方式和multiset相同。
插入元素操作采用底层机制hashtable的insert_equal()。

hash_map与hash_multmap：
每一个元素同时拥有实值和键值

以hashtable为底层机制，所以几乎所有的hash_map行为，都是转调hashtable的操作行为。

与map、multimap相比，hash_map、hash_multimap没有自动排序功能。

hash_map与map一样，实值就是键值。使用方式与set完全相同

插入元素操作采用底层机制hashtable的insert_unique()。

hash_multimap与multimap一样，键值可以重复，pair<key, value>

插入元素操作采用底层机制hashtable的insert_equal()。
*/

//unordered_map与hash_map是一样的，unordered_map是C++11的，其他类似


#include<iostream>
#include<unordered_map>
#include<cstring>
using namespace std;
int main()
{
    unordered_map<const char*, int>days;
    days["january"] = 31;
    days["february"] = 28;
    days["march"] = 31;
    days["april"] = 30;
    days["may"] = 30;
    days["june"] = 30;
    cout << "june->" << days["june"] << endl;//30

    unordered_map<const char*, int>::iterator ite1 = days.begin();
    unordered_map<const char*, int>::iterator ite2 = days.end();
    for (; ite1 != ite2; ++ite1)
        cout << ite1->first << " " << ite1->second << endl;

    system("pause");
    return 0;
}