«Разделяй и властвуй» и множества (серия «114 алгоритмов C++»)

Добро пожаловать в третью статью из серии «114 алгоритмов C++». Сегодня мы рассмотрим алгоритмы, предлагающие низкую вычислительную сложность, но требующие сортированного или секционированного диапазона.

Сегодня мы обсудим две категории алгоритмов. Алгоритмы «разделяй и властвуй», работающие за время O(logn), и линейные алгоритмы, применимые только в отсортированных диапазонах.

Хотя контейнеры на основе хеша дают нам возможность искать любой элемент в среднем за время O(1), у этого подхода есть два недостатка. Во-первых, мы можем искать только определенный элемент, и если этого элемента нет в контейнере, мы получаем простой сбой поиска. Во-вторых, наш тип должен быть хешируемым.

Алгоритмы «разделяй и властвуй» позволяют искать границы на основе строгого слабого упорядочения и работают, даже если конкретное значение контейнера отсутствует. Кроме того, поскольку мы работаем с отсортированным контейнером, то после определения границы мы можем легко получить доступ к соседним значениям.

Если вы не читали предыдущую главу этой серии, строгий слабый порядок – это порядок, который удовлетворяет следующим ограничениям:

• антирефлексивный: f(a,a) = false,
• антисимметричный: f(a,b) = true => f(b, а) = false,
• и транзитивный: f(a,b) = true && f(b,c) = true => f(a,c) = true.

lower_bound, upper_bound, equal_range

C++ предлагает три алгоритма поиска границ.

Алгоритмы отличаются тем, какую границу они ищут:

• lower_bound возвращает первый элемент, который не меньше предоставленного значения;
• upper_bound возвращает первый элемент, который больше предоставленного значения.

Если такого элемента не существует, оба алгоритма возвращают конечный итератор.

struct ExamResult {
    std::string student_name;
    uint16_t score;
};

const std::vector<ExamResult>& get_results();

int main() {
    const std::vector<ExamResult>& results = get_results();

    auto lb = std::ranges::lower_bound(results, 49, {}, &ExamResult::score);
    auto ub = std::ranges::upper_bound(results, 99, {}, &ExamResult::score);
 
    for (auto it = results.begin(); it != lb; it++) {
        // Обработка провалившихся, до 48
    }
    
    for (auto it = lb; it != ub; it++) {
        // Обработка прошедших, 49-99
    }
    
    for (auto it = ub; it != results.end(); it++) {
        // Обработка отличников, 100+
    }
}

Если вы читали предыдущую главу, этот фрагмент кода может показаться вам знакомым, поскольку мы использовали std::partition для очень похожего поведения. Основное отличие состоит в том, что мы работаем с неизменяемым диапазоном (строка 9), который, как мы ожидаем, уже отсортирован (в данном случае по оценке). Когда мы используем оба значения, lower_bound и upper_bound, результирующий поддиапазон будет представлять закрытый диапазон значений, в данном случае [49,99] (строки 11, 12).

Логарифмическое поведение доступно только для диапазонов произвольного доступа. Использование lower_bound или upper_bound для std::set, std::multiset, std::map или std::multimap приведет к линейному поиску.

Поэтому все эти контейнеры предоставили свои O(logn) реализации поиска нижней и верхней границ в виде методов.

std::multiset<int> data{1, 2, 3, 4, 5, 6, 6, 6, 7, 8, 9};

auto lb = data.lower_bound(6);
// std::distance(data.begin(), lb) == 5, *lb == 6

auto ub = data.upper_bound(6);
// std::distance(data.begin(), ub) == 8, *ub == 7

Комбинация lower_bound и upper_bound – это equal_range, который возвращает обе границы.

Мы могли бы смоделировать equal_range, вызвав для одного и того же значения как lower_bound, так и upper_bound.

std::vector<int> data{1, 2, 3, 4, 5, 6, 6, 6, 7, 8, 9};

auto [lb, ub] = std::equal_range(data.begin(), data.end(), 6);
// std::distance(data.begin(), lb) == 5, *lb == 6
// std::distance(data.begin(), ub) == 8, *ub == 7

Синтаксис квадратных скобок (если вы с ним не знакомы) представляет собой структурированные привязки из C++17. Структурированные привязки позволяют нам разложить std::pair, возвращаемый equal_range, на две именованные переменные.

partition_point, binary_search

