C++の動的配列とリスト

いちごパック > C++の解説 > C++の動的配列とリスト
C++には標準機能として、 vectorと呼ばれる動的な配列と、listと呼ばれるリストがあります。 また、vectorと似ていて先頭への挿入を速くしたdequeと呼ぶ疑似配列もあります。 ここでは、これらをまとめてcontainer(コンテナ)と呼ぶことにします。
いずれの機能も、任意のタイプに対応したテンプレートクラスとして実装され、 データの集合の保持と読み書きの機能を提供しています。
これらのテンプレートクラスの使い方について説明します。

vector、list、dequeの違い

vectorは、データを連続したメモリに保持します。 listは、要素ごとにデータとその前後の要素へのポインタを保持します。 dequeは、データを断片的に連続したメモリに保持します。
各クラスが要素を持つ方法の概念図に示します。 具体的な実装方法はライブラリごとに違いますので、この概念図通りの実装とは限りません。


したがって、vectorの要素に対しては通常のポインタ演算が利用できますが、 dequeやlistではポインタ演算は利用できず、クラスとして提供される疑似ポインタ(iterator)が必要になります。 また、listでは要素ごとにその前後の要素へのポインタを保持する必要があるため、余分なメモリが必要になります。 C++11以降では、前方向へのアクセスが不要な場合には、 listの代わりに前方向へのアクセスを省くことで軽量化したforward_listを利用することもできます。
各クラスの主な違いを表にまとめました。
機能vectorlistdeque
先頭あるいは終端から順にアクセス〇〇〇
任意の位置へのアクセス〇遅い〇
先頭への要素挿入遅い〇〇(たまに遅い)
終端への要素挿入〇(たまに遅い)〇〇(たまに遅い)
任意の位置への要素挿入遅い〇遅い
通常のポインタアクセス〇不可不可
要素ごとの追加メモリなし大きいわずかにある
汎用アルゴリズムの利用〇△(専用メソッドあり)〇

すべてに共通の操作

個々のクラスを説明する前に、 すべてのテンプレートクラスに共通の操作を示します。
共通操作の大まかなインターフェースは以下の通りです。クラス名はcontainerとしています。 
template <typename T, typename Talloc = std::allocator<T> >
class container
{
public:
    typedef T value_type;
    typedef Talloc allocator_type;
    typedef T& reference;
    typedef const T& const_reference;
    typedef (実装依存の型) iterator;
    typedef (実装依存の型) const_iterator;
    typedef (実装依存の型) reverse_iterator;
    typedef (実装依存の型) const_reverse_iterator;
    typedef (実装依存の型) difference_type;
    typedef (実装依存の型) size_type;

    explicit container(const allocator_type& alloc = allocator_type());
    explicit container(size_type count,
                       const value_type& val = value_type(),
                       const allocator_type& alloc = allocator_type());
    template <typename Titerator>
    container(Titerator itr_begin, Titerator itr_end,
              const allocator_type& alloc = allocator_type());
    ~container();

    template <typename Titerator>
    void assign(Titerator itr_begin, Titerator itr_end);
    void assign(size_type count, value_type val);

    iterator begin();
    const_iterator begin() const;
    iterator end();
    const_iterator end() const;

    reverse_iterator rbegin();
    const_reverse_iterator rbegin() const;
    reverse_iterator rend();
    const_reverse_iterator rend() const;

    bool empty() const;
    size_type size() const;
    size_type max_size() const;
    void clear();
    void resize(size_type count, value_type val = value_type());
    void swap(container<T>& another);

    void push_back(const value_type& val);
    void pop_back();
    iterator insert(iterator itr_pos, const value_type& val);
    template <typename Titerator>
    void insert(iterator itr_pos, Titerator itr_begin, Titerator itr_end);
    void insert(iterator itr_pos, size_type count, value_type val);
    iterator erase(iterator itr_pos);
    iterator erase(iterator itr_begin, iterator itr_end);

    reference front();
    const_reference front() const;
    reference back();
    const_reference back() const;

    ...
};

iterator(イタレータ)

