list


マクロ定義

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

型定義

typedef struct List List
 listの型
typedef PRIVATE_TYPE * ListIterator
 イテレータ

関数

ListList_new (void)
 生成
void List_delete (List *self)
 破棄
size_t List_size (List *self)
 要素数を取得
int List_empty (List *self)
 空チェック
ListIterator List_begin (List *self)
 最初の要素のイテレータ
ListIterator List_end (List *self)
 最後の要素の次のイテレータ
ListIterator List_rbegin (List *self)
 最後の要素のイテレータ
ListIterator List_rend (List *self)
 最初の要素の前のイテレータ
ListIterator List_next (ListIterator pos)
 次のイテレータ
ListIterator List_prev (ListIterator pos)
 前のイテレータ
T * List_data (ListIterator pos)
 イテレータによる要素のアクセス
T * List_front (List *self)
 最初の要素のアクセス
T * List_back (List *self)
 最後の要素のアクセス
ListIterator List_insert (List *self, ListIterator pos, T data)
 要素を挿入
ListIterator List_insert_ref (List *self, ListIterator pos, T const *data)
 参照渡しで要素を挿入
int List_insert_n (List *self, ListIterator pos, size_t n, T data)
 複数個の要素を挿入
int List_insert_n_ref (List *self, ListIterator pos, size_t n, T const *data)
 参照渡しで複数個の要素を挿入
int List_insert_array (List *self, ListIterator pos, T const *data, size_t n)
 配列の要素を挿入
int List_insert_range (List *self, ListIterator pos, ListIterator first, ListIterator last)
 指定範囲の要素を挿入
int List_push_front (List *self, T data)
 先頭に要素を挿入
int List_push_front_ref (List *self, T const *data)
 参照渡しで先頭に要素を挿入
int List_push_back (List *self, T data)
 末尾に要素を挿入
int List_push_back_ref (List *self, T const *data)
 参照渡しで末尾に要素を挿入
ListIterator List_erase (List *self, ListIterator pos)
 要素を削除
ListIterator List_erase_range (List *self, ListIterator first, ListIterator last)
 指定範囲の要素を削除
void List_pop_front (List *self)
 最初の要素を削除
void List_pop_back (List *self)
 最後の要素を削除
void List_clear (List *self)
 全要素を削除
int List_resize (List *self, size_t n, T data)
 要素数を変更
void List_swap (List *self, List *x)
 交換
void List_splice (List *self, ListIterator pos, List *x, ListIterator first, ListIterator last)
 つなぎ換え
void List_sort (List *self, int(*comp)(const void *p1, const void *p2))
 ソート
void List_reverse (List *self)
 逆順に並べ替え
void List_merge (List *self, List *x, int(*comp)(const void *p1, const void p2 *))
 マージ

説明

listは双方向リンクリストである。 任意の位置での要素の挿入・削除の計算量がO(1)であるが、要素のランダムアクセスはできない。

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

#include <cstl/list.h>

#define CSTL_LIST_INTERFACE(Name, Type)
#define CSTL_LIST_IMPLEMENT(Name, Type)

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

使用例:
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <cstl/list.h>

typedef struct {
    char *key;
    int value;
} Hoge;

Hoge *Hoge_new(char *key, int value)
{
    Hoge *self = malloc(sizeof(Hoge));
    self->key = key;
    self->value = value;
    return self;
}

void Hoge_delete(Hoge *self)
{
    free(self);
}

void Hoge_print(Hoge *self)
{
    printf("%s: %d\n", self->key, self->value);
}

/* listのインターフェイスと実装を展開 */
CSTL_LIST_INTERFACE(HogeList, Hoge *)
CSTL_LIST_IMPLEMENT(HogeList, Hoge *)

