A hash-map implementation using an open-addressing scheme, with iterator support.

HashMap2.cpp

template<typename Key, typename Value>
class HashMap2
{
public:
	
	using size_t = std::size_t;
	
	using hash_function_t = std::function<size_t(const Key& key)>;
	
	
	static const size_t minimum_capacity = 8;
	
	
	struct Pair
	{
		Pair(const Key& k, Value& v)
		: key(k)
		, value(v)
		{ }
		
		const Key& key;
		Value& value;
	};
	
private:
	
	struct Item
	{
		Item(const Key& k = Key(),
			 const Value& v = Value())
		: key(k)
		, value(v)
		, pair(key, value)
		, is_alive(true)
		{ }
		
		Pair pair;
		
		Key key;
		Value value;
		
		bool is_alive;
	};
	
	
	class BaseIterator
	{
	public:
		
		BaseIterator(Item** items = nullptr, size_t index = 0)
		: _index(index)
		, _items(items)
		{ }
		
		BaseIterator(const BaseIterator& other)
		: _index(other._index)
		, _items(other._items)
		{ }
		
		BaseIterator(BaseIterator&& other) noexcept
		: BaseIterator()
		{
			swap(other);
		}
		
		BaseIterator& operator=(BaseIterator other)
		{
			swap(other);
			
			return *this;
		}
		
		virtual ~BaseIterator() = default;
		
		
		virtual void swap(BaseIterator& other)
		{
			using std::swap;
			
			swap(_index, other._index);
			
			swap(_items, other._items);
		}
		
		friend void swap(BaseIterator& first, BaseIterator& second)
		{
			first.swap(second);
		}
		
		virtual BaseIterator& operator++()
		{
			++_index;
			
			while(! _items[_index] || ! _items[_index]->is_alive)
			{
				++_index;
			}
			
			return *this;
		}
		
		virtual BaseIterator operator++(int)
		{
			auto previous = *this;
			
			++*this;
			
			return previous;
		}
		
		virtual BaseIterator& operator--()
		{
			--_index;
			
			while(! _items[_index] || ! _items[_index]->is_alive)
			{
				--_index;
			}
			
			return *this;
		}
		
		virtual BaseIterator operator--(int)
		{
			auto following = *this;
			
			--*this;
			
			return following;
		}
		
		virtual bool operator==(const BaseIterator& other)
		{
			return _items == other._items && _index == other._index;
		}
		
		virtual bool operator!=(const BaseIterator& other)
		{
			return ! (*this == other);
		}
		
		
	protected:
		
		size_t _index;
		
		Item** _items;
	};
	
public:
	
	
	class ConstIterator : public BaseIterator
	{
	public:
		
		using BaseIterator::_items;
		using BaseIterator::_index;
		
		ConstIterator(Item** items = nullptr, size_t index = 0)
		: BaseIterator(items, index)
		{ }
		
		const Pair& operator*() const
		{
			return _items[_index]->pair;
		}
		
		const Pair* operator->() const
		{
			return &_items[_index]->pair;
		}
	};
	
	class Iterator : public BaseIterator
	{
	public:
		
		using BaseIterator::_items;
		using BaseIterator::_index;
		
		Iterator(Item** items = nullptr, size_t index = 0)
		: BaseIterator(items, index)
		{ }
		
		Pair& operator*()
		{
			return _items[_index]->pair;
		}
		
		Pair* operator->() const
		{
			return &_items[_index]->pair;
		}
		
		operator ConstIterator() const
		{
			return {_items, _index};
		}
		
	};
	
	HashMap2(const hash_function_t& function = std::hash<Key>(),
			 size_t capacity = minimum_capacity)
	: _items(new Item*[capacity + 1])
	, _size(0)
	, _alive(0)
	, _capacity(capacity)
	, _hash_function(function)
	, _end(_items, _capacity)
	{
		_nullify();
		
		_items[capacity] = new Item;
	}
	
	HashMap2(std::initializer_list<std::pair<Key, Value>> items,
			 const hash_function_t& function = std::hash<Key>(),
			 size_t capacity = minimum_capacity)
	: _size(0)
	, _alive(0)
	, _hash_function(function)
	{
		_capacity = std::max(capacity, items.size() * 2);
		
		_items = new Item*[_capacity];
		
		_nullify();
		
		_end = Iterator(_items, _capacity);
	}
	
