4
\$\begingroup\$

The following is an implementation of a (hash) map with one constraint: keep all the values in a contiguous array.

I've done this to train my skills. So far I'm not sure how to get ride of the duplicated code.

Header:

#include <algorithm>
#include <cassert>
#include <utility>
#include <vector>

/**
 * An associative container that contains values in a contiguous fashion.
 *
 * The order of the values may change (on deletion).
 */
template <typename Key, typename Value> class map
{
  // Main map's functions:
public:
  Value& operator[](const Key& key);
  std::size_t count(const Key& key) const;
  std::size_t erase(const Key& key);
  std::size_t size() const noexcept;

public:
  std::vector<Value>& getValues(void) noexcept;

private:
  typedef std::size_t   Hash;
  static std::hash<Key> Hasher; ///< A hash function
  struct Slot
  {
    Hash        hash;  ///< The key's hash
    Key         key;   ///< A copy of the key
    std::size_t index; ///< Index in the values array
  };
  ///< Hold a key, its hash and the index to the data

  typedef std::vector<Slot> Bucket;
  ///< A bucket of key-hash-index

  typedef std::array<Bucket, 10> BucketList;
  ///< A vector of buckets to clusterize the key search

  BucketList         buckets;
  std::vector<Value> values;
};

Implementation (Inlined in the same header):

template <typename Key, typename Value> std::hash<Key> map<Key, Value>::Hasher;


template <typename Key, typename Value>
Value& map<Key, Value>::operator[](const Key& key)
{
  const auto h = Hasher(key);

  std::size_t indexInBucketList = 0;
  Bucket&     bucket            = buckets[h % buckets.size()];
  while (indexInBucketList < bucket.size()) {
    const auto& slot = bucket[indexInBucketList];
    if (slot.hash == h && slot.key == key) {
      return values[slot.index];
    }
    indexInBucketList++;
  }
  values.push_back({});
  bucket.push_back({h, key, values.size() - 1});
  return values.back();
}

template <typename Key, typename Value>
std::size_t
map<Key, Value>::count(const Key& key) const
{
  if (values.size() < 1) return 0;

  const auto h = Hasher(key);

  std::size_t   indexInBucketList = 0;
  const Bucket& bucket            = buckets[h % buckets.size()];
  while (indexInBucketList < bucket.size()) {
    const auto& slot = bucket[indexInBucketList];
    if (slot.hash == h && slot.key == key) {
      return 1;
    }
    indexInBucketList++;
  }
  return 0;
}

template <typename Key, typename Value>
std::size_t
map<Key, Value>::erase(const Key& key)
{
  const auto h = Hasher(key);

  std::size_t indexInBucketList = 0;
  Bucket&     bucket            = buckets[h % buckets.size()];
  while (indexInBucketList < bucket.size()) {
    const auto& slot = bucket[indexInBucketList];
    if (slot.hash == h && slot.key == key) {
      // First delete the data
      const auto index = slot.index;
      if ((index + 1) < values.size()) { // Avoid swap on the end element
        constexpr bool do_copy = std::is_trivially_copyable<Value>::value;
        if (do_copy) {
          values[index] = values.back();
        } else {
          std::swap(values[index], values.back());
        }
      }
      // (No better way to) Update the bucket of the end data:
      for (std::size_t i = 0; i < buckets.size(); ++i) {
        for (auto& s : buckets[i]) {
          const auto size_minus_one = values.size() - 1;
          if (s.index == size_minus_one) {
            s.index = index;
            goto removal;
          }
        }
      }

    removal:
      values.pop_back();

      // Then delete the slot
      if ((indexInBucketList + 1) < bucket.size()) {
        bucket[indexInBucketList] = bucket.back();
      }
      bucket.pop_back();
      return 1;
    }
    indexInBucketList++;
  }
  return 0;
}

template <typename Key, typename Value>
std::size_t
map<Key, Value>::size() const noexcept
{
  return values.size();
}


template <typename Key, typename Value>
std::vector<Value>&
map<Key, Value>::getValues(void) noexcept
{
  return values;
}
\$\endgroup\$
  • \$\begingroup\$ This is pretty hard to review without seeing the implementation of BucketList and Bucket, considering a fair bit of the complexity is possibly hidden in there. \$\endgroup\$ – Frank Sep 22 '17 at 2:38
  • \$\begingroup\$ Bucket is a std::vector of Slot. And BucketList is a vector of Bucket \$\endgroup\$ – FloFu Sep 28 '17 at 9:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.