Y a-t-il une raison technique pour laquelle std :: lower_bound n'est pas spécialisé pour les itérateurs d'arbre rouge-noir?

Question

J'ai toujours supposé que l' std::lower_bound() s'exécute en temps logarithmique si je passe une paire de rouge-noir arbre itérateurs (set::iterator ou map::iterator) à elle. J'ai dû brûler deux fois d'avis qu' std::lower_bound() s'exécute en O(n) fois dans ce cas, au moins avec la libstdc++ mise en œuvre. Je comprends que la norme n'ont pas la notion du rouge-noir arbre itérateurs; std::lower_bound() va les traiter comme des itérateurs bidirectionnels et advance dans le temps linéaire. Je ne vois pas pourquoi la mise en œuvre ne pouvaient pas créer une mise en œuvre spécifique itérateur balise rouge-noir arbre itérateurs et d'appel spécialisée lower_bound() si le passé dans les itérateurs arrive d'être rouge-noir arbre des itérateurs.

Est-il une raison technique std::lower_bound() n'est pas spécialisé pour les rouge-noir arbre itérateurs?

---

Mise à JOUR: Oui, je suis conscient de la découverte des fonctions de membre, mais c'est pas le point. (Dans basé sur un modèle de code je ne peut pas avoir accès au conteneur ou de ne travailler que sur une partie de l'emballage.)

---

Après le bounty a expiré: je trouve Mehrdad et Yakk réponses les plus convaincantes. Je ne pouvais pas décider entre le trop; je donne la prime à Mehrdad et en acceptant Yakk de réponse.

Answer 1

Il y a plusieurs raisons:

1. Lors de l'utilisation de la non-membre de la version d'un autre prédicat peut être utilisé. En fait, un autre prédicat a à être utilisé lors de l'utilisation, par exemple, un std::map<K, V> que la carte prédicat fonctionne sur Ks, tandis que la gamme opère sur des paires d' K et V.
2. Même si le prédicat est compatible, la fonction dispose d'une interface à l'aide d'une paire de nœuds quelque part dans l'arborescence plutôt que le nœud racine qui seraient nécessaires pour une recherche efficace. Mais il est probable qu'il y a des parents pointeurs, nécessitant donc pour l'arbre semble inappropriée.
3. Les itérateurs fournis à l'algorithme ne sont pas tenus d'être l' t.begin() et de la t.end() de l'arbre. Ils peuvent être quelque part dans l'arbre, ce qui rend l'utilisation de la structure de l'arbre potentiellement inefficace.
4. La bibliothèque standard ne dispose pas d'un arbre d'abstraction ou d'algorithmes sur les arbres. Bien que l'associatif commandé conteneurs sont [probablement] mis en œuvre en utilisant les arbres les algorithmes correspondants ne sont pas exposés à un usage général.

La partie que je considère question est de savoir si l'utilisation d'un nom générique pour un algorithme linéaire de la complexité avec des itérateurs bidirectionnels et logarithmique de la complexité avec des itérateurs à accès aléatoire (je comprends que le nombre de comparaisons est logarithmique de la complexité dans les deux cas et que les mouvements sont considérés comme pour être rapide).

Answer 2

