xor_listの実装

C++ Hamigaki

http://d.hatena.ne.jp/y-hamigaki/20100118
の解説です。
やたら長くなったので続きを読む記法。

std::listのデータ構造

std::listの構造を知っておくとxor_listを理解しやすいので、まずstd::listの構造について説明します。
必ずしもこうある必要はありませんが、大抵こんな感じだと思います。
まず、要素を格納するノードです。

// ノードの基底クラス
struct list_node_base
{
    list_node_base* prev_; // 前のノードのポインタ
    list_node_base* next_; // 次のノードのポインタ
};

// 実際のノード
template<class T>
struct list_node : list_node_base
{
    T value;
};

双方向連結リストなので、前後のノードへの二つのポインタと一つの値を持ちます。
反復子は対称要素を含むノードのポインタを持っているため、前方/後方へ要素を辿ることができます。
リンク部分をlist_node_baseに分けているのは、

  • インライン展開できなかった場合のコードの膨張を防ぐことができる(リンク操作の大部分は要素の型に依存しない)
  • リストの両端で値を持たないノードがあるとコードを単純化できる場合がある

からです。
値にアクセスする場合を除いて、ノードはlist_node_baseのインスタンスとして扱います。
リンクポインタの型もlist_node_base*です。
値にアクセする場合はlist_node<T>へダウンキャストします。

これを使うとリストは次のように表現できます。

// リストの型非依存部分の実装
class list_impl
{
public:
    list_impl()
    {
        sentry_.prev_ = &sentry_;
        sentry_.next_ = &sentry_;
    }

private:
    list_node_base sentry_; // ダミーノード
};

ここでsentry_.next_が先頭ノードを、sentry_.prev_が末尾ノードを示します。
リストが空の状態では共にsentry_を指しており、環状リストになっているのが分かると思います。
環状リストは終端ノードが存在しないため、挿入/削除操作で終端ノードにおける分岐処理が不要です。
また、sentry_は末尾の一つ先のノード、つまりend()が指すノードとなります。
*end()は不正なので、値を持たないlist_node_baseで十分です。

データ構造

さて、今度はxor_listのノードです。

// ノードの基底クラス
struct xl_node_base
{
    uintptr_t link_; // 前後のノードのポインタ値の排他的論理和

    // リンク先の設定
    void link(xl_node_base* prev, xl_node_base* next)
    {
        link_ =
            reinterpret_cast<uintptr_t>(prev) ^
            reinterpret_cast<uintptr_t>(next) ;
    }
};

// 実際のノード
template<class T>
struct xl_node : xl_node_base
{
    T value;
};

std::listのようにダミーノードを使って実装してみます。

// ダミーノードを使った実装
class xl_impl_dummy
{
public:
    xl_impl_dummy()
    {
        sentry_.link(&sentry_, &sentry_);
    }

private:
    xl_node_base sentry_;
};

空の状態は問題なさそうです。
ノードp0を追加してみます。

sentry_.link(p0, &n0); // sentry_.link_ = 0;
p0->link(&sentry_, &sentry_); // p0->link_ = 0;

さて、手元にはsentry_のアドレスとsentry_.link_(=0)だけが残りました。
ここからp0を取り出すのは不可能です。
XOR連結リストを辿るにはもう一つポインタが必要なのです。
実際、反復子は対称要素のノードと一つ前のノードの二つのポインタを持っています。
では、ダミーノードを二つ使うのはどうでしょう。

// ダミーノード二つを使った実装
class xl_impl_dummy2
{
public:
    xl_impl_dummy2()
    {
        head_.link(&tail_, &tail_);
        tail_.link(&head_, &head_);
    }

private:
    xl_node_base head_; // 先頭の一つ前のノード
    xl_node_base tail_; // 末尾の一つ先のノード
};

同じくp0を追加してみます。

head_.link(&tail_, p0);
p0->link(&head_, &tail_);
tail_.link(p0, &head_);

p0はhead_.linkの値とtail_のアドレスから算出できます。
データ構造上はこれで問題ありません。
ですが、STL風コンテナとしてはある重要な性質を欠いています。
理由は後の節に書きますが、結果としてxor_listは環状リストではなく、先頭/末尾要素のポインタを保持する形で実装しています。

// ポインタ二つを使った実装
class xl_impl_ptr2
{
public:
    xl_impl_ptr2()
        : head_ptr_(0), tail_ptr_(0)
    {
    }

private:
    xl_node_base* head_ptr_; // 先頭ノードへのポインタ
    xl_node_base* tail_ptr_; // 末尾ノードへのポインタ
};

先頭の一つ前、末尾の一つ先はヌルポインタ扱いとします。

head_ptr_ = p0;
p0->link(0,0);
tail_ptr_ = p0;

p0〜p2をを追加した場合はこうなります。

head_ptr_ = p0;
p0->link(0,p1);
p1->link(p0,p2);
p2->link(p1,0);
tail_ptr_ = p2;

swap()の要件

