Hi all,
On browsing the draft standard library section, it seems to me that the
storage overhead of the container classes are not well specified. In
particular, from the definition of vector<T> given, it appears that an
implementation can only ever grow a vector and never reclaim its storage. At
the least, a user of the class can not assume otherwise. For example,

void f()
{
 vector<int> v1(1000000), v2(1000000); // initially large vectors
 vector<int> v3(1); // initially small vector

 int* pi = &v1[1];
 v1.erase(v1.begin()+1, v1.end());
 // v1.capacity() >= 1000000, v1.size() == 1 here as the standard
(necessarily) specifies that storage is not reallocated so *pi remains valid

 ... other operations on v1

 // at this point we know there are no iterators or references that need to
remain
 // valid so we would like to reclaim storage on v1
 v1.reserve(1); // This won't work, reserve() is defined to only increase
capacity() not decrease it.

 v1.resize(1);  // This won't work, resize() is defined in terms of erase()
which is defined not to reallocate.

 v1.compact(); // Ideally, an operation like this would be defined such that
(for the default allocator at least) v1.capacity() will be  equal to
vector<int>(v1.size()).capacity() i.e. the same storage overhead as a newly
initialized vector of the same size.

 v1.clear() // One would expect that this would free all allocated memory
but clear() is defined in terms of erase() and so this is not guaranteed.
clear() should be defined such that v1.clear().capacity() ==
vector<int>().capacity() is a post-condition (at least for default
allocator) i.e. it has only the same storage overhead as a newly initialised
default empty vector.

 v2 = v3; // One would expect that v2 now only allocates as much memory as
required, but this is not guaranteed by the standard. It could still have
v2.capacity() >= 1000000. Ideally assignment would be specified for vector
such that (v2 = v3).capacity() == vector<int>(v2.size()).capacity() is  a
post-condition .
}

The post-conditions discussed above should be easy to guarantee for the
default allocator- the allocator storage overhead is implementation-specific
but deterministic. At the minimum, they could degrade to suggested behaviour
for user-supplied allocators. The container classes' definitions are careful
to give time complexity guarantees without which they would not be usable in
many situations; I think that some minimum guarantees on space complexity
are also required.

(Note: these comments also apply to basic_string.)

What do others think? Have I missed something here?

,Brian Parker (bparker@gil.com.au)
---
[ comp.std.c++ is moderated.  To submit articles: Try just posting with your
                newsreader.  If that fails, use mailto:std-c++@ncar.ucar.edu
  comp.std.c++ FAQ: http://reality.sgi.com/austern/std-c++/faq.html
  Moderation policy: http://reality.sgi.com/austern/std-c++/policy.html
  Comments? mailto:std-c++-request@ncar.ucar.edu
]