この記事では、C++の標準ライブラリであるSTL(Standard Template Library)について学びます。
STLは、プログラミングを効率的に行うための便利なツールがたくさん詰まったライブラリです。
特に、データを整理したり、検索したり、変換したりするための「アルゴリズム」に焦点を当てて解説します。
具体的な使い方やサンプルコードを通じて、初心者でもわかりやすく理解できるように説明していきます。
この記事を読むことで、STLの基本的な使い方や、プログラムをより効率的に書くためのテクニックを身につけることができます。
STL(Standard Template Library)とは
STLの概要
STL(Standard Template Library)は、C++の標準ライブラリの一部であり、データ構造とアルゴリズムの集合体です。
STLは、プログラマーが効率的にデータを操作するためのツールを提供し、コードの再利用性と保守性を向上させます。
STLは、コンテナ、イテレータ、アルゴリズムの3つの主要なコンポーネントで構成されています。
STLの構成要素
コンテナ
コンテナは、データを格納するためのオブジェクトです。
STLには、様々な種類のコンテナが用意されており、用途に応じて使い分けることができます。
代表的なコンテナには、vector、list、deque、set、mapなどがあります。
イテレータ
イテレータは、コンテナ内の要素にアクセスするためのオブジェクトです。
イテレータを使用することで、コンテナの要素を順番に操作することができます。
イテレータは、ポインタのように振る舞い、*演算子や++演算子を使って要素にアクセスしたり、次の要素に移動したりすることができます。
アルゴリズム
アルゴリズムは、データを操作するための関数群です。
STLには、ソート、検索、変換、集計など、様々なアルゴリズムが用意されています。
これらのアルゴリズムは、コンテナとイテレータを組み合わせて使用することができます。
アルゴリズムの基本
アルゴリズムとは
アルゴリズムとは、特定の問題を解決するための手順や方法のことです。
プログラミングにおいては、データの操作や処理を行うための具体的な手順を指します。
STLのアルゴリズムは、汎用的に設計されており、様々なコンテナに対して適用することができます。
STLアルゴリズムの特徴
STLのアルゴリズムは、以下の特徴を持っています。
- 汎用性: 様々なコンテナに対して適用可能
- 効率性: 高速な処理を実現
- 再利用性: コードの再利用を促進
アルゴリズムの使用方法
ヘッダーファイルのインクルード
STLのアルゴリズムを使用するためには、対応するヘッダーファイルをインクルードする必要があります。
例えば、ソートアルゴリズムを使用する場合は、<algorithm>ヘッダーファイルをインクルードします。
#include <algorithm>
#include <vector>
#include <iostream>イテレータの利用
STLのアルゴリズムは、イテレータを使用してコンテナの要素にアクセスします。
例えば、std::sortアルゴリズムを使用してvectorをソートする場合、begin()とend()イテレータを渡します。
std::vector<int> vec = {3, 1, 4, 1, 5, 9};
std::sort(vec.begin(), vec.end());ソートアルゴリズム
sort
基本的な使い方
std::sortは、指定された範囲の要素を昇順にソートするアルゴリズムです。
以下の例では、vectorの要素をソートしています。
#include <algorithm>
#include <vector>
#include <iostream>
int main() {
std::vector<int> vec = {3, 1, 4, 1, 5, 9};
std::sort(vec.begin(), vec.end());
for (int n : vec) {
std::cout << n << " ";
}
return 0;
}カスタム比較関数の利用
std::sortは、カスタム比較関数を使用してソート順を指定することもできます。
以下の例では、降順にソートしています。
#include <algorithm>
#include <vector>
#include <iostream>
bool compare(int a, int b) {
return a > b;
}
int main() {
std::vector<int> vec = {3, 1, 4, 1, 5, 9};
std::sort(vec.begin(), vec.end(), compare);
for (int n : vec) {
std::cout << n << " ";
}
return 0;
}stable_sort
基本的な使い方
std::stable_sortは、安定ソートを行うアルゴリズムです。
安定ソートとは、同じ値の要素の相対的な順序を保持するソートのことです。
#include <algorithm>
#include <vector>
#include <iostream>
int main() {
std::vector<int> vec = {3, 1, 4, 1, 5, 9};
std::stable_sort(vec.begin(), vec.end());
for (int n : vec) {
std::cout << n << " ";
}
return 0;
}sortとの違い
std::sortは高速ですが、安定ソートではありません。
一方、std::stable_sortは安定ソートですが、std::sortよりも若干遅いです。
安定性が必要な場合はstd::stable_sortを使用します。
検索アルゴリズム
find
基本的な使い方
std::findは、指定された範囲内で特定の値を検索するアルゴリズムです。
以下の例では、vector内の値を検索しています。
#include <algorithm>
#include <vector>
#include <iostream>
int main() {
std::vector<int> vec = {3, 1, 4, 1, 5, 9};
auto it = std::find(vec.begin(), vec.end(), 4);
if (it != vec.end()) {
std::cout << "Found: " << *it << std::endl;
} else {
std::cout << "Not Found" << std::endl;
}
return 0;
}binary_search
基本的な使い方
std::binary_searchは、ソートされた範囲内で特定の値を二分探索するアルゴリズムです。
以下の例では、ソートされたvector内の値を検索しています。
#include <algorithm>
#include <vector>
#include <iostream>
int main() {
std::vector<int> vec = {1, 1, 3, 4, 5, 9};
bool found = std::binary_search(vec.begin(), vec.end(), 4);
if (found) {
std::cout << "Found" << std::endl;
} else {
std::cout << "Not Found" << std::endl;
}
return 0;
}ソート済みコンテナの必要性
std::binary_searchは、ソートされた範囲でのみ正しく動作します。
ソートされていない範囲で使用すると、正しい結果が得られません。
find_if
基本的な使い方
std::find_ifは、指定された範囲内で条件を満たす最初の要素を検索するアルゴリズムです。
以下の例では、偶数の値を検索しています。
#include <algorithm>
#include <vector>
#include <iostream>
bool is_even(int n) {
return n % 2 == 0;
}
int main() {
std::vector<int> vec = {3, 1, 4, 1, 5, 9};
auto it = std::find_if(vec.begin(), vec.end(), is_even);
if (it != vec.end()) {
std::cout << "Found: " << *it << std::endl;
} else {
std::cout << "Not Found" << std::endl;
}
return 0;
}カスタム条件の利用
std::find_ifは、カスタム条件を指定するために関数ポインタやラムダ式を使用できます。
上記の例では、is_even関数を条件として使用しています。
変換アルゴリズム
transform
基本的な使い方
std::transformは、指定された範囲の要素を変換し、結果を別の範囲に格納するアルゴリズムです。
以下の例では、vectorの各要素を2倍にしています。
#include <algorithm>
#include <vector>
#include <iostream>
int main() {
std::vector<int> vec = {1, 2, 3, 4, 5};
std::vector<int> result(vec.size());
std::transform(vec.begin(), vec.end(), result.begin(), [](int n) { return n * 2; });
for (int n : result) {
std::cout << n << " ";
}
return 0;
}複数コンテナの変換
std::transformは、2つの入力範囲を受け取り、それらを組み合わせて変換することもできます。
以下の例では、2つのvectorの要素を加算しています。
#include <algorithm>
#include <vector>
#include <iostream>
int main() {
std::vector<int> vec1 = {1, 2, 3};
std::vector<int> vec2 = {4, 5, 6};
std::vector<int> result(vec1.size());
std::transform(vec1.begin(), vec1.end(), vec2.begin(), result.begin(), std::plus<int>());
for (int n : result) {
std::cout << n << " ";
}
return 0;
}copy
基本的な使い方
std::copyは、指定された範囲の要素を別の範囲にコピーするアルゴリズムです。
以下の例では、vectorの要素を別のvectorにコピーしています。
#include <algorithm>
#include <vector>
#include <iostream>
int main() {
std::vector<int> vec = {1, 2, 3, 4, 5};
std::vector<int> result(vec.size());
std::copy(vec.begin(), vec.end(), result.begin());
for (int n : result) {
std::cout << n << " ";
}
return 0;
}条件付きコピー
std::copy_ifは、指定された条件を満たす要素のみをコピーするアルゴリズムです。
以下の例では、偶数の要素のみをコピーしています。
#include <algorithm>
#include <vector>
#include <iostream>
bool is_even(int n) {
return n % 2 == 0;
}
int main() {
std::vector<int> vec = {1, 2, 3, 4, 5};
std::vector<int> result;
std::copy_if(vec.begin(), vec.end(), std::back_inserter(result), is_even);
for (int n : result) {
std::cout << n << " ";
}
return 0;
}集計アルゴリズム
accumulate
基本的な使い方
std::accumulateは、指定された範囲の要素を集計するアルゴリズムです。
以下の例では、vectorの要素の合計を計算しています。
#include <numeric>
#include <vector>
#include <iostream>
int main() {
std::vector<int> vec = {1, 2, 3, 4, 5};
int sum = std::accumulate(vec.begin(), vec.end(), 0);
std::cout << "Sum: " << sum << std::endl;
return 0;
}カスタム集計関数の利用
std::accumulateは、カスタム集計関数を使用して集計方法を指定することもできます。
以下の例では、要素の積を計算しています。
#include <numeric>
#include <vector>
#include <iostream>
int main() {
std::vector<int> vec = {1, 2, 3, 4, 5};
int product = std::accumulate(vec.begin(), vec.end(), 1, std::multiplies<int>());
std::cout << "Product: " << product << std::endl;
return 0;
}count
基本的な使い方
std::countは、指定された範囲内で特定の値の出現回数を数えるアルゴリズムです。
以下の例では、vector内の特定の値の出現回数を数えています。
#include <algorithm>
#include <vector>
#include <iostream>
int main() {
std::vector<int> vec = {1, 2, 3, 1, 2, 1};
int count = std::count(vec.begin(), vec.end(), 1);
std::cout << "Count of 1: " << count << std::endl;
return 0;
}count_if
基本的な使い方
std::count_ifは、指定された範囲内で条件を満たす要素の出現回数を数えるアルゴリズムです。
以下の例では、偶数の要素の出現回数を数えています。
#include <algorithm>
#include <vector>
#include <iostream>
bool is_even(int n) {
return n % 2 == 0;
}
int main() {
std::vector<int> vec = {1, 2, 3, 4, 5, 6};
int count = std::count_if(vec.begin(), vec.end(), is_even);
std::cout << "Count of even numbers: " << count << std::endl;
return 0;
}カスタム条件の利用
std::count_ifは、カスタム条件を指定するために関数ポインタやラムダ式を使用できます。
上記の例では、is_even関数を条件として使用しています。
その他の便利なアルゴリズム
for_each
基本的な使い方
std::for_eachは、指定された範囲の各要素に対して特定の操作を行うアルゴリズムです。
以下の例では、vectorの各要素を出力しています。
#include <algorithm>
#include <vector>
#include <iostream>
void print(int n) {
std::cout << n << " ";
}
int main() {
std::vector<int> vec = {1, 2, 3, 4, 5};
std::for_each(vec.begin(), vec.end(), print);
return 0;
}ラムダ式の利用
std::for_eachは、ラムダ式を使用して簡潔に操作を記述することもできます。
以下の例では、vectorの各要素を出力しています。
#include <algorithm>
#include <vector>
#include <iostream>
int main() {
std::vector<int> vec = {1, 2, 3, 4, 5};
std::for_each(vec.begin(), vec.end(), [](int n) { std::cout << n << " "; });
return 0;
}unique
基本的な使い方
std::uniqueは、指定された範囲内で連続する重複要素を削除するアルゴリズムです。
以下の例では、vector内の連続する重複要素を削除しています。
#include <algorithm>
#include <vector>
#include <iostream>
int main() {
std::vector<int> vec = {1, 2, 2, 3, 3, 3, 4, 5};
auto it = std::unique(vec.begin(), vec.end());
vec.erase(it, vec.end());
for (int n : vec) {
std::cout << n << " ";
}
return 0;
}ソートとの組み合わせ
std::uniqueは、ソートされた範囲で使用すると、全ての重複要素を削除することができます。
以下の例では、vectorをソートしてから重複要素を削除しています。
#include <algorithm>
#include <vector>
#include <iostream>
int main() {
std::vector<int> vec = {4, 2, 1, 3, 2, 3, 4, 5};
std::sort(vec.begin(), vec.end());
auto it = std::unique(vec.begin(), vec.end());
vec.erase(it, vec.end());
for (int n : vec) {
std::cout << n << " ";
}
return 0;
}remove
基本的な使い方
std::removeは、指定された範囲内で特定の値を削除するアルゴリズムです。
以下の例では、vector内の特定の値を削除しています。
#include <algorithm>
#include <vector>
#include <iostream>
int main() {
std::vector<int> vec = {1, 2, 3, 1,