Несмотря на название, partition_point работает очень похоже на upper_bound, однако вместо поиска определенного значения он ищет с использованием предиката.

Точка раздела (partition_point) вернет первый элемент, который не удовлетворяет предоставленному предикату. Этот алгоритм требует только разделения диапазона (относительно предиката).

std::vector<int> data{1, 2, 3, 4, 5, 6, 7, 8, 9};
auto pp = std::partition_point(data.begin(), data.end(), 
                                [](int v) { return v < 5; });
// *pp == 5

Наконец, бинарный поиск служит проверкой присутствия, возвращая логическое значение, указывающее, присутствует ли запрошенное значение в отсортированном диапазоне или нет.

Хотя функционально идентичный вызову equal_range и проверке, является ли возвращаемый диапазон пустым, binary_search обычно работает быстрее. Это связано с тем, что алгоритм binary_search должен быть реализован как один поиск, а equal_range допускает два.

std::vector<int> data{1, 2, 3, 4, 5, 6, 7, 8, 9};

auto [lb, ub] = std::ranges::equal_range(data, 5);
bool exists = std::ranges::binary_search(data, 5);
assert((lb != ub) && exists);

Поскольку в диапазоне присутствует число пять, equal_range вернет непустой диапазон, а binary_search вернет true.

Стандартная библиотека C: bsearch

От стандартной библиотеки C C++ наследует bsearch. Этот алгоритм возвращает один из элементов, равный предоставленному ключу, или nullptr, если такой элемент не найден.

int data[] = {-2, -1, 0, 1, 2};
int size = sizeof data / sizeof(int);

auto cmp = [](const void* left, const void* right){
    int vl = *(const int*)left;
    int vr = *(const int*)right;

    if (vl < vr) return -1;
    if (vl > vr) return 1;
    return 0;
};

int value = 1;
void* el1 = bsearch(&value, data, size, sizeof(int), cmp);
assert(*static_cast<int*>(el1) == 1);

value = 3;
void *el2 = bsearch(&value, data, size, sizeof(int), cmp); 
assert(el2 == nullptr);

Как и в случае с qsort, нет смысла использовать bsearch в коде C++.

В зависимости от конкретного варианта использования подходящей заменой может быть один из ранее упомянутых алгоритмов.

int data[] = {-2, -1, 0, 1, 2};
int size = sizeof data / sizeof(int);

int value = 1;
bool exist = std::binary_search(&data[0], &data[size], value);

auto candidate = std::lower_bound(&data[0], &data[size], value);
if (candidate != &data[size] && *candidate == value) {
    // обработка элемента
}

auto [lb, ub] = std::equal_range(&data[0], &data[size], value);
if (lb != ub) {
    // обработка равных элементов
}

includes

Первый линейный алгоритм, о котором мы поговорим, это std::includes. Этот алгоритм определяет, является ли один диапазон поддиапазоном другого. Поскольку мы работаем с отсортированными диапазонами, std::includes выполняется за линейное время.

Здесь мы проверяем, содержит ли входной текст все строчные английские буквы.

std::vector<char> letters('z'-'a'+1,'\0');
std::iota(letters.begin(), letters.end(), 'a');

std::string input = "the quick brown fox jumps over the lazy dog";
std::ranges::sort(input);

assert(std::ranges::includes(input, letters));

Сначала мы программно генерируем список английских букв, используя другой алгоритм std::iota (строка 2). Алгоритм iota генерирует последовательно увеличивающиеся значения, чтобы заполнить заданный диапазон. Для этого мы предварительно размещаем вектор из 26 элементов (строка 1).

merge, inplace_merge

Еще одна операция, выполнимая за линейное время, – это объединение (слияние) двух отсортированных диапазонов.

Результат операции слияния сохраняется с использованием предоставленного итератора вывода. Обратите внимание, что выходной диапазон не может перекрываться ни с одним из входных диапазонов.

Операция слияния стабильна. Равные элементы из первого диапазона будут располагаться перед равными элементами из второго диапазона.

struct LabeledValue {
    int value;
    std::string label;
};

std::vector<LabeledValue> data1{{1, "first"}, {2, "first"}, {3, "first"}};
std::vector<LabeledValue> data2{{0, "second"}, {2, "second"}, {4, "second"}};

std::vector<LabeledValue> result;
std::ranges::merge(data1, data2, std::back_inserter(result),
  [](const auto& left, const auto& right) { return left.value < right.value; });
