6.2 list 演算

この節では、list データ型で提供される各メンバー関数の詳細を説明します。これらのメンバー関数は、list の基本演算を提供します。これらは、第 IV 部で説明している汎用アルゴリズムで、大幅に拡張することができます。

list の宣言方法は多数あります。最も単純な形式では、コレクションが維持する要素の型を記述するだけで list が宣言されます。これは、integer や double、ポインタ型、ユーザが定義した型などと同様に、基本言語型とすることもできます。ユーザが定義した型の場合、このコンストラクタは新しく作成された要素の初期化に使用されるため、ユーザが定義した型がコピーコンストラクタを実装する必要があります。この形式で宣言されたコレクションには、最初は要素がありません。

list <int> list_one;
list <Widget *> list_two;
list <Widget> list_three;

---

注: ポインタを保持するコンテナを宣言した場合、ポイントされるオブジェクトのメモリーを管理する必要があります。コンテナから項目が消去されても、コンテナクラスが自動的にこのようなオブジェクトのためにメモリーの空きメモリーを作成することはありません。

---

宣言のもうひとつの形式では、最初から等価要素を含むコレクションを作成します。この形式のコンストラクタは、変換演算子として使用できないことを意味する explicit として宣言されます。これによって、整数が不注意から list に変換されないようにすることができます。コンストラクタは size と initial value という 2 つの引数を使用します。2 つ目の引数は、含まれる型がデフォルトのコンストラクタを持つ場合、省略可能です。作成される初期要素の数だけが指定される場合、これらの値はデフォルトコンストラクタで初期化されます。それ以外の場合は、要素が 2 つ目の引数の値で初期化されます。

list <int> list_four (5);  // 5 要素、0 に初期化される
list <double> list_five (4, 3.14);   // 4 要素、初期値は 3.14
list <Widget> wlist_six (4);  // デフォルトコンストラクタ、4 要素
list <Widget> list_six (3, Widget(7));  // Widget(7) の 3 つのコピー

他のコレクションの要素と 1 組の開始反復子と終了反復子を使用して、これらの list を初期化することもできます。引数はあらゆる形式の反復子になることが可能なため、コレクションは、反復子をサポートする標準 C++ ライブラリの任意のコンテナクラスから引き出された値で、初期化することができます。したがって、反復子の引数は任意の形式にすることができます。テンプレートを使用してメンバー関数を特殊化する機能が要求されるため、一部のコンパイラはこの機能をサポートしていません。このような場合、copy() 汎用アルゴリズムを使用する別の手法を使用することができます。 copy() を使用してlist が初期化される場合、コピー演算によって出力演算を list に変換するために、挿入反復子を作成する必要があります (2.4 節)。インサータは、値がコピーされる list と、値が配置される位置を示す反復子の 2 つの引数を要求します。挿入反復子は、既存の list の任意の位置に要素をコピーするためにも使用することができます。

list <double> list_seven (aVector.begin(), aVector.end());

                  // 以下は上記と等価
list <double> list_eight;
copy (aVector.begin(), aVector.end(), 
       inserter(list_eight, list_eight.begin()));

また、insert() 演算も、反復子で示される値を list に配置するために使用することができます (6.2.3 節)。挿入反復子は、generator で作成される値のシーケンスで list を初期化するために使用します (13.2.3 節)。以下に、この例を示します。

list <int> list_nine;          
                                   // list 1 2 3 ... 7 を初期化する
generate_n (inserter(list_nine, list_nine.begin()), 
    7, iotaGen(1));

コピーコンストラクタ は、list を他の list から引き出された値で初期化するために使用します。また、代入演算子も同じ処理を実行します。いずれの場合も、要素の型への代入演算子が新しい値のコピーに使用されます。

list <int> list_ten (list_nine);          // コピーコンストラクタ
list <Widget> list_eleven;
list_eleven = list_six;        // 代入によってコピーされる値

assign() メンバー関数は代入演算子と似ていますが、より汎用性があり、より多くの引数を必要とする場合もあります。代入と同様に、コンテナの既存の値が削除され、引数で指定された値で置換されます。デストラクタがコンテナの要素型に定義されている場合、削除される要素に対してデストラクタが呼び出されます。assign() には 2 つの形式があります。

• 1 つは、既存のコンテナのサブシーケンスを指定する、2 つの反復子の引数を使用する形式です。このサブシーケンスからの値は受け手の新しい要素となります。

• もう 1 つは、数とコンテナの要素型の任意の値を使用する形式です。呼び出されると、コンテナは、コンテナ型のデフォルト値または指定された初期値のいずれかに等しい数で指定された要素数だけを保持するようになります。型にデフォルトコンストラクタが含まれていない場合は、初期値を指定する必要があります。

