Подводные камни компараторов в С++

При использовании компаратора в алгоритмах boost::sort и std::sort важно учитывать некоторые особенности работы этих алгоритмов, игнорирование которых может привести к неожиданным последствиям, в том числе к segmentation fault.



Чаще всего при сортировке объектов пользовательских типов написание кода сравнения элементов коллекции не вызывает вопросов. Компаратор должен возвращать true, если первый аргумент меньше второго, то есть в отсортированном массиве первый аргумент должен идти перед вторым. Алгоритмы сначала вызывают компаратор для пары элементов x и y. Если компаратор вернул true, значит, элемент x меньше y и он должен идти в коллекции перед элементом y, если false, то компаратор вызывается повторно для пары y и x. Если компаратор опять вернул false, значит, элементы равны, иначе порядок определен.

Меня зовут Олег Игнатов, я — Development Team Lead в команде KICS (Kaspersky Industrial CyberSecurity) «Лаборатории Касперского». Мы защищаем промышленные инфраструктуры и сети от специализированных киберугроз. В этой статье расскажу о некоторых особенностях использования компараторов в С++, знание которых позволит не наступить на различные грабли и сэкономить время при разборе багов.

Введение

Начнем с простого примера. Допустим, у нас есть вектор некоторых объектов Device и нам нужно сортировать их по полю name, в этом случае компаратор может выглядеть так:

struct Client
{
    string name;
    string city;
};
sort(data.begin(), data.end(), [](const auto& x, const auto& y) {
    return x.name < y.name;
});

Если нужно сначала сортировать по city, затем по name, то компаратор усложнится незначительно:

sort(data.begin(), data.end(), [](const auto& x, const auto& y) {
    if (x.city < y.city)
        return true;
    if (y.city < x.city)
        return false;
    return x.name < y.name;
});

Сначала анализируем city. Если они равны, то принимаемся за name.

Чтобы не запутаться в множественных условиях, можно использовать std::tie для упаковки объекта в std::tuple перед сравнением:

sort(data.begin(), data.end(), [](const auto& x, const auto& y) {
    return std::tie(x.city, x.name) < std::tie(y.city, y.name);
});

Segmentation fault

Однако на практике иногда появляются задачи, где требуется провести более сложное упорядочивание элементов контейнера. Допустим, у нас в базе хранится дерево некоторых объектов, каждый узел которого описан структурой:

struct Node
{
    int id = 0;
    int parentId = 0;
};

Мы хотим отсортировать коллекцию этих объектов таким образом, чтобы сначала шли все элементы, у которых нет родителя, далее родительские элементы и в конце дочерние элементы.

Сходу можно написать такой компаратор:

const auto nodeComparator = [](const auto& lhs, const auto& rhs){
    return lhs.parentId == 0 || lhs.id == rhs.parentId;
};

Он выглядит довольно логично, соответствует нашим требованиям, и более того, он работает (!) на небольших коллекциях.

Если же попробовать выполнить сортировку условно большой коллекции, в которой присутствует более одного объекта с parentId = 0, то программа упадет с segmentation fault. Выясняется, что программа зависает на бесконечном цикле сортировки, так как на вход компаратор получает пары элементов (a, b) и (b, a) и возвращает в обоих случаях ответ true, что не дает однозначно определить порядок элементов. Такой компаратор нельзя использовать в алгоритмах boost и std, так как он не удовлетворяет требованиям стандарта и приводит к UB. Это еще один способ отстрелить себе ногу, который прошел все возможные статические проверки.

Теперь пара слов о том, что значит небольшая коллекция и что значит большая. На тестовых примерах удалось выяснить, что библиотеки boost и std переключают свои алгоритмы сортировки, когда количество элементов в коллекции становится больше или равным 7.

Алгоритм сортировки не специфицируется стандартом языка и может варьироваться. Обычно это Introsort, который может использовать сортировку вставками, быструю и пирамидальную сортировки в зависимости от количества элементов в коллекции. Предположительно, на коллекциях с числом элементов менее 7 используется алгоритм сортировки вставками, в противном случае — быстрая сортировка с оптимизациями.

Таким образом, приведенный выше компаратор будет прекрасно работать ровно до тех пор, пока клиент не создаст в системе 7-й объект. После этого система выйдет из строя.

Для решения данной задачи проще всего оказалось предварительно заполнить карту уровней для всех объектов и далее использовать ее при сортировке в компараторе.

Undefined Behaviour

Интересно, а вообще, для каждой пары элементов вызывается компаратор при сортировке и можем ли мы полагаться на это в компараторе?

