STL container of fixed capacity but variable size

From: Synge Todo (wistaria_at_[hidden])
Date: 2002-01-30 10:45:44

Dear Boosters,

I would like to propose an STL container of fixed capacity but
variable size.

Sometimes we need a light-weight vector-like container in our codes.
The `array' class in the current Boost library is a good candidate for
such purposes.  However, since the size of vector is fixed at the
compile time, sometimes it is difficult to use it together with
generic algorithms.

For example, in the adjacency_list class in the Boost Graph Library
(BGL), if one can replace the container for out-edges (std::vector by
default) to a light-weight vector like array, it is expected that
overhead in memory allocation will be reduced grately.

Actually, in most applications (at least in my research field), the
maximum number of out-edges in a graph is limited to a certain small
integer of O(1)-O(10).  Therefore, we could fix the capacity of the
container safely at compile time.  However, clearly boost::array can
not be used instead of std::vector in this case, since the number of
out-edges can change if we add/remove edges to/from a graph.  I
believe that similar situations are commonly observed in many
applications in many fields.

That's the motivation why I propose a new container class with fixed
capacity but with variable size.  I have written a simple code and
uploaded it to

  http://groups.yahoo.com/group/boost/files/array2.hpp

which defines a class template:

  template<class T, std:size_t N> boost::array2.

This class might be used almost everywhere instead of std::vector,
except that its capacity is fixed to a (small) integer specified by
the second template parameter, and it throws an exception when its
size exceeds its capacity.

As for the name, I simply named this class as `array2', but presumably
it's not a good name.  'resizable_array', `variable_array', or
`fixed_capacity_vector' might be better.  One possibility should be to
combine the current boost::array class template and my new one into
one class template, and to specialize depending on the third template
parameter:

  template<class T, std::size_t N, bool RESIZABLE = false> array;
  template<class T, std::size_t N, false> array {
    static const bool resizable = false;
    // original boost::array
  };
  template<class T, std::size_t N, true> array
    static const bool resizable = true;
    // array2
  };

Any comments/suggestions will be greatly appreciated.

Best regards,

Synge Todo
wistaria_at_[hidden]