deque


マクロ定義

#define CSTL_DEQUE_INTERFACE(Name, Type)
 インターフェイスマクロ
#define CSTL_DEQUE_IMPLEMENT(Name, Type)
 実装マクロ

型定義

typedef struct Deque Deque
 dequeの型

関数

DequeDeque_new (void)
 生成
void Deque_delete (Deque *self)
 破棄
size_t Deque_size (Deque *self)
 要素数を取得
int Deque_empty (Deque *self)
 空チェック
T * Deque_at (Deque *self, size_t idx)
 インデックスによる要素のアクセス
T * Deque_front (Deque *self)
 最初の要素のアクセス
T * Deque_back (Deque *self)
 最後の要素のアクセス
int Deque_insert (Deque *self, size_t idx, T data)
 要素を挿入
int Deque_insert_ref (Deque *self, size_t idx, T const *data)
 参照渡しで要素を挿入
int Deque_insert_n (Deque *self, size_t idx, size_t n, T data)
 複数個の要素を挿入
int Deque_insert_n_ref (Deque *self, size_t idx, size_t n, T const *data)
 参照渡しで複数個の要素を挿入
int Deque_insert_array (Deque *self, size_t idx, T const *data, size_t n)
 配列の要素を挿入
int Deque_insert_range (Deque *self, size_t idx, Deque *x, size_t xidx, size_t n)
 指定範囲の要素を挿入
int Deque_push_front (Deque *self, T data)
 先頭に要素を挿入
int Deque_push_front_ref (Deque *self, T const *data)
 参照渡しで先頭に要素を挿入
int Deque_push_back (Deque *self, T data)
 末尾に要素を挿入
int Deque_push_back_ref (Deque *self, T const *data)
 参照渡しで末尾に要素を挿入
void Deque_erase (Deque *self, size_t idx, size_t n)
 要素を削除
void Deque_pop_front (Deque *self)
 最初の要素を削除
void Deque_pop_back (Deque *self)
 最後の要素を削除
void Deque_clear (Deque *self)
 全要素を削除
int Deque_resize (Deque *self, size_t n, T data)
 要素数を変更
void Deque_swap (Deque *self, Deque *x)
 交換

説明

dequeは可変長な両端キューである。 先頭と末尾での要素の挿入・削除の計算量がO(1)であり、それ以外の位置の要素の挿入・削除の計算量はO(N)である。 インデックスによる要素のランダムアクセスが可能。

dequeを使うには、<cstl/deque.h>をインクルードし、以下のマクロを用いてコードを展開する必要がある。

#include <cstl/deque.h>

#define CSTL_DEQUE_INTERFACE(Name, Type)
#define CSTL_DEQUE_IMPLEMENT(Name, Type)

CSTL_DEQUE_INTERFACE() は任意の名前と要素の型のdequeのインターフェイスを展開する。 CSTL_DEQUE_IMPLEMENT() はその実装を展開する。

また、CSTL_DEQUE_INTERFACE() を展開する前に、<cstl/algorithm.h>をインクルードすることにより、 アルゴリズムが使用可能となる。

使用例:
#include <stdio.h>
#include <cstl/deque.h>

/* dequeのインターフェイスと実装を展開 */
CSTL_DEQUE_INTERFACE(IntDeque, int)
CSTL_DEQUE_IMPLEMENT(IntDeque, int)

int main(void)
{
    int i;
    /* intのdequeを生成。
     * 型名・関数のプレフィックスはIntDequeとなる。 */
    IntDeque *deq = IntDeque_new();

    for (i = 0; i < 32; i++) {
        /* 末尾から追加 */
        IntDeque_push_back(deq, i);
    }
    for (i = 0; i < 32; i++) {
        /* 先頭から追加 */
        IntDeque_push_front(deq, i);
    }
    /* 要素数 */
    printf("size: %d\n", IntDeque_size(deq));
    for (i = 0; i < IntDeque_size(deq); i++) {
        /* インデックスによる要素の読み書き */
        printf("%d,", *IntDeque_at(deq, i));
        *IntDeque_at(deq, i) += 1;
        printf("%d\n", *IntDeque_at(deq, i));
    }

    /* 先頭から全要素を取り出して削除 */
    while (!IntDeque_empty(deq)) {
        printf("%d\n", *IntDeque_front(deq));
        IntDeque_pop_front(deq);
    }
    printf("size: %d\n", IntDeque_size(deq));

    /* 使い終わったら破棄 */
    IntDeque_delete(deq);
    return 0;
}

