こんにちは。
最近、C++ でユニークID (UUID) について扱うことがあったので、扱い方について書いておこうと思います。
UUID
概要
UUID (Universally Unique Identifier) とは、ID用に使われる 128bit の数値のことです。
よく使われる int型 (32bit) では最大で 2^32 ≒ 4.3 × 10^9 種類の数値しか表せませんが、UUID の場合は 2^128 ≒ 3.4 × 10^38 種類もの数値を表すことができます。
そのため、UUIDでは（世界的な規模で）IDをランダムに生成したとしても現実的には衝突することはないとして使われています。
生成方法が何であれ、将来的なことを考えるとIDは 128bit 以上で持っておくのが妥当だと考えられます。（不足した場合の対処が大変なため）
管理方法
ID を UUID で管理する場合、0から順に生成されるとは限らないため、vector 等のデータ構造で管理することはできません。
そのため、キー (= ID) と値のペアとして管理することになります。
アクセス速度を考慮すると、ハッシュマップを使うのが良いと考えられます。
ハッシュマップとは、キーからハッシュ値の算出方法をあらかじめ決めておき、ハッシュ値に該当するアドレスに値を保存するデータ構造です。
従って、要素へのアクセス、挿入、削除 の計算量はいずれも O(1) となり、非常に高速です。
ただし、順序が存在しないデータ構造なので、ID順に並べる必要がある場合は 二分木等のデータ構造を使う必要があります。
（二分木のアクセス、挿入、削除 の計算量は O(log N)）
以降では、実際に C++ で UUID を扱う方法について見ていきます。
C言語標準データ型 uuid_t
概要
C++ 標準で用意されているものが uuid_t というデータ型です。（C言語にもあります）
具体的には、以下のように定義されています。
typedef unsigned char uuid_t[16];
つまり、16byte (= 128bit) の生配列です。
詳しく知りたい方は /usr/include/uuid/uuid.h で確認できます。（Linux系の場合）
使い方
まず uuid_t の基本的な使い方を記載します。
#include <uuid/uuid.h>
int main()
{
// UUID をランダム生成
uuid_t u0;
uuid_generate(u0);
// UUID を文字列に変換
char c0[UUID_STR_LEN];
uuid_unparse(u0, c0);
// 文字列を UUID に変換
uuid_t u1;
uuid_parse(c0, u1);
// UUID を比較 ... 等しい: 0, 左が小さい: 負, 左が大きい: 正
int i0 = uuid_compare(u0, u1);
// UUID をコピー
uuid_t u2;
uuid_copy(u2, u0);
// NULL値を生成
uuid_clear(u0);
// NULL値と比較 ... NULL: 1, それ以外: 0
int i1 = uuid_is_null(u0);
}
次に、ハッシュマップでのデータの管理方法を記載します。
#include <uuid/uuid.h>
#include <cstring>
#include <unordered_map>
class Uuid
{
public:
uuid_t uuid;
Uuid(const uuid_t src)
{
uuid_copy(uuid, src);
}
}
class HashUuid
{
public:
size_t operator () (const Uuid &src) const
{
size_t dst = 0;
std::memcpy(&dst, src.uuid, sizeof(size_t));
return dst;
}
}
bool operator == (const Uuid &lhs, const Uuid &rhs)
{
return uuid_compare(lhs.uuid, rhs.uuid) == 0;
}
int main()
{
uuid_t u0;
uuid_generate(u0);
std::unordered_map<uuid, int, hashuuid> m0;
m0[u0] = 123;
}
上記の通り、ハッシュマップを使うためには、あらかじめハッシュ値を計算するクラスと、演算子「==」を定義しておく必要があります。
問題点
uuid_t が class 型ではなく生配列であるところが圧倒的な問題点です。
生配列ということは、uuid_t は実際には配列の先頭のポインタしか持っていません。
そのため、C++ というより C言語 に近いコードになってしまいます。
具体的には、以下のような問題が考えられます。
戻り値として返せない
以下のコードは実行時にエラーを起こします。
uuid_t func()
{
uuid_t tmp;
uuid_generate(tmp);
return tmp;
}
int main()
{
uuid_t u0 = func();
}
理由は、func が返すのは単にポインタであり、関数内の tmp はスコープを抜けた瞬間に消えるため、ポインタの指す先の値（= tmp）が存在しないためです。
このように、生配列では便利な記述が使えません。
STLのコンテナと相性が悪い
本来、ハッシュマップは以下のようにしたいところでした。
std::unordered_map<uuid_t, int, HashUuidT> m0;
しかし、uuid_t がポインタを表すため、ハッシュマップの最初の要素にはポインタが格納されてしまいます。
（本当は 16byte の配列を入れたい）
これを回避するために、先程の使用例ではわざわざ Uuid というクラスを作っていました。
以上のように、生配列は扱いがかなり面倒なので、使うことはお勧めしません。
Boost Uuid
概要
C++ の代表的なライブラリともいえる Boost が提供している Uuid を利用する方法があります。
uuid_t とは異なり、boost::uuids::uuid は class なので、C++ 風に扱うことができます。
class 中にはいくつかメンバ関数が用意されており、例えば std::size_t hash_value(boost::uuids::uuid const& u) はハッシュマップ用のハッシュ値を返す関数になっています。
詳しくは、公式ドキュメント をご確認ください。
強いこだわりがない限り、uuid_t よりもこちらを使うことを強くおすすめします。
使い方
boost::uuids::uuid の基本的な使い方を記載します。
#include <boost/uuid/uuid.hpp>
#include <boost/uuid/uuid_generators.hpp>
#include <boost/uuid/uuid_io.hpp>
#include <boost/lexical_cast.hpp>
#include <boost/unordered_map.hpp>
int main()
{
// UUID をランダム生成
boost::uuids::uuid u0 = boost::uuids::random_generator{}();
// UUID を文字列に変換
std::string s0 = boost::lexical_cast<std::string>(u0);
// 文字列を UUID に変換
boost::uuids::uuid u1 = boost::lexical_cast<boost::uuids::uuid>(s0);
// UUID を比較 ... 等しい: true, 異なる: false
bool b0 = u0 == u1
// UUID をコピー
boost::uuids::uuid u2 = u0;
// nil値を生成
u0 = boost::uuids::nil_generator{}();
// nil値と比較 ... nil: true, それ以外: false
bool b1 = u0.is_nil();
// ハッシュマップ作成
boost::unordered_map<boost::uuids::uuid, int> m0;
m0[u1] = 123;
}
まず、include 部分の説明をします。
- uuid.hpp … boost::uuids::uuid の型を使うときに必要（ヘッダでの定義など）
- uuid_io.hpp … uuid ⇔ string の変換に必要
uuid_io.hpp をインクルードせずに lexical_cast.hpp だけインクルードすると、以下のようなエラーが出るため注意してください。
/usr/include/boost/lexical_cast/detail/converter_lexical.hpp: In instantiation of ‘struct boost::detail::deduce_source_char_impl<boost::detail::deduce_character_type_later<boost::uuids::uuid> >’:
/usr/include/boost/lexical_cast/detail/converter_lexical.hpp:279:89: required from ‘struct boost::detail::deduce_source_char<boost::uuids::uuid>’
/usr/include/boost/lexical_cast/detail/converter_lexical.hpp:406:85: required from ‘struct boost::detail::lexical_cast_stream_traits<boost::uuids::uuid, std::__cxx11::basic_string<char> >’
/usr/include/boost/lexical_cast/detail/converter_lexical.hpp:468:15: required from ‘struct boost::detail::lexical_converter_impl<std::__cxx11::basic_string<char>, boost::uuids::uuid>’
/usr/include/boost/lexical_cast/try_lexical_convert.hpp:196:44: required from ‘bool boost::conversion::detail::try_lexical_convert(const Source&, Target&) [with Target = std::__cxx11::basic_string<char>; Source = boost::uuids::uuid]’
/usr/include/boost/lexical_cast.hpp:41:60: required from ‘Target boost::lexical_cast(const Source&) [with Target = std::__cxx11::basic_string<char>; Source = boost::uuids::uuid]’
../example.cpp:1:1: required from here
/usr/include/boost/lexical_cast/detail/converter_lexical.hpp:210:13: error: static assertion failed: Source type is neither std::ostream`able nor std::wostream`able
BOOST_STATIC_ASSERT_MSG((result_t::value || boost::has_left_shift< std::basic_ostream< type >, T >::value),
^
/usr/include/boost/lexical_cast/detail/converter_lexical.hpp: In instantiation of ‘struct boost::detail::deduce_target_char_impl<boost::detail::deduce_character_type_later<boost::uuids::uuid> >’:
/usr/include/boost/lexical_cast/detail/converter_lexical.hpp:270:89: required from ‘struct boost::detail::deduce_target_char<boost::uuids::uuid>’
/usr/include/boost/lexical_cast/detail/converter_lexical.hpp:407:92: required from ‘struct boost::detail::lexical_cast_stream_traits<std::__cxx11::basic_string<char>, boost::uuids::uuid>’
/usr/include/boost/lexical_cast/detail/converter_lexical.hpp:468:15: required from ‘struct boost::detail::lexical_converter_impl<boost::uuids::uuid, std::__cxx11::basic_string<char> >’
/usr/include/boost/lexical_cast/try_lexical_convert.hpp:196:44: required from ‘bool boost::conversion::detail::try_lexical_convert(const Source&, Target&) [with Target = boost::uuids::uuid; Source = std::__cxx11::basic_string<char>]’
/usr/include/boost/lexical_cast.hpp:41:60: required from ‘Target boost::lexical_cast(const Source&) [with Target = boost::uuids::uuid; Source = std::__cxx11::basic_string<char>]’
../example.cpp:1:1: required from here
/usr/include/boost/lexical_cast/detail/converter_lexical.hpp:243:13: error: static assertion failed: Target type is neither std::istream`able nor std::wistream`able
BOOST_STATIC_ASSERT_MSG((result_t::value || boost::has_right_shift<std::basic_istream<wchar_t>, T >::value),
また以前に説明した通り、ハッシュ値を返す関数 hash_value が class 内に用意されているため、boost::unordered_map を使えばわざわざハッシュ関数を自分で設定する必要はありません。
最後に
ユニークID (UUID) を C++ で扱う2つの方法を紹介しました。
質問や要望等があれば、コメント欄にてお知らせください。
コメント