using vector to encapulate a tree - non const copy constructors [C++]

Prev: template no-match
Next: how can operator new overrun memory?!

From: terry on 15 Nov 2006 21:09

Repost as the original (13th Oct) did not appear on the site.

Hi, I have a problem with the way some implimentations of vector and other
stl containers refuse to use non-const contructors. My question is - is
the way they function the correct interpretation of the standard - and
if so
why.

MOTIVATION
The following data structure
class mytree: public T, protected std::vector<mytree>{};

defines a tree with an object of type T at each node (it is in top down
form where at each node, one has a value of type T, and a container of
offspring
trees).

Of course, one must define copy constructors and assignment operators and
maybe some interesting iterators before it has real value, but still, the
above declaration gives a top down encapsulation for trees.

The problem for me is that, for efficiency, one needs a non-const version
of the assignment and copy constructors. Everyone expects the constructor

mytree(const mytree & rhs)

to be defined, and of course it must do a deep copy, perhaps based on
using std::vector::assign. But one also really needs

mytree(mytree & rhs)

where the constructor copies the T object and swaps the container content
from the rhs into the lhs and so moves the whole tree just by moving the
root.

The rhs has no meaning afterwards but this is what you expect and want in
many circumstances. This constructor will probably use std::vector::swap
to move the content of the container of trees across.

Overall, this can easily be developed to construct an elegant tree as well
as
variant data structures for specific circumstances with good reuse of code.
The STL class manages all data allocation and deletion etc. Insertions are
relatively cheap etc.

The penalties of the deep copy are used only if they are required.

PROBLEM
My problem is that it seems that whenever a controlled sequence is copied or
moved to a new location by the stl container implimentations in microsoft or
g++ configurations the code seems to convert the objects to be copied to
const
reference types before calling the copy constructor.

This is, in my view, a bad decision, as I believe that it is up to the
input_iterator pointing to the data to be moved to decide whether the
controlled sequence is const and then C++ should choose the constructor
appropriately to match the signature presented.

Is this an issue caused by the standard?

Here is an example that, I hope, demonstrates the issue clearly:

//
#include <vector>

class T
{
public:
T(){}
T(const T & a){} //const copy constructor
};

class S
{
public:
S(){}
S(S& a){} //copy constructor
};

int main(int argc, char* argv[])
{
{
std::vector<T> u(10);
T a;
T* pp=&a;
T* p=pp++;
std::vector<T> v(p,pp);
}
{
// std::vector<S> u(10);
//uncomment the line above to produce an error
//even though there is a default constructor
S a;
S* pp=&a;
S* p=pp++;
//std::vector<S> v(p,pp);
//uncomment the line above produces an error
//even though there is a copy constructor
//and p is of type S*
//and so provides write-able access to its target so the provided copy
//constructor could be used
}
return 0;
}

--
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]

From: Ulrich Eckhardt on 16 Nov 2006 05:22

terry wrote:

> Repost as the original (13th Oct) did not appear on the site.
>
> Hi, I have a problem with the way some implimentations of vector and other
> stl containers refuse to use non-const contructors. My question is - is
> the way they function the correct interpretation of the standard - and
> if so
> why.
>
> MOTIVATION
> The following data structure
> class mytree: public T, protected std::vector<mytree>{};

This comes up pretty often: vector<> requires a complete type as parameter
but 'mytree' above is not a complete type.

> The problem for me is that, for efficiency, one needs a non-const version
> of the assignment and copy constructors. Everyone expects the constructor
>
> mytree(const mytree & rhs)
>
> to be defined, and of course it must do a deep copy, perhaps based on
> using std::vector::assign. But one also really needs
>
> mytree(mytree & rhs)
>
> where the constructor copies the T object and swaps the container content
> from the rhs into the lhs and so moves the whole tree just by moving the
> root.

I don't follow you. A constructor that in fact swaps with the object it was
passed makes very limited sense. Using this as addition to one that does a
copy is just dangerous, consider this code:

yourtree t2(this->t1);

Does this copy or swap? Answer is that you can't tell, because you'd need
the context of the memberfunction (i.e. whether it is const or not) to
determine that. Such extreme differences depending on innocent changes are
a recipe for disaster.

In case you only want to avoid copying, you might consider implementing
semantics similar to std::auto_ptr or maybe create something like the MOJO
framework (search the web for it). Otherwise, an explicit swap()
memberfunction is also possible.

> PROBLEM
> My problem is that it seems that whenever a controlled sequence is copied
> or moved to a new location by the stl container implimentations in
> microsoft or g++ configurations the code seems to convert the objects to
> be copied to const
> reference types before calling the copy constructor.
>
> This is, in my view, a bad decision, as I believe that it is up to the
> input_iterator pointing to the data to be moved to decide whether the
> controlled sequence is const and then C++ should choose the constructor
> appropriately to match the signature presented.

No, sorry. The containers assume value semantics, which is also the reason
why e.g. std::auto_ptr is not suitable for storage in such a container.
Value semantics mean that copying does not modify the former value.

Uli

--
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]

From: loufoque on 16 Nov 2006 05:22

terry wrote:

> But one also really needs
>
> mytree(mytree & rhs)
>
> where the constructor copies the T object and swaps the container content
> from the rhs into the lhs and so moves the whole tree just by moving the
> root.

What you need is move semantics actually, which aren't in C++ yet.

--
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]

From: Le Chaud Lapin on 16 Nov 2006 21:04

From: terry on 17 Nov 2006 03:40

>> class mytree: public T, protected std::vector<mytree>{};
>
> This comes up pretty often: vector<> requires a complete type as parameter
> but 'mytree' above is not a complete type.

I think you are wrong on this - I am pretty sure this is corredct and well
withint he standard.
In particular mytree's size is well defined in much the same way a pointer
is defined.
vector<> encapuslates a pointer to an aray stored on the heap

--
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]

| Next | Last
Pages: 1 2 3 4 5 6 7
Prev: template no-match
Next: how can operator new overrun memory?!