非順序連想コンテナ

STLコンテナ型その3

非順序連想コンテナはSTLコンテナの一種です。
以下のコンテナクラスが連想コンテナに分類されます。

非順序連想コンテナは、名前の通り順序を持たない連想コンテナクラスです。
setやmapなどの連想コンテナは、要素の順序は自動的に決定されますが、非順序連想コンテナは要素の順序に意味を持ちません。
キーはハッシュテーブルという方法で管理されます。

ランダムアクセスはできません。
要素の挿入は高速です。
要素の検索は高速です。

非順序連想コンテナは通常の連想コンテナと使い方は基本的に同じです。
ただし要素の順序付けがないので、範囲を指定して○○といった操作はできません。

ハッシュテーブルの動作イメージ

配列の添え字には0以上の整数値しか使用することができません。
これは先頭アドレスからの相対位置で要素を特定するためです。
(先頭アドレス + (インデックス × 要素サイズ))

ハッシュテーブルは、最初にある程度のサイズの空の配列を確保しておきます。
あるキーを与えたとき、これをハッシュ関数という関数に通してハッシュ値を生成します。
ハッシュ値は0以上の整数値で、ハッシュ関数は同じキーを与えた場合は常に同じ値を返します。
この値をハッシュテーブルが確保する配列の要素数で割り、余りを求めます。
この余りを配列のインデックス(添え字)として格納位置を決定します。

//ハッシュテーブルの動作イメージ
//このコードは動作しません

const int arraySize = 8;

std::pair<std::string, int> pair1 = { "abc", 123 };
std::pair<std::string, int> pair2 = { "xyz", 789 };

int arr[arraySize];

//このstring_to_hash関数は、std::string型を
//0以上の整数値に変換すると仮定する
int hash1 = string_to_hash(pair1.first) % arraySize;
int hash2 = string_to_hash(pair2.first) % arraySize;

arr[hash1] = pair1.second;
arr[hash2] = pair2.second;

std::cout << arr[hash1] << std::endl; //123
std::cout << arr[hash2] << std::endl; //789

//ハッシュテーブルは上記のような操作を以下のコードで行える

std::unordered_map<std::string, int> umap;
umap["abc"] = 123;
umap["xyz"] = 789;

std::cout << umap["abc"] << std::endl; //123
std::cout << umap["xyz"] << std::endl; //789

この方法はハッシュ関数の計算時間だけでアクセス先を決定できるので、高速な処理が可能です。

しかしハッシュ関数は異なるキーから同じハッシュ値を生成することがあります。
(これ自体は問題ではなく、そういう仕様です)
また、ハッシュ値が異なる場合でも配列の要素数で割った余りをインデックスにするため、同じインデックスになることもあります。
これをハッシュの衝突と言います。

これを解決する方法として、配列の要素(ハッシュテーブルではスロットという)には値を直接保存するのではなく、値を保存するためのリスト(forward_listなど)を格納します。
つまりスロット内のリストへのアクセスとリスト内の要素へのアクセスの二段階で値を管理するわけです。
一つのスロットで複数の値を管理するので、スロットのことをバケット(バケツのこと)とも言います。

ハッシュテーブルは、要素数が配列サイズ(バケット数)の上限に近づくほど衝突が起こりやすくなり、速度が低下します。
かといって、配列のサイズを大きくしすぎるとメモリが無駄になります。
このバランスをうまく調整できれば、非順序付き連想コンテナはほとんどの場合で連想コンテナよりも高速に動作します。

一見ややこしそうですが、これらの処理はコンテナクラスが自動的に行ってくれます。
ただしバケット数の調整だけはプログラマが行ったほうが高速に動作します。
調整しなくても要素数が足りなくなったら自動的に拡張されますが、速度が大幅に低下する可能性があります。

自作クラスをキーにする