Упростим условия предыдущей задачи. Допустим, мы хотим, чтобы в коллекции родители шли левее своих детей. Тогда тело нашего компаратора можно записать одной строкой:

const auto nodeComparator = [](const auto& lhs, const auto& rhs){
    return lhs.id == rhs.parentId;
};

На первый взгляд лаконично, просто и соответствует требованиям к компаратору. Если элемент lhs является родительским по отношению к элементу rhs, то условие вернет true. Порядок определен. Если элемент lhs является дочерним по отношению к элементу rhs, то условие вернет false. Далее компаратор будет вызван снова для тех же элементов, но в другом порядке. В этом случае условие вернет true. Порядок определен. Если оба элемента являются детьми или оба элемента являются родителями, то для любой перестановки компаратор вернет false. Таким образом, эти элементы для алгоритма сортировки будут равны. Все ОК, все должно работать.

Запускаем решение на небольшой коллекции, и все работает. Запускаем на коллекции из 7 элементов:

id | parentId
1    0
4    5
5    1
6    1
7    1
8    1
9    1

Здесь элемент 4 является дочерним по отношению к элементу 5. Но вместо ожидаемой отсортированной последовательности 1, 5, 4… получаем последовательность 1, 4, 5…

Почему элементы 4 и 5 не упорядочились?

Как уже было сказано выше, на коллекции с числом элементов не менее 7 библиотеки boost и std начинают использовать алгоритм быстрой сортировки, который работает по принципу divide and conquer, с дополнительными оптимизациями. Далее приведены трассировки вызовов компаратора в формате: элемент слева, элемент справа, результат работы компаратора:

6, 1 => false
9, 6 => false
1, 6 => true
4, 6 => false
8, 6 => false
7, 6 => false
6, 6 => false
5, 6 => false
4, 6 => false
1, 6 => true
6, 4 => false
6, 5 => false
7, 6 => false
8, 7 => false
9, 8 => false

Алгоритм sort взял средний элемент 6 и начал независимо сортировать элементы слева и справа от него.

При сравнении элементов 4 и 6 выяснилось, что они равны:

4, 6 => false
6, 4 => false

Аналогично для элементов 5 и 6 выяснилось, что они равны:

5, 6 => false
6, 5 => false

Далее благодаря оптимизациям алгоритм sort вообще не стал вызывать компаратор для элементов 4 и 5, потому что очевидно, что они тоже равны, хотя мы ожидали увидеть элемент 5 левее элемента 4.

А что говорит стандарт:



Компаратор должен удовлетворять стандартному математическому определению Strict Weak Ordering (подробнее см. у Josuttis):

• если a меньше b, то b больше или равно a;
• если a меньше b и b меньше c, то a меньше c;
• если a равно b и b равно c, то a равно c.

Последнее свойство в математике называется Transitivity of equivalence. Это свойство не выполнялось нашим компаратором, что приводило к Undefined Behaviour при его использовании в алгоритмах boost и STL.

Пример сложного компаратора

Хотелось бы привести пример довольно сложного компаратора.

bool operator ()(const DbOfficeData* lhs, const DbOfficeData* rhs) const
{
    if (!lhs->parent && !rhs->parent)
        return lhs->item.description < rhs->item.description;
    if (lhs->children.size() == rhs->children.size())
    {
        if (lhs->dbItem.type == rhs->dbItem.type)
        {
            if (lhs->dbItem.type == OfficeType::Regional)
                return lhs->dbItem.address < rhs->dbItem.address;
            if (lhs->dbItem.type == OfficeType::Local)
                return lhs->dbItem.ordersCount < rhs->dbItem.ordersCount;
            return lhs->item.description < rhs->item.description;
        }
        return lhs->dbItem.type == OfficeType::Global;
    }
    return lhs->children.size() > rhs->children.size();
}

Можно выделить три цели, которые преследует данный компаратор.

1. Упорядочить все элементы по количеству детей.
2. Если количество детей совпадает, то дополнительно упорядочить по некоторым другим полям.
3. Дополнительно к первым двум пунктам упорядочить корневые элементы, у которых не задан parent, по полю description.

Здесь проблема в том, что сортировка идет по независимым критериям. Поясню на простом примере. Допустим, есть структура:

struct Client
{
    string name;
    int age = 0;
    bool hasOrders = false;
};

Если мы выполняем сортировку сначала по name, потом по age, то проблем не возникает, так как это зависимые друг от друга критерии. Сравнение по age выполняется только, если у двух объектов равны name.

