Применение контейнеров и алгоритмов STL в C++
Привет, Хабр!
STL — это коллекция компонентов, предназначенных для работы с данными. Включает в себя: контейнеры, алгоритмы, итераторы и функциональные объекты, STL в общем своего рода швейцарский ножик в этом деле. Контейнеры помогают управлять коллекциями данных различных типов, алгоритмы предоставляют общие методы для их обработки, итераторы служат связующим звеном между контейнерами и алгоритмами, а функциональные объекты позволяют гибко настраивать поведение стандартных операций.
Рассмотрим подробнее.
Контейнеры STL
Последовательные контейнеры
std::vector — это динамический массив, который может изменять свой размер во время выполнения программы, это дает быстрый доступ к элементам по индексу, благодаря чему является одним из самых часто используемых контейнеров в C++:
#include
#include
int main() {
std::vector numbers = {1, 2, 3, 4, 5};
numbers.push_back(6); // добавляем элемент в конец
// доступ к элементам
std::cout << "Third element: " << numbers[2] << std::endl;
// итерация по vector
for(int num : numbers) {
std::cout << num << " ";
}
std::cout << std::endl;
return 0;
} std::list — это двусвязный список, который позволяет вставлять и удалять элементы из любой позиции в контейнере. В отличие от vector, list не поддерживает прямой доступ по индексу, но в целом более гибче:
#include
#include
int main() {
std::list numbers = {1, 2, 3, 4, 5};
numbers.push_front(0); // добавляем элемент в начало списка
// удаление элемента
numbers.remove(3);
// итерация по list
for(int num : numbers) {
std::cout << num << " ";
}
std::cout << std::endl;
return 0;
}
std::deque (double-ended queue) — это индексируемая последовательность элементов, которая поддерживает добавление и удаление как с начала, так и с конца контейнера. deque сочетает в себе некоторые из качеств vector и list:
#include
#include
int main() {
std::deque numbers = {2, 3, 4};
numbers.push_front(1); // добавляем элемент в начало
numbers.push_back(5); // дбавляем элемент в конец
// доступ к элементам
std::cout << "First element: " << numbers.front() << std::endl;
std::cout << "Last element: " << numbers.back() << std::endl;
// удаление первого элемента
numbers.pop_front();
// итерация по deque
for(int num : numbers) {
std::cout << num << " ";
}
std::cout << std::endl;
return 0;
} Ассоциативные контейнеры
std::set — это контейнер, который хранит уникальные элементы в отсортированном порядке. Пойдет для задач, где надо быстро проверять наличие элементов, не беспокоясь о дубликатах:
#include
#include
int main() {
std::set numbers = {4, 2, 1, 3, 5};
numbers.insert(6); // добавляем новый элемент
numbers.insert(3); // попытка добавить дубликат без эффекта т.е
// проверяем наличие элемента
if (numbers.find(4) != numbers.end()) {
std::cout << "4 is in the set" << std::endl;
}
// итерация по set
for(int num : numbers) {
std::cout << num << " "; // элементы будут отсортированы
}
std::cout << std::endl;
return 0;
} std::multiset похож на set, но позволяет хранить дубликаты элементов:
#include
#include
int main() {
std::multiset numbers = {5, 2, 1, 3, 2};
numbers.insert(2); // добавляем еще один дубликат
// Итерация по multiset
for(int num : numbers) {
std::cout << num << " "; // дубликаты сохранены
}
std::cout << std::endl;
return 0;
} std::map — это ассоциативный контейнер, который хранит пары ключ-значение в отсортированном порядке. Каждый ключ в map уникален, и его можно использовать для фаст доступа к соответствующему значению:
#include
#include std::multimap работает аналогично map, но позволяет хранить несколько значений для одного ключа:
#include
#include Неупорядоченные контейнеры
std::unordered_set — это контейнер, который хранит уникальные элементы в неупорядоченном виде. Он дает весьма быстрые операции вставки, удаления и поиска за счет использования хеш-таблички:
#include
#include
int main() {
std::unordered_set numbers = {4, 1, 2, 3, 5};
numbers.insert(6); // добавляем новый элемент
numbers.erase(1); // удаляем элемент
// проверяем наличие элемента
if (numbers.find(4) != numbers.end()) {
std::cout << "4 is in the set" << std::endl;
}
// итерация по unordered_set
for(int num : numbers) {
std::cout << num << " ";
}
std::cout << std::endl;
return 0;
} std::unordered_map — это ассоциативный контейнер, который хранит пары ключ-значение в неупорядоченном виде:
#include
#include
int main() {
std::unordered_map fruitCount = {{"apple", 2}, {"banana", 5}};
fruitCount["orange"] = 4; // дбавляем новую пару ключ-значение
// удаление элемента
fruitCount.erase("banana");
// доступ к элементам
std::cout << "Apples: " << fruitCount["apple"] << std::endl;
// итерация по unordered_map
for(const auto& pair : fruitCount) {
std::cout << pair.first << ": " << pair.second << std::endl;
}
return 0;
} Адаптеры контейнеров
std::stack предоставляет функциональность стека, реализуя LIFO. То бишь это означает, что последний добавленный элемент будет первым при извлечении:
#include
#include
int main() {
std::stack numbers;
numbers.push(1); // добавляем элементы
numbers.push(2);
numbers.push(3);
// Извлекаем элементы
while (!numbers.empty()) {
std::cout << numbers.top() << " "; // показываем верхний элемент
numbers.pop(); // удаляем верхний элемент
}
std::cout << std::endl;
return 0;
} std::queue реализует функциональность очереди, следуя FIFO:
#include
#include
int main() {
std::queue numbers;
numbers.push(1); // добавляем элементы
numbers.push(2);
numbers.push(3);
// извлекаем элементы
while (!numbers.empty()) {
std::cout << numbers.front() << " "; // показываем первый элемент
numbers.pop(); // удаляем первый элемент
}
std::cout << std::endl;
return 0;
} std::priority_queue управляет набором элементов так, что самый высокий (или приоритетный) элемент всегда находится на вершине:
#include
#include
int main() {
std::priority_queue numbers;
numbers.push(3);
numbers.push(1);
numbers.push(4);
numbers.push(2);
// иззвлекаем элементы
while (!numbers.empty()) {
std::cout << numbers.top() << " "; // показываем элемент с наивысшим приоритетом
numbers.pop(); // удаляем элемент с наивысшим приоритетом
}
std::cout << std::endl;
return 0;
} Алгоритмы STL
Поиск
Алгоритмы поиска в STL помогают находить элементы в контейнерах. Один из самых базовых — std::find:
#include
#include
#include
int main() {
std::vector data = {1, 2, 3, 4, 5};
auto it = std::find(data.begin(), data.end(), 3);
if (it != data.end()) {
std::cout << "Found: " << *it << std::endl;
} else {
std::cout << "Not found" << std::endl;
}
return 0;
} Сортировка
Сортировка — тоже базовая операция в программировании. STL предлагает std::sort для сортировки:
#include
#include
#include
int main() {
std::vector data = {5, 1, 4, 2, 3};
std::sort(data.begin(), data.end());
for (int n : data) {
std::cout << n << " ";
}
std::cout << std::endl;
return 0;
} Перестановка
Для перестановки элементов STL предлагает std::rotate и std::next_permutation:
#include
#include
#include
int main() {
std::vector data = {1, 2, 3, 4, 5};
std::rotate(data.begin(), data.begin() + 2, data.end());
for (int n : data) {
std::cout << n << " ";
}
std::cout << std::endl;
return 0;
} Копирование
std::copy позволяет копировать элементы из одного контейнера в другой:
#include
#include
#include
#include
int main() {
std::vector src = {1, 2, 3, 4, 5};
std::vector dest(5);
std::copy(src.begin(), src.end(), dest.begin());
for (int n : dest) {
std::cout << n << " ";
}
std::cout << std::endl;
return 0;
} Модификация
Есть так же алгоритмы для модификации элементов, например, std::transform:
#include
#include
#include
int main() {
std::vector data = {1, 2, 3, 4, 5};
std::transform(data.begin(), data.end(), data.begin(),
[](int x) { return x * x; });
for (int n : data) {
std::cout << n << " ";
}
std::cout << std::endl;
return 0;
} Удаление элементов
std::remove и std::remove_if позволяют удалять элементы из контейнера по условию:
#include
#include
#include
int main() {
std::vector data = {1, 2, 3, 4, 5, 6};
auto newEnd = std::remove_if(data.begin(), data.end(),
[](int x) { return x % 2 == 0; });
data.erase(newEnd, data.end());
for (int n : data) {
std::cout << n << " ";
}
std::cout << std::endl;
return 0;
} Несколько примеров применения
Предположим, у нас есть список сотрудников, и мы хотим сначала сгруппировать их по отделам, а затем отсортировать внутри каждой группы по убыванию зарплаты:
#include
#include
#include
#include
struct Employee {
std::string name;
std::string department;
int salary;
// конструктор для удобства
Employee(std::string n, std::string d, int s) : name(n), department(d), salary(s) {}
};
// функция для вывода списка сотрудников
void printEmployees(const std::vector& employees) {
for (const auto& e : employees) {
std::cout << e.name << " from " << e.department << ", Salary: " << e.salary << std::endl;
}
}
int main() {
std::vector employees = {
{"Alice", "Accounting", 50000},
{"Bob", "HR", 45000},
{"Charlie", "IT", 70000},
{"Diana", "Accounting", 55000},
{"Eve", "HR", 48000},
{"Frank", "IT", 52000}
};
// сначала группируем по отделам
std::stable_sort(employees.begin(), employees.end(),
[](const Employee& a, const Employee& b) {
return a.department < b.department;
});
// затем сортируем внутри каждой группы по убыванию зарплаты
std::stable_sort(employees.begin(), employees.end(),
[](const Employee& a, const Employee& b) {
return a.salary > b.salary;
});
printEmployees(employees);
return 0;
} Иногда необходимо удалить все дубликаты из вектора, сохраняя только уникальные элементы:
#include
#include
#include
int main() {
std::vector data = {1, 4, 2, 3, 2, 3, 4, 5, 5, 6};
// сортируем данные
std::sort(data.begin(), data.end());
// удаляем дубликаты
auto last = std::unique(data.begin(), data.end());
data.erase(last, data.end());
for (int n : data) {
std::cout << n << " ";
}
std::cout << std::endl;
return 0;
} Представим, что у нас есть вектор целых чисел, и мы хотим преобразовать каждый элемент вектора, умножив его на 2 и вычтя 1. Это можно сделать с помощью std::transform:
#include
#include
#include
int main() {
std::vector data = {1, 2, 3, 4, 5};
std::vector transformedData(data.size());
std::transform(data.begin(), data.end(), transformedData.begin(),
[](int x) { return x * 2 - 1; });
for (int n : transformedData) {
std::cout << n << " ";
}
std::cout << std::endl;
return 0;
} Немного про итераторы STL
Input итераторы — это самый базовый тип итераторов, поддерживающий чтение последовательного доступа. Можно юзать для однопроходного чтения данных из контейнера:
#include
#include
#include
int main() {
std::vector data = {1, 2, 3, 4, 5};
std::istream_iterator start(std::cin), end; // чтение данных из стандартного ввода
std::vector numbers(start, end); // инициализация вектора считанными числами
for (int n : numbers) {
std::cout << n << " ";
}
std::cout << std::endl;
return 0;
} Output итераторы предназначены для однопроходной записи данных в контейнер:
#include
#include
#include
int main() {
std::ostream_iterator out_it (std::cout,", ");
std::vector data = {1, 2, 3, 4, 5};
std::copy(data.begin(), data.end(), out_it); // вывод данных в стандартный вывод
return 0;
}
Forward итераторы поддерживают чтение и запись с возможностью многократного прохода по элементам:
#include
#include
int main() {
std::forward_list flist = {1, 2, 3, 4, 5};
for (auto it = flist.begin(); it != flist.end(); ++it) {
std::cout << *it << " ";
}
std::cout << std::endl;
return 0;
} Bidirectional итераторы расширяют возможности forward итераторов, добавляя возможность двунаправленного обхода (вперед и назад):
#include
#include
int main() {
std::list l = {1, 2, 3, 4, 5};
for (auto it = l.rbegin(); it != l.rend(); ++it) { // обратный обход
std::cout << *it << " ";
}
std::cout << std::endl;
return 0;
}
Random access итераторы предоставляют все возможности bidirectional итераторов, а также поддерживают прямой доступ к любому элементу за константное время:
#include
#include
int main() {
std::vector v = {1, 2, 3, 4, 5};
std::cout << "Third element: " << v[2] << std::endl; // прямой доступ
std::cout << "Second element using iterator: " << *(v.begin() + 1) << std::endl; // Доступ через итератор
return 0;
} Подведём кратко итоги: STL в C++ позволяет ускорить разработку и повысить качество кода.
Пользуясь случаем, напоминаю про бесплатный вебинар, который пройдёт сегодня вечером в рамках курса OTUS по разработке на C++. На этом уроке участники разберут динамическое выделение памяти на этапе компиляции в C++20. Регистрируйтесь, если актуально.
С полным каталогом курсов можно ознакомиться в каталоге.
