C++で配列から要素を削除する方法：2回の走査と1回の走査による実装を解説

本チュートリアルでは、C++を使って配列から特定の要素を削除する2つのアプローチ、「2回の走査（Two Traversals）」と「1回の走査（One Traversal）」について解説します。ここでいう「削除」とは、メモリ上からデータを消去することではなく、削除したい要素以降の要素をすべて1つ前へずらし、実質的に配列からその要素を取り除くことを指します。

2回の走査で要素を削除する方法

まず、2つのループ（走査）を使って配列から要素を削除する手順を見ていきましょう。

• 配列と削除対象の要素を初期化します。
• 要素を削除する関数を作成します。
  • 配列を走査し、削除したい要素を検索します。
  • 要素が見つかった時点でループを抜けます。
  • 要素が見つかった場合は、配列のサイズを1減らします。
  • 見つかった位置以降のすべての要素を、それぞれ1つ前のインデックスへ移動します。
  • 更新後の配列サイズを返します。

コード例

実際のコードを見てみましょう。

#include <bits/stdc++.h>
using namespace std;

int searchAndDeleteElement(int arr[], int n, int k) {
    int i;
    // 削除したい要素を検索
    for (i = 0; i < n; i++) {
        if (arr[i] == k) {
            break;
        }
    }
    // 要素が存在する場合
    if (i < n) {
        // k以降の要素をすべて1つ前のインデックスへ移動
        n = n - 1;
        for (int j = i; j < n; j++) {
            arr[j] = arr[j+1];
        }
    }
    // 更新後のサイズを返す
    return n;
}

int main() {
    int n = 6, k = 4;
    int arr[] = {1, 2, 3, 4, 5, 6};
    int updatedLength = searchAndDeleteElement(arr, n, k);
    // 配列を出力
    for (int i = 0; i < updatedLength; i++) {
        cout << arr[i] << " ";
    }
    cout << endl;
    return 0;
}

実行結果

上記のプログラムを実行すると、次の出力が得られます。

1 2 3 5 6

1回の走査で要素を削除する方法

続いて、1つのループだけで要素を削除できる、より効率的な方法を紹介します。

• 配列と削除対象の要素を初期化します。
• 要素を削除する関数を作成します。
  • 配列を走査しながら、削除したい要素を検索します。
  • 要素が見つかった場合、その要素の代入処理をスキップします。
  • 要素が見つかった後は、残りの要素をすべて1つ前のインデックスへ移動します。
  • 最後に、要素が見つかっていれば n - 1 を、見つからなければ n を返します。

コード例

実際のコードを見てみましょう。

#include <bits/stdc++.h>
using namespace std;

int searchAndDeleteElement(int arr[], int n, int k) {
    // 削除対象が最後の要素の場合
    if (arr[n-1] == k) {
        return n - 1;
    }
    bool isElementFound = false;
    for (int i = 0; i < n; i++) {
        // kとの一致を確認
        if (arr[i] == k && !isElementFound) {
            isElementFound = true;
            continue;
        }
        // 要素が見つかった後は、各要素を1つ前のインデックスへ移動
        if (isElementFound) {
            arr[i-1] = arr[i];
        }
    }
    // 更新後のサイズを返す
    if (isElementFound) {
        return n - 1;
    }
    return n;
}

int main() {
    int n = 6, k = 4;
    int arr[] = {1, 2, 3, 4, 5, 6};
    int updatedLength = searchAndDeleteElement(arr, n, k);
    // 配列を出力
    for (int i = 0; i < updatedLength; i++) {
        cout << arr[i] << " ";
    }
    cout << endl;
    return 0;
}

実行結果

上記のコードを実行すると、次の出力が得られます。

1 2 3 5 6

まとめ

同じ「配列からの要素削除」でも、実装方法によって走査の回数が異なります。2回の走査では「検索」と「シフト処理」を分けて行うためコードは直感的に理解しやすい一方、1回の走査では両方の処理を同時に進められるため、無駄な繰り返しがなく効率的です。どちらの方法も計算量はO(n)ですが、実際の処理速度という点では1回の走査の方が有利といえます。用途に応じて使い分けるとよいでしょう。

本チュートリアルについてご不明な点がある場合は、コメント欄にてお気軽にお問い合わせください。