配列よりSTL

複数のデータをまとめて扱うような場合、何でもかんでも配列を使ってやろうとしていないでしょうか?

連結リストなどを自分でコーディングしていないでしょうか?

C++ではこういった用途向けのライブラリであるSTL(Standard Template Library)とその周辺のテンプレートクラスが標準化されているので、ほぼ全ての場合で配列を使ったり自分でコーディングするよりもいい選択肢となります。

ここではSTLの中で配列の代替として使用できる動的配列vectorと連結リストlistの紹介をします。

目次

STLの概要

STLはデータを格納するコンテナと、その要素にアクセスするためのイテレータ、コンテナに対する処理であるアルゴリズム、アルゴリズムの詳細な動作を決定するファンクタ(関数オブジェクト)からなります。

STLはデータ構造とアルゴリズムを分離したライブラリなのですが、データ構造の部分のみをとっても強力なので、まずはSTLでデータ構造を担当するコンテナとイテレータについての説明をします。

STLはstd名前空間に含まれます。コンテナを使うためのヘッダは以下の通りです。

動的配列(vector)

動的配列として使用できるvectorはvectorヘッダをインクルードすることで使用できます。

言語付属の配列は一度サイズを決定してしまうとサイズを拡張するためには新しい領域を確保し、そこにコピーし、古い領域を破棄するといった面倒な作業が必要ですが、vectorを使用することでそういった面倒から解放されます。

しかもテンプレートとinline関数を使用することで通常の配列と同等の効率を誇りますので、配列の代替としても使用できます。

使い方は簡単で、言語付属の配列と同じような使い方が可能です。

コンストラクタ

vectorにはデフォルトコンストラクタ、コピーコンストラクタ以外にサイズを指定するコンストラクタがよく使用されます。

サイズを拡張する際には先ほど言ったように確保、コピー、破棄といった処理が行われますので、要素の最大数が分かっているような場合にはサイズを指定しておくことで拡張を防ぎ、速度の低下を防ぐことが出来ます。

#include <vector>

int main() {
    using std::vector;
    vector<int> test1;          // デフォルトコンストラクタを使用
    vector<int> test2 = test1;  // コピーコンストラクタ使用
    vector<int> ary(10);        // int ary[10]の代替
}

テンプレートを使用しているので、ユーザー定義のクラスや構造体にも対応しています。

vector<vector<Hoge> >のようにすることで2次元配列のような使い方も可能です。

サイズ

vectorでは現在の要素数や許容量を得たり、要素数や許容量を変更することが可能です。

要素数は格納されているデータの個数を表し、許容量は確保した領域で何個のデータを格納できるか(領域を拡張しないでどれだけ要素数を増やせるか)を表します。

よって、要素数≦許容量となります。

関数名宣言説明
sizesize_type size() const;要素数を得る関数
capacitysize_type capacity() const;許容量を得る関数
emptybool empty() const;空かどうかを返す関数
resizevoid resize(size_type newSize, Type initValue = Type());要素数をnewSizeに変更する関数 追加された要素はinitValueで初期化される
reservevoid reserve(size_type newSize);許容量をnewSizeに変更する関数

これ以外にmax_size関数がありますが、使用することは無いでしょう。

resize関数で変更するのはsize関数で返ってくる値、reserve関数で変更するのはcapacity関数で返ってくる値です。

ちなみにこれらの関数で現在の値よりも小さい値を指定した場合、resize関数では要素数(size関数で返る値)は変りますが、許容量(capacity関数で返る値)は変らず、reserve関数の場合は何も起きません。

つまり、一度確保した領域は解放されません。

要素へのアクセス

vectorの各要素へのアクセスにはat関数かoperator[ ]を使用します。

現在の要素数を超えた要素数を指定すると、at関数ではout_of_range例外を投げますが、operator[ ]を使用した場合は不定な値が返ります。

例外はここでは説明しませんが、ここではそのようなアクセスはしませんのでどちらを使っても同じ動作となります。

#include <vector>
#include <iostream>

void printAll(const std::vector<int>&);

int main() {
    using std::vector;
    vector<int> ary(10);
    
    ary[0]      = 1;    // 配列のような使用が可能
    ary.at(1)   = 2;    // ary[1] = 2とほぼ等価
    printAll(ary);
    
    ary.resize(2);      // 要素数を2に減らす
    printAll(ary);
    
    ary.reserve(20);    // 許容量を20に増やす
    printAll(ary);
    
    ary.resize(5, 3);   // 要素数を5に増やし、3で初期化
    printAll(ary);
}