list_six.assign(list_ten.begin(), list_ten.end());
list_four.assign(3, 7);        // 値 7 の 3 つのコピー
list_five.assign(12);            // 値 0 の12 のコピー

最後に、2 つの list は、演算 swap() によって内容全体を交換することができます。引数コンテナが受け手の値を引き受ける際に、受け手はそれらが引数であるとみなします。交換は非常に効率がよく、適切な場合には、要素対要素の明示的な転送に優先して使用されるべきです。

list_ten.swap(list_nine);        // list 9 と 10 を交換する

クラス list には多数の型の定義が含まれ、一般的にそのほとんどが宣言文に使用されます。たとえば、integer の list のための反復子は、次の形式で宣言することができます。

list<int>::iterator location;

iterator に加えて、表 10 では次の型を定義します。

表 10 -- クラス list の型の定義

値はさまざまな方法で list に挿入することができます。要素はほとんどの場合、list の先頭または末尾に追加されます。これらのタスクは、それぞれ push_front() および push_back() 演算によって提供されます。この 2 つの演算は両方のタイプのコンテナで (一定時間) 効率的です。

list_seven.push_front(1.2);
list_eleven.push_back (Widget(6));

6.2.1 節 では、挿入反復子と、copy() または generate() 汎用アルゴリズムを利用して、list の反復子で示される位置に値を配置する方法を説明しました。インサータを作成する必要のない、insert() という名前のメンバー関数もあります。簡単に説明すると、list の先頭と末尾をそれぞれ示す関数 begin() と end() を生成する反復子によって返される値です。このいずれかを使用する挿入は、それぞれ push_front() または push_back() と等価です。1 つの反復子だけを指定すると、デフォルトの要素値が挿入されます。

// list の先頭にデフォルト型を挿入する
list_eleven.insert(list_eleven.begin()); 
// list の末尾に Widget 8 を挿入する
list_eleven.insert(list_eleven.end(), Widget(8));

反復子はlist の中間の位置を示すことができます。この反復子を作成する方法はいくつかあります。たとえば、find() 汎用アルゴリズムの呼び出しなど、13.3 節で説明する検索演算の結果を使用することができます。

//  list で最初に値 5 が出現する位置を
//  検索する
list<int>::iterator location = 
  find(list_nine.begin(), list_nine.end(), 5);
// 直前に 11 を挿入する
location = list_nine.insert(location, 11);

これによって、反復子で示される位置の直前に新しい値が挿入されます。insert() 演算自身は、挿入された値の位置を示す反復子を返します。この結果の値は、上記の呼び出しでは無視されます。

---

注: vector や deque とは異なり、list の中間からの挿入または削除によってコンテナ内の他の要素への参照またはポインタが無効になることはありません。同じコンテナを参照するために 2 つ以上の反復子が使用される場合、この特性が重要となります。

---

また、引数値の固定数のコピーを挿入することもできます。この形式の insert() は値の位置を算出しません。

line_nine.insert (location, 5, 12);       // 5、12 を挿入する

最後に、1 組の反復子によって示されるシーケンス全体を list に挿入することができます。insert() の結果として、有効な値が返されることはありません。

// list_ten の内容全体を list_nine に挿入する
list_nine.insert (location, list_ten.begin(), list_ten.end());

1 つの list を他の list に繋ぐ方法は多数あります。list の繋ぎ演算は、項目が受け手の list に追加されると同時に引数 list から削除されるという点で、挿入とは異なります。この理由から、list の繋ぎ演算は非常に効率よく実行できるため、適切な場合にはいつでも使用されるべきです。挿入とともに、メンバー関数 splice() は、list の繋ぎ演算が行われるべき受け手 list 内の場所を示すために反復子を使用します。引数は list 全体、list 内の 1 つの要素 (反復子によって示される)、または list のサブシーケンス (1 組の反復子によって示される) のいずれかです。

// list 10 の最後の要素を繋ぐ
list_nine.splice (location, list_ten, list_ten.end()); 
// list 10 のすべてを繋ぐ
list_nine.splice (location,  list_ten);
// list 9 を list 10 に戻す
list_ten.splice (list_ten.begin(), list_nine, 
   list_nine.begin(), location);

merge() 演算を使用して、2 つの順序付き list を組み合わせて 1 つにすることができます。引数 list は空白のまま、引数 list の値は順序付き list にマージされます。マージは安定しています。つまり、要素は、元の list からの相対順序を保存します。同じ名前の汎用アルゴリズムを使用すると (14.6 節)、2 つの形式がサポートされます。1 つは含まれている型に定義された演算子 < を使用する形式です。もう 1 つは、値を順序付けるための引数として提供される 2 項関数を使用する形式ですが、これはすべてのコンパイラでサポートされているわけではありません。後者の形式が望ましいにもかかわらずサポートされていない場合は、より一般的な汎用アルゴリズムを使用することができますが、この場合、多少効率が悪くなります。

