コンテナ(STL)についての説明

導入

49代cashewです。プログラミング研究会に所属しています。いよいよ明日から授業が始まりますね。1年生が一番緊張すると思いますが2年生の僕もかなり緊張しています。

後で見返してみると雑な部分が多いですが我慢して読んで頂ければ幸いです。まず始めに新入生がミスに入ってからの流れについて説明させて頂きます。

プログラミング研究会(以下「プロ研」)では毎年新入生にブロック崩しを作ってもらうことになっています。プログラミング未経験者はさらに基礎の部分から説明があります。その講座が終わるとそれぞれ企画(早稲田祭などに向け本格的にゲームを作る)に入っていきます。

基礎的なことはブロック崩しで学ぶことが出来るので、それらの講座を学び終えた後C++やjavaを学ぶ人に向けてコンテナと言うものを説明したいと思います。

コンテナ(STL)というものは配列を使いやすくしたものと考えてもらって構いません。具体的には配列の長さを変えることが出来たり、配列のサイズを簡単に取得したり、要素を消したりC言語では作れるけれども難しかったことをいとも容易くに実現することが出来ます。

コラム:どの言語を学ぶかプログラミング言語は色々ありますが基本的に使っている人が多いものが良いと考えます。(他人と話しやすい。ネットで検索しやすい)また、ゲーム作りを念頭に考えるとオブジェクト指向をサポートしているものが良いです。(ゲームではクラスを多用します)もちろん使いたいライブラリが有るのであればその言語に合わせましょう。(DxLib&Cocos2d-x->C++,iPhone開発(ネイティブ)->Objective-C,Unity->Javascript又はC#) C言語よりもC++、C++よりもJava/C#のほうが高級(人間が自然に使いやすい)ということも覚えておくと良いかもしれません。

プログラミングを学ぶ順番について

プログラミングを学ぶおすすめの順番について説明しておきます。(C++中心で)

初歩的な部分(ブロック崩し講座内で説明のある部分)

C言語の部分(ザックリでごめんなさい。多すぎて列挙できません)
クラスについて(オブジェクト指向言語の中でもっとも重要な物!!!)
Dxライブラリの簡単な関数の説明

ブロック崩し講座ではオブジェクト指向の最も基礎的な部分について学びます。

自分で学ばなくてはならない基礎的な部分

この部分はブロック崩し講座では説明されませんがここを勉強しないとC++を使えるようになったとは言いにくいです。

コンソール入出力(初歩的だがゲーム制作では使わないので講座では学ばない)
値渡し/参照渡し(これが出来ないと関数を作っても思ったように動かないことがある)
命名規則(言語仕様ではないが命名規則はプログラミングを学ぶ上で重要)
コンストラクタ/デストラクタ
コンテナ(STL)(今回説明するところ)
C++での文字列の扱い(string)
クラスの継承(重要!)
ファイル読み書き(ストリーム)

基礎的ではない部分

テンプレート
アルゴリズム
実行時型情報(RTTI)
SFINAE(C++だけの仕様かも？)
...(続く)

C++やjavaの機能はこれだけでなく覚えきれないほど大量にあります。完全にマスターしたと言える人は(全国的に)相当少ないと思います。ゆっくり学んでいきましょう。(ミスの活動は交流会のようなものでプログラミングが出来るようになるためには活動外の時間にプログラミングの勉強をすることが必要です。)

C言語を勉強したことのない人は最初にC言語を学ぶことをお勧めします。C言語は現在出回っている言語の文法の基本となるものです。(もちろんC言語の文法を受け継いでいない言語も存在はします。) C言語を勉強し終えたらC++かJavaを学ぶ事をお勧めします。(JavaScriptもかなり人気があると感じるが残念ながらクラスをサポートしない) C++/Javaを使い始めると一番最初にクラスを学びます。クラスというものはザックリ言ってしまうと"物"を定義するための物です。ここの説明は長くなる&説明しにくいので他の人や講座に任せます。

STLとは何だ!?

前置きが長くなりましたがSTLを説明します。新入生用講座の知識が完全に身につくと次に使えるようになると便利です。まだプログラミングを始めたことがない人は講座を終えたあたりに思い出して読んで頂きたいです。STLというのはC++で配列の代わりとなるものです。STLが使えるようになると普通の配列をそこまで使わなくなったりします。もうちょっと詳しく言うと良く使うデータ構造をあらかじめ実装したものといえると思います。有名どころとしてはvector,list,mapなどがあります。STLというのはC++でのコンテナの名称ですが、JavaでもコンテナはあるのでJavaを使いたいという人でも大丈夫です。

ベクタとリスト(とdeque)

まずベクタとよばれるものから説明します。これは長さを変える事のできる配列(可変長配列という)です。C言語の配列だと一度サイズを決めてしまうとサイズを変更できませんでした。さらにそのサイズの大きさを取得するのは注意が必要だったりしました。この部分を改善したものがベクタです。

コラム C言語で似た機能を実装するにはmalloc,realloc,free,callocなどを使います。

Javaでは? ベクタはJavaではArrayListとして存在します。(リストという名前ですが一般的な意味としての”リスト”であってC++のリストの構造ではありません。C++のリストは”リンクリスト”と呼ばれています。) (リンク)リストはJavaではLinkedListという名前です。 dequeはそのままJavaでもDequeです。

ベクタの得意なことは

N番目の要素にアクセスすること
配列の最後に要素を追加すること

です。逆に苦手(遅い)なものは

末尾以外に要素を追加(挿入)すること
末尾以外の要素を削除すること

です。なぜかというと下の図を見てください。

配列を知っている人にはなめているようで申し訳ないのですがこれは配列の要素がどのようにメモリに配置されているかを表した図です。要素が順番に配置されている訳です。末尾の要素を追加するのは簡単です。後ろに一個増やせばいいからです。しかし途中に要素を入れる場合どうなるでしょう。 ImageOfVectorInsert 要素を入れようとしたところの後ろの要素が移動しています。この移動があるために途中の要素の追加や削除が遅いのです。

この途中への挿入・削除が遅いということが問題になる場合ベクタではなくListを使います。リストを図で表すと下のようになります。 ImageOfList 要素が順番通りになっていないことや、各要素が前と後ろの要素の位置を持っていることが重要です。このような構造になっていると要素の追加は簡単です。 ImageOfListInsert この図で赤くなっている部分を修正するだけで要素を追加できることがListの良い点なのです。しかし弱点が多くなります。

N番目の要素を取り出すのが遅い(わざわざ最初から辿るから)
要素数が少ないとベクタの方が速かったりする

ベクタもリストもデメリットとメリットがどっちもどっちだったりしますが、途中に挿入したりN番目の要素にアクセスしたりする場合はどうするかというとdeque(デック)を使います。(途中への挿入かつランダムアクセスがある場合dequeが良いという記事を見掛けたのですが実際にやってみたらベクタより遅くなってしまいました。)dequeは知名度が低いものの先頭はもちろん末尾への追加もvectorより速いので勧める人が多いです。dequeは内部的にはvectorとはかなり違いますが使うだけには先頭に要素を追加するのが速いか否かと考えてもらって構いません。

使い方に関してはここに書くと長くなるためググるか活動に来て先輩に聞いてください。

これらのことを実際に測ってみました。(もっと気になる人は調べると沢山情報が出てきます。) 以下の計測では各計測ごとに要素数を変化させています。ご注意ください。g++でコンパイルしたため他のライブラリの実装だと時間が変わる可能性があります。また、基本的に要素数が大きい場合について述べます。要素数が小さい場合大抵vectorとdequeが強くlistが弱いとの記事が多いと思います。（未検証)

