Kontenery STL

Część sekcji Programowanie obiektowe ścieżki C++ w Coddy. Lekcja 71 z 104.

Kontenery STL to klasy szablonowe, które przechowują i organizują kolekcje obiektów. Każdy typ kontenera jest zoptymalizowany pod kątem różnych wzorców dostępu i operacji. Wybór odpowiedniego kontenera do Twoich potrzeb może znacząco wpłynąć na wydajność programu.

Kontenery sekwencyjne przechowują elementy w określonej kolejności:

#include <vector>
#include <list>

std::vector<int> vec = {1, 2, 3};  // Tablica dynamiczna, szybki dostęp swobodny
vec.push_back(4);                   // Dodanie na końcu: amortyzowany koszt O(1)
int x = vec[2];                     // Dostęp przez indeks: O(1)

std::list<int> lst = {1, 2, 3};    // Lista dwukierunkowa
lst.push_front(0);                  // Dodanie na początku: O(1)
lst.push_back(4);                   // Dodanie na końcu: O(1)

Kontenery asocjacyjne przechowują elementy w posortowanej kolejności, aby umożliwić szybkie wyszukiwanie:

#include <map>
#include <set>

std::set<int> s = {3, 1, 4, 1};    // Unikalne posortowane elementy: {1, 3, 4}
s.insert(2);                        // Wstawianie: O(log n)
bool found = s.count(3);            // Sprawdzanie istnienia: O(log n)

std::map<std::string, int> ages;   // Pary klucz-wartość, posortowane według klucza
ages["Alice"] = 25;                 // Wstawianie/aktualizacja: O(log n)
ages["Bob"] = 30;
std::cout << ages["Alice"];        // Dostęp: O(log n)

Kontenery nieuporządkowane używają tablic mieszających, aby zapewnić jeszcze szybsze wyszukiwanie w przypadku średnim:

#include <unordered_map>

std::unordered_map<std::string, int> scores;
scores["player1"] = 100;            // Wstawianie: średnio O(1)
scores["player2"] = 200;
std::cout << scores["player1"];    // Dostęp: średnio O(1)

Używaj vector, gdy potrzebujesz szybkiego dostępu swobodnego, list przy częstym wstawianiu elementów w środku, map/set, gdy potrzebujesz uporządkowanych danych, oraz unordered_map, gdy szybkość wyszukiwania ma kluczowe znaczenie, a kolejność nie ma znaczenia.

Wyzwanie

Łatwy

Stwórzmy system zarządzania ocenami uczniów, który pokazuje, jak różne kontenery STL służą różnym celom. Użyjesz wielu typów kontenerów, aby efektywnie organizować dane uczniów, dobierając odpowiedni kontener do każdego zadania.

Utworzysz dwa pliki, aby uporządkować swój kod:

GradeManager.h: Zdefiniuj klasę GradeManager, która używa wielu kontenerów STL do zarządzania informacjami o uczniach.
Twoja klasa powinna używać:
- std::vector<std::string> do przechowywania imion i nazwisk uczniów w kolejności ich dodania
- std::map<std::string, int> do powiązania imienia i nazwiska każdego ucznia z jego oceną
- std::set<int> do śledzenia wszystkich unikalnych przypisanych ocen
Zaimplementuj te metody:
- addStudent(const std::string& name, int grade): dodaje ucznia wraz z jego oceną do wszystkich trzech kontenerów
- getGrade(const std::string& name): zwraca ocenę danego ucznia na podstawie jego imienia i nazwiska, używając mapy
- printRoster(): wypisuje imiona i nazwiska wszystkich uczniów w kolejności ich dodania (z wektora), każde w nowym wierszu
- printGrades(): wypisuje wszystkich uczniów wraz z ich ocenami w kolejności alfabetycznej (mapa sortuje je automatycznie), w formacie name: grade, każdy wpis w osobnym wierszu
- printUniqueGrades(): wypisuje wszystkie unikalne oceny w kolejności rosnącej (set zajmuje się tym automatycznie), oddzielone spacjami, po czym wypisuje znak nowej linii
main.cpp: Wczytaj dane i pokaż, jak każdy typ kontenera służy innemu celowi.
Wczytaj sześć danych wejściowych (każdą w osobnym wierszu):
1. Imię i nazwisko pierwszego ucznia
2. Ocena pierwszego ucznia (liczba całkowita)
3. Imię i nazwisko drugiego ucznia
4. Ocena drugiego ucznia (liczba całkowita)
5. Imię i nazwisko trzeciego ucznia
6. Ocena trzeciego ucznia (liczba całkowita)
Utwórz obiekt GradeManager i dodaj wszystkich trzech uczniów. Następnie pokaż różne zachowania kontenerów:
1. Wypisz Roster (insertion order):, a następnie wywołaj printRoster()
2. Wypisz Grades (alphabetical):, a następnie wywołaj printGrades()
3. Wypisz Unique grades:, a następnie wywołaj printUniqueGrades()
4. Odczytaj ocenę drugiego ucznia i wypisz <name>'s grade: <grade>

Na przykład dla danych wejściowych 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

Zwróć uwagę, że wektor zachowuje kolejność dodawania (Charlie, Alice, Bob), mapa automatycznie sortuje według klucza (Alice, Bob, Charlie), a zbiór przechowuje tylko unikalne wartości w posortowanej kolejności (85 pojawia się raz, a nie dwa razy). Każdy typ kontenera sprawdza się w innych zadaniach!

Spróbuj swoich sił

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

using namespace std;

int main() {
    // Wczytaj dane trzech uczniów
    string name1, name2, name3;
    int grade1, grade2, grade3;
    
    cin >> name1;
    cin >> grade1;
    cin >> name2;
    cin >> grade2;
    cin >> name3;
    cin >> grade3;
    
    // TODO: Utwórz obiekt GradeManager
    
    // TODO: Dodaj wszystkich trzech uczniów do GradeManager
    
    // TODO: Wypisz "Roster (insertion order):" i wywołaj printRoster()
    
    // TODO: Wypisz "Grades (alphabetical):" i wywołaj printGrades()
    
    // TODO: Wypisz "Unique grades:" i wywołaj printUniqueGrades()
    
    // TODO: Znajdź ocenę drugiego ucznia i wypisz "<name>'s grade: <grade>"
    
    return 0;
}