Re: [boost] [submission] STL-compliant containers with copy-on-write

Subject: Re: [boost] [submission] STL-compliant containers with copy-on-write
From: Alexandr Sterligov (sterligov.ak_at_[hidden])
Date: 2011-03-31 11:00:16

I'm working with embedded software and we have to use COW containers pretty
often. I haven't found any COW container implementation which may replace
STL containers and had to implemented it. It is not possible to make STL
containers with COW keeping all semantics of the STL containers. For
example, almost any member-function may throw, because copy ctor may throw.

It is not always safe to replace std::vector with mine cow_vector, but in
most cases it is safe.
For example, it is not safe if you have saved constant pointer or constant
reference from constant cow_vector. But with std::vector saving addresses is
not a good idea as well, because resize, push_back and others may cause
address change.

In my implementation iterators are safe, for example:
cow_vector<int> a;
a.push_back( 1 );

cow_vector<int> b;
b.push_back( 2 );

cow_vector<int>::const_iterator itA = a.begin(); assert( *itA == 1 );
cow_vector<int>::const_iterator itB = b.begin(); assert( *itB == 2 );

b = a;

assert( itA == a.begin() );
assert( itB == b.begin() );
assert( *itA == 1 );
assert( *itB == 1 );

a[0] = 3; // or *a.begin() = 3

assert( itA == a.begin() );
assert( itB == b.begin() );
assert( *itA == 3 );
assert( *itB == 1 );

You example:

int* p = &v[1]; // copying is done here
v[0] = 1;
assert( p == &v[1] ); // still valid as copying was done before.

But in following case it won't work now:

void test( const cow_vector<int>& a )
{
    const int *a = &v[1];
    v[0] = 1;
    assert( p != &v[1] ); // sorry, another pointer if internal buffer was
shared.
}

Please note, that it's possible to do copying if any reference or pointer is
taken from iterator or container itself, but my current implementation
doesn't do it. That's easy to change.

> IMO it isn't possible to really make that work anyway since STL
> containers expose references to their elements *and* make guarantees
> about iterator stability and element layout.  For example, if v is a
> vector and I do
>
>     v[0] = 1;
>
> it's not allowed to change the address of v[1]
> --
> Dave Abrahams
> BoostPro Computing
> http://www.boostpro.com

----
Best regards,
Alexander Sterligov