Existe-t-il une classe sorted_vector, qui prend en charge insert () etc.?

Question

Souvent, il est plus efficace d'utiliser une triés std::vector au lieu de std::set. Personne ne sait d'une bibliothèque de classe sorted_vector, qui, fondamentalement, a une interface similaire à l' 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 d' find - éléments, etc?

Je sais que 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 d'utiliser 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.

Answer 1

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:

• Plus rapide de recherche que les 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 stables 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 cad 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.

Answer 2

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 ça à 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, puis d'appeler l' std::sort() une fois, après les insertions.

Answer 3

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:

• STL conforme vectoriel trié Par Martin Holzherr

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.

Answer 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 regardez 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.

Answer 5

Le Loki d'Alexandresu a une implémentation vectorielle triée, si vous ne voulez pas passer par l'effort insignifiant de rouler le vôtre.