非順序連想コンテナのキーに自作クラスのインスタンスを使用する場合は、等価演算子のオーバーロードをして(==演算子)、さらにハッシュ値を算出する方法を用意する必要があります。

class TestClass
{
public:
    int x;
    int y;
    int z;

    TestClass(int x = 0, int y = 0, int z = 0)
        :x(x), y(y), z(z) {}

    bool operator==(const TestClass& r) const {
        return
            x == r.x &&
            y == r.y &&
            z == r.z;
    }

    //ついでに!=演算子もオーバーロード
    bool operator!=(const TestClass& r) const {
        return !(this->operator==(r));
    }
};

ハッシュ値を得るには、ハッシュ計算用の関数オブジェクトを定義する方法と、std::hashクラステンプレートを特殊化する方法があります。

関数オブジェクト

関数オブジェクトは、構造体(またはクラス)内で関数呼び出し演算子(operator())をオーバーロードしたものです。
オーバーロードの処理は、目的のユーザー定義型を引数に取り、ハッシュの計算を行い、std::size_t型を返すようにします。

struct Hash {
    std::size_t operator()(const TestClass& key) const
    {
        //std::hashを利用してハッシュ値を生成
        //XORで結合
        std::hash<int> hashint;
        return hashint(key.x) ^ hashint(key.y) ^ hashint(key.z);
    }
};

ハッシュ関数は、同じ値を与えた場合は必ず同じハッシュ値を生成しなければなりません。
これを満たすならばハッシュ値の計算方法は自由で、異なる値から同じハッシュ値が生成されることは問題ありません。
ただし、同じハッシュ値が生成されやすいような処理はパフォーマンスに悪影響となります。
(パフォーマンスを気にしないなら、極端なことを言えば引数の値に関係なくすべて0を返すようにしても動作はします)

今回はstd::hash<int>を使用してそれぞれのメンバのハッシュ値を計算し、XOR(^演算子)で結合しています。
std::hash<int>はint型からハッシュ値を計算する関数オブジェクトです。
C++の基本型やstd::string型などのC++標準の型は、std::hashのテンプレート型引数にそのまま指定できるようにあらかじめ用意(特殊化)されています。
最終的にひとつの値が欲しいのでこれらを結合するのですが、XORで結合すると同じ値が生成されにくくなるそうです。

上記の方法で作成した関数オブジェクトを、連想コンテナの宣言時のテンプレート実引数に追加します。

int main()
{
	std::unordered_set<TestClass, Hash> uset{
		TestClass(1),
		TestClass(2),
		TestClass(42)
	};

	std::unordered_map<TestClass, int, Hash> umap{
		{TestClass(1), 1},
		{TestClass(2), 2},
		{TestClass(42), 3}
	};
}

unordered_set(unordered_multiset)ならテンプレート実引数の第二引数に、unordered_map(unordered_multimap)なら第三引数に指定します。
こうすることでハッシュ値の生成にはこの関数オブジェクトが使用されるようになり、キーに自作クラスを指定できるようになります。

std::hashの特殊化

すでに説明した通り、std::hashは基本型をそのままテンプレート実引数に指定することができます。
これと同じことを自作クラスで行うにはテンプレートの明示的特殊化を用います。

namespace std {
	//std::hashクラステンプレートをTestClassで明示的特殊化
    template <>
    struct hash<TestClass>
    {
        std::size_t operator ()(const TestClass& key) const
        {
            std::hash<int> hashint;
            return hashint(key.x) ^ hashint(key.y) ^ hashint(key.z);
        }
    };
}

std::hashと同じstd名前空間でhashクラステンプレートの特殊化を行います。
(std::hashはstructで定義されているのでそれに合わせています)
処理の中身は先ほどの関数オブジェクトの時と同じです。

これでハッシュテーブルのキーにユーザー定義クラスを指定することができます。
ハッシュ値の生成には特殊化したクラスが使用されます。

