Привет, Хабр!
STL — это коллекция компонентов, предназначенных для работы с данными. Включает в себя: контейнеры, алгоритмы, итераторы и функциональные объекты, STL в общем своего рода швейцарский ножик в этом деле. Контейнеры помогают управлять коллекциями данных различных типов, алгоритмы предоставляют общие методы для их обработки, итераторы служат связующим звеном между контейнерами и алгоритмами, а функциональные объекты позволяют гибко настраивать поведение стандартных операций.
Рассмотрим подробнее.
Контейнеры STL
Последовательные контейнеры
std::vector — это динамический массив, который может изменять свой размер во время выполнения программы, это дает быстрый доступ к элементам по индексу, благодаря чему является одним из самых часто используемых контейнеров в C++:
#include <iostream> #include <vector> int main() { std::vector<int> 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 <iostream> #include <list> int main() { std::list<int> 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 <iostream> #include <deque> int main() { std::deque<int> 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 <iostream> #include <set> int main() { std::set<int> 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 <iostream> #include <set> int main() { std::multiset<int> 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 <iostream> #include <map> int main() { std::map<std::string, int> fruitCount = {{"apple", 2}, {"banana", 5}}; fruitCount["orange"] = 4; // Добавляем новую пару ключ-значение // доступ к элементам std::cout << "Apples: " << fruitCount["apple"] << std::endl; // итерация по map for(const auto& pair : fruitCount) { std::cout << pair.first << ": " << pair.second << std::endl; } return 0; }std::multimap работает аналогично map, но позволяет хранить несколько значений для одного ключа:
#include <iostream> #include <map> int main() { std::multimap<std::string, int> fruitCount = {{"apple", 2}, {"apple", 3}, {"banana", 5}}; fruitCount.insert({"apple", 1}); // добавляем еще одно значение для ключа "apple" // итерация по multimap auto range = fruitCount.equal_range("apple"); for(auto it = range.first; it != range.second; ++it) { std::cout << it->first << ": " << it->second << std::endl; } return 0; }Неупорядоченные контейнеры
std::unordered_set — это контейнер, который хранит уникальные элементы в неупорядоченном виде. Он дает весьма быстрые операции вставки, удаления и поиска за счет использования хеш-таблички:
#include <iostream> #include <unordered_set> int main() { std::unordered_set<int> 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 <iostream> #include <unordered_map> int main() { std::unordered_map<std::string, int> 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; }Адаптеры контейнеров
Алгоритмы поиска в STL помогают находить элементы в контейнерах. Один из самых базовых — Сортировка — тоже базовая операция в программировании. STL предлагает Для перестановки элементов STL предлагает Есть так же алгоритмы для модификации элементов, например, Предположим, у нас есть список сотрудников, и мы хотим сначала сгруппировать их по отделам, а затем отсортировать внутри каждой группы по убыванию зарплаты: Иногда необходимо удалить все дубликаты из вектора, сохраняя только уникальные элементы: Представим, что у нас есть вектор целых чисел, и мы хотим преобразовать каждый элемент вектора, умножив его на 2 и вычтя 1. Это можно сделать с помощью Input итераторы — это самый базовый тип итераторов, поддерживающий чтение последовательного доступа. Можно юзать для однопроходного чтения данных из контейнера: Output итераторы предназначены для однопроходной записи данных в контейнер: Forward итераторы поддерживают чтение и запись с возможностью многократного прохода по элементам: Bidirectional итераторы расширяют возможности forward итераторов, добавляя возможность двунаправленного обхода (вперед и назад): Random access итераторы предоставляют все возможности bidirectional итераторов, а также поддерживают прямой доступ к любому элементу за константное время: Подведём кратко итоги: STL в C++ позволяет ускорить разработку и повысить качество кода. Пользуясь случаем, напоминаю про бесплатный вебинар, который пройдёт сегодня вечером в рамках курса OTUS по разработке на C++. На этом уроке участники разберут динамическое выделение памяти на этапе компиляции в C++20. Регистрируйтесь, если актуально. С полным каталогом курсов можно ознакомиться в каталоге. std::stack предоставляет функциональность стека, реализуя #include <iostream> #include <stack> int main() { std::stack<int> 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 реализует функциональность очереди, следуя #include <iostream> #include <queue> int main() { std::queue<int> 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 <iostream> #include <queue> int main() { std::priority_queue<int> 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
Поиск
std::find:#include <algorithm> #include <vector> #include <iostream> int main() { std::vector<int> 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; }Сортировка
std::sort для сортировки:#include <algorithm> #include <vector> #include <iostream> int main() { std::vector<int> 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; }Перестановка
std::rotate и std::next_permutation:#include <algorithm> #include <vector> #include <iostream> int main() { std::vector<int> 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 <algorithm> #include <vector> #include <iostream> #include <iterator> int main() { std::vector<int> src = {1, 2, 3, 4, 5}; std::vector<int> 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 <algorithm> #include <vector> #include <iostream> int main() { std::vector<int> 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 <algorithm> #include <vector> #include <iostream> int main() { std::vector<int> 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 <algorithm> #include <iostream> #include <vector> #include <string> 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<Employee>& employees) { for (const auto& e : employees) { std::cout << e.name << " from " << e.department << ", Salary: " << e.salary << std::endl; } } int main() { std::vector<Employee> 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 <algorithm> #include <vector> #include <iostream> int main() { std::vector<int> 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; }std::transform:#include <algorithm> #include <vector> #include <iostream> int main() { std::vector<int> data = {1, 2, 3, 4, 5}; std::vector<int> 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
#include <iostream> #include <vector> #include <iterator> int main() { std::vector<int> data = {1, 2, 3, 4, 5}; std::istream_iterator<int> start(std::cin), end; // чтение данных из стандартного ввода std::vector<int> numbers(start, end); // инициализация вектора считанными числами for (int n : numbers) { std::cout << n << " "; } std::cout << std::endl; return 0; }#include <iostream> #include <iterator> #include <algorithm> int main() { std::ostream_iterator<int> out_it (std::cout,", "); std::vector<int> data = {1, 2, 3, 4, 5}; std::copy(data.begin(), data.end(), out_it); // вывод данных в стандартный вывод return 0; } #include <forward_list> #include <iostream> int main() { std::forward_list<int> flist = {1, 2, 3, 4, 5}; for (auto it = flist.begin(); it != flist.end(); ++it) { std::cout << *it << " "; } std::cout << std::endl; return 0; }#include <list> #include <iostream> int main() { std::list<int> l = {1, 2, 3, 4, 5}; for (auto it = l.rbegin(); it != l.rend(); ++it) { // обратный обход std::cout << *it << " "; } std::cout << std::endl; return 0; }#include <vector> #include <iostream> int main() { std::vector<int> 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; }
ссылка на оригинал статьи https://habr.com/ru/articles/793278/
Добавить комментарий