	HashMap2(const HashMap2& other)
	: _size(other._size)
	, _alive(other._alive)
	, _capacity(other._capacity)
	, _hash_function(other._hash_function)
	{
		_items = new Item*[_capacity];
		
		for (size_t i = 0; i < _capacity; ++i)
		{
			if (other._items[i]) _items[i] = new Item(*other._items[i]);
			
			else _items[i] = nullptr;
		}
		
		_end = Iterator(_items, _capacity);
	}
	
	HashMap2(HashMap2&& other) noexcept
	: HashMap2()
	{
		swap(other);
	}
	
	HashMap2& operator=(HashMap2 other) noexcept
	{
		swap(other);
	}
	
	void swap(HashMap2& other)
	{
		using std::swap;
		
		swap(_items, other._items);
		
		swap(_size, other._size);
		
		swap(_alive, other._alive);
		
		swap(_capacity, other._capacity);
		
		swap(_hash_function, other._hash_function);
		
		swap(_end, other._end);
	}
	
	friend void swap(HashMap2& first, HashMap2& second)
	{
		first.swap(second);
	}
	
	~HashMap2()
	{
		for (size_t i = 0; i < _capacity; ++i)
		{
			delete _items[i];
		}
		
		delete [] _items;
	}
	
	
	Iterator begin()
	{
		std::size_t index = 0;
		
		while(! _items[index] || ! _items[index]->is_alive) ++index;
		
		return {_items, index};
	}
	
	Iterator end()
	{
		return _end;
	}
	
	
	ConstIterator begin() const
	{
		std::size_t index = 0;
		
		while(! _items[index] || ! _items[index]->is_alive) ++index;
		
		return {_items, index};
	}
	
	ConstIterator end() const
	{
		return _end;
	}
	
	
	Iterator insert(const Key& key, const Value& value)
	{
		size_t index = _hash(key);
		
		for (size_t step = 0; _items[index]; index = _hash(key, ++step))
		{
			if (_items[index]->is_alive && _items[index]->key == key)
			{
				_items[index]->value = value;
			}
		}
		
		_items[index] = new Item(key, value);
		
		++_alive;
		
		if (++_size == _capacity/2)
		{
			_resize();
			
			return find(key);
		}
		
		return {_items, index};
	}
	
	template<typename Itr>
	void insert(Itr begin, Itr end)
	{
		for ( ; begin != end; ++begin)
		{
			insert(*begin);
		}
	}
	
	
	void erase(const Key& key)
	{
		bool found = erase_if_found(key);
		
		if (! found) throw std::invalid_argument("No such key to erase!");
	}
	
	void erase(Iterator itr)
	{
		erase(*itr);
	}
	
	bool erase_if_found(const Key& key)
	{
		size_t index = _hash(key);
		
		for (size_t step = 0; _items[index]; index = _hash(key, ++step))
		{
			if (_items[index]->is_alive && _items[index]->key == key)
			{
				_items[index]->is_alive = false;
				
				if (--_alive == _capacity/8) _resize();
				
				return true;
			}
		}
		
		return false;
	}
	
	template<typename Itr>
	void erase(Itr begin, Itr end)
	{
		for ( ; begin != end; ++begin)
		{
			erase(*begin);
		}
	}
	
	void clear()
	{
		for (size_t i = 0; i < _capacity; ++i)
		{
			delete _items[i];
		}
		
		delete [] _items;
		
		_capacity = minimum_capacity;
		
		_items = new Item*[_capacity + 1];
		
		_items[_capacity] = new Item;
		
		_end = Iterator(_items, _capacity);
		
		_nullify();
		
		_alive = _size = 0;
	}
	
	
	bool contains(const Key& key) const
	{
		size_t index = _hash(key);
		
		for(size_t step = 0; _items[index]; index = _hash(key, ++step))
		{
			if (_items[index]->is_alive &&
				_items[index]->key == key) return true;
		}
		
		return false;
	}
	
	
	Value& at(const Key& key)
	{
		return _at(key);
	}
	
	const Value& at(const Key& key) const
	{
		return _at(key);
	}
	
	Iterator find(const Key& key)
	{
		return _find(key);
	}
	