配列内の位置をC/C++言語ではポインタで表現し、ポインタの指す位置は加減算でずらせます。 C++では、vectorやlistなどのcontainerに対するポインタをiteratorと呼んでいます。 また、要素の内容を参照できても変更できないiteratorは、const_iteratorと呼ばれています。
  • iteratorの指す位置は、加減算でずらせます。
  • vectorやdequeなど、任意の位置へのアクセスが速いcontainerは、iteratorを1つずらす機能、iteratorを複数ずらす機能の両方を実装しています(ランダムアクセスイタレータ)。
  • listなど、任意の位置へのアクセスが遅いcontainerは、iteratorを1つずらす機能のみ実装しています(シーケンシャルアクセスイタレータ)。
  • iteratorの前にアスタリスク(*)をつけることで、ポインタと同じように要素の内容にアクセスできます。
    • データ列を渡すためにiteratorが引数として必要であれば、 ポインタはランダムアクセス可能なiteratorとして利用できます。
    iteratorに対する操作は以下の通りです。
    演算子シーケンシャルランダム操作
    *A〇〇iteratorが指す要素にアクセスします。
    ++A〇〇iteratorを1つ後の要素にずらします。
    --A〇〇iteratorを1つ前の要素にずらします。シーケンシャルで前方向にずらせないクラスでは使えません。
    A+=n×〇iteratorをnだけ後の要素にずらします。
    A+-n×〇iteratorをnだけ前の要素にずらします。
    A-B×〇iterator AとBの間の要素数を求めます。
    iteratorの型はcontainerに依存します。 例えばstd::vectorであれば、std::vector::iteratorという型を持ちます。 C++11以降であればこのような複雑な型を書かずに、 型をautoとしたうえでbegin()などiteratorの型を持つ変数を返せば、 自動的にstd::vector::iteratorと解釈してくれます。

    共通のメソッド

    vector、list、dequeの各containerは、次の共通のメソッドを持ちます。
    メソッド概要
    コンストラクタ()要素なしで初期化します。
    コンストラクタ(count,val)valをcount個繰り返したデータで初期化します。
    コンストラクタ(他データ列の開始位置,他データ列の終了位置)iteratorとして与えられた開始位置を含み、終了位置を含まないデータ列で初期化します。
    assign(count,val)valをcount個繰り返したデータを割り当てます。
    assign(他データ列の開始位置,他データ列の終了位置)iteratorとして与えられた開始位置を含み、終了位置を含まないデータ列を割り当てます。
    begin()開始位置のiteratorを返します。containerがconstの場合はconst_iteratorを返します。
    end()終了位置のiteratorを返します。containerがconstの場合はconst_iteratorを返します。
    rbegin()逆から開始するiteratorであるreverse_iteratorを返します。containerがconstの場合はconst_reverse_iteratorを返します。
    rend()逆から開始した場合の終了位置をreverse_iterator型で返します。containerがconstの場合はconst_reverse_iteratorを返します。
    empty()要素が1つもなければtrue、要素が1つでもあればfalseを返します。
    size()要素数を返します。
    max_size()要素数の限界を返します。実際にこの要素数まで確保できるとは限りません。
    clear()すべての要素を解放します。
    resize(count,val)要素数をcountにします。要素数が増える場合は、増えた部分をvalで初期化します。
    swap(同じcontainer型)引数で与えたcontainerとの間でcontainerの内容を交換します。
    push_back(val)valを最後の要素として追加します。要素数は1つ増えます。
    pop_back()最後の要素を破棄します。要素数は1つ減ります。
    insert(挿入位置,val)指定された挿入位置に、valを1つ挿入します。
    insert(挿入位置,他データ列の開始位置,他データ列の終了位置)指定された挿入位置に、iteratorとして与えられた開始位置を含み、終了位置を含まないデータ列を挿入します。
    insert(挿入位置,count,val)指定された挿入位置に、valをcount個繰り返したデータを挿入します。
    erase(削除位置)指定された削除位置(iterator指定)にあるデータ1つを削除します。
    erase(削除開始位置,削除終了位置)指定された削除開始位置(iterator指定)を含み、削除終了位置(iterator指定)を含まないデータ列をまとめて削除します。
    front()先頭の要素への参照を返します。containerがconstの場合はconst参照を返します。
    back()最後の要素への参照を返します。containerがconstの場合はconst参照を返します。
    共通操作のコード例を示します。 
    #include <iostream>

