C++ STL : FastCollection

De Wiki de Calcul Québec
Aller à : Navigation, rechercher
Autres langues :anglais 100% • ‎français 100%

C++ STL : la classe FastCollection, basée sur std::vector

Les conteneurs (container classes) de la STL (Standard Template Library) sont extrêmement performants et leur utilisation est fortement recommandée chaque fois que le contexte le permet. Si les besoins spécialisés d'une application ne sont pas satisfaits par les conteneurs disponibles, il est généralement possible d'en étendre les fonctionnalités ou de les jumeler pour arriver à ses fins. Cette approche est préférable à l'écriture d'un nouveau conteneur maison.

L'exemple qui suit montre comment on peut se servir de la classe std::vector<T> pour construire une collection dynamique d'éléments où les opérations d'accès, d'insertion et de suppression sont très rapides. Pour ces deux derniers points, le conteneur std::list<T> est souvent le meilleur choix. Cependant, il s'accompagne d'un surcoût (e.g. deux pointeurs stockés avec chaque élément) qui est parfois inacceptable. Aussi, le vector a le gros avantage d'occuper un espace contigu en mémoire, ce qui favorise un meilleur usage de la cache du processeur.


Fichier : fastcollection.cpp
#include <vector>
 
using namespace std;
 
//------------------------------------------------------------------------------
// Unsorted collection of elements, based on std::vector. Removing elements
// creates a gap at the beginning of the list. New elements are added in the gap,
// if any. Otherwise, they are pushed back at the end of the vector container.
//
// This container is very effective when insertions and deletions abound.
// Filling the gap prevents excessive calls to std::vector::push_back, thus
// consuming less memory and limiting buffer reallocations.
//------------------------------------------------------------------------------
template <class T>
class FastCollection
{
public:
    // constructor
    FastCollection();
 
    // clear all elements
    void Clear();
 
    // get first valid element's index (> 0 when a gap exists)
    inline size_t Begin() const;
 
    // get last valid element's index
    inline size_t End() const;
 
    // add an element
    inline void Add(const T& element);
 
    // remove an element
    inline void Remove(size_t position);
 
    // access any element
    inline const T& operator [] (size_t position) const;
    inline T& operator [] (size_t position);
 
private:
    vector<T>   elements;
    size_t      begin;
};
 
 
template <class T>
FastCollection<T>::FastCollection() : begin(0) {}
 
template <class T>
void FastCollection<T>::Clear()
{
    elements.clear();
    begin = 0;
}
 
template <class T>
size_t FastCollection<T>::Begin() const
{
    return begin;
}
 
template <class T>
size_t FastCollection<T>::End() const
{
    return elements.size() - 1;
}
 
template <class T>
void FastCollection<T>::Add(const T& element)
{
    if (begin == 0)
    {
        elements.push_back(element);
    }
    else
    {
        elements[--begin] = element;
    }
}
 
template <class T>
void FastCollection<T>::Remove(size_t position)
{
    elements[position] = elements[begin++];
}
 
template <class T>
const T& FastCollection<T>::operator [] (size_t position) const
{
    return elements[position];
}
 
template <class T>
T& FastCollection<T>::operator [] (size_t position)
{
    return elements[position];
}


L'extrait suivant illustre l'utilisation de ce conteneur :


Fichier : exemple_fastcollection.cpp
FastCollection<int> myCollection;
 
myCollection.Add(1);
myCollection.Add(2);
...
myCollection.Remove(0);
...
myCollection.Add(100);
 
for (size_t i = myCollection.Begin(); i <= myCollection.End(); ++i)
{
    cout << myCollection[i] << endl;
}


Outils personnels
Espaces de noms

Variantes
Actions
Navigation
Ressources de Calcul Québec
Outils
Partager