A wrapper of unordered_map that still has O(1) insertion, erasing and access, but keeps the order deterministic

deterministic-unordered-map.hpp

#include <functional> // std::equal_to, std::hash
#include <iterator>
#include <memory> // std::alloactor
#include <type_traits> // std::conditional_t
#include <unordered_map>
#include <utility> // std::pair, std::swap
#include <vector>

////////////////////////////////////////////////////////////////////////////////
// A simple implementation of a deterministic wrapper of unordered_map.
//
// When each element is inserted, it keeps track of the index of insertion, so
// that the final order is only dependent on the order of insertion and erasing,
// but not on the key value.
//
// It is slower and takes more memory than the standard std::unordered_map but
// preserves the constant complexity (on average) in inserting, erasing and
// accessing.
//
// Possible improvements include:
//   - Use pointers instead of values in internal index tracker (index_) to
//     save space.
//   - Implement more interface to resemble the STL library.
////////////////////////////////////////////////////////////////////////////////

template<
    class Key,
    class T,
    class Hash = std::hash<Key>,
    class KeyEqual = std::equal_to<Key>,
    class Allocator = std::allocator< std::pair<const Key, T> >
> class deterministic_unordered_map {

    ///////////////////////////////////////////////////////////////////////////
    // Types
    ///////////////////////////////////////////////////////////////////////////
public:
    using umap_type = std::unordered_map< Key, T, Hash, KeyEqual, Allocator >;
    using vec_type = std::vector< const Key * >;

    using key_type = Key;
    using mapped_type = T;
    using value_type = std::pair< const Key, T >;
    using hasher = Hash;
    using key_equal = KeyEqual;
    using allocator_type = Allocator;
    using size_type = typename vec_type::size_type;

    using reference = value_type&;
    using const_reference = const value_type&;

private:
    struct hash_by_ptr_ {
        std::size_t operator()(const Key* k) { return hasher()(*k); }
    };
    struct key_equal_by_ptr_ {
        bool operator()(const Key* k1, const Key* k2) { return key_equal()(*k1, *k2); }
    };

public:
    using index_type = std::unordered_map< Key*, size_type, hash_by_ptr_, key_equal_by_ptr_ >;

    // The random-access iterator
private:
    template< bool Const = false > class iterator_impl_;
public:
    using iterator = iterator_impl_< false >;
    using const_iterator = iterator_impl_< true >;


    ///////////////////////////////////////////////////////////////////////////
    // Data members
    ///////////////////////////////////////////////////////////////////////////
private:

    umap_type data_;
    vec_type order_;
    std::unordered_map<key_type, size_type> index_;


    ///////////////////////////////////////////////////////////////////////////
    // Methods
    ///////////////////////////////////////////////////////////////////////////
public:

    // Currently this map has to be initialized from empty
    deterministic_unordered_map() {}

    // Erase by position
    iterator erase(const_iterator position) {
        const key_type& key = position->first;
        const key_type& key_last = *order_.back();
        if(!key_equal()(key, key_last)) {
            // Swap the current key with the last key stored in order_ vector.
            size_type& idx_key = index_[key]; // (avg O(1))
            size_type& idx_key_last = index_[key_last]; // (avg O(1))
            std::swap(order_[idx_key], order_[idx_key_last]); // Swap key with key_last stored in vector (O(1))
            idx_key_last = idx_key; // Update key_last index with key index
        }
        index_.erase(key); // Erase key in index map (avg O(1))
        order_.pop_back(); // Remove last element (O(1))
        auto res = data_.erase(position); // (avg O(1))
        return iterator(position);
    }
    // Erase by key
    size_type erase(const key_type& k) {
        size_type result = data_.erase(k); // (avg O(1))
        if(result) {
            const key_type& key_last = *order_.back();
            if(!key_equal()(k, key_last)) {
                // Swap the current key with the last key stored in order_ vector.
                size_type& idx_key = index_[k]; // (avg O(1))
                size_type& idx_key_last = index_[key_last]; // (avg O(1))
                std::swap(order_[idx_key], order_[idx_key_last]); // Swap key with key_last stored in vector (O(1))
                idx_key_last = idx_key; // Update key_last index with key index
            }
            index_.erase(k); // Erase key in index map (avg O(1))
            order_.pop_back(); // Remove last element (O(1))
        }
        return result;
    }
    
    std::pair<iterator, bool> insert(const value_type& val) {
        auto result = data_.insert(val); // Normal insertion (avg O(1))
        if(result.second) {
            index_.insert({val.first, order_.size()}); // Map key to index (avg O(1))
            order_.emplace_back(&result.first->first); // Store key in vector (O(1))
        }
        iterator it(&order_.back(), &data_);
        return std::pair<iterator, bool>({it, result.second});
    }
    // Move insertion is not implemented
    
    mapped_type& operator[](const key_type& k) {
        if(data_.find(k) == data_.end()) { // (avg O(1))
            // Need insertion
            index_.insert({k, order_.size()}); // Map key to index (avg O(1))
            order_.emplace_back(&k); // Store key in vector (O(1))
        }
        return data_[k];
    }
    // operator[] that takes rvalue reference is not implemented
    
    // This function is only dependent on the insertion order.
    // No bound checking is performed.
    mapped_type& get_by_index(size_type pos) {
        return operator[](*order_[pos]);
    }
    
    size_type size()const noexcept {
        return data_.size();
    }

};

