Контейнеры STL

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

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

Последовательные контейнеры поддерживают элементы в определенном порядке:

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

Ассоциативные контейнеры хранят элементы в отсортированном порядке для быстрого поиска:

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

Неупорядоченные контейнеры используют хеш-таблицы для еще более быстрого поиска в среднем случае:

#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: Определите класс GradeManager, который использует несколько контейнеров STL для управления информацией о студентах.
Ваш класс должен использовать:
- std::vector<std::string> для хранения имен студентов в порядке их добавления
- std::map<std::string, int> для связывания имени каждого студента с его оценкой
- std::set<int> для отслеживания всех уникальных оценок, которые были выставлены
Реализуйте следующие методы:
- addStudent(const std::string& name, int grade) — добавляет студента с его оценкой во все три контейнера
- getGrade(const std::string& name) — возвращает оценку для заданного имени студента, используя map
- printRoster() — выводит все имена студентов в порядке их добавления (из вектора), каждое на новой строке
- printGrades() — выводит всех студентов с их оценками в алфавитном порядке (map делает это автоматически), в формате name: grade на каждой строке
- printUniqueGrades() — выводит все уникальные оценки в порядке возрастания (set делает это автоматически), разделенные пробелами, после чего следует символ новой строки
main.cpp: Считайте входные данные и продемонстрируйте, как каждый тип контейнера служит своей цели.
Считайте шесть входных значений (каждое на отдельной строке):
1. Имя первого студента
2. Оценка первого студента (целое число)
3. Имя второго студента
4. Оценка второго студента (целое число)
5. Имя третьего студента
6. Оценка третьего студента (целое число)
Создайте объект GradeManager и добавьте всех трех студентов. Затем продемонстрируйте различное поведение контейнеров:
1. Выведите Roster (insertion order):, а затем вызовите printRoster()
2. Выведите Grades (alphabetical):, а затем вызовите printGrades()
3. Выведите Unique grades:, а затем вызовите printUniqueGrades()
4. Найдите оценку второго студента и выведите <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

Обратите внимание, как вектор сохраняет порядок вставки (Charlie, Alice, Bob), map автоматически сортирует по ключу (Alice, Bob, Charlie), а set хранит только уникальные значения в отсортированном порядке (85 появляется один раз, а не два). Каждый тип контейнера отлично справляется с определенными задачами!

Шпаргалка

Контейнеры STL — это шаблонные классы для хранения и организации коллекций объектов. Каждый тип оптимизирован для различных операций.

Последовательные контейнеры

Поддерживают элементы в определенном порядке:

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

Ассоциативные контейнеры

Хранят элементы в отсортированном порядке для быстрого поиска:

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

Неупорядоченные контейнеры

Используют хеш-таблицы для более быстрого поиска в среднем случае:

#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: Скорость поиска критична, порядок не имеет значения

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

#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: Вывести "Roster (insertion order):" и вызвать printRoster()
    
    // TODO: Вывести "Grades (alphabetical):" и вызвать printGrades()
    
    // TODO: Вывести "Unique grades:" и вызвать printUniqueGrades()
    
    // TODO: Найти оценку второго студента и вывести "<name>'s grade: <grade>"
    
    return 0;
}