Грокаем C++ on Telegram: “Strict weak ordering #опытным На первый взгляд…”

Strict weak ordering
#опытным

На первый взгляд, всё выглядит рабочим: мы создаём 40 заказов с одинаковой ценой 100 и уникальными id, затем сортируем по возрастанию цены, используя <=. Программа компилируется и даже выполняется без ошибок… пока не достигнет определённого размера. Тогда она падает с segmentation fault.

struct Order {
    int price;
    int id;
};

int main() {
    std::vector<Order> book;
    for (int i = 0; i < 40; ++i) {
        book.push_back({100, i});
    }
    std::sort(book.begin(), book.end(),
              [](const Order& a, const Order& b) {
                  return a.price <= b.price;
              });
    std::cout << "book.size() = " << book.size() << '\n';

    return 0;
}

Но почему так? Мы же вообще ничего криминального не делали, а получили UB.

Баг на самом деле в том, что компаратор не удовлетворяет требованию strict weak ordering. Конкретно проблема в иррефлексивности компаратора. Для любых двух элементов с одинаковой ценой (в нашем случае все цены равны 100) компаратор возвращает true в обе стороны:

- comp(a, b) = 100 <= 100 → true
- comp(b, a) = 100 <= 100 → true

Это означает, что comp(a,a) тоже true (так как 100 <= 100). Согласно стандарту, компаратор должен возвращать false для сравнения объекта с самим собой. Это и есть требование иррефлексивности. Нарушение этого правила приводит к тому, что алгоритм сортировки некорректно сравнивает одинаковые элементы и по итогу входит за границы последовательности

Ну окей. "А почему эффекты проявляются только после определенного размера последовательности?"

Потому что реализация std::sort в стандартной библиотеке обычно использует интроспективную сортировку (introsort), которая выбирает стратегию в зависимости от размера диапазона:

1️⃣ Для малых подмассивов (обычно < 16 элементов) используется сортировка вставками (insertion sort). На каждом шаге работы эта сортировка проходится по всем предыдущим элементам и меняет текущий, если компаратор возвращает true. Есть четкая граница остановки - первый элемент. Поэтому даже если компаратор будет возвращать true для одинаковых элементов, то это приведет лишь к лишним обменам элементов.

2️⃣ Для больших диапазонов introsort переключается на быструю сортировку (quicksort) с разбиением (partitioning) вокруг опорного элемента (pivot).

Именно в фазе разбиения и прячется баг. Алгоритм разбиения тут примерно следующий. Обычно выбирается опорный элемент pivot. Затем два указателя двигаются навстречу друг другу, пока не найдут элементы, которые должны быть поменяны местами:

while (comp(*left, pivot)) ++left;   // пока левый < pivot
while (comp(pivot, *right)) --right; // пока pivot < правый

Если comp использует <=, то для равных элементов оба условия вернут true:

- comp(*left, pivot) вернёт true (если *left == pivot, то pivot <= pivot → true)
- comp(pivot, *right) тоже true (если *right == pivot).

Таким образом, левый указатель будет двигаться вправо, пока не выйдет за границы, а правый — влево, также за пределы. Это приводит к чтению/записи за пределами массива и, в конечном счёте, к крашу.

Решение тут простое и даже есть соответствующая мемная паста на кодфосес. "Компаратор в С++ должен возвращать false, если аргументы равны". Или в нашем примере:

std::sort(book.begin(), book.end(),
              [](const Order& a, const Order& b) {
                  return a.price < b.price;
              });

Reflect on your life. Stay cool.

#STL