hast_table.cpp

#include <cstddef>
#include <cstdint>
#include <list>
#include <vector>
#include <functional> // use std::hash<Key>
#include <memory> // unique_ptr
#include <stdexcept> // out_of_range
#include <iostream>
#include <string>
#include <unordered_map>
#include <random>
#include <limits>  // numeric_limits::min/max

std::size_t INITIAL_HASH_TABLE_SIZE {10}; // size for 10 hashes

using Key = uint32_t;
using Value = double;
using List = std::list<std::tuple<Key, Value>>;

class hash_table {
private:
    const static std::hash<Key> hash_function;
    std::vector<std::unique_ptr<List>> table = std::vector<std::unique_ptr<List>>(
        INITIAL_HASH_TABLE_SIZE
        );
    
    size_t calc_index(Key key) const {
        return hash_function(key) % table.size();
    }
public:
    hash_table() = default;
    
    Value & operator[](Key key) {  // operator for assigning
        auto index = calc_index(key);
        if (table[index] == nullptr) {
            table[index] = std::make_unique<List>();
        }
        auto & list = *(table[index]);
        for (auto & pair : list) {
            if (std::get<0>(pair) == key) {
                return std::get<1>(pair);
            }
        }
        list.emplace_front(key, 0xDEADBEEF);
        return std::get<1>(list.front());
    }

    Value at(Key key) const {
        const auto index = calc_index(key);
        if (table[index] != nullptr) {
            for (const auto & pair : *table[index]) {
                if (std::get<0>(pair) == key) {
                    return std::get<1>(pair);
                }
            }
        }
        throw std::out_of_range("key");
    }

    void remove(Key key) {
        const auto index = calc_index(key);
        if (table[index] != nullptr) {
            auto & list_ = *table[index];
            for (auto it = list_.begin(); it != list_.end(); ++it) {
                if (std::get<0>(*it) == key) {
                    list_.erase(it);
                    return;
                }
            }
        }
        throw std::out_of_range("key");
    }
};

const std::hash<Key> hash_table::hash_function {}; 


int main() {
    auto ht = hash_table{};
    try {
        const auto value = ht.at(0);
        std::cout << "Bad: " << value << std::endl;
    }
    catch (const std::out_of_range & e) {
        std::cout << "Good: " << e.what() << std::endl;
    }

    try {
        ht.remove(666);
        std::cout << "Bad" << std::endl;
    }
    catch (const std::out_of_range & e) {
        std::cout << "Good: " << e.what() << std::endl;
    }

    ht[0] = 5.5;
    if (ht.at(0) == 5.5) {
        std::cout << "Good" << std::endl;
    }
    else {
        std::cout << "Bad" << std::endl;
    }

    ht[0] = 6.6;
    if (ht.at(0) == 6.6) {
        std::cout << "Good" << std::endl;
    }
    else {
        std::cout << "Bad" << std::endl;
    }

    std::cout << "0xDEADBEEF as Value = " << static_cast<Value>(0xDEADBEEF) \
              << std::endl;

    std::random_device random_device;
    std::mt19937 random_generator {random_device()};
    std::uniform_real_distribution<Value> value_distr {0.0, 10.0};
    std::uniform_int_distribution<Key> key_distr {
        std::numeric_limits<Key>::min(), std::numeric_limits<Key>::max()
    };
    std::uniform_int_distribution<bool> bool_distr {false, true};
    //std::uniform_int_distribution<Key> key_distr {20, 200};
    ht = hash_table{};
    auto map_ = std::unordered_map<Key, Value>{};
    for (unsigned int i = 0; i < 1000; ++i) {
        auto key = key_distr(random_generator);
        auto value = value_distr(random_generator);

        ht[key] = value;
        map_[key] = value;

        for (const auto pair: map_) {
            if (ht[pair.first] != pair.second) {
                std::cout << "i=" << i << ", map_[" << pair.first << "]=" \
                     << pair.second << "; ht[" << pair.first << "]=" \
                     << ht[pair.first] << std::endl;
                std::cout << "something went wrong" << std::endl;
                return 1;
            }
        }
    }

    for (const auto pair: map_) {
        const auto key = pair.first;
        ht.remove(key);
        try {
            ht.at(key);
            std::cout << "something went wrong with .at" << std::endl;
            return 1;
        }
        catch (const std::out_of_range & e) {}
        try {
            ht.remove(key);
            std::cout << "something went wrong with .remove" << std::endl;
            return 1;
        }
        catch (const std::out_of_range & e) {}
    }
    std::cout << "everything went well" << std::endl;
}