C・C++で配列の重複した値を取り除く
このレッスンでは、最初に出てきた順番を保ったまま、配列の中の重複した値を取り除きます。
はじめに
順番を保ったまま重複を取り除くには、別の結果用の配列を作ります。元の配列の各要素について、すでに結果の配列にあるかどうかを調べ、まだなければ追加します。
大切なポイント
- コンパイラの警告(compiler warning)を有効にして、すべての警告を直しましょう。
- それぞれの値のデータ型と寿命(lifetime)をしっかり理解しましょう。
- 入力データと配列のインデックスの範囲は必ずチェックしましょう。
CとC++のコード例
C
main.c
#include <stdio.h>
int main(void) {
int input[] = {1, 2, 1, 3, 2, 4}, output[6], size = 0;
// Keep the first occurrence of every value.
for (int i = 0; i < 6; ++i) { int seen = 0; for (int j = 0; j < size; ++j) if (output[j] == input[i]) seen = 1; if (!seen) output[size++] = input[i]; }
for (int i = 0; i < size; ++i) printf("%s%d", i ? " " : "", output[i]); puts("");
}
1 2 3 4
C++
main.cpp
#include <iostream>
#include <unordered_set>
#include <vector>
int main() {
std::vector input{1, 2, 1, 3, 2, 4}; std::vector<int> output; std::unordered_set<int> seen;
// Insert returns true only for the first occurrence.
for (int value : input) if (seen.insert(value).second) output.push_back(value);
for (size_t i = 0; i < output.size(); ++i) std::cout << (i ? " " : "") << output[i]; std::cout << '\n';
}
1 2 3 4
CとC++の比較
内側のループは、input[i]がすでにoutputにあるかを調べ、変数seenに記録します。seenが0のときだけ、値をoutputの末尾に加えてsizeを増やします。結果は1 2 3 4です。この方法はわかりやすいもののO(n²)かかります。データが多い場合、C++ではstd::unordered_setでより速く調べられます。
C
Cは小さな手続き型の関数を使い、データがメモリ上でどう表されるかをそのまま見せます。
C++
C++は低レベルの操作もできるまま、ライブラリの型やより安全な抽象化を加えます。
発展問題
両方のバージョンを実行し、コードを書き換えて、それぞれの言語がもたらす安全性の違いを観察しましょう。
- 不正な入力や境界の値で試しましょう。
- 警告を増やすフラグ-Wall -Wextra -Wpedanticを付けてコンパイルしましょう。
- 共通の宣言はヘッダーファイルに、実装は別のファイルに分けましょう。
チャレンジで練習する
このレッスンの内容を使って実際の問題を解きましょう。各チャレンジはブラウザで動き、すぐにテストされ、AI のレビューも受けられます。
すべてのチャレンジ