C++プログラミングにおいて、STLのコンテナは非常に重要な役割を果たします。しかし、初心者にとっては理解が難しい部分もあります。
本記事では、STLのコンテナについてわかりやすく詳しく解説していきます。
STLのコンテナとは
STL(Standard Template Library)は、C++の標準ライブラリの一部であり、データ構造やアルゴリズムなどを提供しています。その中でも、コンテナと呼ばれるデータ構造について解説します。
コンテナは、複数の要素を格納するためのデータ構造です。STLでは、以下のようなコンテナが用意されています。
- vector
- deque
- list
- forward_list
- set
- multiset
- map
- multimap
それぞれ異なる特徴を持っており、適切に使い分けることで効率的なプログラミングが可能になります。
次の見出しでは、各コンテナについて詳しく解説します。
シーケンスコンテナ
C++のSTLには、データを格納するための様々なコンテナが用意されています。その中でも、シーケンスコンテナは要素を順序付けして格納することができます。
vector
vectorは、可変長配列を表現するためのコンテナです。
要素の追加や削除が末尾以外では効率的ではありませんが、ランダムアクセスに優れているため、要素へのアクセスが高速です。
また、メモリ上に連続した領域に要素を格納するため、キャッシュ効果も期待できます。
#include <iostream>
#include <vector>
int main() {
// int型のvectorを宣言して、初期化
std::vector<int> vec = {1, 2, 3, 4, 5};
// 要素へのアクセス
std::cout << vec[2] << std::endl; // 3
// 要素の追加
vec.push_back(6);
vec.push_back(7);
// 要素数の取得
std::cout << vec.size() << std::endl; // 7
// 要素の削除
vec.erase(vec.begin() + 3); // 4番目の要素を削除
// 全要素の出力
for (auto x : vec) {
std::cout << x << " ";
}
std::cout << std::endl;
return 0;
}
3
7
1 2 3 5 6 7 このコードでは、int型のvectorを宣言し、初期化しています。
要素へのアクセスは、通常の配列と同様、vec[3]のようにインデックスを指定して行うことが可能です。
要素の追加には、push_backメソッドを使用します。
また、要素数の取得には、sizeメソッドを使用します。sizeof(vec) / sizeof(int)みたいなことをする必要はありません。
deque
dequeは、double-ended queueの略称であり、両端から要素を追加・削除できるように設計されたコンテナです。
vectorと同様にランダムアクセスが可能ですが、先頭や末尾からの挿入・削除も高速に行えます。
ただし、メモリ上では複数のブロックに分かれているため、キャッシュ効果はvectorよりも低くなります。
#include <iostream>
#include <deque>
int main() {
std::deque<int> dq; // dequeの宣言
dq.push_front(1); // 先頭に1を追加
dq.push_back(2); // 末尾に2を追加
dq.push_back(3); // 末尾に3を追加
// 先頭から順に表示
for (int i = 0; i < dq.size(); i++) {
std::cout << dq[i] << " ";
}
std::cout << std::endl;
dq.pop_front(); // 先頭の要素を削除
// 末尾から順に表示
for (int i = dq.size() - 1; i >= 0; i--) {
std::cout << dq[i] << " ";
}
std::cout << std::endl;
return 0;
}
1 2 3
3 2 このコードでは、dequeに要素を追加し、先頭から順に表示した後、先頭の要素を削除し、末尾から順に表示しています。
list
listは双方向連結リストを表現するためのコンテナです。
先頭や末尾からの挿入・削除が高速である一方で、ランダムアクセスはO(n)と、無視できないレベルで非常に遅くなります。
また、各ノードごとにポインタを持つ必要があるため、メモリ使用量も多くなります。
挿入・削除操作が多い場合や大量の小さなデータを扱う場合に有効です。
#include <iostream>
#include <list>
int main() {
std::list<int> my_list;
//要素の追加
my_list.push_back(1);
my_list.push_back(2);
my_list.push_front(0);
//要素の削除
my_list.pop_back();
my_list.pop_front();
//要素の取得
std::cout << "First element: " << my_list.front() << std::endl;
std::cout << "Last element: " << my_list.back() << std::endl;
//イテレータを使った要素の操作
std::list<int>::iterator it;
for (it = my_list.begin(); it != my_list.end(); ++it) {
std::cout << *it << std::endl;
}
return 0;
}
First element: 1
Last element: 1
1forward_list
forward_listは単方向連結リストを表現するためのコンテナです。
listよりもメモリ使用量が少なくなりますが、逆方向への走査やランダムアクセスは不可能です。
先頭からしか辿れない単方向性を生かした処理(例：先頭への追加・削除)では高速性能を発揮します。
#include <iostream>
#include <forward_list>
int main() {
std::forward_list<int> flist = {1, 2, 3, 4, 5};
// 先頭に要素を追加
flist.push_front(0);
// 特定の要素の後ろに要素を挿入
auto it = flist.begin();
++it;
flist.insert_after(it, 6);
// 先頭の要素を削除
flist.pop_front();
// 全要素の表示
for (int& x : flist) {
std::cout << x << " ";
}
std::cout << std::endl;
return 0;
}
1 6 2 3 4 5 このコードでは、forward_listを使って、リストの先頭に要素を追加したり、特定の要素の後ろに要素を挿入したり、先頭の要素を削除したりしています。
また、forループを使ってリストの全要素を表示しています。単方向でしか参照できないかわりに非常に高速であるため、要素を先頭から順番にアクセスする前提であれば、forward_listが役立ちます。
連想コンテナ
C++のSTLには、データを格納するための様々なコンテナが用意されています。前回はシーケンスコンテナについて解説しましたが、今回は連想コンテナについて解説します。
set
setは、重複を許さずに要素を格納することができるコンテナです。
内部的には二分探索木で実装されており、要素の挿入や削除、検索などが高速に行えます。
また、要素が自動的にソートされるため、昇順で要素を取り出すことができます。
以下はsetの基本的な使い方です。
#include <iostream>
#include <set>
int main() {
std::set<int> s;
// 要素の追加
s.insert(3);
s.insert(1);
s.insert(4);
// 要素の検索
if (s.find(3) != s.end()) {
std::cout << "3 is found" << std::endl;
}
// 全要素の表示
for (auto x : s) {
std::cout << x << " ";
}
}
3 is found
1 3 4 setでは同じ値を格納することはできず、しようとした場合は追加されません。
同じ値の追加も行う場合は、multisetを使用します。
multiset
multisetは、setと同じく重複を許さずに要素を格納することができますが、同じ値を複数格納することができます。そのため、setよりも柔軟な使い方が可能です。基本的な使い方はsetと同じです。
map
mapは、キーと値をペアで格納することができるコンテナです。
内部的には二分探索木で実装されており、キーの検索や値の挿入・削除などが高速に行えます。
また、キーに対して自動的にソートされるため、昇順でキーを取り出すことができます。
以下はmapの基本的な使い方です。
#include <iostream>
#include <map>
int main() {
std::map<std::string, int> m;
// 要素の追加
m["apple"] = 100;
m["banana"] = 200;
m["orange"] = 300;
// 要素の検索
if (m.find("apple") != m.end()) {
std::cout << "price of apple: " << m["apple"] << std::endl;
}
// 全要素の表示
for (auto x : m) {
std::cout << x.first << ": " << x.second << std::endl;
}
}
price of apple: 100
apple: 100
banana: 200
orange: 300mapでは同じキーを複数持つことができません。(m["apple"] = 200とm["apple"] = 100を共存させられない)
同じキーを複数持ちたい場合はmultisetを使用します。
multimap
multimapは、mapと同じくキーと値をペアで格納することができますが、同じキーを複数持つことが出来ます。そのため、mapよりも柔軟な使い方が可能です。基本的な使い方はmapと同じです。
コンテナアダプタ
コンテナアダプタは、既存のコンテナをベースにして新しいインターフェースを提供するものです。STLには、stack、queue、priority_queueという3つのコンテナアダプタがあります。
stack
stackは、LIFO(Last In First Out)データ構造を提供するコンテナアダプタです。
スタックに要素を追加する操作をpushと呼び、最後に追加された要素を取り出す操作をpopと呼びます。
また、スタックの先頭にある要素を参照する操作をtopと呼びます。
以下は、stackの基本的な使い方の例です。
#include <iostream>
#include <stack>
int main() {
std::stack<int> s;
s.push(1);
s.push(2);
s.push(3);
while (!s.empty()) {
std::cout << s.top() << std::endl;
s.pop();
}
return 0;
}
3
2
1この例では、int型の値を格納するスタックsを作成し、1から3までの値をpushしています。
その後、whileループ内でsが空でない限り、s.top()でスタックの先頭にある値を表示し、s.pop()でその値を取り出しています。
queue
queueは、FIFO(First In First Out)データ構造を提供するコンテナアダプタです。
キューに要素を追加する操作をpushと呼び、先頭から要素を取り出す操作をpopと呼びます。
以下は、queueの基本的な使い方の例です。
#include <iostream>
#include <queue>
int main() {
std::queue<int> q;
q.push(1);
q.push(2);
q.push(3);
while (!q.empty()) {
std::cout << q.front() << std::endl;
q.pop();
}
return 0;
}
1
2
3この例では、int型の値を格納するキューqを作成し、1から3までの値をpushしています。その後、whileループ内でqが空でない限り、q.front()でキューの先頭にある値を表示し、q.pop()でその値を取り出しています。
priority_queue
priority_queueは、「優先度付きキュー」とも呼ばれるコンテナアダプタです。
要素が追加される際に自動的にソートされます。
デフォルトでは大きい値から小さい値へソートされますが、std::greater<T>関数オブジェクトや比較関数オブジェクト等指定することも可能です。
以下はpriority_queueの基本的な使い方の例です。
#include <iostream>
#include <queue>
int main() {
std::priority_queue<int> pq;
pq.push(2);
pq.push(5);
pq.push(1);
while (!pq.empty()) {
std::cout << pq.top() << std::endl;
pq.pop();
}
return 0;
}
5
2
1この例ではソート処理を行っていませんが、自動的にpqが降順にソートされているのが確認できます。
その後、pq.top() でキューが空になるまで取得し続けています。
これらのコンテナを活用することで、より効率的に大規模かつ複雑なプログラムも開発できるようになります。