[Lemon-user] EdgeMap copy constructor

[Alpár Jüttner]

Hi Peter,

First of all, sorry for the slow answer (I start almost all of my emails
this way nowadays... ;) )

> On 11/06/2010 08:59 PM, Alpár Jüttner wrote:
> > > As far as I know, the C++ standard only allows default constructible
> > > data type as the template parameter of std::vector<>, so EdgeMaps
> > > couldn't have been used anyway.
> This is not the case, vector[1] does not impose such requirement for its
> contained type. You can give a default value for the constructor of
> vector, and it will be copied n times, or you can give your own
> Allocator as well.

You are right, though I guess [1] you are referring to has very little
to do with the current C++ standard, and is obviously faulty in several
places. For example it does not even require that the base type is copy
constructable.

> > > The fundamental problem with using EdgeMaps (and basically any other BIG
> > > datastructures) together with std::vector<> is that the latter one
> > > copies its elements from time to time, which results in copying huge
> > > chunks of memory.
> You are correct, vector will copy a lot of memory if your objects are
> big in this sense, but it should be a *user's* decision to do this or not.

The point is that there is a heavy dispute what the copy constructor
(and operator=) should actually do. And this dispute has not been
settled down yet (though it seems suspended...).

Basically, there are two options:
      * These operators should simply copy the contents of the map both
        when it is applied to the same map types and when to different
        one.
      * "Cheap copy concept": Introduce a reference counting for the
        default maps, and
              * when a default map is copied to a map _of the same
                type_, it would just create a new reference to the same
                storage. The contents of the map could be copied
                (detached from the other maps referencing the same
                storage) explicitly by map.copy().
              * copying between different map types would result in
                copying the full contents.

This second approach has several advantages: using maps in stl
containers (e.g. std:vector<>) is efficient, you could (efficiently)
return a map from a function as a return value and it is copied only if
the result must be stored in a different map type etc.

It has however a close to prohibitive drawback - some people feel very
surprised (or even personally offended ;) to see two container objects
sharing their storage. Although it is very common in modern languages
like Python, it seems frightening many C++ developers.

> > > I suggest using
> > >
> > > std::vector< lemon::ListGraph::EdgeMap< bool > * >
> > >
> > > and manually allocating and de-allocating the components with new and
> > > delete. A bit cumbersome but works.
> Unfortunately I am forced to do this, and also to manually copy each
> EdgeMap with a loop. Bottom line: memory is still copied but not as
> conveniently as with a copy constructor.

I don't understand why do you have to copy the maps.

std::vector< lemon::ListGraph::EdgeMap< bool > * > maps;
for(int i=0; i<100; i++)
  maps.push_back(new lemon::ListGraph::EdgeMap< bool >(g) );

I can't see any map copying here.

> If you still think EdgeMap shouldn't be copyable

As you see, I didn't say that. We simple haven't concluded yet.
Any argument, discussion, dispute, flamewar etc. in this topic can be
helpful to achieve conclusion.

Best regards,
Alpar


>  you
>  should have a
> conceptual reason for this: I'm not that familiar with the library to
> judge this from this point of view, but in my opinion your memory
> argument is not strong enough.
> 
> Regards.
> Peter
> 
> [1] http://www.sgi.com/tech/stl/Vector.html
> 
> -- Peter Vizi Ph.D. student Faculty of Information Technology Pazmany
> Peter Catholic University
> 
> 	
> Peter Vizi <peter.vizi at itk.ppke.hu>
> Ph.D. Student
> Faculty of Information Technology
> Peter Pazmany Catholic University
> _______________________________________________
> Lemon-user mailing list
> Lemon-user at lemon.cs.elte.hu
> http://lemon.cs.elte.hu/mailman/listinfo/lemon-user