10
votes

Distance entre STD :: Set Begin () et STD :: Définir Itérator in O (logn)

J'ai besoin de trouver l'index d'un élément dans STD :: Set. Cet indice peut être visualisé comme la distance de l'itérateur du début. Une façon peut être: xxx

cela prend clairement O (n) heure. Mais nous savons que la distance de la racine dans un arbre de recherche binaire tel que mise en œuvre par définie peut être trouvée en interne dans O (journal n) TIME.

est leur façon de mettre en œuvre la même chose pour trouver l'index dans O (journal n) TEMPS EN C ++ SET?

c++ set stl iterator std

3 commentaires

Pourquoi auriez-vous besoin de l'index?

Êtes-vous sûr qu'il est possible de trouver la distance dans O (log n) heure dans un arbre de recherche binaire? SET est typiquement un arbre noir rouge, qui n'a pas beaucoup d'informations sur chaque nœud sur le nombre d'éléments dans ses sous-arbres de gauche et de droite respectivement. N'oubliez pas que vous ne cherchez pas la distance directement de la racine, vous recherchez le nombre total de feuilles à gauche de la feuille que vous avez.


                                        
                                                                            @Stevejessop: Ohh, donc leur n'est pas un moyen de calculer l'index dans O (logn) dans l'arbre R-B alors?



                                    
                    5 Réponses :
                    
                                            
                            
                                
                                    4
 votes
                                
                            
                            
                                
                                     Vous pouvez utiliser la fonction   std :: Set <> :: Trouver   pour rechercher un élément  x  et calculer le  Distance  sur le premier itérateur de l'ensemble.  xxx  
 Cependant, comme indiquent que les commentaires indiquent que l'exécution de distance dépend du type d'itérateur utilisé. Dans le cas d'un ensemble, il s'agit d'un itérateur bidirectionnel et de la distance est O (n).                                  


                                                                    
                                    
                                    
                                        3 commentaires
                                        
                                                                                            
                                                    C'est  O (journal n + m) , cependant. Mais le meilleur que vous puissiez faire, Afaik.                                                

                                                
                                                                                            
                                                    Mais  STD :: Distance  est O (n) ici.                                                
                                                
                                                                                            
                                                    Je sais à propos de STD :: Distance, mais cela est mis en œuvre de la même manière que l'écrit dans la question et est définitivement d'o (n).                                                
                                                
                                                                                    

                                    

                                                            

                        

                        
                                            
                            
                                
                                    1
 votes
                                
                            
                            
                                
                                     Vous ne pouvez pas utiliser de marématics avec des itérateurs bidirectionnels. Donc, seule une manière acceptable est de compter vous-même (combien de  int  moins que x vous inséré dans ensemble). 

 Mais, si vous avez une "collecte de données" et de "collection" et "de données", il vaut probablement la peine de remplacer  STD :: SET  avec trié  std :: vecteur . Son plus difficile à entretenir, mais avoir ses propres avantages, y compris des marématics d'itérateurs (vous pouvez donc obtenir la recherche avec O (log n) avec  std :: binaire_search  et la distance avec O (1))                                 


                                                                    
                                    
                                    
                                        0 commentaires
                                        
                                                                                    
                                    
                                                            

                        

                        
                                            
                            
                                
                                    3
 votes
                                
                            
                            
                                
                                     Vous pouvez utiliser le tri  std :: vecteur  . S'il est trié, vous pouvez trouver un élément dans  O (journal n) . Et vous pouvez trouver la distance dans le temps constant  o (1) . 

 Par vecteur trié, je veux dire qu'après chaque insertion (ou après de nombreuses insertions), vous faites  std :: Trier (v.begin (), v.end ());  

 Si votre type à l'intérieur  std :: Set   n'est pas aussi léger que  int  - vous pouvez garder les deux -  std :: set   et trié Vecteur d'itérateurs  std :: Vecteur  :: Itérateur> . Mais il ne pouvait pas trival de conserver ces structures en synchronisation. Peut-être que vous pouvez ajouter une position similaire à  t ? Ou garder  std :: set , comp_first_of_pair >  où  comp_first_of_pair  est juste d'avoir  définir  Trier uniquement par  t  et le second  int  est destiné à garder la position dans SET? 

 Juste quelques idées - avoir même  o (1)  distance ...                                 


                                                                    
                                    
                                    
                                        2 commentaires
                                        
                                                                                            
                                                    Mais trier après chaque insertion dans std :: vecteur me coûterait O (nlogn). Où est l'avantage?                                                
                                                
                                                                                            
                                                    1) Vous ne pouvez trier qu'après une série d'insertions consécutives. 2) Coût d'insertion dans  std :: Set <>  est  o (journal> - N insertions:  O (n log n) . 3) Peut-être que vous  insérer  une fois - mais la distance de test plusieurs fois ....                                                

                                                
                                                                                    

                                    

                                                            

                        

                        
                                            
                            
                                
                                    1
 votes
                                
                            
                            
                                
                                     Si calculer l'index est  vraiment  votre goulot d'étranglement, alors je vois 2 options: 


 stocker l'index. Soit dans les nœuds eux-mêmes ou dans un  STD :: map .
Bien sûr, cela signifie que vous devez garder ce cache mis à jour. 
 Utilisez un  std :: vecteur . Ce n'est pas aussi mauvais que cela pourrait regarder d'abord.
Si vous gardez le vecteur toujours trié, vous pouvez l'utiliser comme un  définir .
Les performances seront similaires à  définir .
Le plus grand inconvénient est: le nœud peut être copié beaucoup.
(Ceci peut être compensé à l'aide des pointeurs,  Boost: partagé_ptr  ou  std :: unique_ptr  [C ++ 11 seulement])
de 

Pour rechercher un élément que vous utilisez  std :: inférieur . de 

Au lieu d'insertion / push_back, vous faites:  Insérer (BASTER_BOUND (B, E, X), X)  
                                


                                                                    
                                    
                                    
                                        2 commentaires
                                        
                                                                                            
                                                    Insérer est une fonction O (n) en vecteur                                                
                                                
                                                                                            
                                                    Et n'oubliez pas d'utiliser une version spécialisée de BASTER_BOND pour les conteneurs qui le met en œuvre. NEWER UTILISE STD :: Multi) Carte et (MULTI) SETS ET (MULTI)                                                
                                                
                                                                                    
                                    
                                                            

                        

                        
                                            
                            
                                
                                    2
 votes
                                
                            
                            
                                
                                     Vous pouvez trouver l'index d'un élément dans un ensemble dans O (journal (n)) avec un ensemble commandé:  https://www.geeksforgeeks.org/ordered-set-gnu-c-pbds/ . Ceci est implémenté comme un arbre noir noir. Je sais que ce sujet est très vieux, mais cela pourrait aider les lecteurs à l'avenir.                                 

                                                                    
                                    
                                    
                                        1 commentaires
                                        
                                                                                            
                                                    Plutôt que de créer un lien vers une ressource externe, veuillez extraire la partie correspondante de celle-ci et l'inclure dans votre réponse.

Articles qui pourrait vous intéresser : Catalina C ++: L'utilisation d'en-têtes <cmath> génère une erreur: aucun membre nommé 'signbit' dans l'espace de noms global installation du compilateur c ++ 11 (+) sans autorisation d'administrateur Application de console C ++ VS2019 - Le débogueur n'acceptera pas les arguments de commande Meilleur moyen en C ++ de garder une grosse structure atomique?