1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980 |
- #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 */
|