C++のmap STLを使って学生の出席番号と名前を管理するプログラム

本記事では、C++のmapコンテナ(STL)を使用して、学生の出席番号(整数型)と名前(文字列型)を管理するプログラムを紹介します。

標準入力からn個のクエリが与えられます。各クエリ(各行)は基本的に2つの要素で構成され、タイプ1のクエリの場合は3つの要素になります。1番目の要素は操作の種類、2番目の要素は出席番号、そしてタイプ1の場合のみ3番目の要素として名前が与えられます。

操作の種類

• 挿入(Insert):指定された出席番号に対応するキーとして、名前をマップに登録します。
• 削除(Delete):指定された出席番号に対応するエントリをマップから削除します(存在する場合)。
• 検索(Search):指定された出席番号でマップ内の名前を検索します。見つかれば名前を表示し、存在しない場合は「Not found」と表示します。

入出力の例

例えば、n = 8 で queries = [[1,5,"Atanu"], [1,8,"Tapan"], [1,3,"Manish"], [2,8], [1,9,"Piyali"], [3,8], [3,3], [3,5]] の場合、出力は [Not found, Manish, Atanu] となります。これは、出席番号8が削除済みのため存在せず、出席番号3の学生の名前が「Manish」、出席番号5の学生の名前が「Atanu」であるためです。

解法のアプローチ

この問題を解くためには、以下の手順に従います。

• n := クエリの総数を受け取る
• キーが整数型、値が文字列型のマップ m を定義する
• n が0になるまで以下を繰り返す:
  • 現在のクエリタイプ t を読み込む
  • 出席番号 roll を読み込む
  • t が1の場合:
    • 名前を読み込み、m[roll] に代入する
  • t が2の場合:
    • m[roll] に空文字列を代入する(削除扱い)
  • それ以外の場合(検索):
    • m[roll] が空文字列でなければ、その内容を表示する
    • 空文字列であれば「Not found」を表示する

実装例

理解を深めるために、以下の実装を見てみましょう。

#include <iostream>
#include <map>
using namespace std;
int main(){
    int n;
    cin >> n;
    map<int, string> m;
    while (n--) {
        int t;
        cin >> t;
        int roll;
        cin >> roll;
        if (t == 1) {
            string name;
            cin >> name;
            m[roll] = name;
        } else if (t == 2) {
            m[roll] = "";
        } else {
            if(m[roll] != "")
                cout << m[roll] << endl;
            else
                cout << "Not found" << endl;
        }
    }
}

入力例

8
1 5 Atanu
1 8 Tapan
1 3 Manish
2 8
1 9 Piyali
3 8
3 3
3 5

出力例

Not found
Manish
Atanu

C++のmapは内部で平衡二分探索木(赤黒木)を使用しているため、挿入・削除・検索のすべての操作がO(log n)の計算量で実行できます。この特性により、大量の学生データを効率的に管理することが可能です。