void dump(const container<char>& ichigo)
{
    container<char>::const_iterator ichigo_i;

    std::cout << "size = " << ichigo.size();
    std::cout << ", data = ";
    for (ichigo_i = ichigo.begin();
         ichigo_i != ichigo.end();
         ++ichigo_i) {
        std::cout << *ichigo_i;
    }
    std::cout << std::endl;
}

void dump_reverse(const container<char>& ichigo)
{
    container<char>::const_reverse_iterator ichigo_i;

    std::cout << "reverse data = ";
    for (ichigo_i = ichigo.rbegin();
         ichigo_i != ichigo.rend();
         ++ichigo_i) {
        std::cout << *ichigo_i;
    }
    std::cout << std::endl;
}

int main()
{
    std::cout << "[ichigo1]" << std::endl;

    container<char>  ichigo1;
    dump(ichigo1);
    ichigo1.resize(3, 'A');
    dump(ichigo1);
    ichigo1.clear();
    dump(ichigo1);
    ichigo1.assign(4, 'B');
    dump(ichigo1);

    std::cout << "[ichigo2]" << std::endl;

    const char* ichigo2str = "ichigo";
    container<char>  ichigo2(ichigo2str, ichigo2str+6);
    dump(ichigo2);
    dump_reverse(ichigo2);
    ichigo2.push_back('C');
    dump(ichigo2);
    ichigo2.insert(ichigo2.begin(), 3, '*');
    dump(ichigo2);
    ichigo2.insert(ichigo2.begin(), ichigo2str, ichigo2str+6);
    dump(ichigo2);
    ichigo2.erase(ichigo2.begin());
    dump(ichigo2);
    ichigo2.pop_back();
    dump(ichigo2);

    std::cout << "max size = " << ichigo2.max_size() << std::endl;
    std::cout << "front = " << ichigo2.front() << std::endl;
    std::cout << "back = " << ichigo2.back() << std::endl;

    return 0;
}
    containerをvector、list、dequeのいずれかとすれば動作します。 例えば、先頭に以下のコードを挿入すればvectorになります。 
    #include <vector>
#define container std::vector
    実行結果の1例を示します。max_size()の出力は機種やクラスの種類に依存します。 
    [ichigo1]
size = 0, data = 
size = 3, data = AAA
size = 0, data = 
size = 4, data = BBBB
[ichigo2]
size = 6, data = ichigo
reverse data = ogihci
size = 7, data = ichigoC
size = 10, data = ***ichigoC
size = 16, data = ichigo***ichigoC
size = 15, data = chigo***ichigoC
size = 14, data = chigo***ichigo
max size = 4294967295
front = c
back = o

    vectorクラス

    vectorは、メモリ上で要素を連続したデータとして持つ、サイズ可変の配列です。 vectorでは、container共通のメソッドに加えて次のメソッドが実装されています。
    メソッド概要
    capacity()確保されているメモリの量を要素数単位で返します。
    reserve(count)少なくともcount要素のメモリを確保します。ここで指定した要素数までは、resize()やpush_back()で増やしてもメモリの確保が発生しなくなります。
    operator[](index)index番目の要素への参照を返します。containerがconstの場合はconst参照を返します。
    at(index)index番目の要素が存在するかチェックしてから、index番目の要素への参照を返します。要素が存在しない場合はstd::out_of_range例外を発生させます。
    containerとしてvectorを使うと、配列記号[]やat()メソッドなどでランダムアクセスできます。
    vectorの大まかなインターフェースは以下の通りです。containerに共通の部分は省略しています。 
    #include <vector>
template <typename T, typename Talloc = std::allocator<T> >
class vector
{
public:
    (共通部分は省略)

    size_type capacity() const;
    void reserve(size_type count);

