Сортировка множеством

304

02 мая 2017, 07:27

У меня есть некоторая неупорядоченная последовательность пар целых чисел std::pair<int, int>. Если все элементы этой последовательности добавить в std::set<std::pair<int, int>> set, гарантируется ли стандартом, что цикл for(auto&& pair : set) std::cout << pair.first << ' '; выдаст упорядоченную по неубыванию последовательность?

Answer 1

Параграф 23.2.4:

Associative containers provide fast retrieval of data based on keys. The library provides four basic kinds of associative containers: set, multiset, map and multimap.

Параграф 23.2.10:

The fundamental property of iterators of associative containers is that they iterate through the containers in the non-descending order of keys where non-descending is deﬁned by the comparison that was used to construct them.

UPD Параграф 6.5.4:

The range-based for statement for ( for-range-declaration : for-range-initializer ) statement is equivalent to:

{
    auto &&__range = for-range-initializer ;
    auto __begin = begin-expr ;
    auto __end = end-expr ;
    for ( ; __begin != __end; ++__begin ) {
        for-range-declaration = *__begin;
        statement
    }
}

Версия: N4582

Answer 2

Да

у типа std::pair<...> перегружен оператор < который сравнивает сперва std::pair::first элементы (если они равны то уже вторые сравниваются), поэтому всё отработает как и ожидалось - в выводе будет отсортированно по не убыванию

std::set<std::pair<int, int>> mySet;
mySet.insert({ 5, -1 });
mySet.insert({ 3, 4 });
mySet.insert({ 4, 1 });
mySet.insert({ 2, 2 });
mySet.insert({ 1, 2 });
for (auto && p : mySet)
{
    cout << p.first << '\n';
}

p.s.

Только не забудьте, что при наличии одинаковых первых значений в set такие дубликаты не попадут