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

[Jason Heyes]

To my understanding, std::vector does not use reference counting to avoid
the overhead of copying and initialisation. Where can I get a reference
counted implementation of std::vector? Thanks.

[Gianni Mariani]

Jason Heyes wrote:

To my understanding, std::vector does not use reference counting to avoid
the overhead of copying and initialisation. Where can I get a reference
counted implementation of std::vector? Thanks.

You might want to check out boost::shared_ptr.

Or, you could do somthing like this :

#include <vector>

template <typename T>
class vector_reference_counted
: public std::vector<T>
{

int m_reference_count;

public:

inline vector_reference_counted()
: m_reference_count( 1 )
{
}

inline vector_reference_counted( const vector_reference_counted &
i_rhs )
: m_reference_count( 1 ),
std::vector<T>( i_rhs )
{
}

inline vector_reference_counted & operator = ( const
vector_reference_counted & i_rhs )
{
// reference count does not change upon assignment

* static_cast< std::vector<T> * >( this ) = i_rhs;

return * this;
}

inline vector_reference_counted & operator = ( const std::vector<T>
& i_rhs )
{
// reference count does not change upon assignment

* static_cast< std::vector<T> * >( this ) = i_rhs;

return * this;
}

int AddRef()
{
int l_count = ++ m_reference_count;
return l_count;
}

int Release()
{
int l_count = -- m_reference_count;

if ( l_count == 0 )
{
delete this;
}

return l_count;
}

};

[Jason Heyes]

"Gianni Mariani" <gi*******@mariani.ws> wrote in message
news:br********@dispatch.concentric.net...

Jason Heyes wrote:

To my understanding, std::vector does not use reference counting to avoid the overhead of copying and initialisation. Where can I get a reference
counted implementation of std::vector? Thanks.
You might want to check out boost::shared_ptr.

Why? I know about the shared_ptr. How does it help?

Or, you could do somthing like this :

#include <vector>

template <typename T>
class vector_reference_counted
: public std::vector<T>
{

int m_reference_count;

public:

inline vector_reference_counted()
: m_reference_count( 1 )
{
}

inline vector_reference_counted( const vector_reference_counted &
i_rhs )
: m_reference_count( 1 ),
std::vector<T>( i_rhs )
{
}

inline vector_reference_counted & operator = ( const
vector_reference_counted & i_rhs )
{
// reference count does not change upon assignment

* static_cast< std::vector<T> * >( this ) = i_rhs;

return * this;
}

inline vector_reference_counted & operator = ( const std::vector<T>
& i_rhs )
{
// reference count does not change upon assignment

* static_cast< std::vector<T> * >( this ) = i_rhs;

return * this;
}

int AddRef()
{
int l_count = ++ m_reference_count;
return l_count;
}

int Release()
{
int l_count = -- m_reference_count;

if ( l_count == 0 )
{
delete this;
}

return l_count;
}

};

I don't see how that helps either. Please explain.

[Gianni Mariani]

Jason Heyes wrote:

"Gianni Mariani" <gi*******@mariani.ws> wrote in message
news:br********@dispatch.concentric.net...

Jason Heyes wrote:

To my understanding, std::vector does not use reference counting to

I don't see how that helps either. Please explain.

Maybe you should explain what you're trying to do.

[Jason Heyes]

"Gianni Mariani" <gi*******@mariani.ws> wrote in message
news:br********@dispatch.concentric.net...

Maybe you should explain what you're trying to do.

Here is a program that uses std::vector.

#include <algorithm>
#include <vector>
#include <iostream>

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

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

sort(nums.begin(), nums.end());

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

I want another class so I can change the above code into this.

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

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

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

sort(nums.begin(), nums.end());

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

See how the code is exactly the same except that std::vector is replaced
with SharedVector? This is what I want to be able to do. I want a class that
replaces std::vector but does the same thing as std::vector and uses
reference counting in it's implementation. Is that possible?

[John Carson]

"Jason Heyes" <ge******@optusnet.com.au> wrote in message
news:3f***********************@news.optusnet.com.a u