int main(void)
{
    Hoge *hoge;
    /* イテレータ */
    HogeListIterator pos;
    /* (Hoge *)のlistを生成。
     * 型名・関数のプレフィックスはHogeListとなる。 */
    HogeList *lst = HogeList_new();

    /* 末尾から追加 */
    hoge = Hoge_new("aaa", 1);
    HogeList_push_back(lst, hoge);
    hoge = Hoge_new("bbb", 2);
    HogeList_push_back(lst, hoge);

    /* 先頭から追加 */
    hoge = Hoge_new("ccc", 3);
    HogeList_push_front(lst, hoge);
    hoge = Hoge_new("ddd", 4);
    HogeList_push_front(lst, hoge);

    /* 要素数 */
    printf("size: %d\n", HogeList_size(lst));

    for (pos = HogeList_begin(lst); pos != HogeList_end(lst); 
            pos = HogeList_next(pos)) {
        /* イテレータによる要素のアクセス */
        Hoge_print(*HogeList_data(pos));
        (*HogeList_data(pos))->value++;
        Hoge_print(*HogeList_data(pos));
    }
    for (pos = HogeList_begin(lst); pos != HogeList_end(lst); 
            pos = HogeList_next(pos)) {
        Hoge *h = *HogeList_data(pos);
        if (!strcmp(h->key, "bbb")) {
            hoge = Hoge_new("eee", 5);
            /* 要素の挿入 */
            HogeList_insert(lst, pos, hoge);
        }
    }
    for (pos = HogeList_begin(lst); pos != HogeList_end(lst);) {
        Hoge *h = *HogeList_data(pos);
        if (!strcmp(h->key, "bbb")) {
            Hoge_delete(h);
            /* 要素の削除 */
            pos = HogeList_erase(lst, pos);
        } else {
            pos = HogeList_next(pos);
        }
    }

    /* 先頭から全要素を削除 */
    while (!HogeList_empty(lst)) {
        Hoge *h = *HogeList_front(lst);
        Hoge_print(h);
        Hoge_delete(h);
        HogeList_pop_front(lst);
    }

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

マクロ定義

#define CSTL_LIST_INTERFACE ( Name,
Type   ) 

インターフェイスマクロ

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

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

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

#define CSTL_LIST_IMPLEMENT ( Name,
Type   ) 

実装マクロ

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

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

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


型定義

typedef struct List List

listの型

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

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

typedef PRIVATE_TYPE* ListIterator

イテレータ

要素の位置を示す。 イテレータ同士の比較は、 == , != が使用できる。< , > , <= , >= は使用できない。

以下、関数から返されたイテレータを有効なイテレータという。 未初期化のイテレータ、または削除された要素のイテレータ、または値が0のイテレータを無効なイテレータという。

PRIVATE_TYPEは非公開の型である。


関数

List* List_new ( void   ) 

生成

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

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

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

void List_delete ( List self  ) 

破棄

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

引数:
self listオブジェクト

size_t List_size ( List self  ) 

要素数を取得

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

int List_empty ( List self  ) 

空チェック

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

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

ListIterator List_begin ( List self  ) 

最初の要素のイテレータ

引数:
self listオブジェクト
戻り値:
self の最初の要素のイテレータ

ListIterator List_end ( List self  ) 

最後の要素の次のイテレータ

引数:
self listオブジェクト
戻り値:
self の最後の要素の次のイテレータ

ListIterator List_rbegin ( List self  ) 

最後の要素のイテレータ

引数:
self listオブジェクト
戻り値:
self の最後の要素のイテレータ

ListIterator List_rend ( List self  ) 

最初の要素の前のイテレータ

引数:
self listオブジェクト
戻り値:
self の最初の要素の前のイテレータ

ListIterator List_next ( ListIterator  pos  ) 

次のイテレータ

引数:
pos イテレータ
戻り値:
pos が示す位置の要素の次のイテレータ
事前条件:
pos が有効なイテレータであること。

posList_end() または List_rend() でないこと。

ListIterator List_prev ( ListIterator  pos  ) 

前のイテレータ

引数:
pos イテレータ
戻り値:
pos が示す位置の要素の前のイテレータ
事前条件:
pos が有効なイテレータであること。

posList_end() または List_rend() でないこと。

T* List_data ( ListIterator  pos  ) 

イテレータによる要素のアクセス

引数:
pos イテレータ
戻り値:
pos が示す位置の要素へのポインタ
事前条件:
pos が有効なイテレータであること。

posList_end() または List_rend() でないこと。

T* List_front ( List self  ) 

最初の要素のアクセス

引数:
self listオブジェクト
戻り値:
self の最初の要素へのポインタ
事前条件:
self が空でないこと。

T* List_back ( List self  ) 

最後の要素のアクセス

引数:
self listオブジェクト
戻り値:
self の最後の要素へのポインタ
事前条件:
self が空でないこと。

ListIterator List_insert ( List self,
ListIterator  pos,
data 
)

要素を挿入

selfpos が示す位置に、data のコピーを挿入する。

引数:
self listオブジェクト
pos 挿入する位置
data 挿入するデータ
戻り値:
挿入に成功した場合、新しい要素のイテレータを返す。

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

事前条件:
posself の有効なイテレータであること。

ListIterator List_insert_ref ( List self,
ListIterator  pos,
T const *  data 
)

参照渡しで要素を挿入

selfpos が示す位置に、*data のコピーを挿入する。

引数:
self listオブジェクト
pos 挿入する位置
data 挿入するデータへのポインタ
戻り値:
挿入に成功した場合、新しい要素のイテレータを返す。

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

事前条件:
posself の有効なイテレータであること。

data がNULLでないこと。

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