Теперь представим, что для коллекции объектов Client был написан компаратор следующего вида:

bool operator ()(const auto& lhs, const auto& rhs) const
{
    if (lhs.hasOrders && rhs.hasOrders)
        return lhs.name < rhs.name;
    return lhs.age < rhs.age;
}

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

Возьмем три объекта типа Client:

{
    {"a", 10, true},
    {"b", 1, true},
    {"c", 5, false}
}

Стандарт гласит, что если компаратор возвращает true для пар объектов (a, b) и (b, c), то он должен также вернуть true для пары (a, c). Это требование стандарта здесь не работает, и мы получаем Undefined Behaviour. Нарушается принцип Strict Weak Ordering:
если a меньше b и b меньше c, то a меньше c.

Вариант с нашим компаратором отличается только большей сложностью, но проблема с ним та же самая. Сортировка по description в строке 4 идет независимо от сортировки по children.size(), так как зависит от третьего условия: поля parent. Несложно написать тест, который использует тестовые данные из предыдущих примеров, а именно: вектор из 7 элементов, в котором 2-й и 3-й элементы должны поменяться местами при сортировке, но этого не происходит. Код теста приводить не буду, так как он тривиальный.

Мы можем это исправить, полностью разделив сортировку объектов с parent и без него.

Вместо условия:

if (!lhs->parent && !rhs->parent)
	return lhs->item.description < rhs->item.description;

Получится:

if (!lhs->parent || !rhs->parent)
{
    if (!lhs->parent && !rhs->parent)
        return lhs->item.description < rhs->item.description;
    return !lhs->parent
}

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

Компаратор для ассоциативных контейнеров

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

struct Client
{
    string name;
    string city;
};

Задача не сложная: заполнить мапу данными и за логарифмическое время выполнять поиск. Но есть одна особенность. Если city не задан, то элемент должен возвращаться при поиске по любому city. То есть, к примеру, есть данные:

1. name="Ivanov", city=""
2. name="Petrov", city=""
3. name="Sidorov", city=""
4. name="Leonov", city="Moscow"
5. name="Ivanov", city="Ufa"

Поиск по name=Leonov, city=Moscow должен вернуть 4-й элемент, это понятно.
А вот поиск по name=Ivanov, city=Moscow должен вернуть 1-й элемент, так как у него city не задан, а значит, подходит любое искомое значение, а name совпадает с искомым.

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

Контейнер std::map у себя внутри ищет элемент бинарным поиском, начиная с элемента 3. name=Sidorov, city="".

Предположим, что мы ищем два элемента подряд, сначала один, потом другой:

name=Leonov, city=Moscow
name=Ivanov, city=Moscow

При сравнении их с 3-м элементом оба элемента выглядят совершенно равнозначно, то есть не получится реализовать компаратор так, чтобы для одного элемента он сказал, что надо дальше идти бинарным поиском налево, а для другого — направо. А ведь именно это и требуется, потому что, как было показано выше, для первого искомого элемента подходит 4-й элемент в мапе, а для второго — 1-й.

Дело в том, что свойства хранимых в мапе элементов отличаются от свойств искомых элементов, а именно отличается смысл поля city для хранимых и искомых элементов. Хранимые элементы можно просто сравнивать между собой по city и, как следствие, сортировать. А вот по отношению к искомым элементам city работает как маска: если она не задана, то элемент подходит. Все это приводит к тому, что для данной задачи невозможно написать компаратор, который бы удовлетворял требованиям Strict Weak Ordering.

Для данной задачи логичным решением будет использовать две мапы: одну для элементов, у которых не задана city, вторую — для всех остальных.

Примечательно, что такое решение не увеличивает алгоритмическую сложность поиска.

Заключение

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

Если все-таки было принято решение использовать единственный компаратор, то следует обратить внимание на требования, которые предъявляются к компаратору. В частности, компаратор должен удовлетворять требованиям Strict Weak Ordering.

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

Если вам было интересно и вы тоже хотите строить интеллектуальные средства защиты сетей, приходите к нам :) У нас много планов по реализации новых фичей и никакого legacy. А попасть к нам можно всего лишь за 2-3 дня. Подробности — тут.

А здесь можно проверить свои знания C++ в нашей игре про умный город.

Список источников

1. The C++ Standard Library. Nicolai M. Josuttis
2. Эффективное использование STL. Скотт Мейерс
3. std::sort
4. Introsort
5. C++ named requirements: Compare
6. Strict Weak Ordering
7. Strict Weak Ordering and the C++ STL
8. Standard for Programming Language C++