STL-Container

Teil des Abschnitts Objektorientierte Programmierung der C++-Journey von Coddy — Lektion 71 von 104.

STL-Container sind Template-Klassen, die Sammlungen von Objekten speichern und organisieren. Jeder Containertyp ist für unterschiedliche Zugriffsmuster und Operationen optimiert. Die Wahl des richtigen Containers für Ihre Bedürfnisse kann die Leistung Ihres Programms erheblich beeinflussen.

Sequenzcontainer behalten Elemente in einer bestimmten Reihenfolge bei:

#include <vector>
#include <list>

std::vector<int> vec = {1, 2, 3};  // Dynamisches Array, schneller Direktzugriff
vec.push_back(4);                   // Am Ende hinzufügen: O(1) amortisiert
int x = vec[2];                     // Zugriff über Index: O(1)

std::list<int> lst = {1, 2, 3};    // Doppelt verkettete Liste
lst.push_front(0);                  // Am Anfang hinzufügen: O(1)
lst.push_back(4);                   // Am Ende hinzufügen: O(1)

Assoziative Container speichern Elemente in sortierter Reihenfolge für eine schnelle Suche:

#include <map>
#include <set>

std::set<int> s = {3, 1, 4, 1};    // Eindeutige sortierte Elemente: {1, 3, 4}
s.insert(2);                        // Einfügen: O(log n)
bool found = s.count(3);            // Existenz prüfen: O(log n)

std::map<std::string, int> ages;   // Schlüssel-Wert-Paare, sortiert nach Schlüssel
ages["Alice"] = 25;                 // Einfügen/Aktualisieren: O(log n)
ages["Bob"] = 30;
std::cout << ages["Alice"];        // Zugriff: O(log n)

Ungeordnete Container verwenden Hash-Tabellen für eine noch schnellere Suche im Durchschnittsfall:

#include <unordered_map>

std::unordered_map<std::string, int> scores;
scores["player1"] = 100;            // Einfügen: O(1) im Durchschnitt
scores["player2"] = 200;
std::cout << scores["player1"];    // Zugriff: O(1) im Durchschnitt

Verwenden Sie vector, wenn Sie schnellen wahlfreien Zugriff benötigen, list für häufige Einfügungen in der Mitte, map/set, wenn Sie sortierte Daten benötigen, und unordered_map, wenn die Suchgeschwindigkeit entscheidend ist und die Reihenfolge keine Rolle spielt.

Aufgabe

Einfach

Lassen Sie uns ein Notenverwaltungssystem für Schüler erstellen, das zeigt, wie verschiedene STL-Container unterschiedliche Zwecke erfüllen. Sie werden mehrere Containertypen verwenden, um Schülerdaten effizient zu organisieren, wobei Sie für jede Aufgabe den richtigen Container auswählen.

Sie werden zwei Dateien erstellen, um Ihren Code zu organisieren:

GradeManager.h: Definieren Sie eine Klasse GradeManager, die mehrere STL-Container verwendet, um Schülerinformationen zu verwalten.
Ihre Klasse sollte Folgendes verwenden:
- Einen std::vector<std::string>, um Schülernamen in der Reihenfolge zu speichern, in der sie hinzugefügt wurden
- Eine std::map<std::string, int>, um jeden Schülernamen mit seiner Note zu verknüpfen
- Ein std::set<int>, um alle eindeutigen Noten zu verfolgen, die vergeben wurden
Implementieren Sie diese Methoden:
- addStudent(const std::string& name, int grade) — fügt einen Schüler mit seiner Note zu allen drei Containern hinzu
- getGrade(const std::string& name) — gibt die Note für einen bestimmten Schülernamen unter Verwendung der Map zurück
- printRoster() — gibt alle Schülernamen in der Reihenfolge aus, in der sie hinzugefügt wurden (aus dem Vector), jeweils in einer neuen Zeile
- printGrades() — gibt alle Schüler mit ihren Noten in alphabetischer Reihenfolge aus (die Map erledigt dies automatisch), formatiert als name: grade in jeder Zeile
- printUniqueGrades() — gibt alle eindeutigen Noten in aufsteigender Reihenfolge aus (das Set erledigt dies), getrennt durch Leerzeichen, gefolgt von einem Zeilenumbruch
main.cpp: Lesen Sie Eingaben ein und demonstrieren Sie, wie jeder Containertyp einem anderen Zweck dient.
Lesen Sie sechs Eingaben ein (jede in einer separaten Zeile):
1. Name des ersten Schülers
2. Note des ersten Schülers (Ganzzahl)
3. Name des zweiten Schülers
4. Note des zweiten Schülers (Ganzzahl)
5. Name des dritten Schülers
6. Note des dritten Schülers (Ganzzahl)
Erstellen Sie einen GradeManager und fügen Sie alle drei Schüler hinzu. Demonstrieren Sie dann die verschiedenen Container-Verhaltensweisen:
1. Geben Sie Roster (insertion order): aus, gefolgt vom Aufruf von printRoster()
2. Geben Sie Grades (alphabetical): aus, gefolgt vom Aufruf von printGrades()
3. Geben Sie Unique grades: aus, gefolgt vom Aufruf von printUniqueGrades()
4. Suchen Sie die Note des zweiten Schülers und geben Sie <name>'s grade: <grade> aus

