An STLed-up hash table using seperate chaining.

SeparateChainingHashTable.cpp

template<typename Key, typename Value>
class SeparateChainingHashTable
{
public:
	
	using size_t = std::size_t;
	
	using pre_hash_t = std::function<size_t(const Key&)>;
	
	static const size_t minimum_capacity;
	
	SeparateChainingHashTable(const pre_hash_t& pre_hash = std::hash<Key>(),
							  size_t capacity = minimum_capacity,
							  size_t load_factor = 4)
	: _load_factor(load_factor)
	, _pre_hash(pre_hash)
	, _nodes(capacity / _load_factor)
	{ }
	
	SeparateChainingHashTable(const std::initializer_list<std::pair<Key, Value>>& list,
							  const pre_hash_t& pre_hash = std::hash<Key>(),
							  size_t capacity = minimum_capacity,
							  size_t load_factor = 4)
	: SeparateChainingHashTable(pre_hash,
								std::max(capacity, list.size()),
								load_factor)
	{
		for (const auto& item : list)
		{
			insert(item.first, item.second);
		}
	}
	
	SeparateChainingHashTable(const SeparateChainingHashTable& other)
	: _pre_hash(other._pre_hash)
	, _load_factor(other._load_factor)
	, _nodes(other._nodes)
	{ }
	
	SeparateChainingHashTable(SeparateChainingHashTable&& other)
	: SeparateChainingHashTable()
	{
		swap(other);
	}
	
	SeparateChainingHashTable& operator=(SeparateChainingHashTable other)
	{
		swap(other);
		
		return *this;
	}
	
	void swap(SeparateChainingHashTable& other)
	{
		// Enable ADL
		using std::swap;
		
		swap(_load_factor, other._load_factor);
		
		swap(_pre_hash, other._pre_hash);
		
		swap(_nodes, other._nodes);
	}
	
	friend void swap(SeparateChainingHashTable& first,
					 SeparateChainingHashTable& second)
	{
		first.swap(second);
	}
	
	~SeparateChainingHashTable() = default;
	
	bool insert(const Key& key, const Value& value)
	{
		auto index = _hash(key);
		
		auto node = _find(key, index);
		
		if (node != _nodes[index].end())
		{
			node.second = value;
			
			return false;
		}
		
		_nodes[index].push_back({key, value});
		
		return true;
	}
	
	
	Value& get(const Key& key)
	{
		auto index = _hash(key);
		
		auto node = _find(key, index);
		
		if (node == _nodes[index].end())
		{
			throw std::invalid_argument("No such key!");
		}
		
		return node->second;
	}
	
	const Value& get(const Key& key) const
	{
		auto node = _find(key);
		
		if (node == _nodes[index].end())
		{
			throw std::invalid_argument("No such key!");
		}
		
		return node->value;
	}
	
	
	bool contains(const Key& key)
	{
		return _find(key) != nullptr;
	}
	
	
	void erase(const Key& key)
	{
		auto index = _hash(key);
		
		auto node = _find(key, index);
		
		if (node == _nodes[index].end())
		{
			throw std::invalid_argument("No such key!");
		}
		
		_nodes.erase(node);
	}
	
	void clear()
	{
		_nodes.clear();
	}
	
	Value& operator[](const Key& key)
	{
		auto index = _hash(key);
		
		auto node = _find(key, index);
		
		if (node != _nodes[index].end()) return node->second;
		
		_nodes[index].push_back({key, Value()});
		
		return _nodes[index].back().second;
	}
	
	
	void rehash(size_t buckets)
	{
		resize(buckets * _load_factor);
	}
	
	void resize(size_t new_size)
	{
		_nodes.resize(new_size / _load_factor);
		
		rehash();
	}
	
	size_t load_factor() const
	{
		return _load_factor;
	}
	
	void load_factor(size_t alpha)
	{
		_load_factor = alpha;
		
		resize(_nodes.size());
	}
	
	
	size_t size() const
	{
		return _nodes.size();
	}
	
	bool is_empty() const
	{
		return _nodes.empty();
	}
	
private:
	
	using node_t = std::pair<Key, Value>;
	
	using chain_t = std::list<node_t>;
	
	using container_t = std::vector<chain_t>;
	
	using iterator = typename chain_t::iterator;
	
	using const_iterator = typename chain_t::const_iterator;
	
	const_iterator _find(const Key& key, size_t index) const
	{
		return std::find_if(_nodes[index].begin(),
							_nodes[index].end(),
							[&] (const auto& node) {
								return node.first == key;
							});
	}
	
	iterator _find(const Key& key, size_t index)
	{
		return std::find_if(_nodes[index].begin(),
							_nodes[index].end(),
							[&] (const auto& node) {
								return node.first == key;
							});
	}
	
	size_t _hash(const Key& key) const
	{
		return _pre_hash(key) % _nodes.size();
	}
	
	void _rehash(const container_t& old)
	{
		for (auto& chain : old)
		{
			for (auto node = chain.begin(), end = node.end(); node != end; )
			{
				auto next = std::next(node);
				
				_nodes[_hash(*node)].splice(node);
				
				node = next;
			}
		}
	}
	
	size_t _load_factor;
	
	pre_hash_t _pre_hash;
	
	container_t _nodes;
};

template<typename Key, typename Value>
const typename SeparateChainingHashTable<Key, Value>::size_t
SeparateChainingHashTable<Key, Value>::minimum_capacity = 20;