set


マクロ定義

#define CSTL_SET_INTERFACE(Name, Type)
 set用インターフェイスマクロ
#define CSTL_SET_IMPLEMENT(Name, Type, Compare)
 set用実装マクロ
#define CSTL_MULTISET_INTERFACE(Name, Type)
 multiset用インターフェイスマクロ
#define CSTL_MULTISET_IMPLEMENT(Name, Type, Compare)
 multiset用実装マクロ
#define CSTL_LESS(x, y)   ((x) == (y) ? 0 : (x) < (y) ? -1 : 1)
 昇順指定
#define CSTL_GREATER(x, y)   ((x) == (y) ? 0 : (x) > (y) ? -1 : 1)
 降順指定

型定義

typedef struct Set Set
 set/multisetの型
typedef PRIVATE_TYPE * SetIterator
 イテレータ

関数

SetSet_new (void)
 生成
void Set_delete (Set *self)
 破棄
size_t Set_size (Set *self)
 要素数を取得
int Set_empty (Set *self)
 空チェック
SetIterator Set_begin (Set *self)
 最初の要素のイテレータ
SetIterator Set_end (Set *self)
 最後の要素の次のイテレータ
SetIterator Set_rbegin (Set *self)
 最後の要素のイテレータ
SetIterator Set_rend (Set *self)
 最初の要素の前のイテレータ
SetIterator Set_next (SetIterator pos)
 次のイテレータ
SetIterator Set_prev (SetIterator pos)
 前のイテレータ
T const * Set_data (SetIterator pos)
 イテレータによる要素のアクセス
SetIterator Set_insert (Set *self, T data, int *success)
 要素を挿入(set専用)
SetIterator Set_insert (Set *self, T data)
 要素を挿入(multiset専用)
int Set_insert_range (Set *self, SetIterator first, SetIterator last)
 指定範囲の要素を挿入
SetIterator Set_erase (Set *self, SetIterator pos)
 要素を削除
SetIterator Set_erase_range (Set *self, SetIterator first, SetIterator last)
 指定範囲の要素を削除
size_t Set_erase_key (Set *self, T data)
 指定した値の要素を削除
void Set_clear (Set *self)
 全要素を削除
void Set_swap (Set *self, Set *x)
 交換
size_t Set_count (Set *self, T data)
 指定した値の要素をカウント
SetIterator Set_find (Set *self, T data)
 指定した値の要素を検索
SetIterator Set_lower_bound (Set *self, T data)
 最初の位置の検索
SetIterator Set_upper_bound (Set *self, T data)
 最後の位置の検索
void Set_equal_range (Set *self, T data, SetIterator *first, SetIterator *last)
 指定した値の要素の範囲を取得

説明

setは要素の集合を実現する連想コンテナである。 要素を挿入すると、自動的にソートされる。同じ値の要素を2個以上挿入することはできない。 挿入した要素は読み出し専用となる。 要素の挿入・削除・検索の計算量はO(log N)である。

multisetは要素の重複が許されることを除き、setと同じである。

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

#include <cstl/set.h>

#define CSTL_SET_INTERFACE(Name, Type)
#define CSTL_SET_IMPLEMENT(Name, Type, Compare)

#define CSTL_MULTISET_INTERFACE(Name, Type)
#define CSTL_MULTISET_IMPLEMENT(Name, Type, Compare)

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

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

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

/* setのインターフェイスと実装を展開 */
CSTL_SET_INTERFACE(IntSet, int)
CSTL_SET_IMPLEMENT(IntSet, int, CSTL_LESS)