// result == {0, second}, {1, first}, {2, first}, {2, second}, {3, first}, {4, second}

Параллельная версия требует, чтобы вывод был однонаправленным диапазоном (представленным forward_iterator). Поэтому мы не можем использовать обертки, такие как std::back_inserter, и должны предварительно разместить диапазон вывода достаточной емкости.

std::vector<int> data1{1, 2, 3, 4, 5, 6};
std::vector<int> data2{3, 4, 5, 6, 7, 8};

std::vector<int> out(data1.size()+data2.size(), 0);
std::merge(std::execution::par_unseq,
    data1.begin(), data1.end(),
    data2.begin(), data2.end(),
    out.begin());

Поскольку слияние запрещает перекрытие входных и выходных диапазонов, у нас есть альтернатива – inplace_merge, которая подходит для этого варианта использования.

std::vector<int> range{1, 3, 5, 2, 4, 6};
std::inplace_merge(range.begin(), range.begin()+3, range.end());
// range == { 1, 2, 3, 4, 5, 6 }

unique, unique_copy

Алгоритм std::unique удаляет последовательно повторяющиеся значения. Типовой вариант использования связан с отсортированным диапазоном. Однако это не является требованием std::unique.

Поскольку unique работает на месте и не может изменять размер базового диапазона, он оставляет конец диапазона с неопределенными значениями и возвращает итератор в начало этого поддиапазона (или поддиапазон в случае версии для диапазона).

std::vector<int> data{1, 1, 2, 2, 3, 4, 5, 6, 6, 6};
auto it = std::unique(data.begin(), data.end());
// версия для диапазонов: auto it = std::ranges::unique(data).begin();

// data == {1, 2, 3, 4, 5, 6, не определен, не определен, не определен, не определен}
data.resize(std::distance(data.begin(), it));
// data == {1, 2, 3, 4, 5, 6}

Копирующая версия unique вместо этого выводит уникальные значения в выходной диапазон, представленный итератором.

std::vector<int> data{1, 1, 2, 2, 3, 4, 5, 6, 6, 6};
std::vector<int> out;
std::ranges::unique_copy(data, std::back_inserter(out));
// out == {1, 2, 3, 4, 5, 6}

set_difference, set_symmetric_difference, set_union, set_intersection

Последней группой алгоритмов, требующих сортировки диапазонов, являются операции над множествами.

Все операции над множествами работают одинаково, обрабатывая два входных диапазона и копируя результаты в результирующий диапазон со следующей семантикой:

• разница (difference): элементы, которые присутствуют в первом диапазоне, но отсутствуют во втором;
• симметричная разница (symmetric_difference): элементы, которые присутствуют только в одном из диапазонов, но не в обоих;
• объединение (union): элементы, которые присутствуют в любом из диапазонов;
• пересечение (intersection): элементы, которые присутствуют в обоих диапазонах.

Нам также нужно поговорить о поведении для равных элементов. Если у нас есть m таких элементов в первом диапазоне и n таких элементов во втором диапазоне, результирующий диапазон будет содержать:

• разница (difference): max(m-n,0) элементов;
• симметричная разница (symmetric_difference): abs(m-n), то есть: если m>n, то m-n элементов будут скопированы из первого диапазона; иначе n-m элементов будут скопированы из второго диапазона;
• объединение (union): max(m,n), первые m элементов будут скопированы из первого диапазона, а затем max(n-m,0) элементов – из второго диапазона;
• пересечение (intersection): min(m,n), элементы будут скопированы из первого диапазона.

std::vector<int> data1{1, 2, 5};
std::vector<int> data2{2, 4, 6};

std::vector<int> difference;
std::ranges::set_difference(data1, data2, std::back_inserter(difference));
// difference == {1, 5}

std::vector<int> symmetric;
std::ranges::set_symmetric_difference(data1, data2, std::back_inserter(symmetric));
// symmetric == {1, 4, 5, 6}

std::vector<int> set_union;
std::ranges::set_union(data1, data2, std::back_inserter(set_union));
// set_union == {1, 2, 4, 5, 6}

std::vector<int> intersection;
std::ranges::set_intersection(data1, data2, std::back_inserter(intersection));
// intersection == {2}

Спасибо за чтение

Следующая статья будет посвящена алгоритмам преобразования диапазонов.

Теги