SparseSet.hpp

[詳解]

#pragma once
 
#include <vector>
#include <unordered_map>
 
 
namespace Kisaragi_Lib
{
    /// <summary>
    /// 
    /// </summary>
    /// <typeparam name="Key"></typeparam>
    /// <typeparam name="Value"></typeparam>
    template<class Key, class Value>
    class SparseSet
    {
    private:
        /// <summary>
        /// 疎な配列、keyを引数としてvalue配列の引数を取得する
        /// </summary>
        std::unordered_map<Key, unsigned int>sparseContainer;
 
        /// <summary>
        /// 密な配列、実際のバリューが格納される
        /// </summary>
        std::vector<Value>denseContainer;
 
        /// <summary>
        /// denseをループ処理するときにkeyがほしい時などに使うやつ
        /// </summary>
        std::vector<Key>indexToKey;
    public:
 
        /// <summary>
        /// 配列の追加
        /// </summary>
        /// <param name="_key">配列のKey</param>
        /// <param name="_value">配列の要素</param>
        void Add(const Key& _key, const Value& _value)
        {
            // Keyが重複している場合は、返す
            if (sparseContainer.count(_key) == 1)
            {
                return;
            }
 
            // valueの値を格納.
            denseContainer.push_back(_value);
 
            //格納する引数を計算
            unsigned int index = denseContainer.size() - 1;
 
            // 疎な配列を登録.
            sparseContainer.emplace(_key, index);
 
            // 反転も登録
            indexToKey.push_back(_key);
        }
 
        /// <summary>
        /// _key要素を削除する
        /// </summary>
        /// <param name="_key">削除する要素のKey</param>
        void Erase(const Key& _key)
        {
 
            // Keyが存在しない場合返す
            if (sparseContainer.count(_key) == 0)
            {
                return;
            }
 
 
            //引数を記憶
            unsigned int index = sparseContainer[_key];
            //末尾要素の引数を記憶
            unsigned int lastIndex = denseContainer.size() - 1;
 
            //自身が末尾の場合 or 自身のみしか格納してない場合.
            // 末尾の場合交換せずに処理できる
 
            //自身が末尾要素でない場合、awapを行う
            if (index != lastIndex)
            {
                //最後の要素と入れ替える
                std::swap(denseContainer[index], denseContainer[lastIndex]);
 
                //疎配列の交換
                sparseContainer[indexToKey[lastIndex]] = index;
 
                //indexToKeyの交換
                std::swap(indexToKey[index], indexToKey[lastIndex]);
            }
 
            //各配列の削除処理を行う.
            {
                //要素の削除
                denseContainer.pop_back();
                //疎配列の削除
                sparseContainer.erase(_key);
                //Keyの逆引きを削除
                indexToKey.pop_back();
            }
        }
 
 
        operator std::vector<Value>& ()
        {
            return denseContainer;
        }
 
        Value& operator[](Key _key)
        {
            return denseContainer[sparseContainer[_key]];
        }
    };
}