Zum Beispiel mit den Eingaben 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

Beachten Sie, wie der Vector die Einfügereihenfolge beibehält (Charlie, Alice, Bob), die Map automatisch nach Schlüsseln sortiert (Alice, Bob, Charlie) und das Set nur eindeutige Werte in sortierter Reihenfolge speichert (85 erscheint einmal, nicht zweimal). Jeder Containertyp glänzt bei unterschiedlichen Aufgaben!

Spickzettel

STL-Container sind Template-Klassen zum Speichern und Organisieren von Objektsammlungen. Jeder Typ ist für unterschiedliche Operationen optimiert.

Sequenzielle Container

Behalten Elemente in einer bestimmten Reihenfolge bei:

#include <vector>
#include <list>

std::vector<int> vec = {1, 2, 3};  // Dynamisches Array, schneller Direktzugriff
vec.push_back(4);                   // Am Ende hinzufügen: O(1) amortisiert
int x = vec[2];                     // Zugriff über Index: O(1)

std::list<int> lst = {1, 2, 3};    // Doppelt verkettete Liste
lst.push_front(0);                  // Am Anfang hinzufügen: O(1)
lst.push_back(4);                   // Am Ende hinzufügen: O(1)

Assoziative Container

Speichern Elemente in sortierter Reihenfolge für schnelles Nachschlagen:

#include <map>
#include <set>

std::set<int> s = {3, 1, 4, 1};    // Eindeutige sortierte Elemente: {1, 3, 4}
s.insert(2);                        // Einfügen: O(log n)
bool found = s.count(3);            // Existenz prüfen: O(log n)

std::map<std::string, int> ages;   // Schlüssel-Wert-Paare, nach Schlüssel sortiert
ages["Alice"] = 25;                 // Einfügen/Aktualisieren: O(log n)
ages["Bob"] = 30;
std::cout << ages["Alice"];        // Zugriff: O(log n)

Ungeordnete Container

Verwenden Hash-Tabellen für schnelleres Nachschlagen im Durchschnittsfall:

#include <unordered_map>

std::unordered_map<std::string, int> scores;
scores["player1"] = 100;            // Einfügen: O(1) im Durchschnitt
scores["player2"] = 200;
std::cout << scores["player1"];    // Zugriff: O(1) im Durchschnitt

Den richtigen Container auswählen

vector: Schneller Direktzugriff
list: Häufige Einfügungen in der Mitte
map/set: Sortierte Daten benötigt
unordered_map: Nachschlagegeschwindigkeit kritisch, Reihenfolge spielt keine Rolle

Probier es selbst

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

using namespace std;

int main() {
    // Eingaben für drei Studenten lesen
    string name1, name2, name3;
    int grade1, grade2, grade3;
    
    cin >> name1;
    cin >> grade1;
    cin >> name2;
    cin >> grade2;
    cin >> name3;
    cin >> grade3;
    
    // TODO: Ein GradeManager-Objekt erstellen
    
    // TODO: Alle drei Studenten zum GradeManager hinzufügen
    
    // TODO: "Roster (insertion order):" ausgeben und printRoster() aufrufen
    
    // TODO: "Grades (alphabetical):" ausgeben und printGrades() aufrufen
    
    // TODO: "Unique grades:" ausgeben und printUniqueGrades() aufrufen
    
    // TODO: Die Note des zweiten Studenten nachschlagen und "<name>'s grade: <grade>" ausgeben
    
    return 0;
}