末尾に追加

dequeがvectorより2倍ほど速くなっていますね。 listは末尾への追加の場合(他のSTLと比べて)とても遅くなっています。

ソース

STL	時間(ms)
vector	2054
deque	1162
list	7944

途中に追加

途中に追加した場合説明通りlistが圧倒的に速い結果となりました。意外とvectorとdequeを比べるとvectorが健闘していました。

ソース

STL	時間(ms)
vector	1907
deque	8742
list	7

参照

参照はあまり時間差は無さそうです。

ソース

STL	時間(ms)
vector	1164
deque	1217
list	1003

ソート

int型のデータを10000000個並び替えるソートはベクタが速い結果となりました。

ソース

STL	時間(ms)
vector	4322
deque	6051
list	10732

一方int型を1000個持つクラスを100000個並び替えるソートはこうなりました。

ソース

STL	時間(ms)
vector	470
deque	539
list	91

データのサイズが小さいならベクタ、大きいならリストが速くなるようです。

結論

ゲーム作りではlistはランダムアクセスができないことと要素数が小さい範囲ではそんなに速度にシビアになる必要がないためvectorかdequeを使うべきです。(配列の感覚だとvectorの方が近いのとdequeは情報があまりないのでどちらかと言えばvectorがお勧めです。)

mapとset(とunordered_mapとunordered_set)