int main(void)
{
    int i;
    /* イテレータ */
    IntSetIterator pos;
    /* intのsetを生成。
     * 型名・関数のプレフィックスはIntSetとなる。 */
    IntSet *set = IntSet_new();

    /* 要素を挿入 */
    for (i = 0; i < 64; i++) {
        IntSet_insert(set, i, NULL);
    }
    /* 要素数 */
    printf("size: %d\n", IntSet_size(set));
    for (pos = IntSet_begin(set); pos != IntSet_end(set); 
            pos = IntSet_next(pos)) {
        /* イテレータによる要素の読み出し(書き換えはできない) */
        printf("%d, ", *IntSet_data(pos));
    }
    printf("\n");

    /* 3以上の要素を削除 */
    IntSet_erase_range(set, IntSet_find(set, 3), IntSet_end(set));

    for (pos = IntSet_begin(set); pos != IntSet_end(set); 
            pos = IntSet_next(pos)) {
        /* イテレータによる要素の読み出し(書き換えはできない) */
        printf("%d, ", *IntSet_data(pos));
    }
    printf("\n");

    /* 使い終わったら破棄 */
    IntSet_delete(set);
    return 0;
}
注意:
以下に説明する型定義・関数は、 CSTL_SET_INTERFACE(Name, Type) , CSTL_MULTISET_INTERFACE(Name, Type)NameSet , TypeT を仮に指定した場合のものである。 実際に使用する際には、使用例のように適切な引数を指定すること。
覚え書き:
set専用/multiset専用と記した関数以外の関数は、set/multiset共通の関数である。

コンパイラオプションによって、NDEBUGマクロが未定義かつCSTL_DEBUGマクロが定義されているならば、 assertマクロが有効になり、関数の事前条件に違反するとプログラムの実行を停止する。


マクロ定義

#define CSTL_SET_INTERFACE ( Name,
Type   ) 

set用インターフェイスマクロ

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

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

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

覚え書き:
Type に構造体型を指定することは、構造体コピーによってパフォーマンスが低下する可能性があるため推奨されない。

#define CSTL_SET_IMPLEMENT ( Name,
Type,
Compare   ) 

set用実装マクロ

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

引数:
Name 既存の型と重複しない任意の名前。setの型名と関数のプレフィックスになる
Type 任意の要素の型
Compare 要素を比較する関数またはマクロ

注意:
Compare 以外の引数は CSTL_SET_INTERFACE()の引数と同じものを指定すること。

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

覚え書き:
Type に構造体型を指定することは、構造体コピーによってパフォーマンスが低下する可能性があるため推奨されない。

#define CSTL_MULTISET_INTERFACE ( Name,
Type   ) 

multiset用インターフェイスマクロ

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

使用方法は CSTL_SET_INTERFACE()と同じである。

#define CSTL_MULTISET_IMPLEMENT ( Name,
Type,
Compare   ) 

multiset用実装マクロ

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

使用方法は CSTL_SET_IMPLEMENT()と同じである。

#define CSTL_LESS ( x,
 )     ((x) == (y) ? 0 : (x) < (y) ? -1 : 1)

昇順指定

要素を昇順にソートする場合、 CSTL_SET_IMPLEMENT() , CSTL_MULTISET_INTERFACE()Compare 引数に指定する。

引数:
x 1つ目の値
y 2つ目の値
戻り値:
0 x == y の場合
負の値 x < y の場合
正の値 x > y の場合

#define CSTL_GREATER ( x,
 )     ((x) == (y) ? 0 : (x) > (y) ? -1 : 1)

降順指定

要素を降順にソートする場合、 CSTL_SET_IMPLEMENT() , CSTL_MULTISET_INTERFACE()Compare 引数に指定する。

引数:
x 1つ目の値
y 2つ目の値
戻り値:
0 x == y の場合
負の値 x > y の場合
正の値 x < y の場合


型定義

typedef struct Set Set

set/multisetの型

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

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

typedef PRIVATE_TYPE* SetIterator

イテレータ

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

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

PRIVATE_TYPEは非公開の型である。


関数

Set* Set_new ( void   ) 

生成

要素数が0のset/multisetを生成する。

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

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

void Set_delete ( Set self  ) 

破棄

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

引数:
self setオブジェクト

size_t Set_size ( Set self  ) 

要素数を取得

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

int Set_empty ( Set self  ) 

空チェック

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

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

SetIterator Set_begin ( Set self  ) 

最初の要素のイテレータ

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

SetIterator Set_end ( Set self  ) 

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

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