int main()
{
    //std::hashのテンプレート実引数に
    //TestClassが指定可能になる
    std::hash<TestClass> hash_TestClass;

    std::unordered_set<TestClass> uset{
        TestClass(1),
        TestClass(2),
        TestClass(42)
    };

    std::unordered_map<TestClass, int> umap{
        {TestClass(1), 1},
        {TestClass(2), 2},
        {TestClass(42), 3}
    };
}

共通のメンバ関数

非順序連想コンテナで共通するメンバ関数の対応一覧です。
一覧にない、コンテナクラス固有のメンバ関数は後述します。

arrayクラスやvectorクラス、および連想コンテナと共通の関数は当該ページを参照してください。
イテレータについてはイテレータの項を参照してください。
以下は、上記のページでは説明していない関数について説明します。

std::vector<int> vec;

//全て同じデータ型
std::vector<int>::iterator it1;
auto it2 = vec.begin();
decltype(vec)::iterator it3;

bucket_count関数

bucket_count関数は、バケット数を取得します。

std::unordered_set< int> uset;

std::cout << uset.bucket_count() << std::endl;

uset.insert({ 1, 2, 3, 4, 5, 6, 7, 8, 9 });

std::cout << uset.bucket_count() << std::endl;

8
64

max_bucket_count関数

max_bucket_count関数は、システムが保存可能な最大のバケット数を取得します。

std::unordered_set< int> uset;

std::cout << uset.max_bucket_count() << std::endl;
//出力は環境により異なる

bucket_size関数

bucket_size関数は、指定のバケットのサイズ(バケットに格納されている要素数)を取得します。
バケットの指定は先頭からの番号で行います。

#include <iostream>
#include <string>
#include <unordered_set>

int main()
{
    std::unordered_set<std::string> uset = { "A", "B", "H", "I", "J"};

    //バケット数
    decltype(uset)::size_type count = uset.bucket_count();
    std::cout << "bucket_count=" << count << std::endl;

    //全てのバケットを表示
    for (decltype(uset)::size_type n = 0; n < count; n++) {
        //n番目のバケットサイズを取得
        decltype(uset)::size_type size = uset.bucket_size(n);
        std::cout << "bucket=" << n << ", bucket_size=" << size;

        //n番目のバケットの中身を表示
        std::cout << ", keys={";
        auto it = uset.begin(n);
        while (it != uset.end(n)) {
            std::cout << *it++ << ", ";
        }
        std::cout << "}" << std::endl;
    }
	std::cin.get();
}

bucket_count=8
bucket=0, bucket_size=0, keys={}
bucket=1, bucket_size=0, keys={}
bucket=2, bucket_size=0, keys={}
bucket=3, bucket_size=0, keys={}
bucket=4, bucket_size=2, keys={I, A, }
bucket=5, bucket_size=2, keys={J, B, }
bucket=6, bucket_size=0, keys={}
bucket=7, bucket_size=1, keys={H, }

bucket関数

bucket関数は、指定のキーの格納先となるバケットのインデックス(番号)を取得します。

#include <iostream>
#include <string>
#include <unordered_set>

int main()
{
    std::unordered_set<std::string> uset = { "A", "B", "C" };

    //チェックする文字列
    const char* charactors[]
		= { "A", "B", "C", "D", "E", "F", "G", "H", "I", "J" };

    for (const auto &c : charactors) {
        std::cout << "key=" << c;
		//バケット番号
        std::cout << ", bucket=" << uset.bucket(c);
        std::cout << std::endl;
    }

	std::cin.get();
}

key=A, bucket=4
key=B, bucket=5
key=C, bucket=2
key=D, bucket=3
key=E, bucket=0
key=F, bucket=1
key=G, bucket=6
key=H, bucket=7
key=I, bucket=4
key=J, bucket=5

指定のキーが格納されていない場合でも、格納される先のバケット番号を返します。
ただし実際にキーを格納することでハッシュテーブルが容量不足となり拡張が行われた場合は番号が変わる可能性があります。

