Всегда ли порядок итераций std :: set возрастает в соответствии со спецификацией C ++?

Question

Здесь http://www.cplusplus.com/reference/stl/set/ Я прочитал, что std :: set в C ++ "обычно" реализован в виде дерева (красно-черного?) И отсортирован.

Я не мог понять, означает ли это, что по спецификации порядок итераций множества всегда возрастает? Или это только «обычная деталь реализации», и иногда некоторая библиотека / компилятор может нарушать это соглашение?

Answer 1

В соответствии со стандартом C ++ итерация элементов std::set выполняется в отсортированном порядке, как определено std::less или необязательным аргументом шаблона предиката сравнения.

(Также в соответствии со стандартом C ++ вставка, поиск и удаление занимают не более O (lg n ) времени, поэтому сбалансированные деревья поиска в настоящее время являются единственным жизнеспособным вариантом реализации для std::set, хотя использование красно-черных деревьев не предусмотрено стандартом.)

Answer 2

Это означает, что внутренне std::set будет хранить свои элементы в виде отсортированного дерева.Однако в спецификации ничего не говорится о порядке сортировки.По умолчанию std::set использует std::less и будет располагаться в порядке от низкого до высокого.Однако вы можете настроить функцию сортировки по своему усмотрению, используя этот параметр шаблона:

std::set<valueType, comparissonStruct> myCustomOrderedSet;

Например:

std::set<int, std::greater<int> > myInverseSortedSet;

или

struct cmpStruct {
  bool operator() (int const & lhs, int const & rhs) const
  {
    return lhs > rhs;
  }
};

std::set<int, cmpStruct > myInverseSortedSet;

На самом деле, эти примеры также представлены на сайте, который вы указали.Более конкретно здесь: Конструктор множеств .

Answer 3

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

Answer 4

в соответствии с порядком итерации спецификации набора всегда возрастает

Да, значения набора всегда возрастают, если вы распечатываете их в последовательности.Как говорится в описании, он обычно реализуется с использованием Red-Black Tree (RBT), но авторы компилятора имеют возможность нарушить это, но обычно они придерживаются темы RBT, поскольку любая другая реализация не будет ресурсоэффективной для достижениязадание set.

Answer 5

C ++ 11 N3337 стандартная тяга

http://www.open -std.org / jtc1 / sc22 / wg21 / docs / documents / 2012 / n3337.pdf

23.2.4 «Ассоциативные контейнеры» говорит:

1 Ассоциативные контейнеры обеспечивают быстрый поиск данных на основе ключей. Библиотека предоставляет четыре основных вида ассоциативные контейнеры: множество, мультимножество, карта и мультикарта.

и

10 Фундаментальное свойство итераторов ассоциативных контейнеров заключается в том, что они выполняют итерации через контейнеры. в нисходящем порядке ключей, где нисходящий определяется сравнением, которое использовалось для построить их.

так да , порядок гарантирован стандартом C ++.

Вот почему, например, gcc 6.4.0 реализует его как BST вместо hashmap: Какова основная структура данных набора STL в C ++?

Сравните это с C ++ 11 unordered_set, который имеет тенденцию обеспечивать лучшую производительность с реализацией хэш-карты, за счет того, что он более ограничен (нет свободного сортированного обхода), как показано на:

• Какова основная структура данных набора STL в C ++?
• Зачем кому-то использовать set вместо unordered_set? например. используя хэш-набор.