コンテナーの基本あれそれ

[arisin]

全てにintを放り込むことができ、＜中身の型＞定義できる。

・std::stack 　スタックデータ構造を実現するコンテナー ・std::queue 　キューデータを実現するコンテナー

この２つはFIFOとFILOの内部データ構造を実現するので、入れる順序と取り出す順序に特徴がある。 ＊一番手前または一番先頭に入れたものにしかアクセス出来ない。

・std::list 　双方向連結リストを実現するコンテナー

要素を前後の要素のアドレスを示すポインターとともに保持するので、前・後ろ・任意の中間地点への挿入が容易。ただし、N番目の要素を取り出したい時、最初のやつの次の次のN番目の・・・と辿らなくてはならず、ランダムアクセス性能が悪い。

・std::forward_list 　単方向（前方）連結リストを実現するコンテナー

・std::array 　単なる配列を実現するコンテナー

単なる配列だが、ランダムアクセスという強い武器がある。 arrayは作る段階で最初からサイズを決める。決まったサイズのぶんだけのメモリーを確保し、隣同士で連速したメモリー領域N個分作る。 なので、N番目の要素はX、M番目はYと、コンパイルした段階でどこのメモリーに入っているか決まるため、アクセスが高速。 ただし、要素数を変えることができず挿入もできない。

・std::vector 　単なる配列だが、実行中に要素数を任意に可変できるコンテナー

vecotrは、arrayと基本的には同じだが、要素数を任意に可変できる。 予めN個分の枠を裏でこっそり作り、基本的にはarrayのように高速にランダムアクセスできる。 さらに、要素を追加する時に、予め作っておいた領域が足りなくなるときには、裏でこっそり新しく倍容量の領域を確保し、いままでの領域のデータを全部そっちにコピーします。表面上は、vectorは容量がスムーズに可変できるarrayというすごく便利なもの。 でも、もちろんこの裏で新たに・・・というのはとても重い処理なのでvectorを使う時には予め、これからN個いれるから用意する v.reserve(100); とかできる機能もある。

通常はstd::vectorを使っておく。

使い方例サンプル：http://melpon.org/wandbox/permlink/0cFw5IYi9om2hkBG

[usagi]

おまけ

全てにintを放り込むことができ、＜中身の型＞定義できる。

これを実現する仕組みが「テンプレート」です。JavaやC#など近年この機能を取り込んだ言語では「ジェネリスク」と呼ばれる機能です。

簡単な、テンプレート関数の例を書きましたので参考にどうぞ: http://melpon.org/wandbox/permlink/D2sqhijNr5ZL9nV2

テンプレート関数ははじめは標準ライブラリー等々にあるものを上手にすらすらと利用できるようになればそれで良いでしょう。自分でテンプレート関数や、この後で紹介するテンプレートクラスを自在に作って楽しめるようになるのはまだもう少し先の事で大丈夫です。

[usagi]

おまけ2: テンプレートクラス

http://melpon.org/wandbox/permlink/Sj24YzsSbPicHBYh

自作でstd::vectorのもどき品の型を作っちゃう事も案外簡単。（実物のstd::vectorはもっと多機能で洗煉されているのだけど、それはまたおいおい勉強していけばよいのです。）

[usagi]

おまけ3: std::array と C配列（＝ネイティブ配列）、ついで程度にstd::vectorとCポインター配列

http://melpon.org/wandbox/permlink/bVy6kiSZ2Xog5OgR

[usagi]

おまけ4: C++標準ライブラリ−のコンテナーとその仲間たち

• 配列型: ランダムアクセス性能最高
  • array (あれい): 要素数固定
  • vector (べくたー): 要素数可変、要素列の終端への要素追加が可能
  • deque (でっく): 要素数可変、要素列の前端と終端の両方への要素追加が可能
• 連結リスト型: 内挿（要素集合の途中への挿入）性能最高
  • list (りすと): 双方向連結リスト
  • forward_list (ふぉわーどりすと): 前方連結リスト（双方向より省メモリー）
• FIFO/LIFO型: より単純で原始的な要素数可変のデータ構造
  • stack (すたっく): 箱にものつめたら上からとりだすFIFO
  • queue (きゅー): 筒に後ろからものつめて前からとりだすLIFO
• 二分木辞書型: 要素からの検索性能最高。二分木型。挿入コストと二分木の偏りに弱い。
  • map (まっぷ): 2つの型とその要素のペア（key&value）を1つの要素として管理。keyによる二分木構造で要素追加時に既に二分木構造によってソートされた位置に挿入される。よってkeyによる要素検索速度が単純な配列よりも速い。
  • set (せっと): 1つの型の要素を管理。二分木構造で要素追加時に二分木構造によりソート。
  • multimap (まるちまっぷ): mapでkeyが重複しても良い様に工夫したもの。
  • multiset (まるちせっと): setで同じ要素が重複しても良い様に工夫したもの。
• ハッシュ辞書型: 要素からの検索性能最高。ハッシュ型。メモリー消費が二分木より大きくなるがより高速な状況が多い。
  • unordered_map (あんおーだーどまっぷ): keyをハッシュ関数を利用してバケット的に管理するハッシュマップ型の辞書構造。検索は高速、但しkeyそのものでソートされているのではなくkeyのハッシュ値でソートされているため、keyによるソートなどはこのデータ構造では期待してはいけない。
  • unordered_set (あんおーだーどせっと): unordered_mapの要素のみ版。
  • unordered_multimap (あんおーだーどまるちまっぷ): unordered_mapのkey重複可能版。
  • unordered_multiset (あんおーだーどまるちせっと): unordered_setの要素重複可能版。

※本来はmap/set系は実装が二分木とはC++言語仕様書では規定されていません。unordered系も実装がハッシュとは規定されていません。同様の検索性能を発揮するデータ構造としてはスキップリストなどもあります。ただ、現実として実際にはmap/set系は二分木、unordered系はハッシュと考えて差し支えありません。

これで全部です。そして、標準ライブラリ−またはその互換をうたうコンテナーを使うと何が便利かというと、

#include <algorithm>

この一言によって、コンテナーという「データの集合」に対して柔軟にアルゴリズムを適用できるようになります。まあ、それはまたの機会に。

[usagi]

閉じます。