Est-il un sorted_vector classe, qui prend en charge insert (), etc.?

Souvent, il est plus efficace d'utiliser une triés std::vector au lieu d'un std::set. Personne ne sait d'une bibliothèque de classe sorted_vector, qui, fondamentalement, a une interface similaire à std::set, mais insère des éléments dans le vecteur trié (de sorte qu'il n'y a pas de doublons), utilise les binaires de recherche à find éléments, etc.?

Je sais c'est pas dur à écrire, mais probablement mieux de ne pas perdre de temps, et d'utiliser une implémentation existante de toute façon.

Mise à jour: La raison de l'utilisation d'un vecteur trié au lieu d'un jeu est la suivante: Si vous avez des centaines de milliers de petits ensembles qui contiennent seulement 10 ou si des membres de chacun, il est plus efficace de la mémoire de l'utiliser juste trié les vecteurs de la place.

  • Pourriez-vous être plus précis sur ce en std::set n'est pas assez efficace?
  • Si vous avez des centaines de milliers de petits ensembles qui contiennent seulement 10 ou si des membres de chacun, il est plus efficace de la mémoire de l'utiliser juste trié les vecteurs de la place.
  • Je ne pense pas qu'il y a un ready-made de classe pour que. Vous pouvez écrire votre propre ou de l'utilisation lower_bound() pour l'insertion et la binary_search() pour la recherche.
  • Si les vecteurs sont de petite taille, la différence entre le binaire et de la recherche séquentielle est susceptible d'être trop petite, de sorte que vous pouvez simplement utiliser un std::vector.
  • La différence va probablement être très importantes à cause de la cache que le jeu va subir.
  • Je suis en train d'écrire ce conteneur. J'en aurais fait en une semaine (avec StackOverflow de l'aide! 🙂 Où est le meilleur endroit pour partager ce code?
  • G: Peut-être télécharger sur google code ou à github et poster le lien ici?
  • C'est par ici: stackoverflow.com/questions/3125905/... . S'il vous plaît laissez-moi savoir si vous faites des améliorations.
  • Je suis un peu en retard à cette question, mais de toute façon 🙂 Vous devriez vérifier si le binaire de recherche triés vecteur de "10" éléments est plus vite que juste une recherche linéaire. Il est tout à fait possible qu'il n'est pas plus rapide, ou il pourrait même être plus lent que le processeur de la direction de la prévision va jouer un rôle important dans ce cas.
  • Document lié par Matt Austern: Pourquoi Vous ne devriez pas Utiliser jeu, et Ce que Vous Devez Utiliser à la Place.

InformationsquelleAutor Frank | 2010-04-25
  1. 28

    Coup de pouce.Conteneur flat_set

    Coup de pouce.Conteneur flat_[multi]carte/jeu de conteneurs sont commandés en vectoriel conteneurs associatifs basés sur Austern et Alexandrescu de lignes directrices. Ces commandé vecteur de conteneurs ont également bénéficié récemment avec l'ajout de la sémantique de déplacement de C++, l'accélération de l'insertion et de l'effacement considérablement les temps. Plat conteneurs associatifs ont les attributs suivants:

    • De recherche plus rapide que la norme de conteneurs associatifs
    • Beaucoup plus rapide itération que les conteneurs associatifs.
    • Moins de consommation de mémoire pour les petits objets (et pour les grands objets si shrink_to_fit est utilisé)
    • L'amélioration des performances du cache (les données sont stockées dans la mémoire contiguë)
    • Non-stable itérateurs (itérateurs sont invalidés lors de l'insertion et de l'effacement d'éléments)
    • Non-copiable et non délocalisables types de valeurs ne peuvent pas être stockés
    • Affaiblissement de l'exception de sécurité que les conteneurs associatifs (copier/déplacer les constructeurs peuvent jeter lors du changement de valeurs dans des ratures et des insertions)
    • Plus lent de l'insertion et de l'effacement que les conteneurs associatifs (spécialement pour les non-mobiles types)

    Démonstration en direct:

    #include <boost/container/flat_set.hpp>
#include <iostream>
#include <ostream>

using namespace std;

int main()
{
    boost::container::flat_set<int> s;
    s.insert(1);
    s.insert(2);
    s.insert(3);
    cout << (s.find(1)!=s.end()) << endl;
    cout << (s.find(4)!=s.end()) << endl;
}

    jalf.com: Si vous voulez un vecteur trié, il est probablement préférable d'insérer tous les éléments, et ensuite appeler std::sort() une seule fois, après les insertions.

    boost::flat_set peut le faire automatiquement:

    template<typename InputIterator> 
flat_set(InputIterator first, InputIterator last, 
         const Compare & comp = Compare(), 
         const allocator_type & a = allocator_type());

    Effets: la construction d'un ensemble vide à l'aide de la comparaison spécifié objet et l'allocateur, et insère des éléments de l'intervalle [first, last).

    Complexité: Linéaire en N, si l'intervalle [first, last) est déjà triés à l'aide de comp et sinon N*log(N), où N est le dernier - premier.

    InformationsquelleAutor Evgeny Panasyuk
  2. 7

    La raison d'un tel contenant ne fait pas partie de la bibliothèque standard, c'est qu'il serait inefficace. À l'aide d'un vecteur de moyens de stockage d'objets doivent être déplacés si quelque chose est inséré dans le milieu du vecteur. Faire cela sur chaque insertion devient inutilement coûteux. (En moyenne, la moitié des objets devront être déplacés pour chaque insertion. C'est assez coûteux)

    Si vous voulez un vecteur trié, il est probablement préférable d'insérer tous les éléments, et ensuite appeler std::sort() une fois, après les insertions.

    • Donc, mise à jour de la triés classe vector pour C++0x sémantique de déplacement.
    • Je ne vois pas comment cela pourrait résoudre le problème. Tous les objets doivent encore être touché, même si c'est seulement un pointeur de swap. Vous êtes toujours en train de faire quelque chose que la structure de données n'est tout simplement pas adapté pour.
    • J'ai commencé à écrire une réponse comme ça, et s'est arrêté parce qu'il n'est tout simplement pas vrai. Pour moins de quelques dizaines d'éléments, ce qui est assez commun, vraiment, se déplaçant en moyenne, la moitié peut facilement être moins cher que de l'exécution d'une allocation et d'un arbre de rééquilibrer. Bien sûr, il est préférable d'appeler sort une fois, et personnellement, je ne regarde pas pour un conteneur pour ce faire, mais c'est une affaire de style.
    • L'insertion de n éléments dans un tableau trié est log n pour trouver le point d'insertion et n/2 pour déplacer les éléments existants, pour n éléments. O(nnlog n), pas efficace du tout. Peut que si n est assez petit mais.
    • En le remplaçant par un nœud à base de discbased n'était pas ma suggéré d'autres si. Comme vous le dites, le tas allocations et des arbres rééquilibrage devient trop cher (bien qu'un allocateur personnalisé pourrait aider un peu). Le tri une fois, à la fin, c'était de ma suggestion.
    • Je suggère une combinaison de std::map et std::vector comme une solution.
    • Downvote: Matt Austern donne très clairement le cas d'utilisation de ce, et est également plus clair sur pourquoi il ne fait pas partie de la STL (le coûteux insérer/supprimer). Indiquant qu'une telle mise en œuvre est inefficace n'est pas correct. Seules quelques opérations sont plus inefficace contre conteneurs associatifs. D'autres sont plus performants. Et comme il le mentionne, les plus chers, souvent, n'a pas d'importance. Downvoted parce que la réponse n'a pas vraiment répondre à la question, ni de distinction à l'efficacité de l'opération, ni mention du coup de pouce parfaitement raisonnable de mise en œuvre.
    • avez-vous par hasard de lire la partie où je vous suggère de vous pouvez trier le vecteur quand vous en avez besoin pour être triés, évitant ainsi la surcharge inutile de tri entre tous insertion, , tout en conservant tous les avantages d'un vecteur trié? Quand je dis qu'une sorted_vector structure de données serait inefficace, je veux dire par rapport à une régulière vecteur est trié sur une base comme-nécessaire. Celle-ci a tous les avantages d'un vecteur trié, sans payer un inutile des coûts en matière d'insertion. Ainsi, l'ancien est inefficace.
    • Ici, une autre downvote. Il y a certainement un cas pour un vecteur trié à se comporter comme un ensemble ou d'un conteneur associatif en termes de son interface, qui a propres caractéristiques de performance (très cher insérer/mettre à jour si vous voulez), et ceci est démontré par l'existence même de boost::flat_map et autres. Cette réponse n'ajoute pas de valeur.
    • inefficace en 2017
    • Cette réponse ignore le fait évident que les types de données abstraites existent à ce que l'on peut cacher les détails d'implémentation, et "do the right thing" qui, dans le cas de cette réponse pose, est de tout simplement ajouter de la valeur insérée à la fin du vecteur jusqu'à ce qu'il est lu par une méthode qui exige qu'elle soit triée. Par exemple, une méthode qui demande la longueur du vecteur n'exige pas que le vecteur être triés pour l'instant. Toutefois, en prenant la valeur médiane de, disons, un vecteur de nombres exigerait que le vecteur être triés de l'état et, si elle n'est pas, à les trier, à l'époque.
    • Cela dépend fortement de la façon dont il va être utilisé. Si vous avez besoin d'effectuer des insertions de façon sporadique et, rarement, mais vous avez besoin très rapidement de la lecture, un vecteur peut être plus rapide, même pour les grandes listes, puis dire un arbre binaire serait.
    • Bien sûr, coût d'insertion ne peut pas d'importance si vous êtes à la recherche de plusieurs ordres de grandeur de plus que vous insérez. Auquel cas, vecteur post-tri aurait encore du travail, mais peut-être que le binaire de recherche serait moins syntaxiquement sucrées. J'avoue que je n'ai pas réfléchi trop profondément.

    InformationsquelleAutor jalf
  3. 5

    Je pense qu'il n'y a pas " triés contenant de l'adaptateur dans la STL, car il y a déjà approprié conteneurs associatifs pour garder les choses triés qui serait approprié d'utiliser dans presque tous les cas. Pour être honnête, la seule raison pour laquelle je peux penser à du haut de ma tête pour avoir une triés vector<> conteneur peut être à interagir avec les fonctions C qui attendent un tableau trié. Bien sûr, j'ai peut-être raté quelque chose.

    Si vous vous sentez qu'une triés vector<> serait plus approprié à vos besoins (en étant conscient des lacunes de l'insertion d'éléments dans un vecteur), voici une mise en œuvre sur le Code du Projet:

    Je n'ai jamais utilisé, donc je ne peux pas se porter garant pour elle (ou sa licence - si aucun n'est spécifié). Mais une lecture rapide de l'article, et il semble que l'auteur, au moins, a fait un bon effort pour l'adaptateur de conteneur de disposer d'une interface STL.

    Il semble intéressant de regarder de plus près.

    • Un vecteur trié est susceptible d'être plus rapide jusqu'à ce que l'ensemble est assez grand (100 éléments). Ensembles de horrible cache-localité.
    InformationsquelleAutor Michael Burr
  4. 4

    Si vous décidez de rouler vos propres, vous pourriez également vouloir vérifier boost:ublas. Plus précisément:

    #include <boost/numeric/ublas/vector_sparse.hpp>

    et de regarder coordinate_vector, qui met en oeuvre un vecteur de valeurs et indices. Cette structure de données prend en charge O(1) insertion (violation de la sorte), mais ensuite, sortes sur demande Omega(n log n). Bien sûr, une fois triés, les recherches sont en O(logn). Si une partie du tableau est trié, l'algorithme prend cela en compte et trie seuls les nouveaux éléments ajoutés, fait une place de fusion. Si vous vous souciez de l'efficacité, c'est probablement le meilleur que vous pouvez faire.

    InformationsquelleAutor Neil G
  5. 3

    Alexandresu de Loki est un vecteur trié mise en œuvre, si vous ne voulez pas passer par la relativley non négligeable de l'effort de roulement vous sont propres.

    http://loki-lib.sourceforge.net/html/a00025.html

    InformationsquelleAutor Lance Diduck
  6. 0

    Ici est mon sorted_vector classe que j'ai utilisé dans la production de code pour les années. Il a surcharges pour vous permettre d'utiliser un prédicat. Je l'ai utilisé pour des conteneurs de pointeurs, ce qui peut être vraiment une bonne solution dans beaucoup de cas d'utilisation.

    InformationsquelleAutor moodboom