map


マクロ定義

#define CSTL_MAP_INTERFACE(Name, KeyType, ValueType)
 map用インターフェイスマクロ
#define CSTL_MAP_IMPLEMENT(Name, KeyType, ValueType, Compare)
 map用実装マクロ
#define CSTL_MULTIMAP_INTERFACE(Name, KeyType, ValueType)
 multimap用インターフェイスマクロ
#define CSTL_MULTIMAP_IMPLEMENT(Name, KeyType, ValueType, Compare)
 multimap用実装マクロ
#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 Map Map
 map/multimapの型
typedef PRIVATE_TYPE * MapIterator
 イテレータ

関数

MapMap_new (void)
 生成
void Map_delete (Map *self)
 破棄
size_t Map_size (Map *self)
 要素数を取得
int Map_empty (Map *self)
 空チェック
MapIterator Map_begin (Map *self)
 最初の要素のイテレータ
MapIterator Map_end (Map *self)
 最後の要素の次のイテレータ
MapIterator Map_rbegin (Map *self)
 最後の要素のイテレータ
MapIterator Map_rend (Map *self)
 最初の要素の前のイテレータ
MapIterator Map_next (MapIterator pos)
 次のイテレータ
MapIterator Map_prev (MapIterator pos)
 前のイテレータ
KeyT const * Map_key (MapIterator pos)
 イテレータによる要素のキーのアクセス
ValueT * Map_value (MapIterator pos)
 イテレータによる要素の値のアクセス
ValueT * Map_at (Map *self, KeyT key)
 キーとペアになる値のアクセス(map専用)
MapIterator Map_insert (Map *self, KeyT key, ValueT value, int *success)
 要素を挿入(map専用)
MapIterator Map_insert_ref (Map *self, KeyT key, ValueT const *value, int *success)
 参照渡しで要素を挿入(map専用)
MapIterator Map_insert (Map *self, KeyT key, ValueT value)
 要素を挿入(multimap専用)
MapIterator Map_insert_ref (Map *self, KeyT key, ValueT const *value)
 参照渡しで要素を挿入(multimap専用)
int Map_insert_range (Map *self, MapIterator first, MapIterator last)
 指定範囲の要素を挿入
MapIterator Map_erase (Map *self, MapIterator pos)
 要素を削除
MapIterator Map_erase_range (Map *self, MapIterator first, MapIterator last)
 指定範囲の要素を削除
size_t Map_erase_key (Map *self, KeyT key)
 指定キーの要素を削除
void Map_clear (Map *self)
 全要素を削除
void Map_swap (Map *self, Map *x)
 交換
size_t Map_count (Map *self, KeyT key)
 指定キーの要素をカウント
MapIterator Map_find (Map *self, KeyT key)
 指定キーの要素を検索
MapIterator Map_lower_bound (Map *self, KeyT key)
 最初の位置の検索
MapIterator Map_upper_bound (Map *self, KeyT key)
 最後の位置の検索
void Map_equal_range (Map *self, KeyT key, MapIterator *first, MapIterator *last)
 指定キーの要素の範囲を取得

説明

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

multimapはキーの重複が許されることと、キーとペアになる値の直接アクセスが不可能であることを除き、mapと同じである。

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

#include <cstl/map.h>

#define CSTL_MAP_INTERFACE(Name, KeyType, ValueType)
#define CSTL_MAP_IMPLEMENT(Name, KeyType, ValueType, Compare)

#define CSTL_MULTIMAP_INTERFACE(Name, KeyType, ValueType)
#define CSTL_MULTIMAP_IMPLEMENT(Name, KeyType, ValueType, Compare)

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

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

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

/* mapのインターフェイスと実装を展開 */
CSTL_MAP_INTERFACE(StrIntMap, const char *, int)
CSTL_MAP_IMPLEMENT(StrIntMap, const char *, int, strcmp)

/* multimapのインターフェイスと実装を展開 */
CSTL_MULTIMAP_INTERFACE(IntIntMMap, int, int)
CSTL_MULTIMAP_IMPLEMENT(IntIntMMap, int, int, CSTL_LESS)

