
Boost : 
From: Leland Brown (lelandbrown_at_[hidden])
Date: 20060616 17:14:31
 Janek Kozicki <janek_listy_at_[hidden]> wrote:
> One last note: above design does not allow to resize
> vectors and
> matrices in runtime. This limits the library usage.
> Should there be
> added a slower complementary library that will allow
> to resize data in
> runtime? Any ideas?
I agree this is useful, and also that it has a
runtime penalty. But I have an idea to reduce that
penalty, as well as reducing the work for the library
implementer to add this feature, without having to
write a whole parallel library. I had hoped to add
this to my own matrix library, but I haven't yet.
(Actually, I need this capability, but I'm using a
less efficient workaround for now.)
A standard way to implement dynamicallysized data
structures is to use dynamic (heap) memory allocation,
which can be costly. Data sized at compile time, on
the other hand, can be allocated efficiently on the
stack. A compromise that works in many situations is
to set a maximum size for each object at compiletime,
allocate memory for the maximum size, and then only
use part of the structure depending on its current
size set at runtime. This allows the data and its
operations to have an adjustable size (up to a
predetermined maximum) while avoiding heap allocation
 the best of both worlds.
As an example of how this can be implemented, suppose
we augment our vector template with an extra template
argument of type bool, which tells if the vector is
resizable  e.g.:
vector<3,double,false> // 3D vector of double
vector<5,double,true> // vector *up to* 5D
The resizable vector needs an extra member to store
the actual current size, and that size should be used
as the upper limit in loops, instead of the size in
the template argument (see example below).
Both kinds of vectors can be implemented with one
definition, by inheriting from separately specialized
base classes. Here's an example:
template< int N, bool resizable >
class vector_base {};
template< int N >
class vector_base< N, false >
{
const int _n = N; // size is constant
};
template< int N >
class vector_base< N, true >
{
public:
// check 1<=new_size<=N and set _n = new_size
void resize( int new_size );
private:
int _n; // actual size set at runtime
};
Then a single vector implementation works for both:
template< int N, type T, bool resizable >
class vector : vector_base< N, resizable >
{
public:
T magnitude();
...
private:
T elements[N];
};
template< int N, type T, bool resizable >
T vector< N, T, resizable >::magnitude()
{
typedef ... T_squared;
T_squared sum = elements[0] * elements[0];
for (int i=1; i<_n; ++i) // use _n, not N
{
sum += elements[i] * elements[i];
}
return sqrt( sum );
}
Note that for resizable vectors, _n is variable, but
for fixedsize vectors, _n is a compiletime constant,
allowing the compiler to do optimizations like loop
unrolling, as you'd expect for a fixedsize vector.
Operations such as dot product require validating that
both vectors have the same size. Again, if both are
fixedsize vectors, this comparison is a compiletime
constant and can be optimized out.
FWIW, I'm not happy with the syntax above of adding an
extra bool parameter. For my code, I planned to use a
negative value of N to indicate resizable:
vector<3,double> // fixed 3D vector
vector<5,double> // up to 5D vector
matrix<4,14,double> // 4x1 to 4x14 matrix
matrix<14,4,double> // 1x4 to 14x4 matrix
matrix<6,6,double> // both values resizable
but this is admittedly nonintuitive (though it does
make both the library and user code more concise).
BTW, this is where I'd really like to see templatized
typedefs in C++, allowing us to define:
template< int N, type T >
typedef vector< N, T, false > fixed_vector;
template< int N, type T >
typedef vector< N, T, true > resizable_vector;
Thus we'd have:
fixed_vector<N,T>
resizable_vector<N,T>
while using the common vector template defined above.
In _The Design and Evolution of C++_, Bjarne
Stroustrup says adding templatized typedefs would be a
"technically trivial" extension, but questions the
wisdom of the idea. Perhaps there's been some
discussion about this topic in Boost?
 Leland
__________________________________________________
Do You Yahoo!?
Tired of spam? Yahoo! Mail has the best spam protection around
http://mail.yahoo.com
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk