Est std::set itération afin de toujours croissant selon le C++ cahier des charges?

Ici http://www.cplusplus.com/reference/stl/set/ j'ai lu que std::set en C++ est "généralement", mis en œuvre comme un arbre rouge-noir?) et elle est triée.

Je ne pouvais pas comprendre, ça veut dire que par la spécification itération de l'ordre de jeu est toujours croissant? Ou est-ce que "l'habitude de la mise en œuvre du détail" et parfois, une bibliothèque/compilateur de violer cette convention?

InformationsquelleAutor Rodion Gorkovenko | 2012-01-12
  1. 44

    Par la norme C++, l'itération sur les éléments d'un std::set produit dans l'ordre déterminé par std::less ou par l'option de comparaison prédicat argument de modèle.

    (Également par la norme C++, d'insertion, de recherche et de suppression de prendre, au plus O(lg n) de temps, de manière équilibrée arbres de recherche sont actuellement la seule solution viable de mise en œuvre de choix pour std::set, même si l'utilisation des arbres rouge-noir n'est pas prescrite par la norme).

    • Et même pour suffisamment de petites collections où la complexité est dénuée de sens, de la stabilité des itérateurs implique que l'utilisation des index dans un tableau trié ne peuvent pas travailler.
    InformationsquelleAutor Fred Foo
  2. 21

    Cela signifie que, en interne std::set pour le stockage de ses éléments triés arbre. Toutefois, la spécification ne dit rien sur l'ordre de tri. Par défaut, std::set utilise std::less et il en sera de l'ordre de bas en haut. Cependant, vous pouvez faire de la fonction de tri être ce que vous voulez, à l'aide de ce paramètre de modèle:

    std::set<valueType, comparissonStruct> myCustomOrderedSet;

    Ainsi, par exemple:

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

    ou

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

std::set<int, cmpStruct > myInverseSortedSet;

    En fait, ces exemples sont également fournis sur le site web lié. Plus précisément ici: constructeur d'ensemble.

    InformationsquelleAutor Darhuuk
  3. 3

    La valeur par défaut de comparaison est moins, de sorte que le jeu sera ordonnée dans l'ordre croissant. Pour changer cela, vous pouvez spécifier un autre existant ou personnalisé comparateur comme un argument de modèle.

    InformationsquelleAutor Marian Petre
  4. 2

    par la spécification de l'itération de l'ordre de jeu est toujours croissant

    Oui, les valeurs de réglage sont toujours croissant si vous les imprimer dans l'ordre. La description dit, il est généralement mis en œuvre à l'aide de Red-Black Tree(RBT), mais le compilateur écrivains ont la possibilité de violer le présent, mais généralement les coller au Thème de la RBT toute autre mise en œuvre ne sera pas une utilisation efficace des ressources pour réaliser la tâche d' set.

    InformationsquelleAutor Shamim Hafiz
  5. 1

    C++11 N3337 projet de norme

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

    23.2.4 "conteneurs Associatifs" dit:

    1 conteneurs Associatifs fournir une récupération rapide des données basées sur les touches. La bibliothèque fournit quatre types fondamentaux de
    conteneurs associatifs: ensemble, multiset, map et multimap.

    et:

    10 La propriété fondamentale des itérateurs de conteneurs associatifs, c'est qu'ils itérer sur les conteneurs
    dans le non-ordre décroissant des touches de cas de non-descendant est définie par la comparaison qui a été utilisé pour
    leur construction.

    donc oui, l'ordre est garanti par la norme C++.

    C'est pourquoi gcc 6.4.0 par exemple la met en œuvre, comme un BST au lieu de hashmap: Qu'est-ce que les données sous-jacentes de la structure d'un STL jeu en C++?

    Cela contraste avec C++11 unordered_set, qui tend à fournir de meilleures performances avec une table de hachage de la mise en œuvre, au prix d'être plus restreint (pas de libre triés traversal), tel que montré à:

    • Dovoters: veuillez expliquer afin que je puisse apprendre et de s'améliorer info.
    InformationsquelleAutor Ciro Santilli 新疆改造中心996ICU六四事件