	ConstIterator find(const Key& key) const
	{
		return _find(key);
	}
	
	
	Value& operator[](const Key& key)
	{
		size_t index = _hash(key);
		
		for (size_t step = 0; _items[index]; index = _hash(key, ++step))
		{
			if (_items[index]->is_alive && _items[index]->key == key)
			{
				return _items[index]->value;
			}
		}
		
		Item* item = new Item(key);
		
		_items[index] = item;
		
		++_alive;
		
		if (++_size == _capacity/2) _resize();
		
		return item->value;
	}
	
	
	std::pair<Iterator, bool> insert_or_assign(const Key& key,
											   const Value& value)
	{
		size_t index = _hash(key);
		
		for (size_t step = 0; _items[index]; index = _hash(key, ++step))
		{
			if (_items[index]->is_alive && _items[index]->key == key)
			{
				_items[index]->value = value;
				
				return {{_items, index}, false};
			}
		}
		
		_items[index] = new Item(key, value);
		
		++_alive;
		
		if (++_size == _capacity/2)
		{
			_resize(_capacity * 2);
			
			return {find(key), true};
		}
		
		return {{_items, index}, true};
	}
	
	bool insert_or_assign(const Pair& pair)
	{
		insert_or_assign(pair.key, pair.value);
	}
	
	
	size_t size() const
	{
		return _alive;
	}
	
	size_t capacity() const
	{
		return _capacity;
	}
	
	bool is_empty() const
	{
		return _alive == 0;
	}
	
	
	const hash_function_t& hash_function() const
	{
		return _hash_function;
	}

private:
	
	Value& _at(const Key& key) const
	{
		size_t index = _hash(key);
		
		for(size_t step = 0; _items[index]; index = _hash(key, ++step))
		{
			if (_items[index]->is_alive && _items[index]->key == key)
			{
				return _items[index]->value;
			}
		}
		
		throw std::invalid_argument("No such key!");
	}
	
	Iterator _find(const Key& key) const
	{
		size_t index = _hash(key);
		
		for (size_t step = 0; _items[index]; index = _hash(key, ++step))
		{
			if (_items[index]->is_alive && _items[index]->key == key)
			{
				return {_items, index};
			}
		}
		
		return _end;
	}
	
	size_t _linear_hash(const Key& key, size_t step = 0) const
	{
		return (_hash_function(key) + step) % _capacity;
	}
	
	size_t _quadratic_hash(const Key& key, size_t step = 0) const
	{
		static const size_t a = 99;
		static const size_t b = 13;
		
		const size_t offset = (a * step) + (b * (step * step));
		
		return (_hash_function(key) + offset) % _capacity;
	}
	
	size_t _double_hash(const Key& key, size_t step = 0) const
	{
		static const size_t a = 57;
		static const size_t b = 69;
		static const size_t p_1 = 99;

		static const size_t c = 131;
		static const size_t d = 23;
		static const size_t p_2 = 77;
		
		size_t pre_hash = _hash_function(key);
		
		size_t h_1 = _universal_hash(pre_hash, a, b, p_1);
		size_t h_2 = _universal_hash(pre_hash, c, d, p_2);
		
		return (h_1 + step * h_2) % _capacity;
		
	}
	
	size_t _universal_hash(size_t pre_hash,
						   size_t constant_1,
						   size_t constant_2,
						   size_t prime) const
	{
		return ((constant_1 * pre_hash + constant_2) % prime) % _capacity;
	}
	
	size_t _hash(const Key& key, size_t step = 0) const
	{
		return _double_hash(key, step);
	}
	
	void _resize()
	{
		size_t new_capacity = _alive * 4;
		
		if (new_capacity < minimum_capacity) new_capacity = minimum_capacity;

		const size_t old_capacity = _capacity;
		
		Item** old = _items;
		
		_capacity = new_capacity;
		
		_items = new Item*[_capacity + 1];
		
		_nullify();
		
		for (size_t i = 0; i < old_capacity; ++i)
		{
			if (old[i] && old[i]->is_alive)
			{
				size_t index = _hash(old[i]->key);
				
				for (size_t step = 1; _items[index]; ++step)
				{
					index = _hash(old[i]->key, step);
				}
				
				_items[index] = old[i];
				
				old[i] = nullptr;
			}
			
			else delete old[i];
		}
		
		delete [] old;
		
		_size = _alive;

		_items[_capacity] = new Item;
		
		_end = Iterator(_items, _capacity);
	}
	
	void _nullify()
	{
		for (size_t i = 0; i < _capacity; ++i)
		{
			_items[i] = nullptr;
		}
	}
	
	
	Item** _items;
	
	size_t _size;
	
	size_t _alive;
	
	size_t _capacity;
	
	hash_function_t _hash_function;
	
	Iterator _end;
};