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

231
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 defined 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 такие дубликаты не попадут

READ ALSO
Как организовать JavaScript код?

Как организовать JavaScript код?

Как организовать JavaScript код если я пишу не SPA, а только лишь слайдер, валидатор форм и прочие мелочи? И то это всё сторонние плагины которые...

236
Как поделить число нацело в javascript?

Как поделить число нацело в javascript?

Поделить на число без остатка в JS можно несколькоми способами

441
объявление функции javascript

объявление функции javascript

Стажируюсь в компании на фронтенд-разработчика, пришел с строготипизированной джавы, и некоторые моменты мне не очевидны, а именно:

324
Запрет скролла над картами google

Запрет скролла над картами google

Я видел подобные вопросы на этом ресурсе и на оригинальном и у меня все-равно проблема

300