CKTIS / C++
Сортиране, сравнения и диапазони за търсене
Правилното сортиране изисква компаратор, който дефинира строг слаб ред. Двоичното търсене изисква диапазон, разделен според съответното условие; сортирането на целия диапазон е достатъчно, но не винаги необходимо.
Версия: C++23; repository compiler flag, production runtime not attested
Синтаксис
std::sort(first, last, comp);
std::lower_bound(first, last, value, comp);std::sort от <algorithm> подрежда полуотворения диапазон [first, last) според comp: никой по-късен елемент не предхожда по-ранен. Изисква итератори с произволен достъп и елементи, отговарящи на изискванията за преместване и размяна. Извършва O(N log N) сравнения. Не гарантира запазване на реда на еквивалентните елементи; за това използвайте std::stable_sort.
Компараторът трябва да дефинира строг слаб ред. comp(a, b) означава, че a предхожда b, а comp(a, a) трябва да е false. Релацията трябва да е транзитивна. Еквивалентността, дефинирана като !comp(a, b) && !comp(b, a), също трябва да е транзитивна и не е задължително да съвпада с operator==. Не използвайте <=: той нарушава изискването при еднакви аргументи. Ако изискванията към компаратора не са изпълнени, гаранциите на алгоритъма не важат.
Строгият слаб ред и разделянето на диапазоните за търсене са свързани, но различни изисквания. В диапазон, разделен според предикат, първо са всички елементи с резултат true, а след тях — тези с резултат false; която и да е част може да е празна. За std::lower_bound(first, last, value, comp) предикатът е comp(e, value). Функцията връща границата: първия елемент с резултат false или last. Това не доказва, че търсената стойност присъства; не дереферирайте last.
Сортирането по същия ред гарантира това разделяне за всеки ключ. За един ключ е достатъчно само разделянето: [2, 1, 4, 3] удовлетворява предусловието на std::lower_bound за value = 3 и сравнението <, въпреки че не е сортиран. Другите функции за двоично търсене имат собствени изисквания за разделяне. std::lower_bound извършва O(log N) сравнения, но без итератори с произволен достъп може да изисква линеен брой стъпки на итератора.
Примерът сортира цели числа, след което използва същия comp, за да получи индекс 3. Съдържанието е предназначено за C++23; посочената препратка води до развиващ се работен проект, а не до окончателно издание на C++23. Поддръжката от компилатора и производствената среда за изпълнение не е потвърдена.
Примери
#include <algorithm>
#include <cstddef>
#include <iostream>
#include <vector>
int main() {
std::vector<int> values{4, 1, 3, 1, 2};
const auto comp = [](int a, int b) { return a < b; };
std::sort(values.begin(), values.end(), comp);
for (std::size_t i = 0; i < values.size(); ++i) {
if (i != 0) std::cout << ' ';
std::cout << values[i];
}
std::cout << '\n';
const auto it = std::lower_bound(values.begin(), values.end(), 3, comp);
std::cout << "index=" << (it - values.begin()) << '\n';
}
Резултат
1 1 2 3 4 index=3
Показаният код и заявеният резултат са проверени в изолирана среда по метода, записан в доказателството за проверка на тази точна версия.