    reference operator[](size_type index);
    const_reference operator[](size_type index) const;
    reference at(size_type index);
    const_reference at(size_type index) const;

    ...
};

    listクラス

    listは、双方向の位置を持つリストです。 listでは、container共通のメソッドに加えて次のメソッドが実装されています。
    メソッド概要
    push_front(val)valを先頭の要素として追加します。要素数は1つ増えます。
    pop_front()先頭の要素を破棄します。要素数は1つ減ります。
    reverse()リストの順序を逆順にします。
    splice(リスト内位置,他のリスト)リスト内位置に、他のリストの全要素を移動させながら挿入します。挿入した要素は他のリストからは削除されます。
    splice(リスト内位置,他のリスト,他のリストの開始位置)リスト内位置に、他のリストの開始位置以降の要素を移動させながら挿入します。挿入した要素は他のリストからは削除されます。
    splice(リスト内位置,他のリスト,他のリストの開始位置,他のリストの終了位置)リスト内位置に、他のリストの開始位置から終了位置までの要素を移動させながら挿入します。開始位置の要素は対象としますが終了位置の要素は対象としません。挿入した要素は他のリストからは削除されます。
    remove(val)valを持つ要素をすべて削除します。
    remove_if(要素チェック関数)要素チェック関数がtrueを返す要素をすべて削除します。
    unique()同じ要素が連続している場合に、最初の要素を残して削除します。
    unique(同一チェック関数)unique()と同様ですが同一チェック関数がtrueを返す場合は同じ要素、falseを返す場合は違う要素と判断します。
    merge(他のリスト)小さい順にソートされた2つのリストを、1つのソートされたリストとして統合します。
    merge(他のリスト,比較関数)merge(他のリスト)と同様ですが、第1項が第2項より小さい場合にtrueを返す比較関数を与えます。
    sort()リストを要素の小さい順にソートします。
    sort(比較関数)sort()と同様ですが、第1項が第2項より小さい場合にtrueを返す比較関数を与えます。

    listの大まかなインターフェースは以下の通りです。containerに共通の部分は省略しています。 
    #include <list>
template <typename T, typename Talloc = std::allocator<T> >
class list
{
public:
    (共通部分は省略)

    void push_front(const value_type& val);
    void pop_front();

    void reverse();
    void splice(iterator itr_pos, list<T>& another);
    void splice(iterator itr_pos, list<T>& another, iterator itr_another);
    void splice(iterator itr_pos, list<T>& another,
                iterator itr_another_begin, iterator itr_another_end);
    void remove(const value_type& val);
    template <typename Tiffunc>
    void remove_if(Tiffunc func);
    void unique();
    template <typename Tmatch>
    void unique(Tmatch func);
    void merge(list<T>& another);
    template <typanem Tcompare>
    void merge(list<T>& another, Tcompare func);
    void sort();
    template <typanem Tcompare>
    void sort(Tcompare func);

    ...
};

    listを使用したコードの例を以下に示します。 
    #include <iostream>
#include <list>

void dump(std::list<int>& ichigo)
{
    std::list<int>::iterator ichigo_i;

    std::cout << "size = " << ichigo.size() << " data = ";
    for (ichigo_i = ichigo.begin();
         ichigo_i != ichigo.end();
         ++ichigo_i ) {
        std::cout << *ichigo_i << ' ';
    }
    std::cout << std::endl;
}

bool compare(const int val1, const int val2)
{
    return val1 > val2;
}

bool is_ichigo(int val)
{
    return val == 1 || val == 5;
}