(Élaboration d'un commentaire)

Je pense qu'il est possible de fournir un prédicat qui n'est pas équivalent à celui fourni à l' std::set et encore remplir l'exigence d'partiellement trié (pour les jeux spéciaux). Vous ne pouvez donc remplacer l' lower_bound de l'algorithme par un rouge spécial-version noire si le prédicat est l'équivalent de la std::set de la commande.

Exemple:

#include <utility>
#include <algorithm>
#include <set>
#include <iostream>

struct ipair : std::pair<int,int>
{
    using pair::pair;
};

bool operator<(ipair const& l, ipair const& r)
{  return l.first < r.first;  }

struct comp2nd
{
    bool operator()(ipair const& l, ipair const& r) const
    {  return l.second > r.second; /* note the > */ }
};

std::ostream& operator<<(std::ostream& o, ipair const& e)
{  return o << "[" << e.first << "," << e.second << "]";  }

int main()
{
    std::set<ipair, comp2nd> my_set = {{0,4}, {1,3}, {2,2}, {3,1}, {4,0}};
    for(auto const& e : my_set) std::cout << e << ", ";

    std::cout << "\n\n";

    // my_set is sorted wrt ::operator<(ipair const&, ipair const&)
    //        and       wrt comp2nd
    std::cout << std::is_sorted(my_set.cbegin(), my_set.cend()) << "\n";
    std::cout << std::is_sorted(my_set.cbegin(), my_set.cend(),
                                comp2nd()) << "\n";

    std::cout << "\n\n";

    // implicitly using operator<
    auto res = std::lower_bound(my_set.cbegin(), my_set.cend(), ipair{3, -1});
    std::cout << *res;

    std::cout << "\n\n";

    auto res2 = std::lower_bound(my_set.cbegin(), my_set.cend(), ipair{-1, 3},
                                 comp2nd());
    std::cout << *res2;
}

Sortie:

[0,4], [1,3], [2,2], [3,1], [4,0], 

1
1

[3,1]

[1,3]

Answer 3

Grande question. Honnêtement, je pense qu'il y a pas de bonne/convaincre/raison objective à cela.

Presque toutes les raisons que j'ai ici (par exemple, le prédicat exigence) sont des non-questions pour moi. Ils pourraient être gênant à résoudre, mais ils sont parfaitement solubles (par exemple juste besoin d'un typedef pour distinguer les prédicats).

La raison la plus convaincante que je vois dans le plus haut réponse est:

Mais il est probable qu'il y a des parents pointeurs, nécessitant donc pour l'arbre semble inappropriée.

Cependant, je pense qu'il est parfaitement raisonnable de supposer parent pointeurs sont mis en œuvre.

Pourquoi? Parce que la complexité du temps de l' set::insert(iterator, value) est garanti pour être amorti en temps constant si l'itérateur pointe vers l'emplacement correct.

Considérer que:

1. L'arbre doit rester à auto-équilibrage.
2. En gardant un arbre équilibré, il faut examiner le nœud parent à chaque modification.

Comment peut-on éviter de stocker les parents pointeurs ici?

Sans parent pointeurs, afin d'assurer l'arbre est équilibré après l'insertion, l'arbre doit être parcourue à partir de la racine de tous les temps, ce qui n'est certainement pas amortis à temps constant.

Évidemment je ne peux pas mathématiquement prouver qu'il n'existe aucune structure de données qui peuvent fournir cette garantie, si il y a clairement la possibilité que je me trompe et que c'est possible.
Toutefois, en l'absence de telles structures de données, ce que je veux dire c'est que c'est un raisonnable hypothèse, compte tenu du fait que toutes les implémentations de l' set et map que j'ai vu sont en fait des arbres rouge-noir.

---

Note de côté, mais notez que nous avons simplement ne pouvait pas partiellement-spécialiser les fonctions (comme lower_bound) en C++03.
Mais ce n'est pas vraiment un problème, car nous aurions pu spécialisés, un type au lieu de cela, et a transmis l'appel à une fonction membre de ce type.

Answer 4

Il n'y a aucune raison technique, ce ne pouvait être mis en œuvre.

Pour le démontrer, je vais esquisser un moyen de le mettre en œuvre.

Nous ajoutons un nouvel Itérateur catégorie, SkipableIterator. C'est un sous-type d' BiDirectionalIterator et un supertype de RandomAccessIterator.

SkipableIterators la garantie que la fonction between fait dans un contexte où l' std::between est visible œuvres.

template<typeanme SkipableIterator>
SkipableIterator between( SkipableIterator begin, SkipableIterator end )