void printAll(const std::vector<int>& ary) {
    using std::cout; using std::endl;
    cout << "要素数[ " << ary.size() << " ]" << endl;
    cout << "許容量[ " << ary.capacity() << " ]" << endl;
    cout << "要素[ ";
    // 配列と同じようなループが可能
    for (unsigned int i = 0; i < ary.size(); ++i)
        cout << ary[i] << " ";
    cout << "]" << endl << endl;
}

at関数、operator[ ]以外にもfront関数とback関数というものもあります。

最後尾に追加・最後尾を削除

シーケンス(順列)コンテナと呼ばれるコンテナ(vector、list、deque)では最後の要素の次に要素を追加したり、最後の要素を削除したりする作業が多いためそれ専用の関数が用意されています。

それがpush_back関数とpop_back関数です。

関数名宣言説明
push_backvoid push_back(const Type& value);最後尾にvalueを追加(要素数+1) する関数
pop_backvoid pop_back();最後尾の要素を削除する関数

push_back関数を使用すると要素数や許容量を意識する必要はなく、足りなくなったら自動的にこれらの拡張を行います。

ちなみにpopなのに戻り値がvoidなのは、関数はただ1つの処理をすべきというプログラムの作法があるからです。

普通popという名前を聞くと「取り出し」て「削除」するという2つの動作を想像するでしょうが、C++の標準ライブラリではこの処理を行うのに2つの関数を使うようにしたのです。

int main() {
    using std::vector;
    vector<int> ary;
    
    printAll(ary);
    
    ary.push_back(10);  // 要素数は0だが、push_backなら自動的に拡張してくれる
    printAll(ary);
    
    ary.push_back(20);
    printAll(ary);
}

全削除

全要素を削除するにはclear関数を使用します。

これを使用すると要素数は0になりますが、許容量は変化しません。

数値配列

vectorのパラメータが以下の条件を満たす場合、valarrayクラスを使用したほうが効率がよくなります。

ちなみにvalarrayはC++の標準ライブラリに含まれていますが、STLには含まれていません。

最後の2項目はまとめると以下のようになります。

T t, t = v            と T t(v)       が同じ意味となる
new (p) T(), *p = v   と new (p) T(v) が同じ意味となる
p->~T(), new (p) T(v) と *p = v       が同じ意味となる

詳しくは標準 C++ ライブラリ・ユーザーズガイドを参照してください(丸投げ)。

イテレータ

イテレータは日本語で反復子とも記述されることがありますが、普通イテレータといいます。本やサイトによっては反復子といった表記を好んで使うところもあるかもしれないので、一応頭の片隅に置いておいてください。

イテレータはコンテナに対して配列のポインタのように振る舞います。

つまり、単項*演算子によって現在指している要素にアクセスでき、++演算子によって次の要素をさすようになります。

この特徴を抽象化したものがイテレータです。

イテレータを使用すると、連結リストや動的配列といったコンテナを区別することなくコンテナの各要素に配列のようにアクセスできるようになります。

イテレータには以下に示すように5つの種類があり、これによって「持っている機能」と、「どのように使われるのか(どんなデータが渡せるのか、と等価)」 が分かります。

実際にはイテレータタグと呼ばれるクラス存在し、イテレータの種類を表します。

InputIterator

InputIteratorはコンテナの各要素の値を取得するための最も単純なイテレータです。

値を設定するためには使用できません。

使用可能な演算子は以下の通りです。

演算子機能
++イテレータが次の要素を指すように変更する
==左辺と右辺のイテレータが等値ならtrueと評価される
!=左辺と右辺のイテレータが等値でないならtrueと評価される
*イテレータが指す要素を取得する(書き込みはしない)
->イテレータが指す要素のメンバを呼び出す

これらの特徴から、このイテレータはconstで修飾された型を扱える、ということが分かります。

これが「どのように使われるのか(どんなデータが渡せるのか)」が分かるということです。

OutputIterator

OutputIteratorはコンテナの各要素の値を設定するための最も単純なイテレータです。

値を取得するためには使用できません。

使用可能な演算子は以下の通りです。

演算子機能
++イテレータが次の要素を指すようにする
*イテレータが指す要素を取得する(書き込みのみ)

ForwardIterator

ForwardIteratorはInputIteratorとOutputIteratorの操作が全て可能なイテレータです。

