STLコンテナ

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

STL containersは、オブジェクトのコレクションを格納し、整理するテンプレートクラスです。各containerの種類は、異なるaccessパターンや操作に合わせて最適化されています。ニーズに合ったcontainerを選択することで、プログラムのパフォーマンスに大きな影響を与えられます。

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

#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)

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

#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)

順序なし containers はハッシュテーブルを使用するため、平均ケースの検索がさらに高速です：

#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>
次のメソッドをImplementします。
- addStudent(const std::string& name, int grade)：学生とその成績を3つすべてのコンテナに追加します
- getGrade(const std::string& name)：mapを使用して、指定された学生名の成績を返します
- printRoster()：追加された順序で、すべての学生名を1行ずつ（vectorから）出力します
- printGrades()：すべての学生とその成績をalphabetical orderで出力します（mapが自動的に処理します）。各行をname: gradeの形式にします
- printUniqueGrades()：すべての重複しない成績をascending orderで出力します（setが処理します）。成績はスペースで区切り、最後に改行を付けます
main.cpp：入力を読み取り、それぞれのコンテナ型が異なる目的に役立つことを示します。
6つの入力を読み取ります（それぞれ別の行に入力します）。
1. First student name
2. First student grade (integer)
3. Second student name
4. Second student grade (integer)
5. Third student name
6. Third student grade (integer)
GradeManagerをCreateし、3人の学生をすべて追加します。その後、異なるコンテナの動作を示します。
1. Roster (insertion order):を出力し、続けてprintRoster()を呼び出します
2. Grades (alphabetical):を出力し、続けてprintGrades()を呼び出します
3. Unique grades:を出力し、続けてprintUniqueGrades()を呼び出します
4. 2人目の学生の成績をLook upし、<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

vectorはinsertion order（Charlie、Alice、Bob）を保持し、mapはkeyによって自動的にソートし（Alice、Bob、Charlie）、setはソートされた順序で重複しない値だけを格納する（85は2回ではなく1回だけ現れる）ことに注目してください。それぞれのコンテナ型は、異なるタスクで力を発揮します。

自分で試してみよう

#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: Print "Roster (insertion order):" and call printRoster()
    
    // TODO: Print "Grades (alphabetical):" and call printGrades()
    
    // TODO: Print "Unique grades:" and call printUniqueGrades()
    
    // TODO: 2人目の学生の成績を調べて "<name>'s grade: <grade>" を出力する
    
    return 0;
}