## 9.1 map データの抽象化

map は、vector や deque と同様に、インデックス付きのデータ構造です。しかし、map は 2 つの重要な点で vector や deque とは異なります。

- まず、map では、インデックス値やキー値を `integer` とする必要がなく、任意の順序付きデータ型とすることができる点です。たとえば、map は実数または文字列でインデックスを作成することができます。また、比較演算子を定義できる任意のデータ型をキーとして使用することができます。vector や deque を使用する場合と同様に、添字演算子または他の手法で要素にアクセスすることができます。

- 次に、map が順序付きデータ構造である点です。これは、要素がキー値で判定された順序のシーケンスで維持されることを意味します。map が値を順序通りに維持するため、既定のキーによって指定された要素をすばやく検出することができます。検索時間は対数的に増加します。list と同様に、map にもサイズの制限はなく、新しい要素の追加や削除に応じて、拡張されたり縮小されたりします。大部分で、map はコレクションを維持する set であると単純に認識することができます。

他のプログラミング言語では、map に似たデータ構造が、辞書、表、または連想配列と呼ばれることがあります。標準 C++ ライブラリでは、2 種類の map があります。

- map データ構造は、一意のキーを要求します。つまり、キー要素とそれに対応する値が 1 対 1 で関連付けられています。map では、既存のキーを使用する新しい値の挿入は無視されます。

- multimap は、複数の異なるエントリに同じキーでインデックスが作成されることを許可します。

このデータ構造は両方とも、挿入、削除、アクセスの各演算を相対的に高速に行い、実行時間は要素数に対し対数的に増加します。pair データ型については、8.2.3 節の挿入の説明を参照してください。

### 9.1.1 インクルードファイル

map または multimap を使用する場合は、必ず `map` ヘッダーファイルをインクルードする必要があります。

    # include <map>

Copyright (c) 1998, Rogue Wave Software, Inc.
このマニュアルに関する誤りのご指摘やご質問は、電子メールにてお送りください。
OEM リリース, 1998 年 6 月