OrderedMap.hpp

[詳解]

#pragma once
 
/*
*   特定のキーの順番で管理する連想配列
* 
*/
 
#include "unordered_map"
#include "vector"
 
 
namespace Kisaragi_Lib
{
    /// <summary>
    /// 順番を持つ連想配列
    /// </summary>
    /// <typeparam name="KeyType">連想配列のKey</typeparam>
    /// <typeparam name="ValueType">連想配列の要素</typeparam>
    template<typename KeyType, typename ValueType>
    class OrderedMap
    {
    private:
        // key to keyOrder index
        std::unordered_map<KeyType, unsigned int> keyToIndex;
 
        // keyの順番を表す
        std::vector<KeyType> keyOrder;
 
        // key順に合わせてvalueを格納
        std::vector<ValueType> value;  
 
    public:
 
#pragma region コンテナ管理
 
        /// <summary>
        /// 要素を末尾に追加する.
        /// </summary>
        /// <param name="_key">引数</param>
        /// <param name="_value">要素</param>
        void Push(KeyType _key, ValueType _value)
        {
            if (keyToIndex.count(_key))
            {
                return;
            }
 
            keyToIndex.emplace(_key, keyOrder.size());
            keyOrder.push_back(_key);
            value.push_back(_value);
        }
 
        /// <summary>
        /// 要素を削除する.
        /// </summary>
        /// <param name="_key">削除する要素のKey</param>
        void Erase(KeyType _key)
        {
            if (!keyToIndex.count(_key))
            {
                return;
            }
 
            //引数を記憶
            unsigned int index = keyToIndex[_key];
            //末尾要素の引数を記憶
            unsigned int lastIndex = keyToIndex.size() - 1;
 
            //自身が末尾の場合 or 自身のみしか格納してない場合.
 
            //自身が末尾要素でない場合
            if (index != lastIndex)
            {
                //削除するKey以降のkeyToIndexを削除後に合わせる
                for (int i = index + 1; i <= lastIndex; i++)
                {
                    //indexを1下げる
                    keyToIndex[keyOrder[i]]--;
                }
            }
 
            //各配列の削除処理を行う.
            {
                //要素の削除
                value.erase(value.begin() + index);
                //疎配列の削除
                keyOrder.erase(keyOrder.begin() + index);
                //Keyの逆引きを削除
                keyToIndex.erase(_key);
            }
        }
 
        /// <summary>
        /// 配列をクリアする
        /// </summary>
        void Clear()
        {
            keyToIndex.clear();
            keyOrder.clear();
            value.clear();
        }
 
        /// <summary>
        /// _key要素があるか検索する
        /// </summary>
        /// <param name="_key">検索したい要素のkey</param>
        /// <returns>存在する : true,存在しない : false</returns>
        bool FindKey(const KeyType& _key)
        {
            return keyToIndex.count(_key);
        }
 
 
#pragma endregion
 
#pragma region 演算子オーバーロード
        /// <summary>
        /// 要素を配列として扱う
        /// </summary>
        operator std::vector<ValueType>& ()
        {
            return value;
        }
 
        /// <summary>
        /// 連想配列の要素を取得する
        /// </summary>
        /// <param name="_key">取得したい要素のkey</param>
        /// <returns>取得した要素</returns>
        ValueType& operator[](KeyType _key)
        {
            if (!FindKey(_key))
            {
                assert(false);
            }
 
            return value[keyToIndex[_key]];
        }
 
 
#pragma endregion
 
 
 
#pragma region キー管理
 
        /// <summary>
        /// 要素順を変更する.
        /// </summary>
        /// <param name="_key1">変更したい要素のKey</param>
        /// <param name="_key2">変更したい要素のKey</param>
        void SwapKeyOrder(KeyType _key1, KeyType _key2)
        {
            //keyが存在するなら.
            if (keyToIndex.count(_key1)==1 && keyToIndex.count(_key2) == 1)
            {
                //順番を入れ替える.
                keyOrder[value[_key1]] = _key2;
                keyOrder[value[_key2]] = _key1;
 
                //対応処理.
                unsigned int tmp = value[_key1];
                value[_key1] = value[_key2];
                value[_key2] = tmp;
 
                unsigned int tmpIndex = keyToIndex[_key1];
                keyToIndex[_key1] = keyToIndex[_key2];
                keyToIndex[_key2] = tmpIndex;
            }
        }
 
        /// <summary>
        /// 現在のkey順を取得する
        /// </summary>
        /// <returns>現在のkey順の配列</returns>
        const std::vector<KeyType>& KeyOrder()
        {
            return keyOrder;
        }
 
#pragma endregion
 
 
    };
}