OrderedHashMap (挿入順も保持する連想配列)

ordered_hash_map.hpp

// ordered_hash_map.hpp
//   https://gist.github.com/m4saka/d02af613dec3481a5f7375657d26cfc2
// The MIT License (https://opensource.org/licenses/MIT)
// Copyright (c) 2020 masaka

#pragma once
#include <type_traits>
#include <vector>
#include <unordered_map>
#include <cstddef>

// 挿入順も保持する連想配列
// (名前によるアクセスとインデックスによるアクセスが定数時間,
//  ただしメモリ効率や削除効率は重視されない)
template <typename Key, typename Value>
class OrderedHashMap
    : private std::vector<std::pair<Key, Value>> // vectorはvirtualなデストラクタを持たないのでprivate継承
{
    // インデックスと衝突するのでキーに整数型は受け付けない
    static_assert(
        !std::is_integral<Key>::value, // Key型は整数型でない
        "OrderedHashMap does not allow an integer type for the key");

private:
    // キーをもとにインデックスを引くハッシュテーブル
    // (削除時のメモリサイズ計算を安全にするため, アクセス速度を多少犠牲にしてポインタではなくインデックスで持つ)
    std::unordered_map<Key, std::size_t> m_idxTable;

public:
    // 基本的にvectorのものを受け継ぐ
    using std::vector<std::pair<Key, Value>>::at;
    using std::vector<std::pair<Key, Value>>::begin;
    using std::vector<std::pair<Key, Value>>::end;
    using std::vector<std::pair<Key, Value>>::cbegin;
    using std::vector<std::pair<Key, Value>>::cend;
    using std::vector<std::pair<Key, Value>>::crbegin;
    using std::vector<std::pair<Key, Value>>::crend;
    using std::vector<std::pair<Key, Value>>::back;
    using std::vector<std::pair<Key, Value>>::empty;
    using std::vector<std::pair<Key, Value>>::size;
    using std::vector<std::pair<Key, Value>>::operator[];
    using typename std::vector<std::pair<Key, Value>>::iterator;

    OrderedHashMap() = default;

    // 要素を直接構築
    template <class... Args>
    void emplace(Args && ... args)
    {
        std::pair<Key, Value> pair(std::forward<Args>(args)...);

        // ハッシュテーブルに挿入されたかどうか判定
        // (emplaceはハッシュテーブル内に既に同じキーが存在する場合は挿入しないため)
        if (m_idxTable.emplace(pair.first, size()).second)
        {
            // 配列へムーブ挿入
            std::vector<std::pair<Key, Value>>::push_back(std::move(pair));
        }
    }

    // 要素を挿入(const参照バージョン)
    void insert(const std::pair<Key, Value> & pair)
    {
        m_idxTable.emplace(pair.first, size());
        std::vector<std::pair<Key, Value>>::push_back(pair);
    }

    // 要素を挿入(右辺値参照バージョン)
    void insert(std::pair<Key, Value> && pair)
    {
        m_idxTable.emplace(pair.first, size());
        std::vector<std::pair<Key, Value>>::push_back(std::move(pair));
    }

    // キーに一致する要素数を返す(0または1)
    std::size_t count(const Key & key) const
    {
        return m_idxTable.count(key);
    }

    // 全要素削除
    void clear() noexcept
    {
        std::vector<std::pair<Key, Value>>::clear();
        m_idxTable.clear();
    }

    // 要素数分の領域の事前確保
    void reserve(std::size_t n)
    {
        std::vector<std::pair<Key, Value>>::reserve(n);
        m_idxTable.reserve(n);
    }

    // イテレータによる要素の削除
    void erase(const typename std::vector<std::pair<Key, Value>>::iterator & it)
    {
        // vectorからの削除
        auto deletedIdx = std::distance(begin(), it);
        std::vector<std::pair<Key, Value>>::erase(it);

        // unordered_mapからの削除(非効率)
        typename std::unordered_map<Key, std::size_t>::iterator itrToDelete;
        for (auto itr = m_idxTable.begin(); itr != m_idxTable.end(); ++itr)
        {
            if ((*itr).second == deletedIdx)
            {
                // unordered_mapなのでeraseによるイテレータ破壊は起きない
                // (eraseではrehashは起きない)ので問題ないはずだが, 念のため
                // ループ中の削除は避ける
                itrToDelete = itr;
            }
            else if ((*itr).second > deletedIdx)
            {
                // インデックスを切り詰められた分だけデクリメント
                --(*itr).second;
            }
        }
        m_idxTable.erase(itrToDelete);
    }

    // キーによる要素の削除
    typename std::vector<std::pair<Key, Value>>::iterator erase(const Key & key)
    {
        if (m_idxTable.count(key))
        {
            auto idxToDelete = m_idxTable.at(key);

            // unordered_mapからの削除
            m_idxTable.erase(key);
            for (auto && pair : m_idxTable)
            {
                if (pair.second > idxToDelete)
                {
                    // インデックスを切り詰められる分だけデクリメント
                    --pair.second;
                }
            }

            // vectorからの削除
            return std::vector<std::pair<Key, Value>>::erase(begin() + idxToDelete);
        }
        else
        {
            return end();
        }
    }

    // 添字アクセス(非constバージョン)
    Value & operator[](const Key & key)
    {
        if (m_idxTable.count(key))
        {
            // 要素が存在する場合はその値を返す
            return (*this)[m_idxTable[key]].second;
        }
        else
        {
            // 要素が存在しない場合は値をデフォルトコンストラクトする
            m_idxTable.emplace(key, size());
            std::vector<std::pair<Key, Value>>::emplace_back(key, Value());
            return back().second;
        }
    }

    // 添字アクセス(constバージョン)
    const Value & operator[](const Key & key) const
    {
        return (*this)[m_idxTable[key]].second;
    }

    // atアクセス(非constバージョン)
    Value & at(const Key & key)
    {
        return at(m_idxTable[key]).second;
    }

    // atアクセス(constバージョン)
    const Value & at(const Key & key) const
    {
        return at(m_idxTable[key]).second;
    }
};