libsimple_compress/source/simple/compress/hash_table.hpp

#ifndef SIMPLE_COMPRESS_HASH_TABLE_HPP
#define SIMPLE_COMPRESS_HASH_TABLE_HPP

#include <cstddef> // std::size_t
#include <vector> // std::vector std::hash
#include <algorithm> // std::partition std::max
#include <functional> // std::not_fn

namespace simple::compress
{

	// why make own map? cause std devour all memory and never give it back
	template <typename Key, typename Value, std::size_t row_count>
	class hash_table
	{

		// TODO; make these contiguous, the buckets often end up very small
		std::vector<std::vector<Value>> table{row_count};
		std::size_t size_{0};

		template <typename T>
		static auto& row(T& self, const Key& key)
		{
			return self.table[std::hash<Key>{}(key) % row_count];
		}

		public:

		using key_type = Key;
		using value_type = Value;

		auto& equal_range(const Key& key)
		{
			return row(*this,key);
		}

		auto& equal_range(const Key& key) const
		{
			return row(*this,key);
		}

		void insert(const Key& key, const Value& value)
		{
			row(*this,key).push_back(value);
			++size_;
		}

		template <typename Pred>
		void erase_if(Pred&& pred)
		{
			size_ = 0;
			for(auto& row : table)
			{
				row.erase(std::partition(row.begin(), row.end(), std::not_fn(pred)), row.end());
				size_ += row.size();
			}
		}

		std::size_t size() { return size_; }

		struct stats_t
		{
			std::size_t total_elements;
			std::size_t non_empty_rows;
			std::size_t max_row_size;
		};

		stats_t stats()
		{
			stats_t s{};
			for(auto&& row : table)
				s.total_elements += row.size(), s.non_empty_rows += bool(row.size()), s.max_row_size = std::max(s.max_row_size, row.size());
			return s;
		}
	};

} // namespace simple::compress

#endif /* end of include guard */