[数据结构与算法]C++高级编程----扩展STL

题目要求：编写一个遵循一般STL规则的基本容器hash_map，考虑类模板编程方式，支持多种数据格式。

分析：
1）hash_map接口支持用户传入自定义的hash函数和hash桶的数目，在用户不知道的情况下提供默认的hash函数和桶数目；

2）数据结构分析：hash_map支持myHash[key] = value能在常数时间内完成，每一个key可能有一系列value，value由（key,value）组成，因此考虑数据结构为:vector<list<pair<key, value>>>;

3）hash函数定义hash算法，支持operator()，返回hash后的值（支持不同指针hash到同一值，考虑模板特例化）；
4) hash_map支持按key查询和删除，按（key, value）插入，支持operator[]；

5）考虑与STL名称空间分离，定义自己的namespace并考虑模板编程，实现方法声明和方法实现隔离(遵从Google C++编程规范，对于模板类编程使用.inl后缀实现隔离)；

头文件定义：

// hash_map.h
#ifndef HASH_MAP_H_
#define HASH_MAP_H_

#include<vector>
#include<list>
#include<string>
#include<iostream>

namespace ProCpp{

    // part 1: define hash function
    template<typename T>
    class hash{
        public:
            size_t operator() (const T& key) const;
    };

    //template specialization
    template<>
    class hash<std::string>{
        public:
            size_t operator() (const std::string& key) const;
    };

    // part 2: define hash_map data struction and operation
    template<typename Key, typename T, typename Compare = std::equal_to<Key>, typename Hash = hash<Key>>
    class hash_map{
        public:
            using key_type = Key;
            using mapped_type = T;
            using value_type = std::pair<Key, T>;
            
            // define constructor
            explicit hash_map(const Compare& comp = Compare(), size_t numBuckets = 101, const Hash& hash = Hash());

            // search operation
            value_type* find(const key_type& key);
            const value_type* find(const key_type& key) const;

            // insert operation: insert (key, value) into hash map
            void insert(const value_type& value);

            // erase operation: erase key from hash map
            void erase(const key_type& key);

            // index operation: search (key, value) pair by key
            T& operator[] (const key_type& key);

        private:
            using ListType = std::list<value_type>;
            std::vector<ListType> mBuckets;
            size_t mSize;
            Compare mComp;
            Hash mHash;
            typename ListType::iterator findElement(const key_type& key, size_t& bucket);
    };
}
#include"hash_map.inl"
#endif

方法实现：

// hash_map.inl

namespace ProCpp{
    // part 1: template hash class
    // hash (key) -> value
    template<typename T>
    size_t hash<T>::operator() (const T& key) const{
        size_t res = 0;
        size_t bytes = sizeof(key);
        for(auto i = 0; i < bytes; i++){
            unsigned char b = *((unsigned char*)&key + i);
            res += b;
        }
        return res;
    }

    // template specialization: hash(string) -> value
    size_t hash<std::string>::operator() (const std::string& key) const{
        size_t res = 0;
        for(size_t i = 0; i < key.size(); i++){
            res += (unsigned char) key[i];
        }
        return res;
    }

    // part 2: hash map operation

    // hash map constructor
    template<typename Key, typename T, typename Compare, typename Hash>
    hash_map<Key, T, Compare, Hash>::hash_map(const Compare& comp, size_t numBuckets, const Hash& hash):mSize(0), mComp(comp), mHash(hash){
        if(numBuckets == 0){
            throw std::invalid_argument("Number of buckets must be positve !");
        }
        mBuckets.resize(numBuckets);
    }

    template<typename Key, typename T, typename Compare, typename Hash>
    typename hash_map<Key, T, Compare, Hash>::value_type* hash_map<Key, T, Compare, Hash>::find(const key_type& key){
        size_t bucket;
        auto it = findElement(key, bucket);
        if(it == mBuckets[bucket].end()){
            return nullptr;
        }
        return &(*it);
    }

    template<typename Key, typename T, typename Compare, typename Hash>
    const typename hash_map<Key, T, Compare, Hash>::value_type* hash_map<Key, T, Compare, Hash>::find(const key_type& key) const{
        return const_cast<hash_map<Key, T, Compare, Hash>*> (this)->find(key);
    }

    template<typename Key, typename T, typename Compare, typename Hash>
    void hash_map<Key, T, Compare, Hash>::insert(const value_type& value){
        size_t bucket;
        auto it = findElement(value.first, bucket);
        if(it == mBuckets[bucket].end()){
            mBuckets[bucket].push_back(value);
            mSize++;
        }
    }

    template<typename Key, typename T, typename Compare, typename Hash>
    void hash_map<Key, T, Compare, Hash>::erase(const key_type& key){
        size_t bucket;
        auto it = findElement(key, bucket);
        if(it != mBuckets[bucket].end()){
            mBuckets[bucket].erase(it);
            mSize--;
        }
    }

    template<typename Key, typename T, typename Compare, typename Hash>
    T& hash_map<Key, T, Compare, Hash>::operator[] (const key_type& key){
        size_t bucket;
        auto it = find(key);
        if(it == nullptr){
            insert(std::make_pair(key, T()));
            it = find(key);
        }
        return it -> second;
    }

    template<typename Key, typename T, typename Compare, typename Hash>
    typename hash_map<Key, T, Compare, Hash>::ListType::iterator hash_map<Key, T, Compare, Hash>::findElement(const key_type& key, size_t& bucket){
        bucket = mHash(key) % mBuckets.size();
        for(auto it = mBuckets[bucket].begin(); it != mBuckets[bucket].end(); ++it){
            if(mComp(it -> first, key)){
                return it;
            }
        }
        return mBuckets[bucket].end();
    }
}

测试案例：

#include<iostream>
#include "hash_map.h"
using namespace std;
using namespace ProCpp;

int main(){
    hash_map<int, int> myHash;
    myHash.insert(make_pair(4, 40));
    myHash.insert(make_pair(4, 50));
    myHash.insert(make_pair(6, 60));
    int key = 4;
    auto found = myHash.find(key);
    if(found != nullptr){
        cout << "find map (" << key << ", " << found -> second << ")"<< endl;
    }else{
        cout << "not found (key, value) pair " << endl;
    }
    myHash[4] = 35;
    myHash[4] = 60;  
    found = myHash.find(key);
    if(found != nullptr){
        cout << "find map (" << key << ", " << found -> second << ")"<< endl;
    }else{
        cout << "not found (key, value) pair " << endl;
    }
    myHash.erase(key);
    found = myHash.find(key);
    if(found != nullptr){
        cout << "find map (" << key << ", " << found -> second << ")"<< endl;
    }else{
        cout << "not found (key, value) pair " << endl;
    }
    return 0;
}