16.3 ユーザー独自のコンテナの作成

既存の標準 C++ ライブラリコンテナに基づく構築のすべてのオプションは、一定量のオーバヘッドを生じます。パフォーマンス要求が重要な場合やコンテナ要求が特に明確な場合は、コンテナをスクラッチから実装する以外に方法はないでしょう。

スクラッチから構築する場合、遵守する必要がある 3 つの設計要求があります。

コンテナインタフェース要求
アロケータインタフェース要求
反復子要求

以上の各要求について、以降の節で説明します。

16.3.1 コンテナ要求の遵守

標準 C++ ライブラリは、コンテナの一般インタフェース要求と、特殊コンテナの特定要求を定義しています。コンテナを作成する場合、まず最初に行う作業は、コンテナの基本インタフェース要求に一致しているかどうかを確認することです。次に、コンテナがシーケンスや連想コンテナとなる場合、これらのカテゴリに固有のすべての追加要求を規定する必要があります。これは、非常に単純なコンテナ以外の場合は、習熟していないユーザーは行うべきではありません。

コンテナのユーザーが、コードを直接読み取らずに、どんな機能が期待できるかを正確に把握する上で、要求の一致は極めて重要です。コンテナ要求については、各コンテナに関する節を参照してください。

16.3.2 アロケータインタフェース要求の遵守

ユーザー定義のコンテナは、すべての記憶管理にアロケータインタフェースを利用します。その例外は、代替アロケータを必要としない、完全に内蔵した環境にあるコンテナです。

allocator クラスの基本インタフェースは、型定義セット、1 対の割り当て関数 allocate および deallocate、1 対の作成・破壊メンバーである construct および destroy で構成されます。型定義は、コンテナがポインタの外観、参照、サイズ、差分を決定するために使用します。この差分とは、2 つのポインタ間の距離のことです。関数は、実際のデータ記憶の管理を実行するために使用されます。

アロケータインタフェースを使用するには、コンテナが以下の 3 つの要求を満たしている必要があります。

コンテナは、以下のような型定義セットを含む必要があります。

typedef Allocator allocator_type;

typedef typename Allocator::size_type size_type;

typedef typename Allocator::difference_type difference_type;

typedef typename Allocator::reference reference;

typedef typename Allocator::const_reference

const_reference;

typedef implementation_defined iterator;

コンテナには、コンストラクタが指定するアロケータ引数のコピーを含む Allocator メンバーも必要です。

protected:

Allocator the_allocator;

コンテナは、この Allocator メンバーをすべての記憶管理に使用する必要があります。たとえば set コンテナは、大規模なバッファーを割り当て、そのバッファーに値を作成するだけの単純な実装を含むことがあります。これはあまり効率的な機構ではありませんが、簡単な例としては役に立つでしょう。簡潔にするため、例外を送出する Allocator::allocate の発行も避けます。

set クラスの簡略バージョンを以下に挙げます。クラスインタフェースは、必要な型定義と、このクラスの Allocator メンバーを示しています。

#include <memory>

namespace my_namespace {

template <class T, class Allocator = std::allocator<T> >
class set
{
public:
   // 上記の型定義とアロケータメンバー
   typedef Allocator allocator_type;
   typedef typename Allocator::size_type size_type;
   typedef typename Allocator::difference_type  
                               difference_type;
   typedef typename Allocator::reference reference;
   typedef typename Allocator::const_reference 
                                         const_reference;

   // 反復子は単純ポインタとなる
   typedef Allocator::pointer iterator;
   typedef Allocator::const_pointer iterator;

protected:
   Allocator the_allocator;  // アロケータのコピー

private:
   size_type buffer_size;
   iterator buffer_start;
   iterator current_end;
   iterator end_of_buffer;

public:
   // 他のコンテナまたは配列から範囲を使用して
   // set を初期化するコンストラクタ
   template <class Iterator>
   set(Iterator start, Iterator finish,
       Allocator alloc = Allocator());

   iterator begin() { return buffer_start; }
   iterator end() { return current_end; } 
};

このクラスインタフェースを仮定して、アロケータを使用する可能なコンストラクタの定義を以下に示します。コードの後の番号付きのコメントは、アロケータの役割を簡単に説明しています。アロケータの処理の詳細については、第 15 章と『標準 C++ クラスライブラリ・リファレンス』のアロケータの節を参照してください。

template <class T, class Allocator>
template <class Iterator>
set<T,Allocator>::set(Iterator start, Iterator finish,
    Allocator alloc) 
  : buffer_size(finish-start + DEFAULT_CUSHION),      
    buffer_start(0), 
    current_end(0), end_of_buffer(0)
{
   // 引数を内部オブジェクトにコピーする
   the_allocator = alloc;                               // 1

   // 初期バッファーを作成する
   buffer_start = the_allocator.allocate(buffer_size);  // 2
   end_of_buffer = buffer_start + buffer_size;

   // バッファーに反復子の範囲から新しい値を作成する
   for (current_end = buffer_start; 
        start != finish;
        current_end++, start++)
      the_allocator.construct(current_end,*start);      // 3

   // ここで標準アルゴリズムを使用して重複を削除する
   std::unique(begin(),end());
}


} // my_namespace の終わり

//1	アロケータパラメータがコンテナの保護されたメンバーにコピーされます。以後、このプライベートコピーをすべての後続の記憶管理に使用することができます。
//2	アロケータの allocate 関数を使用して、初期バッファーが割り当てられます。
//3	`start` および `finish` パラメータによって、コンストラクタに渡される反復子範囲の値を使用して、バッファーの内容が初期化されます。`construct` 関数が特定の位置にオブジェクトを作成します。この場合の位置は、コンテナのバッファー内のインデックスです。

16.3.3 反復子要求

どのコンテナも、反復子の型を定義する必要があります。反復子によって、アルゴリズムはコンテナの内容を繰り返すことができます。反復子は単純なものから非常に複雑なものまでありますが、アルゴリズムに最も影響を及ぼすのは、複雑さではなく反復子のカテゴリです。反復子のカテゴリは、どの方向へ移動できるかなどの反復子の機能を定義します。反復子のカテゴリについては、16.4 節と『標準 C++ クラスライブラリ・リファレンス』の反復子の項に詳しい説明があります。

16.3.2 節の例は、単純ポインタを使用するコンテナの実装を示しています。実際はこの単純ポインタは、最も強力な反復子の型、すなわちランダムアクセス反復子の例になります。反復子がランダムアクセスをサポートする場合、増分の場合と同様に、反復子を容易に追加したり削除したりすることができます。

反復子には機能が劣るものもあります。たとえば、片方向リンク list に添付される反復子の場合、list 内の各ノードは順方向のみのリンクを持つため、単純な反復子は片方向にしかコンテナを移動することができません。このような制約のある反復子は、順方向反復子のカテゴリに分類されます。

begin() および end() などの特定のメンバー関数は、コンテナの反復子を生成します。コンテナの記述には、必ずそのメンバー関数が生成する反復子のカテゴリが記述されている必要があります。これによって、コンテナのユーザーは、どのアルゴリズムをコンテナに適用できるかを確認することができます。