// 明示的な比較関数とマージする
list_eleven.merge(list_six, widgetCompare);

//以下は上記と同様
list<Widget> list_twelve;
merge (list_eleven.begin(), list_eleven.end(), 
   list_six.begin(), list_six.end(), 
   inserter(list_twelve, list_twelve.begin()), widgetCompare);
list_eleven.swap(list_twelve);

要素を list に挿入する方法が多数あるように、list から値を削除する方法も多数あります。値の削除に使用される最も一般的な演算は pop_front() または pop_back() であり、それぞれ list の先頭または末尾から 1 つの要素を削除します。これらのメンバー関数は指定された要素を削除するだけで、それ自身では有効な結果を算出しません。デストラクタが要素の型に定義されている場合、削除される要素として呼び出されます。削除する前に値を検証するには、メンバー関数 front() または back() を使用します。

erase() 演算は、反復子で示される値を削除するために使用することができます。list の場合は、同じ位置を示す引数反復子および他の反復子は削除された後に無効となりますが、他の位置を示す反復子は影響を受けません。また、erase() を使用して、1 組の反復子で示されるサブシーケンス全体を削除することもできます。最初の反復子から最後の反復子までの値が、list から削除されます。ただし、最後の反復子は削除されません。list の中間からの要素の消去は、vector または deque の中間から要素を消去するのとは異なり、効率のよい演算です。

   list_nine.erase (location);

   // 最初の 5 の出現と次の 7 の出現の間にある
   // 値を消去する
list<int>::iterator
   location = find(list_nine.begin(), list_nine.end(), 5);
   list<int>::iterator location2 = 
       find(location, list_nine.end(), 7);
   list_nine.erase (location, location2);

remove() メンバー関数は、指定された値が出現すると、そのすべてを list から削除します。その変形である remove_if()は、指定された述語を満たす値をすべて削除します。この代わりに、remove() または remove_if() の汎用アルゴリズムを使用することができます (13.5.1 節)。この汎用アルゴリズムは list のサイズを小さくすることはありません。代わりに、保存される要素を list の先頭に移動し、list の残りの値は変更しないで、最初の変更されていない要素の位置を示す反復子を返します。この値は erase() メンバー関数と結合して、残りの値を削除するために使用することができます。

list_nine.remove(4);                         // すべての 4 を削除する
list_nine.remove_if(divisibleByThree);     // 3 の倍数を削除する

// 以下は上記と等価
list<int>::iterator location3 = 
remove_if(list_nine.begin(), list_nine.end(), 
           divisibleByThree);
list_nine.erase(location3, list_nine.end());

演算 unique() は list 内で連続する等価要素のグループの最初の要素以外のすべてを消去します。list を順序付ける必要はありません。この代替演算では、2 項関数を使用して隣接する要素を比較し、関数が真の値を算出する場合、2 番目の値を削除します。remove_if() と同様に、unique() の 2 番目の形式をサポートしないコンパイラもあります。この場合、より一般的な unique() 汎用アルゴリズムを使用することができます (13.5.2 節)。次の例では、2 項関数は大なり演算子であり、前の要素より小さいすべての要素を削除します。

// 連続する等価要素の最初の要素を削除する
list_nine.unique();

// 明示的に比較関数を指定する
list_nine.unique(greater<int>());

// 以下は上記と等価
location3 = 
     unique(list_nine.begin(), list_nine.end(), greater<int>());
list_nine.erase(location3, list_nine.end());

メンバー関数 size() は、コンテナで保持されている要素数を算出します。コンテナが空の場合、関数 empty() はブール値 true を返し、通常、ゼロに対する size() のテストよりも高速です。

cout << "Number of elements: " << list_nine.size () << endl;
if ( list_nine.empty () )
   cout << "list is empty " << endl;
else
   cout << "list is not empty " << endl;

メンバー関数 resize() は list のサイズを引数で指定した値に変更します。値は必要に応じて、コレクションの終端に追加または削除されます。任意の 2 番目の引数は、コレクションに追加された新しい要素の初期値を割り当てるために使用することができます。

// サイズが 12 になる、必要に応じて値 17 を追加する
list_nine.resize (12, 17); 