begin(index)、end(index)関数

begin関数、end関数はコンテナのイテレータを返しますが、バケットのインデックスを指定するとバケット内の要素アクセスのためのイテレータを返します。

#include <iostream>
#include <string>
#include <unordered_set>

int main()
{
    std::unordered_set<std::string> uset = { "A", "B", "H", "I", "J" };

    //バケット数
    decltype(uset)::size_type count = uset.bucket_count();
    std::cout << "bucket_count=" << count << std::endl;

    //全てのバケットを表示
    for (decltype(uset)::size_type n = 0; n < count; n++) {
        //n番目のバケットサイズを取得
        decltype(uset)::size_type size = uset.bucket_size(n);
        std::cout << "bucket=" << n << ", bucket_size=" << size;

        std::cout << ", keys={";
        //バケットの要素へのイテレータ
        auto it = uset.begin(n);
        while (it != uset.end(n)) {
            std::cout << *it++ << ", ";
        }
        std::cout << "}" << std::endl;
    }
    std::cin.get();
}

bucket_count=8
bucket=0, bucket_size=0, keys={}
bucket=1, bucket_size=0, keys={}
bucket=2, bucket_size=0, keys={}
bucket=3, bucket_size=0, keys={}
bucket=4, bucket_size=2, keys={I, A, }
bucket=5, bucket_size=2, keys={J, B, }
bucket=6, bucket_size=0, keys={}
bucket=7, bucket_size=1, keys={H, }

戻り値はstd::コンテナクラス<データ型>::local_iterator型で、これはそのバケット内でのみ有効なイテレータです。

cbegin(index)、cend(index)関数

cbegin関数、cend関数はバケット内の要素へのイテレータのconst版です。
戻り値はstd::コンテナクラス<データ型>::const_local_iterator型です。

load_factor関数

load_factor関数は、ハッシュテーブルの負荷率を取得します。

#include <iostream>
#include <string>
#include <unordered_set>

int main()
{
    std::unordered_set<std::string> uset = { "A", "B" };

    std::cout << "size=" << uset.size() << std::endl;
    std::cout << "bucket_count=" << uset.bucket_count() << std::endl;
    std::cout << "load_factor=" << uset.load_factor() << std::endl;
    std::cout << std::endl;

    uset.insert({ "H", "I", "J" });

    std::cout << "size=" << uset.size() << std::endl;
    std::cout << "bucket_count=" << uset.bucket_count() << std::endl;
    std::cout << "load_factor=" << uset.load_factor() << std::endl;

    std::cin.get();
}

size=2
bucket_count=8
load_factor=0.25

size=5
bucket_count=8
load_factor=0.625

負荷率はバケットあたりの要素数の平均で、つまりsize() / bucket_count()の計算結果と等価です。
数値が大きいほどハッシュテーブルの空きが少なく、速度が低下しやすくなります。
ハッシュテーブルは一般に負荷率が0.8あたりから急激にパフォーマンスが悪化するとされます。

max_load_factor関数

max_load_factor関数は、ハッシュテーブルの負荷率の最大値を取得または設定します。

#include <iostream>
#include <string>
#include <unordered_set>

int main()
{
    std::unordered_set<std::string> uset = { "A", "B" };

    //負荷率の最大値を取得
    std::cout << "max_load_factor=" << uset.max_load_factor() << std::endl;

    //負荷率の最大値を設定
    uset.max_load_factor(0.8f);
    std::cout << "max_load_factor=" << uset.max_load_factor() << std::endl;

    std::cin.get();
}

max_load_factor=1
max_load_factor=0.8

引数無しで関数を実行すると負荷率の最大値を取得します。
戻り値はfloat型です。
引数に数値(float型)を指定すると負荷率の最大値を設定します。
この時の戻り値はありません。
数値は0以上である必要があります。

