vector


マクロ定義

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

型定義

typedef struct Vector Vector
 vectorの型

関数

VectorVector_new (void)
 生成
VectorVector_new_reserve (size_t n)
 許容量を予約して生成
void Vector_delete (Vector *self)
 破棄
size_t Vector_size (Vector *self)
 要素数を取得
int Vector_empty (Vector *self)
 空チェック
size_t Vector_capacity (Vector *self)
 許容量を取得
int Vector_reserve (Vector *self, size_t n)
 許容量を予約
void Vector_shrink (Vector *self, size_t n)
 許容量を縮小
T * Vector_at (Vector *self, size_t idx)
 インデックスによる要素のアクセス
T * Vector_front (Vector *self)
 最初の要素のアクセス
T * Vector_back (Vector *self)
 最後の要素のアクセス
int Vector_insert (Vector *self, size_t idx, T data)
 要素を挿入
int Vector_insert_ref (Vector *self, size_t idx, T const *data)
 参照渡しで要素を挿入
int Vector_insert_n (Vector *self, size_t idx, size_t n, T data)
 複数個の要素を挿入
int Vector_insert_n_ref (Vector *self, size_t idx, size_t n, T const *data)
 参照渡しで複数個の要素を挿入
int Vector_insert_array (Vector *self, size_t idx, T const *data, size_t n)
 配列の要素を挿入
int Vector_insert_range (Vector *self, size_t idx, Vector *x, size_t xidx, size_t n)
 指定範囲の要素を挿入
int Vector_push_back (Vector *self, T data)
 末尾に要素を挿入
int Vector_push_back_ref (Vector *self, T const *data)
 参照渡しで末尾に要素を挿入
void Vector_erase (Vector *self, size_t idx, size_t n)
 要素を削除
void Vector_pop_back (Vector *self)
 最後の要素を削除
void Vector_clear (Vector *self)
 全要素を削除
int Vector_resize (Vector *self, size_t n, T data)
 要素数を変更
void Vector_swap (Vector *self, Vector *x)
 交換

説明

vectorは可変長な配列である。許容量を超えた要素の追加をした場合、自動的に拡張する。 末尾での要素の挿入・削除の計算量がO(1)であり、それ以外の位置の要素の挿入・削除の計算量はO(N)である。 インデックスによる要素のランダムアクセスが可能。 また、内部データの連続性は保証される。

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

#include <cstl/vector.h>

#define CSTL_VECTOR_INTERFACE(Name, Type)
#define CSTL_VECTOR_IMPLEMENT(Name, Type)

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

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

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

/* vectorのインターフェイスと実装を展開 */
CSTL_VECTOR_INTERFACE(IntVector, int)
CSTL_VECTOR_IMPLEMENT(IntVector, int)

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

    for (i = 0; i < 64; i++) {
        /* 末尾から要素を追加。自動的に拡張する */
        IntVector_push_back(vec, i);
    }

    /* 許容量の拡張 */
    printf("capacity: %d\n", IntVector_capacity(vec));
    IntVector_reserve(vec, 128);

    for (i = 0; i < 64; i++) {
        /* 先頭に要素を挿入 */
        IntVector_insert(vec, 0, i);
    }
    /* 要素数 */
    printf("size: %d\n", IntVector_size(vec));
    for (i = 0; i < IntVector_size(vec); i++) {
        /* インデックスによる要素の読み書き */
        printf("%d,", *IntVector_at(vec, i));
        *IntVector_at(vec, i) += 1;
        printf("%d\n", *IntVector_at(vec, i));
    }

    /* 先頭から要素数の半分削除 */
    IntVector_erase(vec, 0, IntVector_size(vec) / 2);
    printf("size: %d\n", IntVector_size(vec));

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

マクロ定義

#define CSTL_VECTOR_INTERFACE ( Name,
Type   ) 

インターフェイスマクロ

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

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

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

#define CSTL_VECTOR_IMPLEMENT ( Name,
Type   ) 

実装マクロ

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

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

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


型定義

typedef struct Vector Vector

vectorの型

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

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


関数

Vector* Vector_new ( void   ) 

生成

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

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

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

Vector* Vector_new_reserve ( size_t  n  ) 

許容量を予約して生成

許容量(内部メモリの再割り当てを行わずに格納できる要素数)がn 個、 要素数が0のvectorを生成する。

引数:
n 許容量
戻り値:
生成に成功した場合、vectorオブジェクトを返す。

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

void Vector_delete ( Vector self  ) 

破棄

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

引数:
self vectorオブジェクト

size_t Vector_size ( Vector self  ) 

要素数を取得

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

int Vector_empty ( Vector self  ) 

空チェック

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

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

size_t Vector_capacity ( Vector self  ) 

許容量を取得

引数:
self vectorオブジェクト
戻り値:
self の許容量

int Vector_reserve ( Vector self,
size_t  n 
)

許容量を予約

self の許容量を要素n 個の領域に拡張する。 self が持つ要素は維持され、拡張した領域の初期化はしない。

引数:
self vectorオブジェクト
n 許容量
戻り値:
拡張に成功した場合、非0を返す。

nself の現在の許容量以下の場合、self の変更を行わず非0を返す。

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

void Vector_shrink ( Vector self,
size_t  n 
)

許容量を縮小

self の許容量を要素n 個の領域に縮小する。 nself の現在の要素数以下の場合、self の許容量を要素数と同じにする。 nself の現在の許容量以上の場合、何もしない。

引数:
self vectorオブジェクト
n 許容量

T* Vector_at ( Vector self,
size_t  idx 
)

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

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

T* Vector_front ( Vector self  ) 

最初の要素のアクセス

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

T* Vector_back ( Vector self  ) 

最後の要素のアクセス

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

int Vector_insert ( Vector self,
size_t  idx,
data 
)

要素を挿入

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

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

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

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

int Vector_insert_ref ( Vector self,
size_t  idx,
T const *  data 
)

参照渡しで要素を挿入

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

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

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

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

data がNULLでないこと。

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

int Vector_insert_n ( Vector self,
size_t  idx,
size_t  n,
data 
)

複数個の要素を挿入

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

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

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

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

int Vector_insert_n_ref ( Vector self,
size_t  idx,
size_t  n,
T const *  data 
)

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

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

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

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

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

data がNULLでないこと。

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

int Vector_insert_array ( Vector self,
size_t  idx,
T const *  data,
size_t  n 
)

配列の要素を挿入

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

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

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

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

data がNULLでないこと。

int Vector_insert_range ( Vector self,
size_t  idx,
Vector x,
size_t  xidx,
size_t  n 
)

指定範囲の要素を挿入

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

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

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

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

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

int Vector_push_back ( Vector self,
data 
)

末尾に要素を挿入

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

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

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

int Vector_push_back_ref ( Vector self,
T const *  data 
)

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

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

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

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

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

void Vector_erase ( Vector self,
size_t  idx,
size_t  n 
)

要素を削除

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

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

void Vector_pop_back ( Vector self  ) 

最後の要素を削除

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

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

void Vector_clear ( Vector self  ) 

全要素を削除

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

引数:
self vectorオブジェクト

int Vector_resize ( Vector self,
size_t  n,
data 
)

要素数を変更

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

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

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

void Vector_swap ( Vector self,
Vector x 
)

交換

selfx の内容を交換する。

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


SourceForge.JP