C++ STLのdeque::insert()関数の使い方を徹底解説

本記事では、C++ STLにおけるdequeのinsert()関数の機能と具体的な使い方について詳しく解説します。

deque（デック）とは？

dequeは「Double Ended Queue（両端キュー）」の略称で、コンテナの先頭と末尾の両端で要素の追加（拡張）と削除（縮小）が可能なシーケンスコンテナです。

通常のキューデータ構造では、データの挿入は末尾からのみ、削除は先頭からのみ行います。バス停の行列を思い浮かべると分かりやすいでしょう。新たに並ぶ人は必ず列の最後尾に加わり、先頭にいる人から順番に乗車して列から外れていきます。

一方、dequeではこの挿入と削除を両端のどちらでも行うことができる点が大きな特徴です。

insert()関数とは

dequeのinsert()関数は、deque内の任意の位置に要素を挿入するためのメンバ関数です。主に以下の3通りの使い方ができます。

• 指定した位置に1つの要素を挿入する
• 指定した位置に同じ値をn個まとめて挿入する
• 別のコンテナなど、指定した範囲の要素を一括で挿入する

構文

deque_name.insert(iterator position, const value_type& value);
deque_name.insert(iterator position, size_type n, const value_type& value);
deque_name.insert(iterator position, iterator first, iterator last);

パラメータ

• value：挿入する新しい要素の値を指定します。
• n：挿入する要素の個数を指定します。
• first, last：挿入する要素の範囲を表すイテレータを指定します。［first, last）の範囲が対象となります。

戻り値

新しく挿入された要素のうち、最初の要素を指すイテレータを返します。

計算量の注意点

insert()は挿入位置以降の既存要素を移動させる必要があるため、最悪の場合O(n)の計算量がかかります。頻繁に途中挿入を行う場合はパフォーマンスへの影響に注意しましょう。

入出力イメージ

入力：Deque − 1 2 3 4 5　→　出力：New Deque − 1 1 2 3 4 5（先頭に1を挿入）

入力：Deque − 11 12 13 14 15　→　出力：New Deque − 11 12 12 12 13 14 15（2番目の位置に12を2個挿入）

基本的な手順

• まずdequeを宣言します。
• 次にdequeの内容を出力します。
• その後、insert()関数を呼び出して要素を挿入します。

この流れに従うことで、任意の位置に新しい要素を挿入できます。

サンプル1：指定した位置に1つの要素を挿入する

// deque insert() 関数の動作を確認するC++コード
#include <iostream>
#include <deque>
using namespace std;

int main() {
    // dequeの宣言
    deque<int> dq = { 55, 84, 38, 66, 67 };

    // dequeの内容を表示
    cout << "Deque: ";
    for (auto x = dq.begin(); x != dq.end(); ++x)
        cout << *x << " ";

    // 先頭に22を挿入
    auto pos = dq.begin();
    dq.insert(pos, 22);

    // 挿入後のdequeを表示
    cout << "\nNew Deque: ";
    for (auto x = dq.begin(); x != dq.end(); ++x)
        cout << *x << " ";

    return 0;
}

出力

Input - Deque: 55 84 38 66 67
Output - New Deque: 22 55 84 38 66 67

このコードでは、dq.begin()が指す先頭位置に値22を挿入しています。既存の要素はひとつ後ろにずれ、新しい要素が先頭に追加されます。

サンプル2：同じ値をn個挿入する

// deque insert() 関数の動作を確認するC++コード
#include <iostream>
#include <deque>
using namespace std;

int main() {
    deque<char> dq = { 'B', 'L', 'D' };

    cout << "Deque: ";
    for (auto x = dq.begin(); x != dq.end(); ++x)
        cout << *x << " ";

    // 2番目の位置に'O'を2個挿入
    auto pos = dq.begin();
    dq.insert(pos + 1, 2, 'O');

    cout << "\nNew Deque: ";
    for (auto x = dq.begin(); x != dq.end(); ++x)
        cout << *x << " ";

    return 0;
}

出力

Input - Deque: B L D
Output - New Deque: B L O O D

'B'の直後の位置（begin() + 1）に文字'O'を2個挿入することで、"BLOOD"という並びになります。第2引数に個数、第3引数に挿入する値を渡すのがポイントです。

サンプル3：範囲を指定して要素を挿入する

// deque insert() 関数の動作を確認するC++コード
#include <iostream>
#include <deque>
#include <vector>
using namespace std;

int main() {
    deque<int> dq = { 65, 54, 32, 98, 55 };

    cout << "Deque: ";
    for (auto x = dq.begin(); x != dq.end(); ++x)
        cout << *x << " ";

    // 値19を3個持つvectorを作成
    vector<int> v(3, 19);

    // 先頭にvの全要素を挿入
    auto pos = dq.begin();
    dq.insert(pos, v.begin(), v.end());

    cout << "\nNew Deque: ";
    for (auto x = dq.begin(); x != dq.end(); ++x)
        cout << *x << " ";

    return 0;
}

出力

Input - Deque: 65 54 32 98 55
Output - New Deque: 19 19 19 65 54 32 98 55

vectorのv.begin()からv.end()までの範囲（値19を3個）を、dequeの先頭へ一括挿入しています。このようにinsert()は、他のコンテナの要素をまとめてコピーしたい場合にも非常に便利です。

まとめ

deque::insert()を使えば、「単一要素」「n個の同一要素」「範囲指定」の3つの形式で、deque内の任意の位置に要素を挿入できます。戻り値として挿入された先頭要素を指すイテレータが返される点も押さえておくと、さらに柔軟なコードが書けるようになります。