To my understanding, std::vector does not use reference counting to
avoid the overhead of copying and initialisation. Where can I get a
reference counted implementation of std::vector? Thanks.

You might ask yourself whether you should be seeking such a thing. If
std::vector does not use reference counting, then it is probably for a good
reason. The following is from Josuttis (C++ Standard Library, p. 506):

"The primary goal of vectors is to handle and to manipulate the elements of
the container, not the container as a whole. Thus, vectors implementations
are optimized to operate on elements inside the container.

"The primary goal of strings is to handle and manipulate the container (the
string) as a whole. Thus, strings are optimized to reduce the costs of
assigning and passing the whole container.

"These different goals typically result in completely different
implementations. For example, strings are often implemented by using
reference counting: vectors never are."
--
John Carson
1. To reply to email address, remove donald
2. Don't reply to email address (post here instead)

[tom_usenet]

On Mon, 15 Dec 2003 18:50:03 +1100, "Jason Heyes"
<ge******@optusnet.com.au> wrote:

See how the code is exactly the same except that std::vector is replaced
with SharedVector? This is what I want to be able to do. I want a class that
replaces std::vector but does the same thing as std::vector and uses
reference counting in it's implementation. Is that possible?

It's possible, but I don't know of a free reference counted vector
implementation that conforms to the std::vector interface - it would
be easy to write one of course (though time consuming to code and
debug).

Note that in the posted code it would be a pessimization to have
reference counting. In the few cases where you do need it (to share
ownership of a vector), using a shared_ptr seems the obvious solution.
Why make a special case for a shared vector? int isn't shared...

Tom

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

[Andrew Koenig]

> >I want a class that

replaces std::vector but does the same thing as std::vector and uses
reference counting in it's implementation. Is that possible?

It's possible, but I don't know of a free reference counted vector
implementation that conforms to the std::vector interface - it would
be easy to write one of course (though time consuming to code and
debug).

Easy? Really? Just for curiosity, would you be planning to use the same
semantics as std::vector? If not, what would you change? If so, what would
be the interaction between, say, the "begin" member function and the
reference count?

[Jason Heyes]

"tom_usenet" <to********@hotmail.com> wrote in message
news:45********************************@4ax.com...

On Mon, 15 Dec 2003 18:50:03 +1100, "Jason Heyes"
<ge******@optusnet.com.au> wrote:

See how the code is exactly the same except that std::vector is replaced
with SharedVector? This is what I want to be able to do. I want a class thatreplaces std::vector but does the same thing as std::vector and uses
reference counting in it's implementation. Is that possible?
It's possible, but I don't know of a free reference counted vector
implementation that conforms to the std::vector interface - it would
be easy to write one of course (though time consuming to code and
debug).

On the face of things I think it should be ok if I write my own. Maybe not a
full-blown version but at least something useful for my current project.
Here is something that I wrote based on the public interface of std::vector.

template <class T> class SharedVector
{
SharedPtr<std::vector<T> > ptr;
public:
typedef std::vector<T>::size_type size_type;
typedef IteratorNotDefinedYet iterator;
typedef ConstIteratorNotDefinedYet const_iterator;

explicit SharedVector() : ptr(new std::vector<T>) { }

explicit SharedVector(size_type n, const T &v = T()) :
ptr(new std::vector<T>(n,v)) { }

SharedVector(const SharedVector &x) : ptr(x.ptr) { }

SharedVector(const_iterator first, const_iterator last) :
ptr(new std::vector<T>(first, last)) { }

iterator begin() { return iterator(ptr->begin()); }
const_iterator begin() const { return const_iterator(ptr->begin(),
ptr); }

iterator end() { return iterator(ptr->end()); }
const_iterator end() const { return const_iterator(ptr->end(), ptr); }

T &operator[](size_type pos)
{
ptr.make_unique(); // "copy-on-write" before calling non-const
method
return ptr->operator[](pos);
}

const T &operator[](size_type pos) const { return
ptr->operator[](pos); }
};

I haven't thought alot about allocators, iterators or anything. Just the
obvious things. Feel free to point out what is wrong in the above design.

