Re: [boost] Proposal: Monotonic Containers

Subject: Re: [boost] Proposal: Monotonic Containers
From: Christian Schladetsch (christian.schladetsch_at_[hidden])
Date: 2009-06-14 18:29:41

On Mon, Jun 15, 2009 at 6:39 AM, Thorsten Ottosen <
thorsten.ottosen_at_[hidden]> wrote:

> Christian Schladetsch skrev:
>
>> Hi Thorsten,
>>
>> I have attempted to use boost::auto_buffer for monotonic::inline_storage.
>>
>> If a resize is required and the inline_storage is used by a contiguous
>> container such as a std::vector, the resize breaks said container.
>>
>
> What particularly breaks the container?

A resize that moves the storage for auto_buffer from the stack to the heap
invalidates the pointers used by the vector.

> And why do you want to use auto_buffer for inline_storage?

It was suggested to me that auto_buffer and monotonic were doing similar
things, and that I should investigate using auto_buffer for the storage to
remove any redundancy.

> -Thorsten
>

On a related note:

I am working on a series of containers that allow part of their storage to
come from the stack, and other parts to be on the heap.

I have since written rope<T, C>. This presents a sequence container to the
user, using a list of vectors internally. T is the value_type, C is the
ChunkSize. Each vector within the list-of-vectors is at least ChunkSize
long.

It provides O(N/ChunkSize) access time to elements in the sequence. So it is
slower than a vector, but faster than a list. The speed of access can be
tuned by the user by varying the ChunkSize.

The main benefit of a rope over a vector is that a rope can grow
indefinately without ever needing to be resized.

I realise that 'rope' is a bad name, as it is often used to describe a
similar but different data-structure often used for strings. It's a working
name only at the moment.

I created it mainly to address the issue of resizing vectors that use a
monotonic allocator. When such a vector is resized, it is very wasteful of
memory because the old storage is not reclaimed until the underlying storage
goes out of scope. By using a 'rope' in this case, a sequence with
almost-O(1)-acccess can use a monotonic allocator and still grow.. well,
monotonically, without wasting memory and without ever needing to be
resized.

I am not really convinced of the utility of this, as the main reason for
using a monotonic allocator in the first place is speed, and so it is
counter-intuitive and counter-productive to then have to use to a slower and
not contiguous vector-like thing.

However, it can also support sequences where resizing is otherwise
undesirable or impossible.

For example, my 'rope' supports containers where some of the elements are on
the stack, and others are on the heap.

As another example, a 'rope' could also be made that supports the idea of
`sequence of noncopyable T`, so I'm sticking with the idea for a little
while.

Anyway, it's in the sandbox.

Regards,
Christian