cpp

Работа с отсортированными диапазонами

Для работы с отсортированными диапазонами предназначены следующие функции:

  • merge() — объединяет элементы из отсортированного диапазона между first1 и last1 с элементами из отсортированного диапазона между first2 и last2. Результат сортируется и вставляется в новый диапазон, начинающийся с позиции result. Функция возвращает итератор, указывающий на конец нового диапазона. По умолчанию сравнение производится с помощью оператора <. В параметре comp можно указать пользовательскую функцию сравнения. Формат функции:
#include <algorithm>
iterator merge(first1, last1, first2, last2, result[, comp]);

Пример:

std::vector<int> arr = {1, 2, 5}, arr2 = {1, 5, 6}, res(6, -1);
std::sort(arr.begin(), arr.end());
std::sort(arr2.begin(), arr2.end());
std::merge(arr.begin(), arr.end(), arr2.begin(), arr2.end(),
           res.begin());
for (int &el : res) std::cout << el << ' ';
std::cout << std::endl; // 1 1 2 5 5 6
  • inplace_merge() — объединяет элементы из отсортированного диапазона между first и middle с элементами из отсортированного диапазона между middle и last. Результат сортируется внутри диапазона между first и last. По умолчанию сравнение производится с помощью оператора <. В параметре comp можно указать пользовательскую функцию сравнения. Формат функции:
#include <algorithm>
void inplace_merge(first, middle, last[, comp]);

Пример:

std::vector<int> arr = {1, 2, 5}, arr2 = {1, 5, 6}, res(6, -1);
std::sort(arr.begin(), arr.end());
std::sort(arr2.begin(), arr2.end());
auto it = std::copy(arr.begin(), arr.end(), res.begin());
std::copy(arr2.begin(), arr2.end(), it);
for (int &el : res) std::cout << el << ' ';
std::cout << std::endl; // 1 2 5 1 5 6
std::inplace_merge(res.begin(), res.begin() + 3, res.end());
for (int &el : res) std::cout << el << ' ';
std::cout << std::endl; // 1 1 2 5 5 6
  • includes() — возвращает значение true, если внутри отсортированного диапазона между first1 и last1 содержатся все элементы из отсортированного диапазона между first2 и last2, и false — в противном случае. По умолчанию сравнение производится с помощью оператора <. В параметре comp можно указать пользовательскую функцию сравнения. Формат функции:
#include <algorithm>
bool includes(first1, last1, first2, last2[, comp]);

Пример:

std::vector<int> arr = {1, 2, 3, 4, 5, 6}, arr2 = {1, 3, 6};
std::sort(arr.begin(), arr.end());
std::sort(arr2.begin(), arr2.end());
std::cout << std::boolalpha;
std::cout << std::includes(arr.begin(), arr.end(),
                           arr2.begin(), arr2.end());
std::cout << std::endl; // true
  • set_union() — объединяет элементы из отсортированного диапазона между first1 и last1 с элементами из отсортированного диапазона между first2 и last2. Результат сортируется и уникальные элементы вставляются в новый диапазон, начинающийся с позиции result. Функция возвращает итератор, указывающий на конец нового диапазона. По умолчанию сравнение производится с помощью оператора <. В параметре comp можно указать пользовательскую функцию сравнения. Формат функции:
#include <algorithm>
iterator set_union(first1, last1, first2, last2, result[, comp]);

Пример объединения двух множеств:

std::vector<int> arr = {1, 2, 3}, arr2 = {3, 4, 5}, res(6, -1);
std::sort(arr.begin(), arr.end());
std::sort(arr2.begin(), arr2.end());
auto it = std::set_union(arr.begin(), arr.end(),
                         arr2.begin(), arr2.end(), res.begin());
if (it != res.end()) {
   res.resize(std::distance(res.begin(), it));
}
for (int &el : res) std::cout << el << ' ';
std::cout << std::endl; // 1 2 3 4 5
  • set_difference() — удаляет элементы, входящие в отсортированный диапазон между first2 и last2, из отсортированного диапазона между first1 и last1. Результат вставляется в новый диапазон, начинающийся с позиции result. Функция возвращает итератор, указывающий на конец нового диапазона. По умолчанию сравнение производится с помощью оператора <. В параметре comp можно указать пользовательскую функцию сравнения. Формат функции:
#include <algorithm>
iterator set_difference(first1, last1, first2, last2,
                        result[, comp]);

Пример вычисления разницы двух множеств:

std::vector<int> arr = {1, 2, 3}, arr2 = {1, 2, 4}, res(6, -1);
std::sort(arr.begin(), arr.end());
std::sort(arr2.begin(), arr2.end());
auto it = std::set_difference(arr.begin(), arr.end(),
                   arr2.begin(), arr2.end(), res.begin());
if (it != res.end()) {
   res.resize(std::distance(res.begin(), it));
}
for (int &el : res) std::cout << el << ' ';
std::cout << std::endl; // 3
  • set_symmetric_difference() — вставляет в новый диапазон, начинающийся с позиции result, элементы, которые присутствуют в одном отсортированном диапазоне, но не присутствуют в другом. По умолчанию сравнение производится с помощью оператора <. В параметре comp можно указать пользовательскую функцию сравнения. Формат функции:
#include <algorithm>
iterator set_symmetric_difference(first1, last1, first2, last2,
                                  result[, comp]);

Пример:

std::vector<int> arr = {1, 2, 3}, arr2 = {1, 2, 4}, res(6, -1);
std::sort(arr.begin(), arr.end());
std::sort(arr2.begin(), arr2.end());
auto it = std::set_symmetric_difference(
                   arr.begin(), arr.end(),
                   arr2.begin(), arr2.end(), res.begin());
if (it != res.end()) {
   res.resize(std::distance(res.begin(), it));
}
for (int &el : res) std::cout << el << ' ';
std::cout << std::endl; // 3 4
  • set_intersection() — вставляет в новый диапазон, начинающийся с позиции result, элементы, которые присутствуют в обоих отсортированных диапазонах. По умолчанию сравнение производится с помощью оператора <. В параметре comp можно указать пользовательскую функцию сравнения. Формат функции:
#include <algorithm>
iterator set_intersection(first1, last1, first2, last2,
                          result[, comp]);

Пример пересечения двух множеств:

std::vector<int> arr = {1, 2, 3}, arr2 = {1, 2, 4}, res(6, -1);
std::sort(arr.begin(), arr.end());
std::sort(arr2.begin(), arr2.end());
auto it = std::set_intersection(arr.begin(), arr.end(),
                   arr2.begin(), arr2.end(), res.begin());
if (it != res.end()) {
   res.resize(std::distance(res.begin(), it));
}
for (int &el : res) std::cout << el << ' ';
std::cout << std::endl; // 1 2

Учебник C++ (Qt Creator и MinGW)
Учебник C++ (Qt Creator и MinGW) в формате PDF

Помощь сайту

ЮMoney (Yandex-деньги): 410011140483022

ПАО Сбербанк:
Счет: 40817810855006152256
Реквизиты банка:
Наименование: СЕВЕРО-ЗАПАДНЫЙ БАНК ПАО СБЕРБАНК
Корреспондентский счет: 30101810500000000653
БИК: 044030653
КПП: 784243001
ОКПО: 09171401
ОКОНХ: 96130
Скриншот реквизитов

cpp