BidirectionalIterator

ForwardIteratorの操作に加え、後退も出来るイテレータです。

後で説明するlistはこのタイプのイテレータを提供します。

演算子機能
--イテレータが前の要素を指すように変更する

RandomAccessIterator

BidirectionalIteratorの操作に加え、各要素にランダムアクセスや順序比較が可能なイテレータです。

演算子機能
[ ]添え字によって要素へアクセスする
+=イテレータを指定分進める
-=イテレータを指定分後退させる
+イテレータを指定分進めたイテレータを返す
-イテレータを指定分後退させたイテレータを返す
<左辺のイテレータの指す要素が右辺のイテレータのそれより前の要素を指す場合trueと評価される
<=左辺のイテレータの指す要素が右辺のイテレータのそれと同じか前の要素を指す場合trueと評価される
>左辺のイテレータの指す要素が右辺のイテレータのそれより後の要素を指す場合trueと評価される
>=左辺のイテレータの指す要素が右辺のイテレータのそれと同じか後の要素を指す場合trueと評価される

配列のポインタ

配列のポインタはRandomAccessIteratorの操作を全て備えるため、イテレータとして使用できます。

つまり、イテレータを取る関数には配列のポインタを渡すことが出来るため、配列に対してもコンテナに適用できる関数が使用できます。

使用例

イテレータのvectorでの使用例です。

#include <vector>
#include <iostream>

int main() {
    using namespace std;
    typedef vector<int>::iterator v_itr;
    
    // 配列とポインタを使用したバージョン
    int realAry[] = { 2, 0, 0, 0, 3, 1, 0, 0, 5, 0 };
    int size = sizeof(realAry) / sizeof(realAry[0]);
    
    // 配列とポインタを使用して全要素を出力
    for (int* i = realAry; i != realAry + size; ++i)
        cout << *i << " ";
    cout << endl;
    
    // vectorとイテレータを使用したバージョン
    vector<int> ary(realAry, realAry + size);   // イテレータを使用したコンストラクタ
    
    // vectorとイテレータを使用して全要素を出力
    // begin()は先頭要素を指すイテレータを、
    // end()は最終要素の"次"を指すイテレータを取得する関数
    for (v_itr itr = ary.begin(); itr != ary.end(); ++itr)
        cout << *itr << " ";    // イテレータは配列のポインタと同じように使用できる
    cout << endl;
}

コメントにも書きましたが、end関数は最後の要素の次の要素を指すイテレータを返します。

よって itr != ary.end() のように単純な比較が出来るのです。

もしこれが最後の要素を指すイテレータを返すようだと、itr != --(ary.end()) とでもしなければなりません。

これは分かりにくいですよね(しかも意味もなくBidirectionalIteratorを要求してしまう)。

つまり *(ary.begin()) は意味がありますが、*(ary.end()) には意味がないということでもあります。

これをSTLではよく数学的な表記を用いて [begin, end) と表します。beginは含めるがendは含めない、ということですね。

双方向連結リスト(list)

双方向連結リストとして利用できるlistはlistヘッダをインクルードすることで使用できます。

自分で双方向連結リストを実装するのはかなり面倒ですし、バグを埋め込まずに効率よく実装するのはさらに大変です。

しかし、STLには双方向連結リストも実装されているので、これを使うことによって労力を使わずに効率的な双方向連結リストを使用することが出来ます。

「自分のほうがいい双方向連結リストを作れる」といった考えは捨ててください。それは幻想に過ぎません。

もし、万が一、本当にそんなことが出来るなら、そのソースを持ってコンパイラメーカー(もしくはC++標準化委員会) に売り込みに行きましょう。

「他人の書いたコードなんて信用できるか」といった考えも捨ててください。コンパイラに付属するくらいですから、十分テストされています。

どうしてもこの考えが捨てきれない場合は、あなたはストリーム(coutやファイル入出力)や文字列、計算用ライブラリすらも実装しなければなりませんよ。

ここでイテレータのvectorでの使用例をもう一度使います。

このソースの「vector」という部分をヘッダを含め全て「list」に変更してください (コメントを除くと1行目と6行目と18行目にあります)。

なんと、変更後のコードもきちんと動くのです。これがSTLのすごさの一部です。

コンストラクタ

listもvectorと同様に、デフォルトコンストラクタ、コピーコンストラクタ、サイズを指定するコンストラクタがよく使用されます。

