STLコンテナ

CoddyのC++ジャーニー「オブジェクト指向プログラミング」セクションの一部 — レッスン 71/104。

STLコンテナは、オブジェクトのコレクションを格納し、整理するテンプレートクラスです。各コンテナタイプは、異なるアクセスパターンや操作に最適化されています。ニーズに適したコンテナを選択することは、プログラムのパフォーマンスに大きな影響を与える可能性があります。

シーケンスコンテナは、要素を特定の順序で保持します：

#include <vector>
#include <list>

std::vector<int> vec = {1, 2, 3};  // 動的配列、高速なランダムアクセス
vec.push_back(4);                   // 末尾に追加：ならし計算量 O(1)
int x = vec[2];                     // インデックスによるアクセス：O(1)

std::list<int> lst = {1, 2, 3};    // 双方向連結リスト
lst.push_front(0);                  // 先頭に追加：O(1)
lst.push_back(4);                   // 末尾に追加：O(1)

連想コンテナは、高速な検索のために要素をソートされた順序で格納します：

#include <map>
#include <set>

std::set<int> s = {3, 1, 4, 1};    // 一意でソートされた要素: {1, 3, 4}
s.insert(2);                        // 挿入: O(log n)
bool found = s.count(3);            // 存在確認: O(log n)

std::map<std::string, int> ages;   // キーでソートされたキーと値のペア
ages["Alice"] = 25;                 // 挿入/更新: O(log n)
ages["Bob"] = 30;
std::cout << ages["Alice"];        // アクセス: O(log n)

順序なしコンテナは、ハッシュテーブルを使用して、平均的なケースでの検索をさらに高速化します：

#include <unordered_map>

std::unordered_map<std::string, int> scores;
scores["player1"] = 100;            // 挿入: 平均 O(1)
scores["player2"] = 200;
std::cout << scores["player1"];    // アクセス: 平均 O(1)

高速なランダムアクセスが必要な場合は vector を、途中の挿入が頻繁に行われる場合は list を、ソートされたデータが必要な場合は map/set を、そして検索速度が重要で順序が問われない場合は unordered_map を使用してください。

チャレンジ

簡単

異なる目的のために異なるSTLコンテナがどのように役立つかを示す、学生の成績管理システムを構築しましょう。複数のコンテナタイプを使用して学生データを効率的に整理し、各タスクに適切なコンテナを選択します。

コードを整理するために2つのファイルを作成します：

GradeManager.h: 複数のSTLコンテナを使用して学生情報を管理する GradeManager クラスを定義します。
クラスでは以下を使用する必要があります：
- 追加された順序で学生名を保存するための std::vector<std::string>
- 各学生名と成績を関連付けるための std::map<std::string, int>
- 割り当てられたすべてのユニークな成績を追跡するための std::set<int>
以下のメソッドを実装してください：
- addStudent(const std::string& name, int grade) — 学生とその成績を3つすべてのコンテナに追加します
- getGrade(const std::string& name) — マップを使用して、指定された学生名の成績を返します
- printRoster() — 追加された順序（ベクターから）ですべての学生名を、それぞれ新しい行に出力します
- printGrades() — すべての学生と成績をアルファベット順（マップがこれを自動的に処理します）で、各行に name: grade の形式で出力します
- printUniqueGrades() — すべてのユニークな成績を昇順（セットがこれを処理します）で、スペースで区切って出力し、最後に改行を入れます
main.cpp: 入力を読み取り、各コンテナタイプがどのように異なる目的を果たすかを示します。
6つの入力（それぞれ別の行）を読み取ります：
1. 1人目の学生の名前
2. 1人目の学生の成績（整数）
3. 2人目の学生の名前
4. 2人目の学生の成績（整数）
5. 3人目の学生の名前
6. 3人目の学生の成績（整数）
GradeManager を作成し、3人すべての学生を追加します。次に、異なるコンテナの動作を示します：
1. Roster (insertion order): と出力し、続いて printRoster() を呼び出します
2. Grades (alphabetical): と出力し、続いて printGrades() を呼び出します
3. Unique grades: と出力し、続いて printUniqueGrades() を呼び出します
4. 2人目の学生の成績を検索し、<name>'s grade: <grade> と出力します

例えば、入力が Charlie, 85, Alice, 90, Bob, 85 の場合：

Roster (insertion order):
Charlie
Alice
Bob
Grades (alphabetical):
Alice: 90
Bob: 85
Charlie: 85
Unique grades:
85 90 
Alice's grade: 90

ベクターが挿入順序（Charlie, Alice, Bob）を保持し、マップがキー（Alice, Bob, Charlie）で自動的にソートし、セットがユニークな値のみをソートされた順序で保存（85は2回ではなく1回表示される）していることに注目してください。各コンテナタイプは異なるタスクに優れています！

チートシート

STLコンテナは、オブジェクトのコレクションを格納および整理するためのテンプレートクラスです。各タイプは、異なる操作に対して最適化されています。

シーケンスコンテナ

要素を特定の順序で保持します：

#include <vector>
#include <list>

std::vector<int> vec = {1, 2, 3};  // 動的配列、高速なランダムアクセス
vec.push_back(4);                   // 末尾に追加：ならし計算量 O(1)
int x = vec[2];                     // インデックスによるアクセス：O(1)

std::list<int> lst = {1, 2, 3};    // 双方向連結リスト
lst.push_front(0);                  // 先頭に追加：O(1)
lst.push_back(4);                   // 末尾に追加：O(1)

連想コンテナ

高速な検索のために、要素をソートされた順序で格納します：

#include <map>
#include <set>

std::set<int> s = {3, 1, 4, 1};    // ユニークでソートされた要素：{1, 3, 4}
s.insert(2);                        // 挿入：O(log n)
bool found = s.count(3);            // 存在確認：O(log n)

std::map<std::string, int> ages;   // キーと値のペア、キーでソート
ages["Alice"] = 25;                 // 挿入/更新：O(log n)
ages["Bob"] = 30;
std::cout << ages["Alice"];        // アクセス：O(log n)

非順序コンテナ

平均的なケースでより高速な検索を行うために、ハッシュテーブルを使用します：

#include <unordered_map>

std::unordered_map<std::string, int> scores;
scores["player1"] = 100;            // 挿入：平均 O(1)
scores["player2"] = 200;
std::cout << scores["player1"];    // アクセス：平均 O(1)

適切なコンテナの選択

vector: 高速なランダムアクセス
list: 頻繁な中間への挿入
map/set: ソートされたデータが必要な場合
unordered_map: 検索速度が重要で、順序が関係ない場合

自分で試してみよう

#include <iostream>
#include <string>
#include "GradeManager.h"

using namespace std;

int main() {
    // 3人の学生の入力を読み込む
    string name1, name2, name3;
    int grade1, grade2, grade3;
    
    cin >> name1;
    cin >> grade1;
    cin >> name2;
    cin >> grade2;
    cin >> name3;
    cin >> grade3;
    
    // TODO: GradeManager オブジェクトを作成する
    
    // TODO: 3人すべての学生を GradeManager に追加する
    
    // TODO: "Roster (insertion order):" を出力し、printRoster() を呼び出す
    
    // TODO: "Grades (alphabetical):" を出力し、printGrades() を呼び出す
    
    // TODO: "Unique grades:" を出力し、printUniqueGrades() を呼び出す
    
    // TODO: 2番目の学生の成績を検索し、"<name>'s grade: <grade>" を出力する
    
    return 0;
}