C++ Logo

std-proposals

Advanced search

Re: Introducing "capacity preserving operations"

From: Drew Gross <drew.a.gross_at_[hidden]>
Date: Tue, 29 Dec 2020 14:22:01 -0800
I would be very interested in reviewing previous proposals, do you happen
to have any links handy? Or any recommended search terms? "capacity" or
"capacity preserving" aren't turning up very much, and I don't know what
other terminology people might have used for the same concept.

On Tue, Dec 29, 2020 at 1:01 PM organicoman via Std-Proposals <
std-proposals_at_[hidden]> wrote:

> I guess it would be more adequate to propose, selfaware containers, i.e
> containers that flag themselves with a boolean value to tell that they have
> reallocated memory or their contained object have changed.
> Expl:
> Bool Std::vector<T>::dirty() const;
> Which informs the caller that the original "bits" of this vector have
> changed, "bits" here means on stack and on heap.
> I have tried to think about how to implment this, but i hit the following
> question: will a container be tagged dirty only if it changes the first
> time after its construction, or can it be tagged non dirty after a
> modifying operation?
>
> Self-aware containers are very useful in the sense a user can check if the
> container has changed its heap location, while growing, or one of it's
> contained objects had a side effect and mutated ( changed value).
>
> Understanding this problem to make an adequate implementation is still in
> progress on my side.
>
> Nadir
>
>
>
> Sent from my Galaxy
>
>
> -------- Original message --------
> From: Arthur O'Dwyer via Std-Proposals <std-proposals_at_[hidden]>
> Date: 12/29/20 9:49 PM (GMT+01:00)
> To: Std-Proposals <std-proposals_at_[hidden]>
> Cc: Arthur O'Dwyer <arthur.j.odwyer_at_[hidden]>
> Subject: Re: [std-proposals] Introducing "capacity preserving operations"
>
> 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
> --
> Std-Proposals mailing list
> Std-Proposals_at_[hidden]
> https://lists.isocpp.org/mailman/listinfo.cgi/std-proposals
>

Received on 2020-12-29 16:22:14