C++ Logo

std-proposals

Advanced search

Re: Introducing "capacity preserving operations"

From: Arthur O'Dwyer <arthur.j.odwyer_at_[hidden]>
Date: Tue, 29 Dec 2020 15:48:48 -0500
On Tue, Dec 29, 2020 at 2:56 PM Drew Gross via Std-Proposals <
std-proposals_at_[hidden]> wrote:

> 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.
>

I like this idea in theory.
In practice, I think the project is mostly a review-of-literature: How many
times has this been proposed? in what years? by whom? why was it shot down?
and importantly, what new information has come to light since then?
Because this is *definitely* not the first time anyone's thought of it.

Also, before you start enumerating operations that are capacity-preserving,
you should define what you mean by "capacity."
- For `vector`, you don't just mean that the capacity() remains the same;
you also mean that the data() remains the same pointer, right?
"Capacity-preserving" means "guaranteed not to reallocate."
- For `unordered_map`, do you mean that bucket_count() remains the same?
- For `deque`, there is a concept of reallocation and a concept of
capacity, but it is not exposed through the public API.

The Standardese for "capacity-preserving" is probably more along the lines
of "does not invalidate iterators, pointers, or references into the
controlled sequence."
Notice that `deque` never invalidates pointers or references, but
"reallocating" operations *do* invalidate iterators.

Is it possible that these guarantees are *already* being made in the paper
Standard, but because they are made in Standardese (in terms of
"invalidated iterators"), you simply missed them? IMHO this would be a
problem; but CWG is unlikely to share my HO about it, because "the Standard
is not a teaching document" and so on.

my $.02,
Arthur

Received on 2020-12-29 14:49:01