int main(void)
{
    { /* map */
        /* イテレータ */
        StrIntMapIterator pos;
        /* キーが文字列、値がintのmapを生成。
         * 型名・関数のプレフィックスはStrIntMapとなる。 */
        StrIntMap *map = StrIntMap_new();

        /* 要素を挿入 */
        StrIntMap_insert(map, "aaa", 1, NULL);
        StrIntMap_insert(map, "bbb", 2, NULL);
        /* キーによる値の読み書き */
        printf("%d\n", *StrIntMap_at(map, "aaa"));
        *StrIntMap_at(map, "bbb") = 3;
        *StrIntMap_at(map, "ccc") = 4; /* 存在しないキーの要素は自動的に挿入 */
        /* 要素数 */
        printf("size: %d\n", StrIntMap_size(map));
        for (pos = StrIntMap_begin(map); pos != StrIntMap_end(map); 
                pos = StrIntMap_next(pos)) {
            /* イテレータによる要素の読み書き */
            printf("%s: %d,", *StrIntMap_key(pos), *StrIntMap_value(pos));
            *StrIntMap_value(pos) += 1;
            printf("%d\n", *StrIntMap_value(pos));
        }

        /* 使い終わったら破棄 */
        StrIntMap_delete(map);
    }
    { /* multimap */
        /* イテレータ */
        IntIntMMapIterator pos;
        /* キーがint、値がintのmultimapを生成。
         * 型名・関数のプレフィックスはIntIntMMapとなる。 */
        IntIntMMap *map = IntIntMMap_new();

        /* 要素を挿入 */
        IntIntMMap_insert(map, 1, 1);
        IntIntMMap_insert(map, 2, 2);
        IntIntMMap_insert(map, 1, 3); /* 重複したキーを挿入できる */
        /* 要素数 */
        printf("size: %d\n", IntIntMMap_size(map));

        /* キーが1の要素を探索 */
        for (pos = IntIntMMap_lower_bound(map, 1); 
                pos != IntIntMMap_upper_bound(map, 1); 
                pos = IntIntMMap_next(pos)) {
            /* イテレータによる要素の読み書き */
            printf("%d: %d,", *IntIntMMap_key(pos), *IntIntMMap_value(pos));
            *IntIntMMap_value(pos) += 1;
            printf("%d\n", *IntIntMMap_value(pos));
        }

        /* 使い終わったら破棄 */
        IntIntMMap_delete(map);
    }
    return 0;
}
注意:
以下に説明する型定義・関数は、 CSTL_MAP_INTERFACE(Name, KeyType, ValueType) , CSTL_MULTIMAP_INTERFACE(Name, KeyType, ValueType)NameMap , KeyTypeKeyT , ValueTypeValueT を仮に指定した場合のものである。 実際に使用する際には、使用例のように適切な引数を指定すること。
覚え書き:
map専用/multimap専用と記した関数以外の関数は、map/multimap共通の関数である。

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


マクロ定義

#define CSTL_MAP_INTERFACE ( Name,
KeyType,
ValueType   ) 

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

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

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

KeyType , ValueType を括弧で括らないこと。

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

#define CSTL_MAP_IMPLEMENT ( Name,
KeyType,
ValueType,
Compare   ) 

map用実装マクロ

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

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

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

KeyType , ValueType を括弧で括らないこと。

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

#define CSTL_MULTIMAP_INTERFACE ( Name,
KeyType,
ValueType   ) 

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

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

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

#define CSTL_MULTIMAP_IMPLEMENT ( Name,
KeyType,
ValueType,
Compare   ) 

multimap用実装マクロ

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

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

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

昇順指定

要素を昇順にソートする場合、 CSTL_MAP_IMPLEMENT() , CSTL_MULTIMAP_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_MAP_IMPLEMENT() , CSTL_MULTIMAP_INTERFACE()Compare 引数に指定する。

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


型定義

typedef struct Map Map

map/multimapの型

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

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

typedef PRIVATE_TYPE* MapIterator

イテレータ

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

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

PRIVATE_TYPEは非公開の型である。


関数

Map* Map_new ( void   ) 

生成

要素数が0のmap/multimapを生成する。

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

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

void Map_delete ( Map self  ) 

破棄

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

引数:
self mapオブジェクト

size_t Map_size ( Map self  ) 

要素数を取得

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

int Map_empty ( Map self  ) 

空チェック

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

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

