Geek Answers Handbook

Is there a flat unsorted map / set implementation?

There is boost.container flat_map and others, and Loki AssocVector and many others like these that keep items sorted.

Is there a modern (C ++ 11 with support for moving, etc.) implementation of an unsorted vector adapted as a map / set?

The idea is to use it for very small maps / sets (less than 20 elements) and with simple keys (for which hashing does not always make sense)

+5
source share
4 answers

Something like that?

 template<class Key, class Value, template<class...>class Storage=std::vector> struct flat_map { struct kv { Key k; Value v; template<class K, class V> kv( K&& kin, V&& vin ):k(std::forward<K>(kin)), v(std::forward<V>(vin)){} }; using storage_t = Storage<kv>; storage_t storage; // TODO: adl upgrade using iterator=decltype(std::begin(std::declval<storage_t&>())); using const_iterator=decltype(std::begin(std::declval<const storage_t&>())); // boilerplate: iterator begin() { using std::begin; return begin(storage); } const_iterator begin() const { using std::begin; return begin(storage); } const_iterator cbegin() const { using std::begin; return begin(storage); } iterator end() { using std::end; return end(storage); } const_iterator end() const { using std::end; return end(storage); } const_iterator cend() const { using std::end; return end(storage); } size_t size() const { return storage.size(); } bool empty() const { return storage.empty(); } // these only have to be valid if called: void reserve(size_t n) { storage.reserve(n); } size_t capacity() const { return storage.capacity(); } // map-like interface: // TODO: SFINAE check for type of key template<class K> Value& operator[](K&& k){ auto it = find(k); if (it != end()) return it->v; storage.emplace_back( std::forward<K>(k), Value{} ); return storage.back().v; } private: // C++14, but you can just inject the lambda at point of use in 11: template<class K> auto key_match( K& k ) { return [&k](kv const& kv){ return kv.k == k; }; } public: template<class K> iterator find(K&& k) { return std::find_if( begin(), end(), key_match(k) ); } template<class K> const_iterator find(K&& k) const { return const_cast<flat_map*>(this)->find(k); } // iterator-less query functions: template<class K> Value* get(K&& k) { auto it = find(std::forward<K>(k)); if (it==end()) return nullptr; return std::addressof(it->v); } template<class K> Value const* get(K&& k) const { return const_cast<flat_map*>(this)->get(std::forward<K>(k)); } // key-based erase: (SFINAE should be is_comparible, but that doesn't exist) template<class K, class=std::enable_if_t<std::is_converible<K, Key>{}>> bool erase(K&& k) { auto it = std::remove( storage.begin(), storage.end(), key_match(std::forward<K>(k)) ); if (it == storage.end()) return false; storage.erase( it, storage.end() ); return true; } // classic erase, for iterating: iterator erase(const_iterator it) { return storage.erase(it); } template<class K2, class V2, class=std::enable_if_t< std::is_convertible< K2, Key >{}&& std::is_convertible< V2, Value >{} > > void set( K2&& kin, V2&& vin ) { auto it = find(kin); if (it != end()){ it->second = std::forward<V2>(vin); return; } else { storage.emplace_back( std::forward<K2>(kin), std::forward<V2>(vin) ); } } };

I left the container type as the template argument, so you can use the SBO vector structure if you choose.

In theory, I should set a template parameter to replace equals on keys. However, I made transparent key search functions.

+7
source

If the sets are sure that they are small, you can simply use std::vector (or std::deque ) and search using linear searches. A linear search of O (n) by small vectors can be faster than a search of O (log (n)) by a more complex structure, such as a red-black tree.

That way you can just put elements in vector without sorting them. You will still need to shuffle if you delete elements, but this will always be true for a flat vector structure, whether or not it was sorted, unless you delete only the element back. Why is this so important?

+4
source

There std::unordered_set and std::unordered_map , but as far as I know, they are not implemented using vectors.

A possible option is to write your own hash vector and hash the key using std::hash<Key> , and then index the resulting number along the length of the vector, but then you will need to figure out a way to handle collisions and all the problems that arise manually. Not sure if I recommended this.

An alternative would be to pass a custom allocator to std::unordered_set and std::unordered_map , which perform vector distribution (for example, by owning an internal vector), as suggested by @BeyelerStudios .

+1
source

Evgeny Panasyuk is right, I believe that you want to open an address hash map .
This exactly matches your requirement, only 1 flat buffer, no node allocation, no pointers and no sorting.

Otherwise, you also have flat_map / AssocVector , but they are sorted, unlike your requirement.

For OAHM, I have an implementation of an STL-like common here:
https://sourceforge.net/projects/cgenericopenaddresshashmap/

You can also take a look at the flat_map control page:
boost :: flat_map and its performance compared to the map and unordered_map
OAHM performs very close to flat_map in all tests except iteration.

+1
source

More articles:


All Articles