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

　　　（続き）

　boost::property_tree::basic_ptree を安定ソートするにはどうすればよいか。
メンバ関数 basic_ptree::sort() や STL アルゴリズムなど、
ふつう考えられる方法ではおよそ難しいというのが、前回の話だった。

　ようは同じキーの要素同士の比較において、ソート前の要素の順序を参照できればよいのだが、問題は二つある。
１．要素の順序を表わすデータをどこに持っておくか。
２．ある要素の値から、どうやって（どこかに記憶しておいた）要素の順序を参照するか。
　さて、僕が今回考えたのは、
「要素の値自身が順序を表わす値を持っておけばいいんじゃね？」
ということだ。

　これが vector など最も抽象的なコンテナであれば、保持する要素の型に制限がつけられないため、
要素にどう余分なデータを持たせるか決められないが、今回は basic_ptree である。
　ライブラリの用途や ptree, wptree などの typedef 、また実装を見れば明らかなように、
key_type や data_type として想定されているのは、もっぱら文字列型だ。
　つまり、char や wchar_t など整数型を要素とするコンテナだ。
　コンテナであるから、伸張して何か値をもぐりこませることができるし、要素が整数型と決めれば、整数としてやりとりする事ができる。

　そこで方針としては、
１．basic_ptree::data() に現在のインデックスを書き込み。
２．basic_ptree::sort(Compare comp) に、key と data(に書き込んだインデックス値) をもとにした比較関数オブジェクトを渡してソート。
３．basic_ptree::data() から追加したぶんを除去する。。
これで、ソート前の順序付けが保持される（安定ソート）はずだ。

　言うまでもなく、「要素を並び替える」ための処理で「要素の値を弄る」というのは本質的に汚く、
また無用なバグの原因にもなりかねない。
　例えば例外安全を考えたときに、たとえ基本保証（メモリリークなどプログラムを正常に続行できない状態にならない）ができたとしても、
仮に３．でインデックス値を除去中に例外が投げられたとしたら、除去されなかったぶんの値が basic_ptree::data() に残り、
中で邪悪な行為が行われているとは知りもしない哀れなユーザは、かくして不可解なバグに悩まされる羽目となる。
　RAII や Boost.ScopeExit で解決できないかとも思ったが、余計なコストを生みそうな気がする。

　ともかく、以下にコードを示す。

必要なヘッダ

#include <cstddef>
#include <iterator>
#include <functional>
#include <boost/range.hpp>
#include <boost/next_prior.hpp>
#include <boost/foreach.hpp>
#include <sprig/split_join.hpp>

比較関数オブジェクト stable_sort_ptree_compare

namespace sprig {
    template<
        typename Ptree,
        typename KeyCompare = typename Ptree::key_compare
    >
    class stable_sort_ptree_compare
        : public std::binary_function<
            typename Ptree::value_type,
            typename Ptree::value_type,
            bool
        >
        , private KeyCompare
    {
    public:
        typedef Ptree ptree_type;
        typedef KeyCompare key_compare;
        typedef typename ptree_type::value_type value_type;
        typedef typename ptree_type::size_type size_type;
    public:
        explicit stable_sort_ptree_compare(
            key_compare key_comp = key_compare()
            )
            : key_compare(key_comp)
        {}
        bool operator()(
            value_type const& lhs,
            value_type const& rhs
            ) const
        {
            return key_compare::operator()(lhs.first, rhs.first)
                || !key_compare::operator()(rhs.first, lhs.first)
                && sprig::integer_join<size_type>(
                    boost::prior(
                        boost::end(lhs.second.data()),
                        static_cast<std::ptrdiff_t>(sizeof(size_type))
                        )
                    )
                < sprig::integer_join<size_type>(
                    boost::prior(
                        boost::end(rhs.second.data()),
                        static_cast<std::ptrdiff_t>(sizeof(size_type))
                        )
                    )
                ;
        }
    };
}   // namespace sprig

ソート関数 stable_sort_ptree

namespace sprig {
    //
    // stable_sort_ptree
    //
    template<typename Ptree>
    void stable_sort_ptree(Ptree& ptree) {
        typedef typename Ptree::size_type size_type;
        {
            size_type i = 0;
            BOOST_FOREACH(typename boost::range_reference<Ptree>::type e, ptree) {
                sprig::integer_split(i, std::back_inserter(e.second.data()));
                ++i;
            }
        }
        ptree.sort(stable_sort_ptree_compare<Ptree>());
        BOOST_FOREACH(typename boost::range_reference<Ptree>::type e, ptree) {
            typename Ptree::data_type& data = e.second.data();
            data.erase(
                boost::prior(
                    boost::end(data),
                    static_cast<std::ptrdiff_t>(sizeof(size_type))
                    ),
                boost::end(data)
                );
        }
    }
    //
    // stable_sort_ptree
    //
    template<typename Ptree, typename KeyCompare>
    void stable_sort_ptree(Ptree& ptree, KeyCompare key_comp) {
        typedef typename Ptree::size_type size_type;
        {
            size_type i = 0;
            BOOST_FOREACH(typename boost::range_reference<Ptree>::type e, ptree) {
                sprig::integer_split(i, std::back_inserter(e.second.data()));
                ++i;
            }
        }
        ptree.sort(stable_sort_ptree_compare<Ptree, KeyCompare>(key_comp));
        BOOST_FOREACH(typename boost::range_reference<Ptree>::type e, ptree) {
            typename Ptree::data_type& data = e.second.data();
            data.erase(
                boost::prior(
                    boost::end(data),
                    static_cast<std::ptrdiff_t>(sizeof(size_type))
                    ),
                boost::end(data)
                );
        }
    }
}   // namespace sprig

　なお sprig::integer_split は整数型を sizeof(IntType) 個に分割して OutputIterator に流し込む。
sprig::integer_join　は逆に、InputIterator から要素を整数型に結合して返す。

　ともかく、ひとまずこれで安定ソートを実装できた。
しかし見ての通り非常に汚いことをしているので、望ましいやり方でない。
　本来的には、 Boost.PropertyTree が安定ソートのための機能を提供してくれるのが一番良いのだが。

ボレロ村上 - ENiyGmaA Code

中３女子です。