Note that in the posted code it would be a pessimization to have
reference counting. In the few cases where you do need it (to share
ownership of a vector), using a shared_ptr seems the obvious solution.
Why make a special case for a shared vector? int isn't shared...

Tom

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

Perhaps "SharedVector" isn't the right term. I thought of referring to it as
"VectorRef" instead but I changed my mind. Anyway I certainly believe that a
SharedVector would be much more convenient than a SharedPtr alone. Let me
write another example to make this clear.

class Book
{
std::string title;
SharedVector<Page> pages;

public:
Book(std::string title_, SharedVector<Page> pages_) :
title(title_), pages(pages_) { }

void find(std::string line, SharedVector<Page> &pages_) const {
for (int i=0; i < pages.size(); i++) {
if (pages[i].contains(line))
pages_.push_back(pages[i]);
}
}

friend std::istream &operator>>(std::istream &, Book &);
};

class Page
{
int number;
SharedVector<std::string> lines;

public:
bool contains(std::string line) const
{ return find(lines.begin(), lines.end(), line) != lines.end(); }

friend std::ostream &operator<<(std::ostream &, const Page &);
friend std::istream &operator>>(std::istream &, Page &);
};

using namespace std;

int main()
{
// read book from cin
Book book;
if (!(cin >> book))
return 1;

// find pages that contain the line "foo"
SharedVector<Page> pages;
book.find("foo", pages);

// make another book with them and call it "the story of foo"
Book another_book("the story of foo", pages);

// display the pages using const_iterators, so they stay shared
const SharedVector<Page> &const_pages = pages;
copy(const_pages.begin(), const_pages.end(),
ostream_iterator<Page>(cout, "\n"));
return 0;
};

[Jason Heyes]

"John Carson" <do***********@datafast.net.au> wrote in message
news:3f********@usenet.per.paradox.net.au...

You might ask yourself whether you should be seeking such a thing. If
std::vector does not use reference counting, then it is probably for a good reason. The following is from Josuttis (C++ Standard Library, p. 506):

"The primary goal of vectors is to handle and to manipulate the elements of the container, not the container as a whole. Thus, vectors implementations
are optimized to operate on elements inside the container.

"The primary goal of strings is to handle and manipulate the container (the string) as a whole. Thus, strings are optimized to reduce the costs of
assigning and passing the whole container.

"These different goals typically result in completely different
implementations. For example, strings are often implemented by using
reference counting: vectors never are."
--
John Carson
1. To reply to email address, remove donald
2. Don't reply to email address (post here instead)

Interesting. I will need to think about this. Would you use a vector, say,
to store pixel information about an image? Or would you use a string
instead? Consider:

class Image
{
std::vector<Pixel> pixels;
public:
// an example of a costly operation
Image(const Image &image) : pixels(image.pixels) { }

// other image operations
};

What do you think? Should I have used a string instead of a vector? I'm
confused.

[Karl Heinz Buchegger]

Jason Heyes wrote:

Interesting. I will need to think about this. Would you use a vector, say,
to store pixel information about an image? Or would you use a string
instead? Consider:
Can't talk for John but I know that I wouldn't use a string.
I associate different functionality with something called a string.

class Image
{
std::vector<Pixel> pixels;
public:
// an example of a costly operation
Image(const Image &image) : pixels(image.pixels) { }

// other image operations
};

What do you think? Should I have used a string instead of a vector? I'm
confused.

In cases like this, when I want to emphasize to the user of the class
that this is a costly operation and that he should rethink if he really
wants to do that (or if he simply made a typo) I do:

class Image
{
public:
...
void CopyTo( Image& To );

private:
Image( const Image& Arg ); // not implemented, use CopyTo instead
Image& operator=( const Image& Arg ); // not implemented, use CopyTo instead

std::vector< Pixel > pixels;
};

In other words: I disable the copy constructor and the assigment operator
(assignment operator is debatable) and force the user to explicitely ask
for a copy if he wants one.

--
Karl Heinz Buchegger
kb******@gascad.at

[Jason Heyes]