SetIterator Set_rbegin ( Set self  ) 

最後の要素のイテレータ

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

SetIterator Set_rend ( Set self  ) 

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

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

SetIterator Set_next ( SetIterator  pos  ) 

次のイテレータ

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

posSet_end() または Set_rend() でないこと。

SetIterator Set_prev ( SetIterator  pos  ) 

前のイテレータ

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

posSet_end() または Set_rend() でないこと。

T const* Set_data ( SetIterator  pos  ) 

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

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

posSet_end() または Set_rend() でないこと。

覚え書き:
戻り値のポインタの参照先はconstである。

SetIterator Set_insert ( Set self,
data,
int *  success 
)

要素を挿入(set専用)

data のコピーをself に挿入する。

引数:
self setオブジェクト
data 挿入するデータ
success 成否を格納する変数へのポインタ。ただし、NULLを指定した場合はアクセスしない。
戻り値:
挿入に成功した場合、*success に非0の値を格納し、新しい要素のイテレータを返す。

self が既にdata という値の要素を持っている場合、挿入を行わず、*success に0を格納し、その要素のイテレータを返す。

メモリ不足の場合、*success に0を格納し、self の変更を行わず0を返す。

覚え書き:
この関数はsetのみで提供される。

SetIterator Set_insert ( Set self,
data 
)

要素を挿入(multiset専用)

data のコピーをself に挿入する。 self が既にdata という値の要素を持っている場合、その値の一番最後の位置に挿入される。

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

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

覚え書き:
この関数はmultisetのみで提供される。

int Set_insert_range ( Set self,
SetIterator  first,
SetIterator  last 
)

指定範囲の要素を挿入

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

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

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

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

SetIterator Set_erase ( Set self,
SetIterator  pos 
)

要素を削除

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

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

posSet_end() または Set_rend() でないこと。

SetIterator Set_erase_range ( Set self,
SetIterator  first,
SetIterator  last 
)

指定範囲の要素を削除

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

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

size_t Set_erase_key ( Set self,
data 
)

指定した値の要素を削除

selfdata という値の要素をすべて削除する。

引数:
self setオブジェクト
data 削除する要素の値
戻り値:
削除した数

void Set_clear ( Set self  ) 

全要素を削除

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

引数:
self setオブジェクト

void Set_swap ( Set self,
Set x 
)

交換

selfx の内容を交換する。

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

size_t Set_count ( Set self,
data 
)

指定した値の要素をカウント

引数:
self setオブジェクト
data カウントする要素の値
戻り値:
selfdata という値の要素の数

SetIterator Set_find ( Set self,
data 
)

指定した値の要素を検索

selfdata という値の最初の要素を検索する。

引数:
self setオブジェクト
data 検索する要素の値
戻り値:
見つかった場合、その要素のイテレータを返す。

見つからない場合、 Set_end(self) を返す。

SetIterator Set_lower_bound ( Set self,
data 
)

最初の位置の検索

ソートの基準に従い、selfdata 以上 の値の最初の要素を検索する。

引数:
self setオブジェクト
data 検索する要素の値
戻り値:
見つかった場合、その要素のイテレータを返す。

見つからない場合、 Set_end(self) を返す。

SetIterator Set_upper_bound ( Set self,
data 
)

最後の位置の検索

ソートの基準に従い、selfdata より大きい 値の最初の要素を検索する。

引数:
self setオブジェクト
data 検索する要素の値
戻り値:
見つかった場合、その要素のイテレータを返す。

見つからない場合、 Set_end(self) を返す。

void Set_equal_range ( Set self,
data,
SetIterator first,
SetIterator last 
)

指定した値の要素の範囲を取得

引数:
self setオブジェクト
data 検索する要素の値
first data という値の最初の要素のイテレータを格納する変数へのポインタ
last data という値の最後の要素の次のイテレータを格納する変数へのポインタ
事前条件:
first がNULLでないこと。

last がNULLでないこと。

覚え書き:
selfdata という値の要素を持たない場合、*first , *last ともにSet_end(self)が格納される。


SourceForge.JP