Контейнеры STL

Часть раздела Объектно-ориентированное программирование путешествия по C++ на Coddy. Урок 71 из 104.

STL containers — это шаблонные классы, которые хранят и организуют коллекции объектов. each тип containers оптимизирован для различных шаблонов access и операций. Выбор подходящего контейнера для ваших потребностей может значительно повлиять на производительность вашей программы.

containers поддерживают elements в определённом порядке:

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

Ассоциативные containers хранят 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 служат разным целям. Вы будете использовать несколько типов контейнеров для эффективной организации данных студентов, выбирая подходящий контейнер для каждой задачи.

Вы создадите два файла для организации кода:

GradeManager.h: Define GradeManager class, которая использует несколько контейнеров STL для управления информацией о студентах.
Ваш class должен использовать:
- std::vector<std::string> для хранения имён студентов в порядке, в котором они были добавлены
- std::map<std::string, int> для связывания имени каждого студента с его оценкой
- std::set<int> для отслеживания всех уникальных оценок, которые были назначены
Implement следующие методы:
- addStudent(const std::string& name, int grade): добавляет студента с его оценкой во все три контейнера
- getGrade(const std::string& name): возвращает оценку для заданного имени студента, используя map
- printRoster(): выводит все имена студентов в порядке их добавления (из vector), каждое с новой строки
- printGrades(): выводит всех студентов с их оценками в алфавитном порядке (map обрабатывает это автоматически), в формате name: grade в каждой строке
- printUniqueGrades(): выводит все уникальные оценки в ascending порядке (set обрабатывает это), разделённые пробелами, а затем перевод строки
main.cpp: Прочитайте inputs и продемонстрируйте, как каждый тип контейнера служит отдельной цели.
Прочитайте шесть inputs (каждый в отдельной строке):
1. Имя первого студента
2. Оценка первого студента (целое число)
3. Имя второго студента
4. Оценка второго студента (целое число)
5. Имя третьего студента
6. Оценка третьего студента (целое число)
Create GradeManager и добавьте всех трёх студентов. Затем продемонстрируйте различия в поведении контейнеров:
1. Выведите Roster (insertion order):, затем вызовите printRoster()
2. Выведите Grades (alphabetical):, затем вызовите printGrades()
3. Выведите Unique grades:, затем вызовите printUniqueGrades()
4. Look оценку второго студента и выведите <name>'s grade: <grade>

Например, для inputs 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 (Charlie, Alice, Bob), map автоматически сортирует по Key (Alice, Bob, Charlie), а set хранит только уникальные значения в отсортированном порядке (85 появляется один раз, а не два). Каждый тип контейнера особенно хорошо подходит для разных задач!

Попробуйте сами

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

using namespace std;

int main() {
    // Считать входные данные для трёх студентов
    string name1, name2, name3;
    int grade1, grade2, grade3;
    
    cin >> name1;
    cin >> grade1;
    cin >> name2;
    cin >> grade2;
    cin >> name3;
    cin >> grade3;
    
    // TODO: Создать объект GradeManager
    
    // TODO: Добавить всех трёх студентов в GradeManager
    
    // TODO: Print "Roster (insertion order):" and call printRoster()
    
    // TODO: Print "Grades (alphabetical):" and call printGrades()
    
    // TODO: Print "Unique grades:" and call printUniqueGrades()
    
    // TODO: Найти оценку второго студента и вывести "<name>'s grade: <grade>"
    
    return 0;
}