template< class Key, class T, class Hash, class KeyEqual, class Allocator, bool Const >
inline deterministic_unordered_map< Key, T, Hash, KeyEqual, Allocator >::template iterator_impl_< Const > operator+(
    typename deterministic_unordered_map< Key, T, Hash, KeyEqual, Allocator >::vec_type::iterator::difference_type n,
    const typename deterministic_unordered_map< Key, T, Hash, KeyEqual, Allocator >::template iterator_impl_< Const >& it
) { return it + n; }

template< class Key, class T, class Hash, class KeyEqual, class Allocator >
template< bool Const >
class deterministic_unordered_map< Key, T, Hash, KeyEqual, Allocator >::iterator_impl_ {
public:
    using difference_type = typename vec_type::iterator::difference_type;
    using value_type = deterministic_unordered_map::value_type;
    using pointer = typename std::conditional_t< Const, const value_type *, value_type * >;
    using reference = typename std::conditional_t< Const, const value_type &, value_type & >;
    using iterator_category = std::random_access_iterator_tag;

    iterator_impl_(typename vec_type::iterator::pointer ptr, umap_type* storage) : ptr_(ptr), storage_(storage) {}

    reference operator*()const { return *storage_->find(**ptr_); } // (avg O(1))
    pointer operator->()const { return storage_->find(**ptr_); } // (avg O(1))

    iterator_impl_& operator++() { ++ptr_; return *this; }
    iterator_impl_ operator++(int) { iterator_impl_ res = *this; ++ptr_; return res; }
    iterator_impl_& operator--() { --ptr_; return *this; }
    iterator_impl_ operator--(int) { iterator_impl_ res = *this; --ptr_; return res; }
    iterator_impl_& operator+=(difference_type n) { ptr_ += n; return *this; }
    iterator_impl_ operator+(difference_type n)const { iterator_impl_ res = *this; res += n; return res; }
    friend iterator_impl_ (::operator+ < Key, T, Hash, KeyEqual, Allocator, Const >)(difference_type n, const iterator_impl_& it);
    iterator_impl_& operator-=(difference_type n) { ptr_ -= n; return *this; }
    iterator_impl_ operator-(difference_type n)const { iterator_impl_ res = *this; res -= n; return res; }
    difference_type operator-(const iterator_impl_& rhs)const { return ptr_ - rhs.ptr_; }
    reference operator[](difference_type n)const { return *storage_->find(**(ptr_ + n)); } // (avg O(1))

    bool operator==(const iterator_impl_& rhs)const { return ptr_ == rhs.ptr_ && storage_ == rhs.storage_; }
    bool operator!=(const iterator_impl_& rhs)const { return ptr_ != rhs.ptr_ || storage_ != rhs.storage_; }
    bool operator<(const iterator_impl_& rhs)const { return ptr_ < rhs.ptr_; }
    bool operator>(const iterator_impl_& rhs)const { return ptr_ > rhs.ptr_; }
    bool operator>=(const iterator_impl_& rhs)const { return !operator<(rhs); }
    bool operator<=(const iterator_impl_& rhs)const { return !operator>(rhs); }

private:
    typename vec_type::iterator::pointer ptr_; // const Key **
    umap_type* storage_;

};