distance entre std::set() et std::set itérateur en O(logn)

J'ai besoin de trouver l'indice d'un élément dans std::set. Cet indice peut être visualisée comme la distance de l'itérateur de début.
Une façon peut-être:

for(int i = 0, set<int>::iterator it = s.begin(); it != iteratorToBeFound; ++it, ++i);

De toute évidence, cela prend O(n) fois. Mais nous savons que la distance à partir de la racine dans un arbre de recherche binaire tel que mis en œuvre par l'interne peut être trouvé en O(log n).

Est leurs façon de mettre en œuvre les mêmes pour trouver l'index en O(log n) le temps en C++ ensemble?

Pourquoi auriez-vous besoin de l'index?
Êtes-vous sûr qu'il est possible de trouver la distance en O(log n) temps dans un arbre de recherche binaire? set agit généralement d'un rouge-noir de l'arbre, qui n'a pas beaucoup d'informations à chaque nœud sur la façon dont de nombreux éléments sont à sa gauche et à droite respectivement les sous-arborescences. N'oubliez pas que vous n'êtes pas à la recherche de la distance directement à partir de la racine, vous êtes à la recherche pour le nombre total de feuilles à la gauche de la feuille que vous avez.
Ohh, de sorte que leur n'est pas un moyen pour calculer l'indice en O(logn) dans la R-B de l'arbre?

OriginalL'auteur divanshu | 2012-09-21

  1. 3

    Vous pouvez utiliser triés std::vector<int>. Si elle est triée, vous pouvez rechercher un élément dans O(log n). Et vous pouvez trouver la distance en temps constant O(1).

    Par triés vecteur je veux dire que, après chaque insertion (ou après de nombreuses insertions) vous ne std::sort(v.begin(), v.end());

    Si votre type à l'intérieur de std::set<T> n'est pas comme la lumière comme int - vous pouvez garder les deux - std::set<T> et triés vecteur de itérateurs std::vector<std::set<T>::iterator>. Mais il ne pouvait pas trivial pour garder ces structures dans la synchronisation. Peut-être que vous pouvez ajouter un peu comme la position de T? Ou garder std::set<std::pair<T,int>, comp_first_of_pair<T>> où comp_first_of_pair est juste pour avoir set triés uniquement par T et la deuxième int est pour le maintien de la position dans le jeu?

    Quelques idées - même O(1) distance...

    Mais le tri après chaque insertion dans std::vector m'en coûterait O(nlogn). Où est l'avantage?
    1) Vous pouvez trier seulement après une série d'insertions consécutives. 2) le Coût de l'insertion dans l' std::set<> est O(log n) - n insertions: O(n Log n). 3) Peut-être que vous insert une fois, mais les tests à distance de nombreuses fois....
    Merci @PiotrNycz 🙂

    OriginalL'auteur PiotrNycz

  2. 4

    Vous pouvez utiliser la fonction std::set<>::find à la recherche d'un élément x et de calculer la distance pour la première itérateur de l'ensemble.

    std::distance(s.begin(), s.find(x))

    Cependant, comme les commentaires indiquent la durée d'exécution de la distance dépend du type d'itérateur utilisé. Dans le cas d'un ensemble, c'est un itérateur bidirectionnel et à distance de O(n).

    C'est O(log n + m), cependant. Mais le meilleur que vous pouvez faire, autant que je sache.
    Mais std::distance est O(N) ici.
    Je sais que sur std::distance, mais cela est implémenté de la même manière comme il est écrit dans la question, et certainement est O(n).

    OriginalL'auteur Danvil

  3. 1

    Vous ne pouvez pas utiliser matematics avec des itérateurs bidirectionnels. Donc seule façon acceptable est de compter par vous-même (combien de int moins de X que vous avez inséré dans l'ensemble).

    Mais, si vous avez clairement séparées de "collecte de données" et "utilisation des données" étapes - probablement, il vaut la peine de remplacer std::set avec triés std::vector. Son plus difficile à maintenir, mais ont des avantages, y compris l'itérateur matematics (de sorte que vous pouvez faire des recherches avec O(log n) avec std::binary_search et la distance à O(1) )

    OriginalL'auteur PSIAlt

  4. 1

    Si le calcul de l'indice est vraiment le goulot d'étranglement, puis je vois 2 options:

    • Stocker l'index. Soit dans les nœuds eux-mêmes ou dans un autre std::map.
      Bien sûr, cela signifie que vous devez garder cela cache de mise à jour.
    • Utiliser un std::vector. Ce n'est pas aussi mauvais que cela peut paraître, au premier abord.
      Si vous gardez le vecteur toujours triés, vous pouvez l'utiliser comme un set.
      La performance sera similaire à set.
      Le plus grand inconvénient est: le nœud peut être copié beaucoup.
      (Ceci peut être compensé par l'aide de pointeurs, boost:shared_ptr ou std::unique_ptr [c++11])


      Pour rechercher un élément que vous utilisez std::lower_bound.

      Au lieu d'insérer/push_back vous n': insert( lower_bound(b,e,x), x )

    OriginalL'auteur rtlgrmpf