Is there a reference counted implementation of std::vector?

[Jason Heyes]

When would you use a shared_vector (if ever) and why?

I wouldn't! I'd use a shared_ptr<vector>, since shared_vector is just
syntatic sugar.

Writing a COW shared_vector as you propose that doesn't have
surprising behaviour is not easy - it's not clear what the semantics
should be. To get the "correct" semantics working requires very
conservative sharing, which rather defeats the point...

e.g.

shared_vector<T> v1;
//...
shared_vector<T> v2 = v1; //shared
shared_vector<T> const& v2ref = v2;
T const& t = v2ref[0]; //does this unshare?
assert(v2[0] == v2ref[0]); //this should clearly work!

Tom

C++ FAQ: http://www.parashift.com/c++-faq-lite/
C FAQ: http://www.eskimo.com/~scs/C-faq/top.html

shared_vector<T> v1;
//...
shared_vector<T> v2 = v1; //shared yes
shared_vector<T> const& v2ref = v2;
T const& t = v2ref[0]; //does this unshare? No. v2ref is const
assert(v2[0] == v2ref[0]); //this should clearly work! Yes it does. v2 is
const within expression
// therefore const version of operator[] is called
// which means v2 does not unshare

Am I correct?

 

[tom_usenet]

shared_vector<T> v1;
//...
shared_vector<T> v2 = v1; //shared yes
shared_vector<T> const& v2ref = v2;
T const& t = v2ref[0]; //does this unshare? No. v2ref is const
assert(v2[0] == v2ref[0]); //this should clearly work! Yes it does. v2 is
const within expression
// therefore const version of operator[] is called
// which means v2 does not unshare

Am I correct?

No. non-const operator[] is called for non-const objects.

Tom

C++ FAQ: http://www.parashift.com/c++-faq-lite/
C FAQ: http://www.eskimo.com/~scs/C-faq/top.html

 

[tom_usenet]

shared_vector<T> v1;
//...
shared_vector<T> v2 = v1; //shared yes
shared_vector<T> const& v2ref = v2;
T const& t = v2ref[0]; //does this unshare? No. v2ref is const
assert(v2[0] == v2ref[0]); //this should clearly work! Yes it does. v2 is
const within expression
// therefore const version of operator[] is called
// which means v2 does not unshare

Am I correct?

No. non-const operator[] is called for non-const objects.

Whoops, and the assert was meant to be:

assert(&v2[0] == &v2ref[0]);

Tom

C++ FAQ: http://www.parashift.com/c++-faq-lite/
C FAQ: http://www.eskimo.com/~scs/C-faq/top.html

 

[Karl Heinz Buchegger]

Take the following class:

class Image
{
SharedVector<Pixel> pixels;
// ...
};

and assume it uses compiler-generated constructors. What does it really mean
to make a copy of an Image? It is no longer a costly operation

What's SharedVector?
Is it some sort of reference counted vector?
I guess so. At least it is consistent with the following

but consider
what happens when the Image is mutated.

void Image::negate()
{
pixels.make_unique(); // copying may take place here

SharedVector<Pixel>::size_type i;
for (i=0; i < pixels.size(); i++)
pixels.negate();
}

Now Image::negate is potentially a costly operation. What do you think?

It is a costly operation and may not be what the user of the class
expects. Personally I try to avoid such clever hacks. If the user requests
a copy, he gets a copy. He has a reason for requesting the copy and is willing
to pay the price for that at the moment he is requesting that copy.
But manipulation and copying are 2 different concepts. That's why I avoid
such things. But that's IMHO.

 

[Jason Heyes]

Take the following class:

class Image
{
SharedVector<Pixel> pixels;
// ...
};

and assume it uses compiler-generated constructors. What does it really mean
to make a copy of an Image? It is no longer a costly operation

What's SharedVector?
Is it some sort of reference counted vector?
I guess so. At least it is consistent with the following

but consider
what happens when the Image is mutated.

void Image::negate()
{
pixels.make_unique(); // copying may take place here

SharedVector<Pixel>::size_type i;
for (i=0; i < pixels.size(); i++)
pixels.negate();
}

Now Image::negate is potentially a costly operation. What do you think?