mapについて

mapというのは連想配列と呼ばれるものです。連想配列は添字に任意の数字と文字列を使うことができるものです。たとえば今まではarray_obj[0]=12;といった使い方でしたが連想配列を使うとarray_obj["hogehoge"]=12;と書くことができます。 JavascriptやPHPでは良く使うのでJavaやC++を使ったことが無い人でも知ってる人は多いかもしれません。たとえばユーザーを管理するクラスを作ったとしてそれをベクタに追加していったとします。ユーザーがIDを持っていたとしてIDでユーザーを検索するとします。そのときベクタを使っていると最初から一個ずつIDを探さなくてはいけません。(ソートしていれば2分探索を使うことができますがユーザーを追加したときのコスト(かかる時間の事)が大きいです)しかし(IDをキーとした)連想配列を使うと2分探索により効率よく検索することができます。要するに何かを基準に検索する場合に便利な配列です。逆にこの様な使い方をする場合、簡単に作るにはmap(かunordered_map)で決まりです。

コラムこのmapは木構造を使ってかかれているのですが一部のC++erには不評でした。私に取っては十分速いのですがその人たちには遅かったのです。C++11という2011年で仕様が変わった時のC++では新たにunordered_mapという木構造を使わない連想配列が使われています。ソートされている必要が無い場合unordered_mapの方が速い事が多い様です。詳しくはググって下さい。

コラム mapなのですがキーが重複するものは追加出来ません。この様な場合multimapを使います。自分はまだmultimapを使う機会が無かったので使ったことがありません。詳しくはググって下さい。

setについて

setは集合を扱うためのSTLです。(これもmapと同様に木構造で実装されたsetとハッシュで実装されたunordered_setに分かれます) mapのキーの部分だけを取り出したものと考えてもらえば良さそうです。常に木構造を作るので意外と動きは遅いです。速い動きが必要なプログラミングコンテストなどでは素集合データ構造を使う場合Union-Findというアルゴリズムを使って下さい。普通に使う分には速いのでそこまでの心配はいりません。(setも複数の同じ値を格納するにはmultisetを利用します。多重集合というやつですね。)

Javaでは? 連想配列であるmap/unordered_mapはTreeMap/HashMapという名前でJavaに存在します。集合を扱うset/unordered_setはJavaではTreeSet/HashSetという名前でJavaに存在します。

その他STLについて

valarray

数値を格納するためのベクタを考えてもらって差し支えありません。すべての要素に適用する演算がとても楽になります。足し算、引き算は数学のベクトルと同じように扱うことができるので便利だと思います。

stack

スタックというデータ構造です。FILO/LIFOとか呼ばれる構造です。「スタック」と調べればわかりやすい説明が多くあると思うのでそちらをご覧下さい。有名なデータ構造です。

