#はじめに
初心者の初心者による初心者のためのどうとやらです。
それぞれ通常の配列との違いをまとめたのち、３つの違いをまとめます。
基本的にお堅いことは書きません。
感覚的なものをつかんでいただければ大喜びです。
#目次
- なぜこの３つなのか
- vectorとは
- listとは
- mapとは
- vectorとlistとmapの違い
- 追加速度が違う理由
- 参照速度が違う理由
- まとめ
#なぜこの３つなのか
「この３種類を知っていれば、あらかたのプログラムが組めた。」
という初心者なりの経験則です。
#vectorとは
要素の追加や参照方法などは通常の配列と大して変わりません。
では何が通常と違うか。
通常、配列というものは要素数を最初に決めておかなければなりません。
ですがvector君は、後から「やっぱ要素数チェンジで！」と言っても対応してくれます。
いつも使ってる配列が便利になったやつという認識で大丈夫だと思います。
std::vector<int> vec(3);//int型のvector配列を初期要素数３で宣言。
vec[0] = 0;
vec[1] = 10;
vec[2] = 20;
vec.resize(5);//配列の要素数を５に拡張。
vec[3] = 30;
vec[4] = 40;
ちなみにresizeという物を書かずにそのまま要素番号３に値を追加するとしっかりエラーが出てきます。
###【追記】「エラーが出る」という表現の訂正
エラーが出る事は稀で、黙ってその場所のメモリを壊してしまう場合のが多いそうです。
明確に「ここが違うよ」と教えてくれない場合のが多いので、vectorなど使っていてなにか挙動がおかしいと
思った場合は、要素数がオーバーしていないかを確かめてみましょう。
#listとは
listも要素数を後から変更する事ができます。
ですが通常の配列と比べ、追加・参照の方法がめちゃくちゃ違います。
まず「要素番号を指定してその中身をいじる…」という行為ができません。
（もし仮に「lis[1] = 100;」など書いた場合エラーが出ます。）
そして、基本的にlistを攻略しようとするとイテレーターという強敵に確実に遭遇します。
この強敵のせいでlistを扱うのは３つのうち一番難しいです。
std::list<int> lis;//int型のlist配列を宣言。
lis.push_back(0);
lis.push_back(10);
lis.push_back(20);
この配列の中身は先頭から0,10,20になります。
###イテレーターとは
「イテレーターはイテレーターだよ。」と投げ捨てられるほど全く新しい概念です。
ですが、僕ら初心者が知っている知識で感覚的に近いものはポインターです。
int num = 0;
std::list<int>::iterator ite;
for (ite = lis.begin(); ite != lis.end(); ite++) {
num += *ite;
}
これはlisというlist配列の全要素の合計を計算するプログラムです。
「int型のlist」という型のイテレーターを宣言。
その後、lisという配列の先頭要素のデータをiteに代入。
lis配列の最後の要素になるまでイテレーターを一つずつ足して進める。
そして、イテレーターの中身をnumに足す。といった処理です。
#mapとは
簡単に言えば、要素の指定方法がめちゃくちゃ違うものです。
通常の配列は要素番号を指定する場合「array[0] = 0;」のように[ ]の中に整数値を入れて指定します。
ですがmapは[ ]に入れるモノがなんでもよくなります。
極論、array["いちばんめ"]=1;という書き方ができるようになります。
なのでとにかく文字列(string型など)と相性がいいです。（個人の感想です。）
std::map<std::string, int>map;//string型で指定する,中身がintのmap配列を宣言。
map["メロンパン"] = 120;
map["コッペパン"] = 80;
map["アンパン"] = 100;
int a = map["コッペパン"];//aに80という値が代入される。
#vectorとlistとmapの違い
ずばり違うところは
- 参照の方法
- 追加の処理速度
- 参照の処理速度
です。
| 項目 | vector | list | map |
|---|---|---|---|
| 参照方法 | 要素番号で指定 | イテレーターを使用 | 要素番号などで指定 |
| 追加速度 | 遅い | 速い | 速い |
| 参照速度 | 速い | 遅い | 速い |
| 使用難易度 | 簡単 | 難しい | 普通 |
※最後の使用難易度に関しては個人的な感想です。
※細かい話をすると、追加する場所や参照する場所によって速度は変わります。
なのでこの表が常に絶対正しいという訳ではありません。
###【追記】ここでいう「vectorの追加が遅い」について
今回「遅くなる追加」として扱っている処理は、
実行中に追加するメモリの余裕がなくなり、コピーをして移動する場合の処理です。
純粋にコピーなどが発生しない追加の場合は、vectorも速いとのことです。
その他追加する場所（先頭なのか、真ん中なのかなど）によっても速度は大きく変わるようです。
あいまいな表現で申し訳ありませんでした。
※「コピーして移動」については「追加速度が違う理由」の部分に少し詳しく書いてあります。
【追記の追記】
vectorとlistの追加処理の時間差について軽く実験し、まとめてみました。
よければこちらもご覧ください。
https://qiita.com/mame416/items/2eaedd9e8de372a74b0c
#追加速度が違う理由
mapの追加方法はlistと少し似ていますが、vectorとlistではかなり違います。
なのでvectorとlistを比べていきます。
前半はメモリなど小難しい説明になりますが、後半は例え話で説明します。
###メモリのお話
vectorの場合、メモリ上にデータが全て連なって保存されています。
そのため新しくデータを追加する場合、
今ある配列データの真後ろに隣接して追加しなければなりません。
ですが様々な処理の途中で追加をするので、今追加しようとした場所に
すでに別のデータが存在する場合があります。この場合、
配列の全データ＋追加分が収まるスペースのあるメモリの場所を探し、
配列の全データをごっそり移動させます。
空いている場所を探すのにも時間がかかりますが、単純に
全データを移動させるという処理が果てしなく重たいです。
ですがlistの場合、保存されているデータはすべて独立しています。
そんな状態なのになぜlistが配列と呼ばれるかというと、
それぞれの要素データが、次の要素データのメモリ場所を覚えているからです。
つまり、どれだけ要素が追加されようと、毎回最後の要素データに追加されるデータの場所を
覚えておいてもらえばいいので全員が移動する必要が無いということになります。
このことからvectorは追加に時間がかかり、
listはそこまで時間はかからないという結論になります。
###例え話
あるところに男子５人組の仲良しグループ（ザ・ベクターグループ）と
女子３人組の仲良しチーム（チーム・リスト）がいました。
男子５人はすぐ集まって遊べるように、全員が同じマンションに住んでおり、
女子３人はそれぞれ別々の一軒家に住んでいました。
ある時、１人の男子転校生がやってきました。
彼はすぐ５人組と仲良くなり、グループに入ることになりました。
そして５人組と同じマンションに住もうと思いましたが、
ちょうど満室でそのマンションには住めないとのことです。
そして同時にもう１人、女子転校生がやってきました。
彼女もすぐ３人組と仲良くなり、チームに入ることになりました。
学区内にちょうど空いている一軒家があるらしく、
彼女はそこに住むそうです。
この結果を受け、グループ（チーム）のリーダーはこう言ったそうです。
ベクター「よし！全員で引っ越しだ！」
リスト「また住所教えてね～。」
このくらい追加処理の重たさが違うという事です。
#参照速度が違う理由
今回もvectorとlistで比較していきます。
（mapの参照方法は通常の配列とほぼ同じと書きましたが、内部的な動きが全く違うようです。）
（「木構造」というワードで検索してみると分かるかもしれません。今回は割愛します。）
###参照方法の違い
通常の配列で、それぞれの要素にアクセスする際、内部的には
配列の先頭から、何データ分先にあるかという見方をしています。
例えばint型の配列があったとします。その配列の３番目の要素にアクセスしたい場合は
配列の先頭アドレス＋４バイト×３の場所にアクセスする、という動き方をします。
（この仕組みのせいで配列は０から始まるのです。）
vectorもこれと同じ動き方なのでちゃちゃっとバイト数を計算してその場所を見に行けば
すぐ中身を参照することができます。
しかしlistはそうはいきません。
上の「追加速度が違う理由」の所に書きましたが、listはデータが繫がっておらず独立しています。
この仕様により、先頭アドレスから計算して場所を特定することができません。
そのためどうするか。先頭から１つずつ探っていくしかありません。
仮に100番目のデータにアクセスしたい場合はイテレーターを100回動かすしかありません。
###vectorとlistのどちらを使うか迷ったら
それぞれの要素に別々にアクセスする場合はvector。
先頭から最後の要素を全て順番にアクセスする場合はlist。
…というよりも別々にアクセスする可能性がある場合はlistを使わない。
という意識で良いと思います。
#まとめ
特徴などをかなり簡単に雑にまとめてみました。
ですが一概にこれが最強！というものはありません。
配列のサイズであったり、処理の優先度、プログラムの用途などで変わると思います。
ですが、勉強するならどの順番でいくかと聞かれれば
自分はvector→map→listの順番で勉強すると思います。
最後まで読んでいただき、ありがとうございました。