C++ STL: FastCollection

De Wiki de Calcul Québec
Aller à : Navigation, rechercher
Cette page est une traduction de la page C++ STL : FastCollection et la traduction est complétée à 100 % et à jour.

Autres langues :anglais 100% • ‎français 100%

C++ STL: the FastCollection class, based on std::vector

The container classes within the STL (Standard Template Library) are extremely efficient and their use is strongly recommended each time the context permits. If some specialized needs for an application are not satisfactorily met by the available containers, it is usually possible to extend their functionality or to combine them to get what you need. This approach is preferable to writing a new in-house container.

The following example shows how you can use the std::vector<T> class to build a dynamical collection of elements where read, insert, and delete operations are very fast. For those two last operations, the std::list<T> container is often the best choice. Nevertheless there are additional costs involved (e.g. two pointers are stored for each element) which is sometimes unacceptable. Also, the vector class has the great advantage of using contiguous space in memory, which enables better use of the processor's cache memory.


File : 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];
}


The following snippet shows how to use this container:


File : fastcollection_example.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