queue

キューというデータ構造です。LILO/FIFOとか呼ばれる構造です。「キュー」と調べればわかりやすい説明が多くあると思うのでそちらをご覧下さい。有名なデータ構造です。

priority_queue

queueに似ていますが要素が内部でソートされた状態になっていて先頭から取り出すと常に要素が最も小さいものから出てきます。結構使うらしいです。

bitset

ビット集合というものを扱うためのSTLです。使ったことが無いので良く分かりません。（すみません）

array

C++11(2011年に改訂されたC++)ではarrayというものがあります。arrayつまり「配列」という名前です。このSTLは普通の配列を扱いやすくしたものです。ベクタと同じくsize関数やイテレータを使うことができます。ソートや逆順にする際にベクタと同じ関数を使うことが出来ます。

Javaでは? arrayの機能はJavaでは標準の配列で間に合うと思います。 stackはJavaでもStackです。 queueはJavaではいくつか実装があるようです。調べて最も用途に合うものを使うと良いと思います。ただし、C++でもJavaでもわざわざスタックとキューを使わずにDequeを使うほうが良いと思います。

便利な関数群

さて、今までいろいろなSTLを紹介しましたがSTLはSTL自身だけでなく、その周辺の関数なども便利です。

include <algorithm>

としてアルゴリズムという名前のヘッダファイルをインクルードしてください。このヘッダファイルをインクルードすることで便利な関数群が使えるようになります。(このヘッダファイルに関数が宣言されている)

sort関数

algorithmヘッダのsort関数は様々なSTLをソートするための関数です。(リストはメンバ関数としてsort関数が存在します。) 例)

std::vector<int> vec;
vec.push_back(35);
vec.push_back(10);
vec.push_back(27);
std::sort(vec.begin(),vec.end());
std::cout<<vec[0]<<std::endl; //10が出力される
std::cout<<vec[1]<<std::endl; //27が出力される
std::cout<<vec[2]<<std::endl; //35が出力される

reverse関数

reverse関数はその名の通りSTLを逆順にするための関数です。sort関数とほとんど使い方は同じなので使い方は割愛します。

accumulate関数

accumulate関数は要素の合計を計算する関数です。 int sum=std::accumulate(vec.begin(),vec.end(),0); とすることでsumに合計値が代入されます。

for_each関数

今までは配列のすべての要素に何かをすると言ったときどうやっていたでしょうか。 1.原始的なやりかた

int intArray[10];//ここはvector、arrayでもOK
for(int i=0;i<10;i++){
    intArray[i]+=1;
}

2.STLらしいやりかた

std::array<int,10> intArray;//普通の配列は不可。STLはOK
for(auto it=intArray.begin();it!=intArray.end();it++){
    *it+=10;
}

3.C++11らしいやりかた(私はこれが一番好きな書き方)

int intArray[10];//ここはvector、array、listでもOK
for(auto &it:intArray){
    it+=10;
}

4.for_eachが登場してから好まれる書き方

std::array<int,10> intArray;//普通の配列は不可。STLはOK
std::for_each(intArray.begin(),intArray.end(),[](int &it){
    it+=10;
});

(修正:ソースに不備が有ったため修正いたしました。)

これ以外にもremove_ifやfind_if関数など便利な関数がありますが割愛させて頂きます。知りたかったら活動に来てくださいね。新入生をお待ちしています。

まとめ

とにかくSTLを使ったことが無い人はベクタから使い始めましょう。配列で出来なかった手の届かないかゆいところに手が届くようになります。ベクタを使いこなすことが出来るようになったら他のSTLを使うようにすれば良いと思います。

MIS.W 公式ブログ

早稲田大学公認、情報系創作サークル「早稲田大学経営情報学会」（MIS.W）の公式ブログです！

コンテナ(STL)について【アドベントカレンダー7日目】