#include <cassert>
#include <iostream>
#include <string>

template <typename K, typename V>
class Map
{
private:
    class KeyValuePair
    {
    public:
        KeyValuePair(K k, V v) : key(k), value(v), next(nullptr) {}
        K key;
        V value;
        KeyValuePair *next;
    };

    int size;
    int capacity;
    KeyValuePair **table;

public:
    Map() : size(0), capacity(64)
    {
        table = new KeyValuePair *[capacity];
    }

    Map(int size, int capacity, KeyValuePair **table)
        : size(size), capacity(capacity), table(table) {}
    ~Map()
    {
        for (int i = 0; i < size; i++)
        {
            KeyValuePair *pair = table[i];
            while (pair)
            {
                KeyValuePair *temp = pair;
                pair = pair->next;
                delete temp;
            }
        }
        delete[] table;
    }

    void put(K key, V value)
    {
        for (int i = 0; i < size; i++)
        {
            KeyValuePair *pair = table[i];
            while (pair)
            {
                if (pair->key == key)
                {
                    pair->value = value;
                    return;
                }
                pair = pair->next;
            }
        }

        if (size == capacity)
        {
            capacity *= 2;
            table = new KeyValuePair *[capacity];
        }

        KeyValuePair *new_pair = new KeyValuePair(key, value);
        if (size == 0)
        {
            table[0] = new_pair;
        }
        else
        {
            KeyValuePair *current = table[0];
            while (current->next)
            {
                current = current->next;
            }
            current->next = new_pair;
        }

        size++;
    }

    V get(K key)
    {
        for (int i = 0; i < size; i++)
        {
            KeyValuePair *pair = table[i];
            while (pair)
            {
                if (pair->key == key)
                {
                    return pair->value;
                }
                pair = pair->next;
            }
        }
         assert(0);
    }

    V &operator[](K key)
    {
        for (int i = 0; i < size; i++)
        {
            KeyValuePair *pair = table[i];
            while (pair)
            {
                if (pair->key == key)
                {
                    return pair->value;
                }
                pair = pair->next;
            }
        }
        assert(0);
    }
};

int main()
{
    Map<std::string, int> map;

    map.put("one", 1);
    map.put("two", 2);
    map.put("three", 3);

    std::cout << "one: " << map.get("one") << std::endl;
    std::cout << "two: " << map["two"] << std::endl;
    std::cout << "three: " << map.get("three") << std::endl;

    return 0;
}