int List_insert_n ( List self,
ListIterator  pos,
size_t  n,
data 
)

複数個の要素を挿入

selfpos が示す位置に、data のコピーをn 個挿入する。

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

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

事前条件:
posself の有効なイテレータであること。

int List_insert_n_ref ( List self,
ListIterator  pos,
size_t  n,
T const *  data 
)

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

selfpos が示す位置に、*data のコピーをn 個挿入する。

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

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

事前条件:
posself の有効なイテレータであること。

data がNULLでないこと。

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

int List_insert_array ( List self,
ListIterator  pos,
T const *  data,
size_t  n 
)

配列の要素を挿入

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

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

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

事前条件:
posself の有効なイテレータであること。

data がNULLでないこと。

int List_insert_range ( List self,
ListIterator  pos,
ListIterator  first,
ListIterator  last 
)

指定範囲の要素を挿入

selfpos が示す位置に、[first, last)の範囲の要素のコピーを挿入する。 [first, last)の要素はself が持つ要素でもよい。

引数:
self listオブジェクト
pos 挿入する位置
first コピー元の範囲の開始位置
last コピー元の範囲の終了位置
戻り値:
挿入に成功した場合、非0を返す。

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

事前条件:
posself の有効なイテレータであること。

[first, last)が有効なイテレータであること。

int List_push_front ( List self,
data 
)

先頭に要素を挿入

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

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

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

int List_push_front_ref ( List self,
T const *  data 
)

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

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

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

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

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

int List_push_back ( List self,
data 
)

末尾に要素を挿入

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

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

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

int List_push_back_ref ( List self,
T const *  data 
)

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

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

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

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

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

ListIterator List_erase ( List self,
ListIterator  pos 
)

要素を削除

selfpos が示す位置の要素を削除する。

引数:
self listオブジェクト
pos 削除する要素の位置
戻り値:
削除した要素の次のイテレータ
事前条件:
posself の有効なイテレータであること。

posList_end() または List_rend() でないこと。

ListIterator List_erase_range ( List self,
ListIterator  first,
ListIterator  last 
)

指定範囲の要素を削除

self の[first, last)の範囲の要素を削除する。

引数:
self listオブジェクト
first 削除する範囲の開始位置
last 削除する範囲の終了位置
戻り値:
last
事前条件:
[first, last)がself の有効なイテレータであること。

void List_pop_front ( List self  ) 

最初の要素を削除

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

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

void List_pop_back ( List self  ) 

最後の要素を削除

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

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

void List_clear ( List self  ) 

全要素を削除

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

引数:
self listオブジェクト

int List_resize ( List self,
size_t  n,
data 
)

要素数を変更

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

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

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

void List_swap ( List self,
List x 
)

交換

selfx の内容を交換する。

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

void List_splice ( List self,
ListIterator  pos,
List x,
ListIterator  first,
ListIterator  last 
)

つなぎ換え

selfpos が示す位置に、x の[first, last)の範囲の要素を移動する。

引数:
self listオブジェクト
pos つなぎ換え先
x [first, last)の要素を持つlistオブジェクト
first つなぎ換え元の範囲の開始位置
last つなぎ換え元の範囲の終了位置
事前条件:
posself の有効なイテレータであること。

[first, last)がx の有効なイテレータであること。

selfx が同一ならばpos は[first, last)の範囲外であること。

void List_sort ( List self,
int(*)(const void *p1, const void *p2)  comp 
)

ソート

self のすべての要素を比較関数comp に従ってソートする。 このソートは安定である。

引数:
self listオブジェクト
comp 比較関数
事前条件:
comp には、*p1 == *p2ならば0を、*p1 < *p2ならば正または負の整数を、*p1 > *p2ならば*p1 < *p2の場合と逆の符号の整数を返す関数を指定すること。 (C標準関数のqsort(), bsearch()に使用する関数ポインタと同じ仕様)

void List_reverse ( List self  ) 

逆順に並べ替え

self のすべての要素を逆順に並べ替える。

引数:
self listオブジェクト

void List_merge ( List self,
List x,
int(*)(const void *p1, const void p2 *)  comp 
)

マージ

ソートされた状態であるselfx において、x のすべての要素を比較関数comp に従ってself にマージする。 self はソートされた状態になり、x は空になる。

引数:
self listオブジェクト
x self にマージされるlistオブジェクト
comp 比較関数
事前条件:
comp には、*p1 == *p2ならば0を、*p1 < *p2ならば正または負の整数を、*p1 > *p2ならば*p1 < *p2の場合と逆の符号の整数を返す関数を指定すること。 (C標準関数のqsort(), bsearch()に使用する関数ポインタと同じ仕様)

selfとxがcompに従ってソートされていること。


SourceForge.JP