注意:
以下に説明する型定義・関数は、 CSTL_DEQUE_INTERFACE(Name, Type)NameDeque , TypeT を仮に指定した場合のものである。 実際に使用する際には、使用例のように適切な引数を指定すること。
覚え書き:
コンパイラオプションによって、NDEBUGマクロが未定義かつCSTL_DEBUGマクロが定義されているならば、 assertマクロが有効になり、関数の事前条件に違反するとプログラムの実行を停止する。

マクロ定義

#define CSTL_DEQUE_INTERFACE ( Name,
Type   ) 

インターフェイスマクロ

任意の名前と要素の型のdequeのインターフェイスを展開する。

引数:
Name 既存の型と重複しない任意の名前。dequeの型名と関数のプレフィックスになる
Type 任意の要素の型
注意:
引数は CSTL_DEQUE_IMPLEMENT()の引数と同じものを指定すること。

Type を括弧で括らないこと。

#define CSTL_DEQUE_IMPLEMENT ( Name,
Type   ) 

実装マクロ

CSTL_DEQUE_INTERFACE()で展開したインターフェイスの実装を展開する。

引数:
Name 既存の型と重複しない任意の名前。dequeの型名と関数のプレフィックスになる
Type 任意の要素の型
注意:
引数は CSTL_DEQUE_INTERFACE()の引数と同じものを指定すること。

Type を括弧で括らないこと。


型定義

typedef struct Deque Deque

dequeの型

抽象データ型となっており、内部データメンバは非公開である。

以下、 Deque_new() から返されたDeque構造体へのポインタをdequeオブジェクトという。


関数

Deque* Deque_new ( void   ) 

生成

要素数が0のdequeを生成する。

戻り値:
生成に成功した場合、dequeオブジェクトを返す。

メモリ不足の場合、NULLを返す。

void Deque_delete ( Deque self  ) 

破棄

self のすべての要素を削除し、self を破棄する。 self がNULLの場合、何もしない。

引数:
self dequeオブジェクト

size_t Deque_size ( Deque self  ) 

要素数を取得

引数:
self dequeオブジェクト
戻り値:
self の要素数

int Deque_empty ( Deque self  ) 

空チェック

引数:
self dequeオブジェクト
戻り値:
self の要素数が0の場合、非0を返す。

self の要素数が1以上の場合、0を返す。

T* Deque_at ( Deque self,
size_t  idx 
)

インデックスによる要素のアクセス

引数:
self dequeオブジェクト
idx インデックス
戻り値:
selfidx 番目の要素へのポインタ
事前条件:
idxself の要素数より小さい値であること。
覚え書き:
戻り値はself の変更により無効となる。

T* Deque_front ( Deque self  ) 

最初の要素のアクセス

引数:
self dequeオブジェクト
戻り値:
self の最初の要素へのポインタ
事前条件:
self が空でないこと。
覚え書き:
戻り値はself の変更により無効となる。

T* Deque_back ( Deque self  ) 

最後の要素のアクセス

引数:
self dequeオブジェクト
戻り値:
self の最後の要素へのポインタ
事前条件:
self が空でないこと。
覚え書き:
戻り値はself の変更により無効となる。

int Deque_insert ( Deque self,
size_t  idx,
data 
)

要素を挿入

selfidx 番目の位置に、data のコピーを挿入する。

引数:
self dequeオブジェクト
idx 挿入する位置
data 挿入するデータ
戻り値:
挿入に成功した場合、非0を返す。

メモリ不足の場合、self の変更を行わず0を返す。

事前条件:
idxself の要素数以下の値であること。

int Deque_insert_ref ( Deque self,
size_t  idx,
T const *  data 
)

参照渡しで要素を挿入

selfidx 番目の位置に、*data のコピーを挿入する。

引数:
self dequeオブジェクト
idx 挿入する位置
data 挿入するデータへのポインタ
戻り値:
挿入に成功した場合、非0を返す。

メモリ不足の場合、self の変更を行わず0を返す。

事前条件:
idxself の要素数以下の値であること。

data がNULLでないこと。

覚え書き:
T が構造体型の場合、 Deque_insert() よりも速い。

int Deque_insert_n ( Deque self,
size_t  idx,
size_t  n,
data 
)

複数個の要素を挿入

selfidx 番目の位置に、data のコピーをn 個挿入する。

引数:
self dequeオブジェクト
idx 挿入する位置
n 挿入するデータの個数
data 挿入するデータ
戻り値:
挿入に成功した場合、非0を返す。

メモリ不足の場合、self の変更を行わず0を返す。

事前条件:
idxself の要素数以下の値であること。

int Deque_insert_n_ref ( Deque self,
size_t  idx,
size_t  n,
T const *  data 
)

参照渡しで複数個の要素を挿入

selfidx 番目の位置に、*data のコピーをn 個挿入する。

