C++ Logo


Advanced search

Introducing "capacity preserving operations"

From: Drew Gross <drew.a.gross_at_[hidden]>
Date: Tue, 29 Dec 2020 11:56:25 -0800
In applications that are careful about memory usage, it's important to know
which operations on a container may allocate and/or deallocate memory. A
common use case is to call reserve() on a std::vector during startup with
the expected maximum size of the vector, then calling clear() on that
vector and reusing it instead of creating a new object while the program is
running. This ensures that no allocations will be performed after startup.
It works because clear() is a "capacity preserving operation" for
std::vector: it does not change the capacity of the vector, and adding more
elements up to the (preserved) capacity does not cause allocations. Note
that this is true in practice, and some standard authors believe the
standard requires it, however the standard does not explicitly have a
definition of "capacity preserving".

I would like to propose developing a definition of a "capacity preserving
operation", and requiring that some operations on some containers be
capacity preserving. For example:

std::vector<T>::clear() would be required to be capacity preversing
std::vector<T>::operator=(const std::vector<T>& other) would be required to
be capacity preserving (nuances with allocators to be fleshed out later,
e.g. perhaps requiring capacity to be preserved only when the allocator is
the same)
std::unordered_map<K, V>::erase() would be required to be capacity

For some operations, it could be implementation-defined whether the
operation is capacity preserving, in order to clarify existing behaviour.
For example:

std::unordered_map<T>::clear() would be implementation defined whether it
is capacity preserving
std::unordered_map<K, V>::operator=(const std::unordered_map<K, V>& other)
would be implementation defined whether it is capacity preserving

It may also be worthwhile to explicitly call out some operations as not
capacity preserving, as that could be useful information for implementers
and language users to have, even though it imposes no requirements on
implementers. std::vector<T>::operator=(std::vector<T>&& other) would not
be capacity preserving (alternatively we could explicitly require that the
capacity of the vector is the same as the previous capacity of other).

Received on 2020-12-29 13:56:38