C++ STLメモ3

listとmapについて

まぁ,この2つは用途が全然違うのだが,一緒に解説。


#include <list>

C++ STLメモ2に解説したdequeとvectorナのですが,
dequeにあって,vectorにない機能が1つあります。
insertという機能です。これは要素の途中にデータを
挿入するという機能です。

しかし,よく挿入する場合は,dequeよりもlistの方が
良いでしょう。

データ構造は,双方向連結リストです。簡単にいうと,
芋づる式のデータ構造で,次の要素と前の要素の場所がメモリ上で連続しておらず,
各要素は前後の要素のメモリ上の場所情報を持っている構造なため,
ランダムアクセス(各要素に直でアクセスする)は出来ませんが,
データ構造上,追加削除には強いです。

検索にはもっとも向いていません。
(先頭から1つづつ見て判別する「線形探索」しかできないため・・・。)

各要素のアクセスには,iterator (イテレーター)というのを使わなければ
なりません。反復子といわれるもので,for文で使えば,
各要素を先頭から見ていくのに使えます。

他にもデータの検索の機能であるfindの戻り値などで使われています。
これは,STLのほとんどの型ごとに用意されています。

型名がiteratorのものが多数出てきますが,別の型のことが多いです。

ただ,dequeのitratorとvectorのiteartorとlistのiteratorには互換性があり,
これを活用すれば,データ構造とアルゴリズムの分離というのがある程度できます。

#include <iostream>
#include <list>

using namespace std;

int main()
{
  list<int> datas;

  datas.push_back(5); // この使い方は,vector, dequeと同じ
  datas.push_back(3);
  datas.push_back(4);
  datas.push_back(2);

// 各要素にアクセスするには,イテレーターを使うのが基本になります。
  list<int>::iteartor i;
  for(i = datas.begin(); != datas.end(); i ++) {
    cout << *i << endl; // ポインタ風にアクセスできます。
  }

  return 0;
}





#include <map>

listみたいな性質にランダムアクセスをしたい場合は,mapを使うとよいでしょう。
正確にはランダムアクセスではないですが,データ構造自体に
二分探索という検索機能が付いているので,目的のデータを取り出すのは速い。
listみたいに,途中のデータの追加削除にも強い。

mapの正確なデータ構造は「赤黒木」というもので,「二分探索木」の改良型です。

単純な二分探索木だと,追加するデータが連続のときは,内部構造は,
ほとんどlistと同じになってしまい,二分探索木の高速検索機能が使えない。
なので,赤黒木という改良型を使っています。

mapの中にはハッシュを使った,ハッシュマップというのもあります。
これはならば,通常のmapよりもさらに高速な検索が出来ます。
STLのバージョンや作成元によってはこれが含まれている場合があります。

#include <iostream>
#include <map>
#include <string>

using namespace std;

int main()
{
  map<int, int> a; // 一つ目のintが要素参照用のキーの型,2つめが保持する各要素が保持する値の型
  map<string, int> b;
  map<string, string> c;

  a[5] = 10; // 普通の配列のように使えます。存在しない要素にアクセスすると,要素が自動的に追加されます!
  b["abc"] = 20; // 要素のキーはstring型を使えば,まさに連想配列
  d["xyz"] = "abc"; // ここまでくると,Perl並のコードが書けます。

  cout << a[5] << endl;
  cout << b["abc"] << endl;
  cout << a["xyz"] << endl;

  return 0;
}

こんな風に,プログラミングがどんどん簡単になります!
活用されてはいかがでしょうか?

この記事へのコメント

この記事へのトラックバック