Блог

У меня есть этот векторный объект, который содержит вектор int s

 std::vector<std::vector<int>> vec;
  

Я пытался выяснить, как std::sort(vec.begin(), vec.end()) это работает. Вот мои наблюдения:

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

Сейчас я генерирую несколько 2D-векторов, и кажется, что эти два всегда верны. Однако я сомневаюсь в своем втором предположении. std::sort Действительно ли это работает, или это была просто удача, которая сделала мои предположения правильными?

Сортировка векторных элементов работает так же, как сортировка любого другого типа. std::sort использует объект сравнения, указанный в качестве аргумента. Если ни один из них не был передан явно, std::less используется значение по умолчанию.

std::less использует operator< . Согласно документации vector, это:

Сравнивает содержимое lhs и rhs лексикографически. Сравнение выполняется функцией, эквивалентной std::lexicographical_compare .

---

Лексикографическое сравнение — это операция со следующими свойствами:

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

Короче говоря, лексикографическая сортировка такая же, как сортировка, используемая для словарей (игнорируя странности некоторых языков).

2D векторы сортируются по размеру.

Не совсем. {1}, {3, 4}, {1, 2, 5} было бы отсортировано как {1}, {1, 2, 5}, {3, 4} .

std::sort по умолчанию используется operator < для сортировки. Поскольку std::vector имеет перегруженный operator < файл, он использует это. std::vector::operator < означает ли лексикографическое сравнение, что оно возвращает вектор, содержащий первый меньший элемент. Это означает, что {1, 1, 2} меньше, чем {1, 1, 3} поскольку 2 меньше, чем 3 . Если векторы имеют разную длину, но меньший содержит те же элементы, что и больший, то возвращается меньший. Это означает, что

 int main()
{
    std::vector a{5, 1}, b{10};
    std::cout << (a < b);
}
  

Выводит, 1 поскольку 5 меньше 10 .

 int main()
{
    std::vector a{5, 10}, b{5};
    std::cout << (a < b);
}
  

Печатает, 0 поскольку a больше, чем b но у них один и тот же общий элемент.