MapIterator Map_begin ( Map self  ) 

最初の要素のイテレータ

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

MapIterator Map_end ( Map self  ) 

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

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

MapIterator Map_rbegin ( Map self  ) 

最後の要素のイテレータ

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

MapIterator Map_rend ( Map self  ) 

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

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

MapIterator Map_next ( MapIterator  pos  ) 

次のイテレータ

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

posMap_end() または Map_rend() でないこと。

MapIterator Map_prev ( MapIterator  pos  ) 

前のイテレータ

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

posMap_end() または Map_rend() でないこと。

KeyT const* Map_key ( MapIterator  pos  ) 

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

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

posMap_end() または Map_rend() でないこと。

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

ValueT* Map_value ( MapIterator  pos  ) 

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

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

posMap_end() または Map_rend() でないこと。

ValueT* Map_at ( Map self,
KeyT  key 
)

キーとペアになる値のアクセス(map専用)

引数:
self mapオブジェクト
key キー
戻り値:
selfkey というキーの要素の値へのポインタを返す。

selfkey というキーの要素を持っていない場合、key というキーの新しい要素(値は不定)を挿入し、その要素の値へのポインタを返す。

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

注意:
新しい要素を挿入しようとしてメモリ不足で失敗した場合、戻り値のNULLポインタを逆参照しないように注意すること。
覚え書き:
この関数はmapのみで提供される。

MapIterator Map_insert ( Map self,
KeyT  key,
ValueT  value,
int *  success 
)

要素を挿入(map専用)

keyvalue のコピーのペアを要素としてself に挿入する。

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

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

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

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

MapIterator Map_insert_ref ( Map self,
KeyT  key,
ValueT const *  value,
int *  success 
)

参照渡しで要素を挿入(map専用)

key と*value のコピーのペアを要素としてself に挿入する。

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

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

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

事前条件:
value がNULLでないこと。
覚え書き:
この関数はmapのみで提供される。

ValueT が構造体型の場合、 Map_insert() よりも速い。

MapIterator Map_insert ( Map self,
KeyT  key,
ValueT  value 
)

要素を挿入(multimap専用)

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

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

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

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

MapIterator Map_insert_ref ( Map self,
KeyT  key,
ValueT const *  value 
)

参照渡しで要素を挿入(multimap専用)

key と*value のコピーのペアを要素としてself に挿入する。 self が既にkey というキーの要素を持っている場合、そのキーの一番最後の位置に挿入される。

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

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

事前条件:
value がNULLでないこと。
覚え書き:
この関数はmultimapのみで提供される。

ValueT が構造体型の場合、 Map_insert() よりも速い。

int Map_insert_range ( Map self,
MapIterator  first,
MapIterator  last 
)

指定範囲の要素を挿入

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

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

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

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

MapIterator Map_erase ( Map self,
MapIterator  pos 
)

要素を削除

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

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

posMap_end() または Map_rend() でないこと。

MapIterator Map_erase_range ( Map self,
MapIterator  first,
MapIterator  last 
)

指定範囲の要素を削除

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

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

size_t Map_erase_key ( Map self,
KeyT  key 
)

指定キーの要素を削除

selfkey というキーの要素をすべて削除する。

引数:
self mapオブジェクト
key 削除する要素のキー
戻り値:
削除した数

void Map_clear ( Map self  ) 

全要素を削除

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

引数:
self mapオブジェクト

void Map_swap ( Map self,
Map x 
)

交換

selfx の内容を交換する。

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

size_t Map_count ( Map self,
KeyT  key 
)

指定キーの要素をカウント

引数:
self mapオブジェクト
key カウントする要素のキー
戻り値:
selfkey というキーの要素の数

MapIterator Map_find ( Map self,
KeyT  key 
)

指定キーの要素を検索

selfkey というキーの最初の要素を検索する。

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

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

MapIterator Map_lower_bound ( Map self,
KeyT  key 
)

最初の位置の検索

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

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

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

MapIterator Map_upper_bound ( Map self,
KeyT  key 
)

最後の位置の検索

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

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

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

void Map_equal_range ( Map self,
KeyT  key,
MapIterator first,
MapIterator last 
)

指定キーの要素の範囲を取得

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

last がNULLでないこと。

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


SourceForge.JP