Является ли порядок итераций std:: set всегда возрастающим в соответствии со спецификацией С++?

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

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

Ответы

Ответ 1

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

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

Ответ 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;

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

Ответ 3

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

Ответ 4

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

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

Ответ 5

C++ 11 N3337 стандартный черновик

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

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

1 Ассоциативные контейнеры обеспечивают быстрый поиск данных на основе ключей. Библиотека предоставляет четыре основных типа ассоциативных контейнеров: set, multiset, map и multimap.

а также:

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

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

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

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