読者です 読者をやめる 読者になる 読者になる

ボレロ村上 - ENiyGmaA Code

中3女子です。

Boost.PropertyTree の安定ソート(1)

#include <boost/property_tree/ptree.hpp>

boost::property_tree::ptree ptree;
ptree.sort();


 残念ながら、このコードはコンパイルできなかった(Boost 1.43 + VC9)。
 というのも basic_ptree::sort() は、要素を実際に保持する multi_index_container::sort() を呼び出しているが、これがいけない。
何故なら basic_ptree::value_type は pair であり、
pair 同士の比較では first 同士と second 同士の比較が呼ばれうるが、key_type はふつう文字列であるから比較できるが、
basic_ptree 同士の比較演算子は定義されていない。
 そのため、less::operator()() の呼出のところでコンパイルエラーになっている。


 Boost.PropertyTree のドキュメントには
> Sorts the direct children of this node according to key order.
(このノードの直接の子をキーの順序に応じて並べ替えます。)
とあるが、これは誤りであろう。


 一般に、コンテナ同士の大小比較は定義しがたい。
 であるから、単純に要素のキーを比較する関数オブジェクトを渡してやることを試みた。

#include <boost/lambda/lambda.hpp>
#include <boost/lambda/bind.hpp>
#include <boost/property_tree/ptree.hpp>

typedef boost::property_tree::ptree::value_type value_type;
boost::property_tree::ptree ptree;
ptree.sort(
    boost::lambda::bind(&value_type::first, boost::lambda::_1)
        < boost::lambda::bind(&value_type::first, boost::lambda::_2)
    );


 これはコンパイルも成功し、実行もできた。
確かにキーの昇順でソートされている。
 しかし気に入らないところがある。
安定ソートでないのだ。


 Boost.PropertyTree のドキュメントによれば
> Sorts the direct children of this node according to the predicate.
> The predicate is passed the whole pair of key and child.
(このノードの直接の子を述語に基づいて並べ替えます。
述語は、キーと子の全体のペアを渡されます。)
とあるので、等価なキーをもつ要素同士の順序が保証されないのは妥当である。


 しかしながら、Boost.PropertyTree の実装は Boost.MultiIndex に依っている。
boost/property_tree/detail/exception_implementation.hpp から、宣言を抜き出してみよう。

typedef multi_index_container<value_type,
    multi_index::indexed_by<
        multi_index::sequenced<>,
        multi_index::ordered_non_unique<multi_index::tag<by_name>,
            multi_index::member<value_type, const key_type,
                                &value_type::first>,
            key_compare
        >
    >
> base_container;


 さて、Boost.MultiIndex のドキュメントから Sequenced indices のページを見てみる。
> template void sort(Compare comp);
> Effects: Sorts the index according to comp.
> The sorting is stable, i.e. equivalent elements preserve their relative position.
(comp に応じてインデックスをソートする。
ソートは安定、すなわち同等の要素の相対的な位置が保持されます。)
どうやら multi_index_container の実装は安定ソートらしい。


 Boost.PropertyTree のソースを眺めるかぎり、base_container::sort() に処理を丸投げする以上のことはしていないように思える。
しかしながら、実際にテストしてみた結果では安定ソートでない。
同じキーを持つ要素のソート前の順序は保持されず、ばらばらになってしまった。


 これはどういうことか。
Boost.MultiIndex の実装のバグまたはドキュメントの誤りか、
Boost.PropertyTree が何か特別なことをしているのか、
あるいは自分の解釈の間違い、ないし見落としがあるのか。
 3番目である可能性は高いが、ともかく今回は ptree の安定ソートを書く必要に迫られている。
そのために、Boostの中では屈指の見づらさを誇る Boost.PropertyTree のドキュメントを漁ったりもしたのだ。


 std::stable_sort() に渡すことを一瞬考えたが、そもそもキーが const であるので代入ができるはずがない。
ただの気の迷いであった。


 そういうわけで安定ソートを自作することに決めたが、どうにもスマートな実装が思い浮かばない。
上述のとおり要素を直接書き換えられないので、普通のアルゴリズムとしては実装できない。
 方針としては、事前にソート前の要素の順序を記憶しておいて、同じキーの場合はそれに基づいて比較すれば可能なはず。
しかし要素の同一性をどう判別すればいいか、それが分からない。


 僕はこの議論の驚くべき(真に汚い)解法を思いついたが、長くなったので次回に回す。

   (続く)