"Karl Heinz Buchegger" <kb******@gascad.at> wrote in message
news:3F**************@gascad.at...

Jason Heyes wrote:

Interesting. I will need to think about this. Would you use a vector, say, to store pixel information about an image? Or would you use a string
instead? Consider:
Can't talk for John but I know that I wouldn't use a string.
I associate different functionality with something called a string.

class Image
{
std::vector<Pixel> pixels;
public:
// an example of a costly operation
Image(const Image &image) : pixels(image.pixels) { }

// other image operations
};

What do you think? Should I have used a string instead of a vector? I'm
confused.

In cases like this, when I want to emphasize to the user of the class
that this is a costly operation and that he should rethink if he really
wants to do that (or if he simply made a typo) I do:

class Image
{
public:
...
void CopyTo( Image& To );

private:
Image( const Image& Arg ); // not implemented, use CopyTo

instead Image& operator=( const Image& Arg ); // not implemented, use CopyTo instead
std::vector< Pixel > pixels;
};

In other words: I disable the copy constructor and the assigment operator
(assignment operator is debatable) and force the user to explicitely ask
for a copy if he wants one.

--
Karl Heinz Buchegger
kb******@gascad.at

That looks like the best solution but it gets annoying when other classes
need Image as a member. Consider the Student class for example. Because
Image is not copy-constructible, Student needs CopyTo().

class Student
{
std::string name;
Image picture;
// ...
public:
void CopyTo(Student &To)
{
To.name = name;
picture.CopyTo(To.picture);
}
};

I guess if you get in the habit of it, it isn't so bad.

[tom_usenet]

On Mon, 15 Dec 2003 13:37:57 GMT, "Andrew Koenig" <ar*@acm.org> wrote:

>I want a class that
>replaces std::vector but does the same thing as std::vector and uses
>reference counting in it's implementation. Is that possible?

It's possible, but I don't know of a free reference counted vector
implementation that conforms to the std::vector interface - it would
be easy to write one of course (though time consuming to code and
debug).

Easy? Really? Just for curiosity, would you be planning to use the same
semantics as std::vector? If not, what would you change? If so, what would
be the interaction between, say, the "begin" member function and the
reference count?

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

Semantics are slightly different from std::vector. Basically,
modifications/invalidations of any of the shared copies affect all
iterators/references into any of the copies.

Tom

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

[tom_usenet]

On Tue, 16 Dec 2003 04:31:47 +1100, "Jason Heyes"
<ja********@optusnet.com.au> wrote:

That looks like the best solution but it gets annoying when other classes
need Image as a member. Consider the Student class for example. Because
Image is not copy-constructible, Student needs CopyTo().

class Student
{
std::string name;
Image picture;
// ...
public:
void CopyTo(Student &To)
{
To.name = name;
picture.CopyTo(To.picture);
}
};

I guess if you get in the habit of it, it isn't so bad.

What does copying a student mean? Cloning is still a technology in its
infancy. IOW, most application domain classes shouldn't be copyable.
Only "value-type" classes (that act like "int") need be copyable.

Tom

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

[Karl Heinz Buchegger]

Jason Heyes wrote:

That looks like the best solution but it gets annoying when other classes
need Image as a member. Consider the Student class for example. Because
Image is not copy-constructible, Student needs CopyTo().

class Student
{
std::string name;
Image picture;
// ...
public:
void CopyTo(Student &To)
{
To.name = name;
picture.CopyTo(To.picture);
}
};

I guess if you get in the habit of it, it isn't so bad.

It depends ?

The problem is that it is easy to forget about the '&' in an argument
list:

void foo( Student Arg )
{
do something with Arg
}

Well. This creates a copy of the callers student. But since copying
is a costly operation (a strudent contains an image) you might want
to not allow this automtically. Now the programmer has the choice: If he
is willing to spend the time for creating the copy, he can do so, or he
can rething if the above shouldn't read:

void foo( Student& Arg )
{
}

If the hiding of cctor is a good idea or not may vary by your
milage. Sometimes I do it (if the copying is *really* expensive),
sometimes I don't.