この負荷率を超えるとハッシュテーブルが拡張されます。
このとき、すでに格納されているキーのハッシュは再計算され、別のバケットに移動する可能性があります。
この処理をリハッシュ(再ハッシュ)といいます。

負荷率の最大値を下げるとハッシュの衝突の発生率が下がるため速度の低下を防ぐことができますが、リハッシュが発生しやすくなります。

なお、負荷率の最大値の設定は必ずその値に設定できるとは限らないようです。
現在の負荷率よりも小さな値を指定した場合の動作は実装依存です。
(設定の変更が無視されるか、リハッシュが発生する)

rehash関数

rehash関数は、最小のバケット数を指定してバケット数を調整(リハッシュ)します。

#include <iostream>
#include <unordered_set>

template<typename T>
void showBucketSize(const std::unordered_set<T>& uset)
{
	std::cout << "size=" << uset.size() << std::endl;
	std::cout << "bucket_count=" << uset.bucket_count() << std::endl;
	std::cout << std::endl;
}

int main()
{
	std::unordered_set<int> uset;
	showBucketSize(uset);

	uset.rehash(10);
	showBucketSize(uset);

    std::cin.get();
}

size=0
bucket_count=8

size=0
bucket_count=16

この関数の戻り値はありません。

指定の値にバケット数が設定されるのではなく、少なくとも指定の値以上のバケット数を持つように調整されます。
具体的な動作は実装により異なります。

現在のバケット数よりも少ない値を指定した場合は最大負荷率を超えない数に調整されます。
(size() / max_load_factor())
上記の規定があるだけで、バケット数の縮小ができるという保証はありません。

reserve関数

reserve関数は、最小の要素数を指定してバケット数を調整します。

std::unordered_set<int> uset{ 1, 2, 3 };

std::cout << uset.bucket_count() << std::endl;

//少なくとも10の要素を格納できるようにバケット数を調整
uset.reserve(10);

std::cout << uset.bucket_count() << std::endl;

8
16

この関数の戻り値はありません。

rehash関数は最小のバケット数を指定して調整しますが、こちらは最小の要素数の指定によるバケット数の調整です。
少なくともリハッシュが発生せずに指定の要素数を格納できるようにバケット数が調整されます。
つまり指定の要素数が格納されても負荷率がmax_load_factorを上回ることがないように拡張されます。
つまりrehash(std::ceil(n / max_load_factor()))と同等の処理となります。
(nは引数、std::ceilは小数点の切り上げ)

上記の条件を満たす限り、実際に拡張されるバケット数は実装により異なります。

バケット数を縮小する

rehash関数やreserve関数は、「すでに確保しているよりも小さな値を指定してバケット数を縮小する」という動作ができる保証はありません。
GCCでは縮小が可能なようですが、Visual Studioではできないようです。

バケットサイズを縮小するにはvectorクラスでも紹介したswap技法を使用する方法があります。
ただしコンストラクタにそのままオブジェクトを指定すると現在のハッシュテーブルの構造もコピーされるようなので、イテレーターの範囲を指定します。

#include <iostream>
#include <string>
#include <unordered_set>

//要素数とバケット数を表示する関数
template<typename T>
void showBucketCount(const std::unordered_set<T>& uset)
{
    std::cout << "size=" << uset.size() << std::endl;
    std::cout << "bucket_count=" << uset.bucket_count() << std::endl;
    std::cout << std::endl;
}

