データ構造のmapとは？

mapとはなんでしょうか？英語の意味は写像ですが、
"キーと値が一対一で結びついているもの"で良いでしょうか？
set,table,listの違いについても教えてください。

No.2 ベストアンサー 回答者： Tacosan 回答日時： 2008/08/04 15:21

まあ構造としては「木はグラフの特殊なもの」「パスは木の特殊なもの」なので

グラフ構造 > 木構造 > リスト構造
ではありますが, 普通はそれぞれ適切なものを使うと思います. リストを表現するときにグラフ構造を使うことは可能かもしれないけど, かなり無駄な感じ.

この回答へのお礼

回答ありがとうございます。
なんかちゃんと定義されていないのって気持ち悪いんですよねぇ。
スッキリするまでグラフ理論を勉強しようと思います。
ありがとうございました。

お礼日時：2008/08/09 20:09

No.1 回答者： castable 回答日時： 2008/07/26 02:57

・map

「キーと値のペア」の集まりで、キーに対して値が一意に定まるもの（キーの重複が許されないもの）。
値の重複は許されるので、一対一だけでなく多対1の関係も含みます。

・set
値の集まりで、値の重複が許されないもの。
mapにおけるキーと値をひとかたまりとみなせば、同じようなもの、と考えることもできると思います。

数学で言うところの集合→set、写像→mapでよいと思います。

・table/list
mapとsetが論理的で、機能に言及した分類（どのような制約があるか等）であることに比較すると、table/listは、実装方法による分類というイメージになります。
キーや値の重複を許す／許さないといった点には言及せず、計算コスト（特定の値を持つ要素を見つけるのにどれだけ時間がかかるか等）が（データ構造の）利用者から見えるものとして定められます。

すごく実装を意識して説明すると、
・table
値の集まりで、値が連続的な領域に配置されているもの。
（連続的な領域に配置されていて、位置が既知のため）任意の値にダイレクトにアクセスできる。

映画館の座席の番号とか、マンションの部屋番号とか、番号が分かれば位置が直接特定できるようなイメージです。

・list
値(要素)の集まりで、ある要素からは、その近隣（次、とか前とか）の要素にしかアクセスできない。
一般に、鎖状（１次元）の構造を成す。

よいイメージが思いつきませんが。。。
車内に路線図のない路線バスに乗って「次は○○です」といわれるのを聞きながら目的地に到達するような感じです。。分かりづらいですね^^;;

参考までに、、
機能的な面に着目したデータ構造というと、他にはキューやスタックなどがあります。
実装、構造に着目したデータ構造というと、他には木(tree)構造やグラフがあります。

C++を勉強中でしたら、標準テンプレートライブラリ(STL)の書籍等で分かりやすく説明されているのではと思います。

この回答への補足

もう一つ疑問なのですが、
リスト構造はツリー構造の一種なのでしょうか？
○<->○<->○<->○
分類すると
グラフ　> ツリー構造 > リスト構造
なのでしょうか？

回答して頂いて大変あつかましいのですが、宜しくお願いします。

補足日時：2008/07/27 14:28

この回答へのお礼

詳しい回答ありがとうございます。
すっきりしました。

お礼日時：2008/07/27 08:44