int main()
{
    const int ichigo1data[5] = { 1, 5, 15, 1, 5 };
    std::list<int> ichigo1(&ichigo1data[0], &ichigo1data[5]);
    std::list<int> ichigo2(3, 4);

    std::cout << "[splice 1]" << std::endl;
    dump(ichigo1);
    dump(ichigo2);
    ichigo1.splice(ichigo1.begin(), ichigo2);
    dump(ichigo1);
    dump(ichigo2);

    std::cout << "[splice 2]" << std::endl;
    ichigo2.assign(2, 7);
    dump(ichigo1);
    dump(ichigo2);
    std::list<int>::iterator i1;
    std::list<int>::iterator i2;
    i1 = ichigo1.begin();
    ++i1; ++i1; ++i1;
    ichigo2.splice(ichigo2.end(), ichigo1, i1);
    dump(ichigo1);
    dump(ichigo2);

    std::cout << "[splice 3]" << std::endl;
    i1 = ichigo1.begin();
    ++i1;
    i2 = ichigo1.end();
    --i2;
    ichigo2.splice(ichigo2.begin(), ichigo1, i1, i2);
    dump(ichigo1);
    dump(ichigo2);

    std::cout << "[reverse]" << std::endl;
    ichigo2.reverse();
    dump(ichigo2);

    std::cout << "[sort]" << std::endl;
    ichigo2.sort();
    dump(ichigo2);
    ichigo2.sort(compare);
    dump(ichigo2);

    std::cout << "[unique]" << std::endl;
    ichigo2.unique();
    dump(ichigo2);

    std::cout << "[remove_if]" << std::endl;
    ichigo2.remove_if(is_ichigo);
    dump(ichigo2);

    std::cout << "[merge]" << std::endl;
    const int ichigo1data_2[5] = { 1, 1, 5, 15, 15 };
    const int ichigo2data_2[5] = { 3, 5, 7, 14, 16 };
    ichigo1.assign(&ichigo1data_2[0], &ichigo1data_2[5]);
    ichigo2.assign(&ichigo2data_2[0], &ichigo2data_2[5]);
    dump(ichigo1);
    dump(ichigo2);
    ichigo1.merge(ichigo2);
    dump(ichigo1);
    dump(ichigo2);

    return 0;
}
    実行結果の1例を示します。 
    [splice 1]
size = 5 data = 1 5 15 1 5 
size = 3 data = 4 4 4 
size = 8 data = 4 4 4 1 5 15 1 5 
size = 0 data = 
[splice 2]
size = 8 data = 4 4 4 1 5 15 1 5 
size = 2 data = 7 7 
size = 7 data = 4 4 4 5 15 1 5 
size = 3 data = 7 7 1 
[splice 3]
size = 2 data = 4 5 
size = 8 data = 4 4 5 15 1 7 7 1 
[reverse]
size = 8 data = 1 7 7 1 15 5 4 4 
[sort]
size = 8 data = 1 1 4 4 5 7 7 15 
size = 8 data = 15 7 7 5 4 4 1 1 
[unique]
size = 5 data = 15 7 5 4 1 
[remove_if]
size = 3 data = 15 7 4 
[merge]
size = 5 data = 1 1 5 15 15 
size = 5 data = 3 5 7 14 16 
size = 10 data = 1 1 3 5 5 7 14 15 15 16 
size = 0 data =

    dequeクラス

    dequeは、サイズ可変の配列に似たcontainerです。 dequeでは、container共通のメソッドに加えて次のメソッドが実装されています。
    メソッド概要
    push_front(val)valを先頭の要素として追加します。要素数は1つ増えます。
    pop_front()先頭の要素を破棄します。要素数は1つ減ります。
    operator[](index)index番目の要素への参照を返します。containerがconstの場合はconst参照を返します。
    at(index)index番目の要素が存在するかチェックしてから、index番目の要素への参照を返します。要素が存在しない場合はstd::out_of_range例外を発生させます。
    containerとしてdequeを使うと、 vectorと同じように配列記号[]やat()メソッドなどでランダムアクセスできます。 また、listと同じように、先頭への要素挿入を効率的に行えます。
    dequeの大まかなインターフェースは以下の通りです。containerに共通の部分は省略しています。 
    #include <deque>
template <typename T, typename Talloc = std::allocator<T> >
class deque
{
public:
    (共通部分は省略)

    void push_front(const value_type& val);
    void pop_front();

    reference operator[](size_type index);
    const_reference operator[](size_type index) const;
    reference at(size_type index);
    const_reference at(size_type index) const;

    ...
};