[C ++] [std :: sort] Как это работает с 2D-контейнерами?

Question

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

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

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

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

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

Answer 1

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

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

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

---

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

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

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

---

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

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

Answer 2

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но они имеют один и тот же общий элемент.