between retourne un itérateur entre begin et end. Il retourne end si et seulement si ++begin == end (end est juste après l' begin).

Sur le plan conceptuel, between devrait trouver efficacement un élément "à mi-chemin entre" begin et end, mais nous devons être très prudents afin de permettre une étude randomisée de sauter de la liste ou de l'équilibre rouge noir de l'arbre à la fois pour le travail.

Accès aléatoire itérateurs ont vraiment une mise en œuvre simple d' between -- return (begin + ((end-begin)+1)/2;

Ajouter un nouveau tag est également facile. Dérivation rend les code fonctionne bien tant qu'ils sont correctement utilisés balise de dispatching (et n'a pas explicitement de se spécialiser), mais il y a un petit souci de casse d'ici. Nous pourrions avoir "tag versions" où iterator_category_2 est un raffinement de l' iterator_category (ou soemthing moins hacky), ou on peut utiliser un tout autre mécanisme pour parler de skipable itérateurs (indépendant itérateur trait?).

Une fois que nous avons cette capacité, nous pouvons écrire une rapide commandé algorithmes de recherche qui travaille sur l' map/set et multi. Il serait également travailler sur un saut de liste récipient comme QList. Il serait peut-être encore la même mise en œuvre que l'accès aléatoire version!

Answer 5

Voici une très simple, sans raison technique: Il n'est pas requis par la norme, et tout futur changement va casser la compatibilité avec des existants, le code compilé pour aucune raison.

Le vent de l'horloge datant du début des années 2000, lors de la transition entre la GCC et GCC 3, et plus tard, lors des révisions mineures de GCC 3. De nombreux projets, j'ai travaillé ont été destinés à être compatible binaire; on ne pouvait pas exiger de l'utilisateur de recompiler nos programmes ou plugins, et ne pouvait-on être certain de la version de GCC ils ont été compilés sur ou de la version de la STL ils ont été compilées avec.

La solution: ne pas utiliser la STL. Nous avions dans la maison des chaînes, des vecteurs, et essaie plutôt que d'utiliser la STL. La solution à la dépendance de l'enfer introduit par ostensiblement une partie standard de la langue était si grande, que nous avons abandonné. Pas dans un ou deux projets.

Ce problème a en grande partie disparu, heureusement, et les bibliothèques comme boost se sont engagés à fournir incluent uniquement les versions de la conteneurs STL. Dans GCC 4, je vois pas de problème avec l'utilisation standard des conteneurs STL, et en effet, la compatibilité binaire est beaucoup plus facile, en grande partie en raison des efforts de normalisation.

Mais votre changement d'introduire un nouveau, non-dits, de dépendance

Supposons que demain, une nouvelle structure de données qui vient de sortir, ce qui a beaucoup beats rouge noir des arbres, mais ne fournit pas la garantie que certaines spécialisé itérateurs sont disponibles. Une telle mise en œuvre, qui était très populaire il ya quelques années a été le skip liste, qui offre les mêmes garanties à une beaucoup plus petite empreinte mémoire. Le skip liste ne semblent pas à la casserole, mais une autre structure de données pourrait très bien. Ma préférence personnelle est d'utiliser tente, qui offrent beaucoup plus de performances du cache et plus robuste algorithmique de la performance; leur itérateurs serait sensiblement différent d'un rouge noir des arbres, si quelqu'un en à la bibliothèque libstdc++ décider que ces structures offrent de meilleurs tout autour de performance pour la plupart des usages.

En suivant la norme strictement binaire rétro-compatibilité peut être maintenue même dans le visage de données des modifications de la structure. C'est une Bonne Chose (TM) pour une bibliothèque destinée à être utilisée de façon dynamique. Pour celui qui serait utilisée de manière statique, comme le coup de pouce de Conteneurs de la bibliothèque, je ne voudrais pas bat un œil si ces optimisations ont été bien mis en œuvre et bien utilisé.

Mais pour une bibliothèque dynamique comme libstdc++, binaire rétro-compatibilité est beaucoup plus important.