Is there a flat unsorted map/set implementation?

Question

There is the boost.container flat_map and others, and the Loki AssocVector and many others like these which keep the elements sorted.

Is there a modern (c++11 move-enabled, 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 wouldn't always make sense)

Answer 1

Please look at the sfl library that I have recently updated to GitHub: https://github.com/slavenf/sfl-library

It is C++11 header-only library that offers flat ordered and unordered containers that store elements contiguously in memory. All containers meet requirements of Container, AllocatorAwareContainer and ContiguousContainer. Library is licensed under zlib license.

Answer 2

Evgeny Panasyuk is correct, I believe what you want is an Open Address Hash Map.
This fits exactly your requirement, only 1 flat buffer, no allocation of nodes, no pointers to follow, and unsorted.

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

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

Also you might want to take a look the benchmark page of flat_map:
boost::flat_map and its performance compared to map and unordered_map
The OAHM is performing very close to the flat_map in all tests, except iteration.

Answer 3

Something like this?

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 a template argument, so you can use a SBO vector-like structure if you choose.

In theory, I should expose a template parameter for replacing equals on the keys. I did, however, make the key-search functions transparent.

Answer 4

There's 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 modulo the length of the vector, but then you'll have to figure out a way to handle collisions and all the resulting problems manually. Not sure I recommended that.

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

Answer 5

If the sets are sure to be small then you can just use a std::vector (or std::deque) and do lookup using linear searches. An O(n) linear search over a small vector can be faster than an O(log(n)) search over a more complicated structure such as a red-black tree.

So you could just put elements in a vector without sorting them. You would still need to do some shuffling if you remove elements, but that will always be true for a flat vector-like structure whether it's sorted or not, unless you only ever remove the back element. Why is it important that it's flat anyway?