listの場合、サイズの拡張は常に定数時間で終了(追加する要素が1つの場合) します。

#include <list>

int main() {
    using std::list;
    list<int> test1;            // デフォルトコンストラクタを使用
    list<int> test2 = test1;    // コピーコンストラクタ使用
    list<int> lst(10);          // 要素数10個の双方向連結リストの作成
}

サイズ

listでは要素数取得したり変更したりすることが可能です。

関数名宣言説明
sizesize_type size() const;要素数を得る関数
emptybool empty() const;空かどうかを返す関数
resizevoid resize(size_type newSize, Type initValue = Type());要素数をnewSizeに変更する関数 追加された要素はinitValueで初期化される

これ以外にmax_size関数がありますが、使用することは無いでしょう。

vectorと違い、resize関数で現在の要素数より小さい値を指定すると領域が解放されます。

これは連結リストであるためで、直感的でしょう。

先頭要素、末尾要素の参照

先頭要素にアクセスするにはfront関数を使用し、末尾要素にアクセスするにはback関数を使用します。

#include <list>
#include <iostream>

int main() {
    using namespace std;
    list<int> lst(2);
    
    cout << lst.front() << endl;    // listの先頭要素を表示
    
    lst.front() = 1;                // listの先頭要素を変更
    cout << lst.front() << endl;
    
    cout << lst.back() << endl;     // listの末尾要素を表示
    
    lst.back() = 2;                 // listの末尾要素を変更
    cout << lst.back() << endl;
}

追加・挿入・削除

連結リストの中心となる追加・挿入・削除を行う関数はバリエーションが数多くあります。

vectorと違い、先頭要素に追加する関数と先頭要素を削除する関数も用意されています。

削除を行う関数はiteratorを返しますが、このときのiteratorは削除した次の要素を指しています。

関数名宣言説明
push_frontvoid push_front(const Type& value);先頭にvalueを追加する関数
push_backvoid push_back(const Type& value);末尾にvalueを追加する関数
pop_frontvoid pop_front();先頭の要素を削除する関数
pop_backvoid pop_back();末尾の要素を削除する関数
insertiterator insert(iterator pos, const Type& value);posの位置にvalueを挿入する関数
void insert(iterator pos, size_type n, const Type& value);posの位置にvalueをn個挿入する関数
template <class InputIterator>
void insert(iterator pos, InputIterator begin, InputIterator end);
posの位置に[begin, end)の要素を挿入する関数
eraseiterator erase(iterator pos);posの要素を削除する関数
iterator erase(iterator begin, iterator end);[begin, end)の要素を削除する関数
clearvoid clear();全要素を削除する関数

listに許容量という概念は無いため、erase関数やclear関数を使用すると、削除された要素の領域は解放されます。

アルゴリズム

listはvectorとは違い、メンバ関数としてソートやマージ等が用意されています。

ここでのソートやマージといった操作はリストで効率よく実装できるため存在するもので、STLのアルゴリズム部分とは別物です。

STLのアルゴリズム部分はイテレータを使い、どんなコンテナでも使える汎用的なアルゴリズムの集まりです。

もし使用するコンテナがlistのみであると分かっているならこれらのメンバ関数を使用したほうが効率的です。

関数名宣言説明
removevoid remove(const Type& value);値がvalueと等しい要素を全て削除する関数
uniquevoid unique();連続する要素が同一なら後ろの要素を削除する関数
mergevoid merge(list<Type, Allocator>& lst);自身とlstをマージする関数
sortvoid sort();自身をソートする関数
reversevoid reverse();自身を逆順にする関数

reverse以外はファンクタを使用するバージョン(remove以外は多重定義で実装、removeのみremove_ifという別名の関数で実装) が存在します。

ここであげたもの以外でsplice関数というものがありますが、これはSTLのアルゴリズムにない、完全にlistのみの機能であるため説明はしません。

まとめ?

STLの素晴らしさが分かってもらえたでしょうか。

これでもまだvectorとlistの全部の機能を網羅しているわけではありません。

STLのコンテナは勿論vectorとlistだけではないですし、コンテナとイテレータだけやってもまだアルゴリズムとファンクタが残っています。

これらを組み合わせることでSTLの真価が発揮されますので、ぜひアルゴリズムやファンクタについても勉強してみてください。

STLが使いこなせるようになるにはテンプレートの理解が必要不可欠です。これについても是非理解を深めてください。