Y a-t-il une classe sorted_vector, qui supporte insert() etc.?

Question

Souvent, il est plus efficace d'utiliser un std::vector trié au lieu d'un std::set. Est-ce que quelqu'un connaît une classe de bibliothèque sorted_vector, qui a essentiellement 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 la recherche binaire à find éléments, etc.

Je sais que ce n'est pas difficile à écrire, mais probablement préférable de ne pas perdre de temps et d'utiliser une implémentation existante de toute façon. La raison d'utiliser un vecteur trié au lieu d'un ensemble est la suivante: Si vous avez des centaines de milliers de petits ensembles qui ne contiennent chacun qu'une dizaine de membres, il est plus économique de n'utiliser que des vecteurs triés. au lieu.

Answer 1

Je pense qu'il n'y a pas d'adaptateur 'conteneur trié' dans la STL car il y a déjà les conteneurs associatifs appropriés pour garder les choses triées qui seraient appropriées à utiliser dans presque tous les cas. Pour être honnête, à propos de la seule raison pour laquelle je peux penser d'emblée à un conteneur trié vector<> pourrait être d'interopérer avec les fonctions C qui attendent un tableau trié. Bien sûr, il me manque peut-être quelque chose.

Si vous pensez qu'un vector<> trié serait plus adapté à vos besoins (en étant conscient des lacunes de l'insertion d'éléments dans un vecteur), voici une application du code du projet:

• An STL compliant sorted vector By Martin Holzherr

Je ne l'ai jamais utilisé, donc je ne peux pas le garantir (ou sa licence - si elle est spécifiée). Mais une lecture rapide de l'article et il semble que l'auteur fait au moins un bon effort pour l'adaptateur de conteneur pour avoir une interface STL appropriée.

Cela semble valoir le coup d'œil.

Answer 2

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

Si vous voulez un vecteur Sorted, il est probable préférable d'insérer tous les éléments, puis appelez std::sort()une fois, après les insertions.

Answer 3

Loki d'Alexandresu a une implémentation vectorielle triée, si vous ne voulez pas passer par l'effort insignifiant relativley de rouler vous-même.

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

Answer 4

Si vous décidez de rouler votre propre, vous pouvez également consulter Boost: uBLAS. Spécifiquement:

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

et de voir coordonnée_vector, qui implémente un vecteur de valeurs et d'index. Cette structure de données prend en charge l'insertion O (1) (en violation du tri), mais trie ensuite Oméga à la demande (n log n). Bien sûr, une fois triée, les recherches sont O (logn). Si une partie du tableau est triée, l'algorithme le reconnaît et ne trie que les éléments nouvellement ajoutés, puis effectue une fusion in-situ.Si vous vous souciez de l'efficacité, c'est probablement ce que vous pouvez faire de mieux.

Answer 5

Boost.Container flat_set

Boost.Container flat_ [plusieurs] conteneurs carte/set sont vecteur classés en fonction des conteneurs associatifs à base de Austern et les lignes directrices de Alexandrescu. Ces conteneurs de vecteurs ordonnés ont également bénéficié récemment de l'ajout de la sémantique de déplacement au C++, ce qui a considérablement accéléré les temps d'insertion et d'effacement. conteneurs associatifs plats ont les attributs suivants:

• recherche plus rapide que les conteneurs associatifs standards
• Bien plus itération que les conteneurs associatifs standard.
• moins la consommation de mémoire pour les petits objets (et pour les gros objets si shrink_to_fit est utilisé)
• performances du cache améliorée (les données sont stockées dans la mémoire contiguë)
• itérateurs non stable (itérateurs sont invalidés lors de l'insertion et l'effacement des éléments)
• types de valeurs non copiables et non-mobiles ne peuvent pas être stockées
• plus faible sécurité exception que les conteneurs associatifs standard (copier/déplacer des constructeurs peut lancer lors du changement des valeurs dans les effacements et des insertions)
• plus lente insertion et l'effacement de associatif standard conteneurs (spécialement pour les types non-mobiles)

Live demo:

#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: Si vous voulez un vecteur Sorted, il est probable préférable d'insérer tous les éléments, puis appelez std :: sort() une fois, après les insertions.

boost::flat_set peut faire automatiquement:

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

Effets: Construit un ensemble vide en utilisant l'objet de comparaison spécifiée et l'allocateur, et insère des éléments de l'intervalle [first, last) .

complexité: linéaire en N si la plage [premier, dernier) est déjà triée en utilisant comp et par ailleurs N * log (N), où N est le dernier - premier.

Answer 6

Here est ma classe triée_vector que j'ai utilisée dans le code de production depuis des années. Il a des surcharges pour vous permettre d'utiliser un prédicat personnalisé. Je l'ai utilisé pour des conteneurs de pointeurs, ce qui peut être une très bonne solution dans beaucoup de cas d'utilisation.