C++ Logo


Advanced search

Re: Introducing "capacity preserving operations"

From: Jason McKesson <jmckesson_at_[hidden]>
Date: Tue, 29 Dec 2020 22:24:29 -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.

The standard already has at least most of this covered, with regard to
`std::vector` at least. The standard frequently makes mention of when
"reallocation" may happen. And "reallocation" is defined (though not
in a single, central location) to invalidate
pointers/references/iterators to the container. Anything which
provokes "reallocation" is not "capacity preserving" by your
definition. And similarly, if "reallocation" can't happen, then the
operation is "capacity preserving".

However, because the effect of "reallocation" is defined in terms of
invalidating pointers/references/iterators, the standard only talks
about it with operations where that matters. Assignment (whether
copy-assignment or `vector::assign`) overwrites all existing objects,
so it inherently invalidates such pointers/references, so the concept
of "reallocation" doesn't apply even though the vector may have to
allocate a new slab of memory. Same goes for `clear`.

So the functions that would be affected are `clear`, all `assign`
overloads (including possibly future range versions), and
copy-assignment. That's not a lot, so I'd be hesitant to write up a
whole new concept for it. It'd probably be easy enough to just add
remarks about the behavior of that function that the `capacity` is
unchanged (for assignment, only if the new `size` is <= the old

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

While we should say that the new capacity is equal to the old object's
capacity, I don't think anything more needs to be said in that case.

Received on 2020-12-29 21:24:42