引数:
self dequeオブジェクト
idx 挿入する位置
n 挿入するデータの個数
data 挿入するデータへのポインタ
戻り値:
挿入に成功した場合、非0を返す。

メモリ不足の場合、self の変更を行わず0を返す。

事前条件:
idxself の要素数以下の値であること。

data がNULLでないこと。

覚え書き:
T が構造体型の場合、 Deque_insert_n() よりも速い。

int Deque_insert_array ( Deque self,
size_t  idx,
T const *  data,
size_t  n 
)

配列の要素を挿入

selfidx 番目の位置に、data という配列からn 個の要素のコピーを挿入する。

引数:
self dequeオブジェクト
idx 挿入する位置
data 挿入するデータの配列
n 挿入するデータの個数
戻り値:
挿入に成功した場合、非0を返す。

メモリ不足の場合、self の変更を行わず0を返す。

事前条件:
idxself の要素数以下の値であること。

data がNULLでないこと。

int Deque_insert_range ( Deque self,
size_t  idx,
Deque x,
size_t  xidx,
size_t  n 
)

指定範囲の要素を挿入

selfidx 番目の位置に、xxidx 番目からn 個の要素のコピーを挿入する。 selfx は同じオブジェクトでもよい。

引数:
self dequeオブジェクト
idx 挿入する位置
x コピー元のdequeオブジェクト
xidx x のコピー開始インデックス
n コピーする要素数
戻り値:
挿入に成功した場合、非0を返す。

メモリ不足の場合、self の変更を行わず0を返す。

事前条件:
xidx + nx の要素数以下の値であること。

idxself の要素数以下の値であること。

int Deque_push_front ( Deque self,
data 
)

先頭に要素を挿入

data のコピーをself の最初の要素として挿入する。

引数:
self dequeオブジェクト
data 挿入するデータ
戻り値:
挿入に成功した場合、非0を返す。

メモリ不足の場合、self の変更を行わず0を返す。

int Deque_push_front_ref ( Deque self,
T const *  data 
)

参照渡しで先頭に要素を挿入

*data のコピーをself の最初の要素として挿入する。

引数:
self dequeオブジェクト
data 挿入するデータへのポインタ
戻り値:
挿入に成功した場合、非0を返す。

メモリ不足の場合、self の変更を行わず0を返す。

事前条件:
data がNULLでないこと。
覚え書き:
T が構造体型の場合、 Deque_push_front() よりも速い。

int Deque_push_back ( Deque self,
data 
)

末尾に要素を挿入

data のコピーをself の最後の要素として挿入する。

引数:
self dequeオブジェクト
data 挿入するデータ
戻り値:
挿入に成功した場合、非0を返す。

メモリ不足の場合、self の変更を行わず0を返す。

int Deque_push_back_ref ( Deque self,
T const *  data 
)

参照渡しで末尾に要素を挿入

*data のコピーをself の最後の要素として挿入する。

引数:
self dequeオブジェクト
data 挿入するデータへのポインタ
戻り値:
挿入に成功した場合、非0を返す。

メモリ不足の場合、self の変更を行わず0を返す。

事前条件:
data がNULLでないこと。
覚え書き:
T が構造体型の場合、 Deque_push_back() よりも速い。

void Deque_erase ( Deque self,
size_t  idx,
size_t  n 
)

要素を削除

selfidx 番目からn 個の要素を削除する。

引数:
self dequeオブジェクト
idx 削除開始インデックス
n 削除する要素数
事前条件:
idx + nself の要素数以下の値であること。

void Deque_pop_front ( Deque self  ) 

最初の要素を削除

self の最初の要素を削除する。

引数:
self dequeオブジェクト
事前条件:
self が空でないこと。

void Deque_pop_back ( Deque self  ) 

最後の要素を削除

self の最後の要素を削除する。

引数:
self dequeオブジェクト
事前条件:
self が空でないこと。

void Deque_clear ( Deque self  ) 

全要素を削除

self のすべての要素を削除する。

引数:
self dequeオブジェクト

int Deque_resize ( Deque self,
size_t  n,
data 
)

要素数を変更

self の要素数をn 個に変更する。 nself の現在の要素数以下の場合、要素数がn 個になるまで末尾から要素が削除される。 nself の現在の要素数より大きい場合、要素数がn 個になるまでdata のコピーが末尾から挿入される。

引数:
self dequeオブジェクト
n 要素数
data 挿入するデータ
戻り値:
要素数の変更に成功した場合、非0を返す。

メモリ不足の場合、self の変更を行わず0を返す。

void Deque_swap ( Deque self,
Deque x 
)

交換

selfx の内容を交換する。

引数:
self dequeオブジェクト
x self と内容を交換するdequeオブジェクト


SourceForge.JP