Kisaragi_Lib::SparseSet< Key, Value > クラステンプレート

#include <SparseSet.hpp>

公開メンバ関数
void	Add (const Key &_key, const Value &_value)
	配列の追加
void	Erase (const Key &_key)
	_key要素を削除する
	operator std::vector< Value > & ()
Value &	operator[] (Key _key)

非公開変数類
std::unordered_map< Key, unsigned int >	sparseContainer
	疎な配列、keyを引数としてvalue配列の引数を取得する
std::vector< Value >	denseContainer
	密な配列、実際のバリューが格納される
std::vector< Key >	indexToKey
	denseをループ処理するときにkeyがほしい時などに使うやつ

詳解

template<class Key, class Value>
class Kisaragi_Lib::SparseSet< Key, Value >

テンプレート引数

Key
Value

関数詳解

Add()

template<class Key, class Value>

void Kisaragi_Lib::SparseSet< Key, Value >::Add ( const Key & _key, const Value & _value )

inline

配列の追加

引数

_key	配列のKey
_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);
        }

Erase()

template<class Key, class Value>

void Kisaragi_Lib::SparseSet< Key, Value >::Erase ( const Key & _key )

inline

_key要素を削除する

引数

_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 > &()

template<class Key, class Value>

Kisaragi_Lib::SparseSet< Key, Value >::operator std::vector< Value > & ( )

inline

        {
            return denseContainer;
        }

operator[]()

template<class Key, class Value>

Value & Kisaragi_Lib::SparseSet< Key, Value >::operator[] ( Key _key )

inline

        {
            return denseContainer[sparseContainer[_key]];
        }

メンバ詳解

sparseContainer

template<class Key, class Value>

std::unordered_map<Key, unsigned int> Kisaragi_Lib::SparseSet< Key, Value >::sparseContainer

private

疎な配列、keyを引数としてvalue配列の引数を取得する

参照元 Add(), Erase(), operator[]().

denseContainer

template<class Key, class Value>

std::vector<Value> Kisaragi_Lib::SparseSet< Key, Value >::denseContainer

private

密な配列、実際のバリューが格納される

参照元 Add(), Erase(), operator std::vector< Value > &(), operator[]().

indexToKey

template<class Key, class Value>

std::vector<Key> Kisaragi_Lib::SparseSet< Key, Value >::indexToKey

private

denseをループ処理するときにkeyがほしい時などに使うやつ

参照元 Add(), Erase().

---

このクラス詳解は次のファイルから抽出されました:

• SparseSet.hpp