int main()
{
    std::unordered_set<int> uset{ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
    showBucketCount(uset);

    //適当に要素を削除
    uset.erase(1);
    uset.erase(2);
    uset.erase(3);
    uset.erase(4);

    //Visual Studioではこれらでメモリ解放されない
    uset.rehash(6);
    uset.reserve(6);
    std::cout << "rehash(6)" << std::endl;
    std::cout << "reserve(6)" << std::endl;
    showBucketCount(uset);

	//swap技法で新しいオブジェクトを生成
	//Visual Studioではこれでもメモリ解放されない
    std::unordered_set<int>(uset).swap(uset);
    std::cout << "std::unordered_set<int>(uset).swap(uset)" << std::endl;
    showBucketCount(uset);

	//イテレータの範囲からのswap技法で新しいオブジェクトを生成
    std::unordered_set<int>(uset.begin(), uset.end()).swap(uset);
    std::cout << "std::unordered_set<int>(uset.begin(), uset.end()).swap(uset);" << std::endl;
    showBucketCount(uset);

    std::cin.get();
}

size=10
bucket_count=64

rehash(6)
reserve(6)
size=6
bucket_count=64

std::unordered_set<int>(uset).swap(uset)
size=6
bucket_count=64

std::unordered_set<int>(uset.begin(), uset.end()).swap(uset)
size=6
bucket_count=8

hash_function関数

key_eq関数

hash_function関数は、コンテナに関連付けられた、ハッシュ関数オブジェクトを取得します。
key_eq関数は、コンテナに関連付けられた、キーの比較オブジェクトを取得します。

#include <iostream>
#include <unordered_set>
#include <string>

int main()
{
	std::unordered_set<int> uset{ 1, 2, 3 };

	//ハッシュ関数
	decltype(uset)::hasher hash =  uset.hash_function() ;

	std::cout << "hash(1)=" << hash(1) << std::endl;
	std::cout << "hash(2)=" << hash(2) << std::endl;
	std::cout << "hash(3)=" << hash(3) << std::endl;

	decltype(uset)::size_type v1 = hash(1) % uset.bucket_count();
	decltype(uset)::size_type v2 = hash(2) % uset.bucket_count();
	decltype(uset)::size_type v3 = hash(3) % uset.bucket_count();

	std::cout << "hash(1) % bucket_count=" << v1 << std::endl;
	std::cout << "hash(2) % bucket_count=" << v2 << std::endl;
	std::cout << "hash(3) % bucket_count=" << v3 << std::endl;

	std::cout << std::endl;

	//バケット数
	decltype(uset)::size_type count = uset.bucket_count();
	std::cout << "bucket_count=" << count << std::endl;

	//全てのバケットを表示
	for (decltype(uset)::size_type n = 0; n < count; n++) {
		//n番目のバケットサイズを取得
		decltype(uset)::size_type size = uset.bucket_size(n);
		std::cout << "bucket=" << n << ", bucket_size=" << size;

		//n番目のバケットの中身を表示
		std::cout << ", keys={";
		auto it = uset.begin(n);
		while (it != uset.end(n)) {
			std::cout << *it++ << ", ";
		}
		std::cout << "}" << std::endl;
	}

	std::cout << std::endl;

	//キー比較関数
	decltype(uset)::key_equal key_eq = uset.key_eq();
	std::cout << "key_eq(1, 2)=" << key_eq(1, 2) << std::endl;
	std::cout << "key_eq(1, 1)=" << key_eq(1, 1) << std::endl;

	std::cin.get();
}

hash(1)=4218009092
hash(2)=3958272823
hash(3)=2613195814
hash(1) % bucket_count=4
hash(2) % bucket_count=7
hash(3) % bucket_count=6

bucket_count=8
bucket=0, bucket_size=0, keys={}
bucket=1, bucket_size=0, keys={}
bucket=2, bucket_size=0, keys={}
bucket=3, bucket_size=0, keys={}
bucket=4, bucket_size=2, keys={1, }
bucket=5, bucket_size=2, keys={}
bucket=6, bucket_size=0, keys={3, }
bucket=7, bucket_size=1, keys={2, }

key_eq(1, 2)=0
key_eq(1, 1)=1

ハッシュ関数が返す値は実装依存です。
キー比較関数は、キーが一致する場合はtrue(1)、一致しなければfalse(0)を返します。