週に一回は書きますよ 月に4つ記事を書けばノルマは満たされます。
上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

前の記事からの続き。

この先、SimpleQueueよりましなQueueの実装をいくつか試して、どれだけ違いが出るか確認する予定です。既に実装は他に二種できてます。ないのはテストコードとかプロファイラとか。あと清書。

Queueのインターフェスはちょっと変えました。struct内のstructを用意する代わりに、templateの特殊化で関数を実装することにしました。具体的にはこんなかんじ。

// Push<Queue, Item>::typeでitemを積んだ新しいQueueを返す。
// Primary templateはなにもなし。
template<typename Q_, typename A_> struct Push {};

// SimpleQueueの実装。
template<typename Front_, typename Rear_, typename A_>
struct Push<SimpleQueue<Front_, Rear_>, A_> {
  typedef SimpleQueue<Front_, TList<A_, Rear_> > type;
};

// Physicist Queue(未だ解説してません)での実装。
template<typename Evaled_, int front_size_, typename Front_,
	 int rear_size_, typename Rear_, typename A_>
struct Push<PhysicistQueue<Evaled_, front_size_, Front_, rear_size_, Rear_>,
	    A_> {
  typedef typename PhyQueue_Check<
      Evaled_, front_size_, Front_, rear_size_ + 1,
      TList<A_, Rear_> >::type type;
};

もちろん実際のコードではSimpleQueue用のコードとPhysicistQueue用のコードがこのように並べて書いてあったりはしません。同じPushの特殊化でも全く別々の場所に置けます。

何のQueueでもPush<Queue, A_>であつかえます。QueueはPush, Top, Pop, IsEmptyを提供します。

この書きかたのままだとうまく書けない関数があります。たとえば、Empty<SimpleQueue>::typeで空のSimpleQueueが得られる"Empty関数"があると良いのですが、これを書けません。

// SimpleQueue用の実装
typedef SimpleQueue<NullType, NullType> EmptySimpleQueue;
template<template<typename, typename> class Q>
struct Empty {
  typedef EmptySimpleQueue type;
};

// PhysicistQueue用の実装
typedef PhysicistQueue<NullType, 0, Id<NullType>,
		       0, NullType> EmptyPhysicistQueue;
template<template<typename, int, typename, int, typename> class Q>
struct Empty {
  typedef EmptyPhysicistQueue type;
};
// 実際にはこのようにEmptyを二回定義することはできません。

今の実装は実装の詳細をQueueのテンプレートに書いているため、それらを同じテンプレートで受けるのは不可能です。そのため上のEmpty関数は書けません。いくつか解決策はあります。

  • SimpleQueue<SimpleQueueImpl<Front, Rear> >のように、実装用のクラスを間にはさむ。すると違うQueueでも見た目のtemplateが同じになって受けられるようになる。
    • ヘッダファイルが長くなる。
  • 実装を全てSimpleQueueImplで行う。別に空のSimpleQueueクラスを用意して、Empty<SimpleQueue>::typeSimpleQueueImpl<NullType, NullType>を返すようにする。
    • ユーザがSimpleQueue用のコードを書こうとしたときにSimpleQueueが来ない。
  • EmptySimpleQueueやEmptyPhysicistQueueをSimpleQueue, PhysicistQueueと名付ける。
    • ユーザがSimpleQueue用のコードを書こうとしたときにSimpleQueueが来ない。
    • Empty*QueueはQueueそのものではない。美しくない。
    • どのQueueでも同じように扱えるので、正直Empty*Queue以外に実装の名前が出てくるところがない。ならここでその名前を使っても構わないと思う。

とりあえず最後のを採用したつもりで、Empty関数も*QueueImplも実装することなく書いています。

スポンサーサイト
コメント
この記事へのコメント
コメントを投稿する
URL:
Comment:
Pass:
秘密: 管理者にだけ表示を許可する
 
トラックバック
この記事のトラックバックURL
http://gusmachine.blog49.fc2.com/tb.php/446-fe814aa0
この記事にトラックバックする(FC2ブログユーザー)
この記事へのトラックバック
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。