Применение контейнеров и алгоритмов STL в C++

Привет, Хабр!

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;
}

Адаптеры контейнеров

std::stack предоставляет функциональность стека, реализуя LIFO . То бишь это означает, что последний добавленный элемент будет первым при извлечении:

#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 реализует функциональность очереди, следуя FIFO:

#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

Поиск

Алгоритмы поиска в 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;
}

Сортировка

Сортировка — тоже базовая операция в программировании. STL предлагает 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;
}

Перестановка

Для перестановки элементов STL предлагает 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;
}

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

Input итераторы — это самый базовый тип итераторов, поддерживающий чтение последовательного доступа. Можно юзать для однопроходного чтения данных из контейнера:

#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;
}

Output итераторы предназначены для однопроходной записи данных в контейнер:

#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;
}

Forward итераторы поддерживают чтение и запись с возможностью многократного прохода по элементам:

#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;
}

Bidirectional итераторы расширяют возможности forward итераторов, добавляя возможность двунаправленного обхода (вперед и назад):

#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;
}

Random access итераторы предоставляют все возможности bidirectional итераторов, а также поддерживают прямой доступ к любому элементу за константное время:

#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;
}

Подведём кратко итоги: STL в C++ позволяет ускорить разработку и повысить качество кода.

Пользуясь случаем, напоминаю про бесплатный вебинар, который пройдёт сегодня вечером в рамках курса OTUS по разработке на C++. На этом уроке участники разберут динамическое выделение памяти на этапе компиляции в C++20. Регистрируйтесь, если актуально.

С полным каталогом курсов можно ознакомиться в каталоге.