メンバー関数 front() と back() はそれぞれ、コンテナの最初と最後の項目を返しますが、削除は行いません。list の場合は、目的の要素が先頭または末尾となるまで要素を削除するか、反復子の使用によってのみ、他の要素へのアクセスが可能となります。

list のために作成できる反復子の型は 3 つあります。関数 begin() と end() は list を順方向にすべて参照する反復子を作成します。list データ型の場合、begin() と end() が双方向反復子を作成します。代替関数 rbegin() と rend() は、list の末尾から先頭へと逆方向に参照する反復子を作成します。

list データ型は、特定の値がコレクションに含まれているかどうかを調べるために使用する方法を、直接的に提供することはありません。しかし、汎用アルゴリズム find() または count() のいずれかをこの目的に使用することができます (13.3.1 節 と 13.6.1 節)。たとえば、次の文は、整数 list に要素 17 が含まれているかどうかをテストします。

count (vec_five.begin(), vec_five.end(), 17);

コンパイラが部分的な特殊化をサポートしない場合は、代わりに次のインタフェースを使用する必要があります。

count(vec_five.begin
int num = 0;
count(list_five.begin(), list_five.end(), 17, num);
if (num > 0)
   cout << "contains a 17" << endl;
else
   cout << "does not contain a 17" << endl;

if (find(list_five.begin(), list_five.end(), 17) != list_five.end())
   cout << "contains a 17" << endl;
else
   cout << "does not contain a 17" << endl;

メンバー関数 sort() は要素を昇順で配置します。< 以外の比較演算子を使用する場合は、引数として使用することができます。

list_ten.sort ( );                  // 要素をシーケンスに配置する
list_twelve.sort (widgetCompare);       // ウィジェット比較関数で
                                        // ソートする

list がソートされると、順序付けられたコレクションのための多数の汎用アルゴリズムを list と共に使用することができます (第 14 章)。

13.3 節 で説明する find()、find_if()、adjacent find()、mismatch()、max_element()、min_element()、search() などのさまざまな形式の検索関数を、list に適用することができます。いずれの場合も結果は反復子となり、示された要素を検出するために間接参照とするか、後続の演算の引数として使用することができます。

---

注: 標準 C++ ライブラリの検索アルゴリズムは、検索条件と一致する要素が検出されると、必ず範囲の終端反復子を返します。結果が有効であると保証されていない限り、範囲の終端条件を確認することを推奨します。

---

list に適用できる演算は多数あります。その一部はメンバー関数として提供されます。それ以外は、第 13 章で説明する汎用関数を使用します。

list の場合、メンバー関数 reverse() は list の要素の順序を逆にします。

list_ten.reverse();                 // 要素が逆になる

汎用アルゴリズム transform() は、演算の入力と結果の両方に同じコンテナを使用するだけで、コンテナのすべての値を変更するために使用することができます (13.7.1 節)。たとえば、次のコードは list の各要素を 1 ずつ増分します。

transform(list_ten.begin(), list_ten.end(), 
   list_ten.begin(), bind1st(plus<int>(), 1));

必要な単項関数を作成するには、2 項の整数加算関数の最初の引数を値 1 に設定します。2 つの並列シーケンスを操作する transform() の変形は、このようにして使用することができます。

同様に、関数 replace() と replace_if() は、list の要素を特定の値に置換するために使用することができます (13.4.2 節)。また、list の回転と区分化も実行することができます (13.4.3 節 および 13.4.4 節)。

// 値 5 の位置を検索し、循環させる
location = find(list_ten.begin(), list_ten.end(), 5);
rotate(list_ten.begin(), location, list_ten.end());
// 7 以上の値の使用して区分する partition(list_ten.begin(), list_ten.end(), 
      bind2nd(greater<int>(), 7));

関数 next_permutation() と prev_permutation() は、値のコレクションの次の順列 (または前の順列) を生成するために使用することができます (13.4.5 節)。

next_permutation (list_ten.begin(), list_ten.end());

アルゴリズム for_each() は、コレクションのすべての要素に関数を適用します (13.8 節)。この使用例は deque データ構造の節の基数ソートのプログラム例にあります ( 7.3 節)。

accumulate() 汎用アルゴリズムは、コレクションをスカラー値に還元します (13.6.2 節)。これは、たとえば、多数の list の合計を計算するために使用することができます。accumulate() は基数ソートの例のように使用されることもあります。

cout << "Sum of list is: " << 
      accumulate(list_ten.begin(), list_ten.end(), 0) << endl;

2 つの list は、相互に比較することができます。サイズが同じで、対応するすべての要素が等価である場合、この 2 つの list は等価です。辞書編集する上で、一方の list がもう一方の list よりも小さい場合は、もう一方の list よりも小さくなります (13.6.5 節)。