Application of STL containers and algorithms in C++

Hello, Habre!

STL – this collection componentsintended for working with data. Includes: containers, algorithms, iterators and functional objects, STL is generally a kind of Swiss army knife in this matter. Containers help to manage collections of data of various types, algorithms provide general methods of their processing, iterators serve as a connecting link between containers and algorithms, and functional objects allow you to flexibly configure the behavior of standard operations.

Let’s consider in more detail.

Contents

1 STL containers
2 STL algorithms
3 A bit about STL iterators

STL containers

Sequential containers

std::vector is a dynamic array that can change its size during program execution, it allows quick access to elements by index, making it one of the most commonly used containers in 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 is a doubly linked list that allows you to insert and remove elements from any position in the container. Unlike vector, list does not support direct access by index, but generally more flexible:

#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) is an indexed sequence of elements that supports addition and deletion from both the beginning and the end of the container. deque combines some of the qualities vector and 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;
}

Associative containers

std::set – This is a container that stores unique items in a sorted order. Suitable for tasks where you need to quickly check the presence of elements without worrying about duplicates:

#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 similar to setbut allows you to store duplicate elements:

#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 is an associative container that stores key-value pairs in sorted order. Each key in map is unique and can be used to quickly access the corresponding value:

#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 works similarly mapbut allows you to store multiple values of the same key:

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

Unordered containers

std::unordered_set – This is a container that stores unique elements in an unordered form. It provides very fast insertion, deletion and search operations by using a hash table:

#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 is an associative container that stores key-value pairs in an unordered form:

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

Container adapters

std::stack provides stack functionality by implementing LIFO . That is, this means that the last element added will be the first when removed:

#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 implements the queue functionality by following 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 manipulates a set of elements so that the highest (or priority) element is always on top:

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

Search

Search algorithms in STL help find elements in containers. One of the most basic — 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;
}

Sorting

Sorting is also a basic operation in programming. STL offers std::sort to 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;
}

Permutation

STL offers to rearrange elements std::rotate and 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;
}

Copying

std::copy allows you to copy elements from one container to another:

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

Modification

There are also algorithms for modifying elements, for example 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;
}

Deleting items

std::remove and std::remove_if allows you to remove elements from the container under the condition:

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

Several application examples

Suppose we have a list of employees and we want to first group them by department and then sort within each group by descending salary:

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

Sometimes it is necessary to remove all duplicates from a vector, keeping only unique elements:

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

Let’s say we have a vector of integers and we want to transform each element of the vector by multiplying it by 2 and subtracting 1. This can be done with 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;
}

A bit about STL iterators

Input iterators – This is the most basic type of iterators that supports reading sequential access. Can be used for one-pass reading of data from the container:

#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 iterators intended for one-pass recording of data into the container:

#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 iterators support reading and writing with the possibility of multiple passes through elements:

#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 iterators extend the capabilities of forward iterators by adding the possibility of bidirectional traversal (forward and backward):

#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 iterators provide all the capabilities of bidirectional iterators, and also support direct access to any element in constant time:

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

Let’s summarize briefly: STL in C++ allows you to speed up development and improve code quality.

Taking this opportunity, I would like to remind you about the free webinar that will be held tonight as part of the OTUS course on C++ development. In this lesson, participants will analyze dynamic memory allocation during the compilation phase of C++20. Register if applicable.

The full catalog of courses can be found in the catalog.

All about information technology’s blog

Application of STL containers and algorithms in C++