It is a costly operation and may not be what the user of the class
expects. Personally I try to avoid such clever hacks. If the user requests
a copy, he gets a copy. He has a reason for requesting the copy and is willing
to pay the price for that at the moment he is requesting that copy.
But manipulation and copying are 2 different concepts. That's why I avoid
such things. But that's IMHO.

Yes it looks bad. Its just too much to assume that the user understands
copy-on-write. I know I don't. Do you think it would help if we renamed the
class to SharedImage? At least that way you make the user aware of what he
is playing with.

 

[Jason Heyes]

No. non-const operator[] is called for non-const objects.

Whoops, and the assert was meant to be:

assert(&v2[0] == &v2ref[0]);

Tom

C++ FAQ: http://www.parashift.com/c++-faq-lite/
C FAQ: http://www.eskimo.com/~scs/C-faq/top.html

Hehe. I never noticed that. I just assumed it meant that.

 

[Jason Heyes]

shared_vector<T> v1;
//...
shared_vector<T> v2 = v1; //shared yes
shared_vector<T> const& v2ref = v2;
T const& t = v2ref[0]; //does this unshare? No. v2ref is const
assert(v2[0] == v2ref[0]); //this should clearly work! Yes it does. v2 is
const within expression
// therefore const version of operator[] is called
// which means v2 does not unshare

Am I correct?

No. non-const operator[] is called for non-const objects.

Tom

C++ FAQ: http://www.parashift.com/c++-faq-lite/
C FAQ: http://www.eskimo.com/~scs/C-faq/top.html

How about this design:

template <class T, class A = allocator<T> >
class shared_vector
{
shared_ptr<std::vector<T> > ptr;
public:
// duplicate public interface, forwarding to ptr
// exceptions are copy constructor and assignment and destructor
// which should be compiler generated ones.

// all mutators unshare except those that return an iterator or
reference

// a non-standard function to unshare
};

Here is the usage:

#include <algorithm>
#include <iostream>
#include "shared_vector.h"

std::istream &read_nums(std::istream &is, shared_vector<int> &nums)
{
while (is)
{
int num;
if (is >> num)
nums.push_back(num);
}
return is;
}

int main()
{
shared_vector<int> nums;
if (!read_nums(std::cin, nums))
return 1;

nums.push_back(-1); // vector is automatically unshared by this
operation

nums.unshare(); // manually unshare vector before indirect modification
sort(nums.begin(), nums.end());

for (int i=0; i < nums.size(); i++)
os << nums << endl;
return 0;
}

The user must understand copy-on-write to use shared_vector properly. What
do you think?

 

[tom_usenet]

How about this design:

template <class T, class A = allocator<T> >
class shared_vector
{
shared_ptr<std::vector<T> > ptr;
public:
// duplicate public interface, forwarding to ptr
// exceptions are copy constructor and assignment and destructor
// which should be compiler generated ones.

// all mutators unshare except those that return an iterator or
reference

// a non-standard function to unshare

I think I might make mutators not unshare, and only unshare if the
explicit function is called. This might be less confusing.

};

Here is the usage:

#include <algorithm>
#include <iostream>
#include "shared_vector.h"

std::istream &read_nums(std::istream &is, shared_vector<int> &nums)
{
while (is)
{
int num;
if (is >> num)
nums.push_back(num);
}
return is;
}

int main()
{
shared_vector<int> nums;
if (!read_nums(std::cin, nums))
return 1;

nums.push_back(-1); // vector is automatically unshared by this
operation

But there aren't any copies of num, so unsharing won't happen. I
suppose it's just an example.

nums.unshare(); // manually unshare vector before indirect modification
sort(nums.begin(), nums.end());

for (int i=0; i < nums.size(); i++)
os << nums << endl;
return 0;
}

The user must understand copy-on-write to use shared_vector properly. What
do you think?

I don't see any benefits that outweigh the potential confusions. Users
tend to be confused by classes that do "clever" things behind their
backs, and prefer to have some control. My original example will still
break, and this might well cause confusion. Your shared_vector is
syntatic sugar that might be counter productive compared to an
explicit shared_ptr<vector> that everyone understands the semantics
of.

Tom

C++ FAQ: http://www.parashift.com/c++-faq-lite/
C FAQ: http://www.eskimo.com/~scs/C-faq/top.html