Logo Search packages:      
Sourcecode: rosegarden version File versions  Download package

FastVector< T > Class Template Reference

#include <FastVector.h>

Inheritance diagram for FastVector< T >:


List of all members.

Detailed Description

template<class T>
class FastVector< T >

FastVector is a sequence class with an interface similar to that of the STL vector, with several nice properties and one nasty one:

It allows fast random access, like the STL vector -- although access is not quite as fast, as a little arithmetic is required.

Appending (push_back) and prepending (push_front) are both fast.

The worst-case behaviour is repeated random inserts and deletes of single items, and performance in this case is still as good as vector where builtin types are stored, and much better where deep-copied objects are stored.

Performance is not as good as vector for very short sequences (where vector's simple implementation excels), but it's not bad.

BUT: To achieve all this, it cheats. Objects are moved around from place to place in the vector using memmove(), rather than deep copy. If you store objects with internal pointers, they will break badly. Storing simple structures will be no problem, and if you just store pointers to objects you'll be fine, but it's unwise (for example) to store other containers.

One other difference from the STL vector: It uses placement new with the copy constructor to construct objects, rather than the default constructor and assignment. Thus the copy constructor must work on the stored objects, though assignment doesn't have to.

Do not use this class if:

You do not require random access (operator[]). Use the STL linked list instead, it'll almost certainly be faster.

Your sequence is constructed once at a non-time-critical moment, and subsequently is only read. Use STL vector, as it's more standard and lookup is slightly quicker.

Your sequence is unlikely to contain more than a dozen objects which are only appended (push_back) and you do not require prepend (push_front). Use STL vector, as it's more standard, simpler and often quicker in this case.

You want to pass sequences to other libraries or return them from library functions. Use a standard container instead.

You want to store objects that contain internal pointers or that do not have a working copy constructor.

Chris Cannam, 1996-2001

Definition at line 86 of file FastVector.h.

Public Types

typedef long difference_type
typedef long size_type
typedef T value_type

Public Member Functions

virtual T * array (size_type index, size_type count)
const T & at (size_type index) const
T & at (size_type index)
virtual const_iterator begin () const
virtual iterator begin ()
virtual void clear ()
bool empty () const
virtual const_iterator end () const
virtual iterator end ()
virtual iterator erase (const iterator &i, const iterator &j)
virtual iterator erase (const iterator &i)
template<class InputIterator>
 FastVector (InputIterator first, InputIterator last)
 FastVector (const FastVector< T > &)
template<class InputIterator>
FastVector< T >::iterator insert (const FastVector< T >::iterator &p, InputIterator &i, InputIterator &j)
template<class InputIterator>
iterator insert (const iterator &p, InputIterator &i, InputIterator &j)
virtual iterator insert (const iterator &p, const T &t)
bool operator!= (const FastVector< T > &v) const
bool operator< (const FastVector< T > &) const
bool operator<= (const FastVector< T > &) const
FastVector< T > & operator= (const FastVector< T > &)
bool operator== (const FastVector< T > &) const
bool operator> (const FastVector< T > &) const
bool operator>= (const FastVector< T > &) const
const T & operator[] (size_type index) const
T & operator[] (size_type index)
virtual void push_back (const T &item)
virtual void push_front (const T &item)
virtual const_reverse_iterator rbegin () const
virtual reverse_iterator rbegin ()
virtual const_reverse_iterator rend () const
virtual reverse_iterator rend ()
size_type size () const
void swap (FastVector< T > &v)
 not all of these are defined yet

Protected Member Functions

virtual void insert (size_type index, const T &)
 basic insert -- all others call this
virtual void remove (size_type index)
 basic remove -- erase(), clear() call this

Private Member Functions

size_type bestNewCount (size_type n, size_t) const
void closeGap ()
size_type externalToInternal (size_type index) const
size_t minBlock () const
size_type minSize () const
void moveGapTo (size_type index)
void resize (size_type needed)

Private Attributes

size_type m_count
size_type m_gapLength
size_type m_gapStart
T * m_items
size_type m_size


class  const_iterator
class  const_reverse_iterator
class  iterator
class  iterator_base
class  reverse_iterator

The documentation for this class was generated from the following file:

Generated by  Doxygen 1.6.0   Back to index