swap()には次の要件があります。

23.1/10

  • no swap() function invalidates any references, pointers, or iterators referring to the elements of the

containers being swapped.

ISO/IEC 14882/2003

ダミーノードを使った実装では、先頭要素を指す反復子がダミーノードのポインタを保持しているため、
swap()後に無効になってしまいます。
ダミーノードを使わなかったのはこれを避けるためです。
指す要素のないend()は無効になっても構わないので、末尾要素の後ろにダミーノードを置くことは可能ですが、
前と後ろが対称にならないのが嫌でやめました。(でもダミーをおいた方が多分速い)

sort()

xor_listもstd::listと同じ方法でソートできます。

23.2.2.4
31
Notes: Stable: the relative order of the equivalent elements is preserved. If an exception is thrown the
order of the elements in the list is indeterminate.
32
Complexity: Approximately NlogN comparisons, where N == size().

ISO/IEC 14882/2003

要件はO(NlogN)で安定ソートなので、ほぼマージソート一択かなと。
リンクリストは要素のコピーをしなくても別のリストに分割したり併合したりといったことが簡単にできるので、
マージソートに向いたデータ構造です。
通常、マージソートはシーケンスを二等分して、それぞれをマージソート(再帰)してからマージするわけですが、
マージを処理順に追っていくと、

(((0 + 1) + (0 + 1)) + ((0 + 1) + (0 + 1))) + (((0 + 1) + (0 + 1)) + ((0 + 1) + (0 + 1)))
					↓
((   1    + (0 + 1)) + ((0 + 1) + (0 + 1))) + (((0 + 1) + (0 + 1)) + ((0 + 1) + (0 + 1)))
					↓
((   1    +    1   ) + ((0 + 1) + (0 + 1))) + (((0 + 1) + (0 + 1)) + ((0 + 1) + (0 + 1)))
					↓
(         2          + ((0 + 1) + (0 + 1))) + (((0 + 1) + (0 + 1)) + ((0 + 1) + (0 + 1)))
					↓
(         2          + (   1    + (0 + 1))) + (((0 + 1) + (0 + 1)) + ((0 + 1) + (0 + 1)))
					↓
(         2          + (   1    +    1   )) + (((0 + 1) + (0 + 1)) + ((0 + 1) + (0 + 1)))
					↓
(         2          +          2         ) + (((0 + 1) + (0 + 1)) + ((0 + 1) + (0 + 1)))
					↓
                     4                      + (((0 + 1) + (0 + 1)) + ((0 + 1) + (0 + 1)))

のように要素数が倍々になるようにマージされていくのが分かります。(数字は要素の数、+はマージの意味)
逆に、この順番にマージしていけば再帰などしなくてもマージソートはできるわけです。
アルゴリズムはこうです。

1. リストから要素を一つ取り出す。
↓
2. 取り出した要素でサイズ=1のリストを作る。
↓
3. サイズ=1のリストのストックがなければ、1.に戻る。
↓
4. サイズ=1のリストのストックとマージしてサイズ=2のリストを作る。
↓
5. サイズ=2のリストのストックがなければ、1.に戻る。
↓
6. サイズ=2のリストのストックとマージしてサイズ=4のリストを作る。
↓
7. サイズ=4のリストのストックがなければ、1.に戻る。
↓
(以下略)

要素数を倍々にするため、要素数=1,2,4,8,...,2Nのリストをストックしておく必要があります。(Nはsize_typeのビット数)
最後にストックしておいたリストをマージすればソートの完成です。
コードも比較で例外が発生した場合の対処が入っているだけで、特に大したことはしていません。
等価な要素の順番を変更しないようにしないといけないので、そこだけ注意です。(と言いつつちゃんとテストしてません。)

アロケータの等価性

20.1.5
a1 == a2
returns true iff storage allocated
from each can be deallocated via the other.

ISO/IEC 14882/2003

とあるように、アロケータが「等価である」というのは、一方で確保したメモリをもう一方でも解放できるということです。
このため、理論上はアロケータの等価なリンクリスト間ではノードの受け渡しが可能です。
しかし、std::listではsplice()で移動したノードの反復子/参照が無効になる等、やや制限のある仕様となっています。
実のところ、アロケータの等価でないコンテナの操作に関しては規格では処理系定義となっていて、
等価でないアロケータが中途半端に考慮されている感があります。
最新ドラフトでは、「アロケータが等価でないstd::listのsplice()は未定義」、「splice()しても参照が無効とならない」旨が記述されています。
ただし、xor_listは現行規格に従って作ったので、等価でないアロケータをサポートしています。
http://hamigaki.sourceforge.jp/doc/html/hamigaki/xor_list.html
影響を受けるのは、swap()、splice()、merge()です。
アロケータが等価でない場合、swap()は要素のコピーを行わなければいけません。
従って、O(N)の処理時間がかかり、コピー失敗による例外発生もあり得ます。
この点はコンテナ利用者も注意が必要です。