Class unordered_map_small

src/fl/stl/unordered_map_small.h:32–471

template <typename Key, typename Value,
          typename Equal = fl::SmallMapEqualTo<Key>>
class unordered_map_small {
  public:
    enum insert_result { inserted = 0, exists = 1, at_capacity = 2 };

    using key_type = Key;
    using mapped_type = Value;
    using value_type = fl::pair<Key, Value>;
    using size_type = fl::size;
    using key_equal = Equal;
    using vector_type = fl::vector<value_type>;

    // Forward iterator that skips unoccupied slots.
    struct iterator {
        using reference = value_type&;
        using pointer = value_type*;
        using iterator_category = fl::forward_iterator_tag;

        iterator() FL_NOEXCEPT : mMap(nullptr), mIdx(0) {}
        iterator(unordered_map_small* map, size_type idx) FL_NOEXCEPT
            : mMap(map), mIdx(idx) { advance_to_occupied(); }

        reference operator*() const FL_NOEXCEPT { return mMap->mData[mIdx]; }
        pointer operator->() const FL_NOEXCEPT { return &mMap->mData[mIdx]; }

        iterator& operator++() FL_NOEXCEPT { ++mIdx; advance_to_occupied(); return *this; }
        iterator operator++(int) FL_NOEXCEPT { iterator t = *this; ++(*this); return t; }

        bool operator==(const iterator& o) const FL_NOEXCEPT { return mIdx == o.mIdx; }
        bool operator!=(const iterator& o) const FL_NOEXCEPT { return mIdx != o.mIdx; }

      private:
        void advance_to_occupied() FL_NOEXCEPT {
            if (!mMap) return;
            size_type cap = mMap->mData.size();
            while (mIdx < cap && !mMap->mOccupied.test(mIdx)) ++mIdx;
        }
        unordered_map_small* mMap;
        size_type mIdx;
        friend class unordered_map_small;
    };

    struct const_iterator {
        using reference = const value_type&;
        using pointer = const value_type*;
        using iterator_category = fl::forward_iterator_tag;

        const_iterator() FL_NOEXCEPT : mMap(nullptr), mIdx(0) {}
        const_iterator(const unordered_map_small* map, size_type idx) FL_NOEXCEPT
            : mMap(map), mIdx(idx) { advance_to_occupied(); }
        const_iterator(const iterator& it) FL_NOEXCEPT
            : mMap(it.mMap), mIdx(it.mIdx) {}

        reference operator*() const FL_NOEXCEPT { return mMap->mData[mIdx]; }
        pointer operator->() const FL_NOEXCEPT { return &mMap->mData[mIdx]; }

        const_iterator& operator++() FL_NOEXCEPT { ++mIdx; advance_to_occupied(); return *this; }
        const_iterator operator++(int) FL_NOEXCEPT { const_iterator t = *this; ++(*this); return t; }