Policy-based array

From: Ross Smith (ross.s_at_[hidden])
Date: 2001-08-21 20:55:22

I've finally developed my policy-based array template into something
suitable for showing to the Boost membership.

The template is called boost::vector, and uses policy flags to select:

-- Whether the elements are known to be PODs (which allows some
optimisations);
-- Whether to default-initialise elements if no value is supplied, or
leave them uninitialised;
-- Whether the iterators are classes or just pointers;
-- Whether the vector is fixed-size or variable size;
-- Whether the capacity changes linearly or exponentially;
-- Whether the capacity can only increase (like std::vector), or can
decrease if the size decreases.

Although this was inspired by Andrei Alexandrescu's book, my approach to
policies differs from his in one way: where he used a separate template
argument for each policy, I've merged all the policy flags into a single
argument, composed by bitwise-OR-ing the desired non-default options
together. This may help to answer the "every template parameter loses
half your users" problem. :-)

In its current form, it's not quite ready for submission as a Boost
component, because it falls short of std::vector in at least two ways:

First, the excess elements -- the difference between size() and
capacity() -- are just default-initialised on construction, and left
alone when they're not used. A proper implementation of std::vector
leaves the excess capacity as uninitialised memory, constructing the
elements using placement new only when necessary. This means that my
vector, unlike std::vector, requires its element type to be default
constructible, and will often call constructors and destructors
unnecessarily.

Second, the versions of the constructor and the assign() and insert()
functions that copy a range defined by a pair of iterators only work
with forward iterators or better (because they use std::distance() to
detemine the size of the range). A good std::vector replacement would
have a specialisations for input iterators that repeatedly call
push_back() or insert(one element) instead of constructing the range all
at onec.

I intend to fix both of these shortcomings (and any others anybody
spots, of course) before making a formal submission to Boost.

The code has only been tested with GCC 2.95.3. Because it relies heavily
on partial specialisation, I don't think anyone has a tarball's chance
in Redmond of ever getting anything remotely resembling it to work with
any existing version of MSVC.

I've also included a "boost-ified" version of my smart pointer template.
This isn't really intended as a submission to Boost in its own right,
more as a second example, for comparison with Andrei's, of a policy
based smart pointer. A serious attempt a PBSP for Boost should probably
be designed from scratch, based on a consensus of requirements.

You can find the code at:

http://storm.net.nz/~ross/c++/policy_based.tgz

-- 
Ross Smith <ross.s_at_[hidden]> The Internet Group, Auckland, New Zealand
========================================================================
"Unix has always lurked provocatively in the background of the operating
system wars, like the Russian Army."                  -- Neal Stephenson