--
Karl Heinz Buchegger
kb******@gascad.at

[Jason Heyes]

"tom_usenet" <to********@hotmail.com> wrote in message
news:3s********************************@4ax.com...

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

Semantics are slightly different from std::vector. Basically,
modifications/invalidations of any of the shared copies affect all
iterators/references into any of the copies.

Tom

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

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

[Jason Heyes]

"tom_usenet" <to********@hotmail.com> wrote in message
news:b6********************************@4ax.com...

What does copying a student mean? Cloning is still a technology in its
infancy. IOW, most application domain classes shouldn't be copyable.
Only "value-type" classes (that act like "int") need be copyable.

Tom

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

Is there really a distinction between an int and a Student? They're both
objects, aren't they?

[Jason Heyes]

"Karl Heinz Buchegger" <kb******@gascad.at> wrote in message
news:3F***************@gascad.at...

It depends ?

The problem is that it is easy to forget about the '&' in an argument
list:

void foo( Student Arg )
{
do something with Arg
}

Well. This creates a copy of the callers student. But since copying
is a costly operation (a strudent contains an image) you might want
to not allow this automtically. Now the programmer has the choice: If he
is willing to spend the time for creating the copy, he can do so, or he
can rething if the above shouldn't read:

void foo( Student& Arg )
{
}

If the hiding of cctor is a good idea or not may vary by your
milage. Sometimes I do it (if the copying is *really* expensive),
sometimes I don't.

--
Karl Heinz Buchegger
kb******@gascad.at

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 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[i].negate();
}

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

[tom_usenet]

On Tue, 16 Dec 2003 16:55:57 +1100, "Jason Heyes"
<ja********@optusnet.com.au> wrote:

"tom_usenet" <to********@hotmail.com> wrote in message
news:3s********************************@4ax.com.. .

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

Semantics are slightly different from std::vector. Basically,
modifications/invalidations of any of the shared copies affect all
iterators/references into any of the copies.

Tom

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

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

[tom_usenet]

On Tue, 16 Dec 2003 18:05:31 +1100, "Jason Heyes"
<ja********@optusnet.com.au> wrote:

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 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[i].negate();
}

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

I think Image should be non-copyable, but have a "clone" operation if
you need one.

Tom

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

[Jason Heyes]

"tom_usenet" <to********@hotmail.com> wrote in message
news:fg********************************@4ax.com...

On Tue, 16 Dec 2003 16:55:57 +1100, "Jason Heyes"
<ja********@optusnet.com.au> wrote:

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]

On Tue, 16 Dec 2003 23:05:46 +1100, "Jason Heyes"
<ja********@optusnet.com.au> wrote:

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]

On Tue, 16 Dec 2003 15:47:53 +0000, tom_usenet
<to********@hotmail.com> wrote:

On Tue, 16 Dec 2003 23:05:46 +1100, "Jason Heyes"
<ja********@optusnet.com.au> wrote:

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]

Jason Heyes wrote:

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[i].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.

--
Karl Heinz Buchegger
kb******@gascad.at

[Jason Heyes]

"Karl Heinz Buchegger" <kb******@gascad.at> wrote in message
news:3F***************@gascad.at...

Jason Heyes wrote:

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

Yeah basically. In other words, SharedVector is SharedPtr<std::vector> with
syntactic sugar.

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[i].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.

--
Karl Heinz Buchegger
kb******@gascad.at

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]

"tom_usenet" <to********@hotmail.com> wrote in message
news:ho********************************@4ax.com...

On Tue, 16 Dec 2003 15:47:53 +0000, tom_usenet
<to********@hotmail.com> wrote:

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]

"tom_usenet" <to********@hotmail.com> wrote in message
news:i8********************************@4ax.com...

On Tue, 16 Dec 2003 23:05:46 +1100, "Jason Heyes"
<ja********@optusnet.com.au> wrote:

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[i] << endl;
return 0;
}

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

[tom_usenet]

On Wed, 17 Dec 2003 10:25:37 +1100, "Jason Heyes"
<ja********@optusnet.com.au> wrote:

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[i] << 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