Dietmar Kuehl wrote:
>
> Hi,
> Max Polk (maxpolk@gte.net) wrote:
> : The only problem is that now, each member is not deleted when the list
> : goes out of scope.  I have to MANUALLY, in an ERROR-PRONE way, remember
> : to catch all possible ways I can leave this scope, and traverse the list
> : and delete every element one by one.
>
> This problem is addressed by using "smart pointers". Unfortunately, the
> standard does not include any smart pointer, except 'auto_ptr' which
> unsuitable to be used as value type (although due to other problems
> than those listed by you...). To avoid copying, a referenced counted
> pointer scheme is the best way to cope with resource release. AFAIK, a
> proposal for a referenced counted pointer (which was included in the
> same proposal as 'auto_ptr') was rejected because it was felt to be too
> intrusive (ie. it required certain properties for the managed class).
> There was no suitable proposal received by the standard committee in
> time, so a reference counted pointer is missing from the standard.
Or, rather, it is not present in the standard. There's a significant
question whether it ought to be there. It's simple to write one that's
portable. There's no pressing need to have one in the standard library.
 -- Pete
---
[ comp.std.c++ is moderated.  To submit articles: try just posting with      ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu         ]
[ FAQ:      http://reality.sgi.com/employees/austern_mti/std-c++/faq.html    ]
[ Policy:   http://reality.sgi.com/employees/austern_mti/std-c++/policy.html ]
[ Comments? mailto:std-c++-request@ncar.ucar.edu                             ]

While teaching myself the Standard C++ Library, I came up with a problem
adding to a list.  It appears that I am forced to use copy constructors
when adding to a list:

{
   list <mytype>   lines;
   string          s ("Test");
   lines.push_back (mytype (s));
}

When lines goes out of scope, it destroys the mytype object it contains
as desired.  However, in the push_back call, this takes the object I
just created, creates another one using the copy constructor, then
deletes the first one.

If the mytype object were large, I would be wasting a whole lot of time
copying its data members.  So I thought that I could easily enough make
a list of pointers, as in:

{
   list <mytype *>   lines;
   string          s ("Test");
   lines.push_back (new mytype (s));
}

The only problem is that now, each member is not deleted when the list
goes out of scope.  I have to MANUALLY, in an ERROR-PRONE way, remember
to catch all possible ways I can leave this scope, and traverse the list
and delete every element one by one.

Perhaps, I thought, I could use list<auto_ptr <mytype> >, but NO, it is
not possible since list requires things like operator== and operator>
and const functions which don't make sense or are not possible to
implement for auto_ptr.

It is unbelievable to me that I am forced to use copy constructors to
add to a list, or else forced to have to always try to MANUALLY, in an
ERROR-PRONE way, remember to catch all cases where the list goes out of
scope and delete all its contents.
---
[ comp.std.c++ is moderated.  To submit articles: try just posting with      ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu         ]
[ FAQ:      http://reality.sgi.com/employees/austern_mti/std-c++/faq.html    ]
[ Policy:   http://reality.sgi.com/employees/austern_mti/std-c++/policy.html ]
[ Comments? mailto:std-c++-request@ncar.ucar.edu                             ]

Hi,
Max Polk (maxpolk@gte.net) wrote:
: The only problem is that now, each member is not deleted when the list
: goes out of scope.  I have to MANUALLY, in an ERROR-PRONE way, remember
: to catch all possible ways I can leave this scope, and traverse the list
: and delete every element one by one.

This problem is addressed by using "smart pointers". Unfortunately, the
standard does not include any smart pointer, except 'auto_ptr' which
unsuitable to be used as value type (although due to other problems
than those listed by you...). To avoid copying, a referenced counted
pointer scheme is the best way to cope with resource release. AFAIK, a
proposal for a referenced counted pointer (which was included in the
same proposal as 'auto_ptr') was rejected because it was felt to be too
intrusive (ie. it required certain properties for the managed class).
There was no suitable proposal received by the standard committee in
time, so a reference counted pointer is missing from the standard.

: Perhaps, I thought, I could use list<auto_ptr <mytype> >, but NO, it is
: not possible since list requires things like operator== and operator>
: and const functions which don't make sense or are not possible to
: implement for auto_ptr.

'list<T>' does not require comparison operators for type 'T' unless you
compare lists. However, it is a bug of at least two compilers I know to
require this. But it is not standard conforming such that it is
actually no problem.

Also, the 'auto_ptr' required by the standard has no problem with
'const' functions since owner ship is even transfered from 'const'
objects. However, using 'auto_ptr' in STL containers is inherently
dangerous:  Accesing a value in the list will transfer ownership to the
retrieved object which is normally only a temporary. Thus, it very
likely that you transfer ownership out of the list and end up with
stale pointer in the list. 'auto_ptr' is not intended to be used as
value type of the STL containers and is not really well-suited for this
application. 'auto_ptr' has only very limited uses: It can be used to
avoid resource leaks in the presence of exceptions but apart from this,
I haven't found it to be useful. You really need a reference counted
scheme for resource management with STL containers if you want to avoid
copies.
--
<mailto:dietmar.kuehl@uni-konstanz.de>
<http://www.informatik.uni-konstanz.de/~kuehl/>
I'm seeking a new employment - See my homepage for details
---
[ comp.std.c++ is moderated.  To submit articles: try just posting with      ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu         ]
[ FAQ:      http://reality.sgi.com/employees/austern_mti/std-c++/faq.html    ]
[ Policy:   http://reality.sgi.com/employees/austern_mti/std-c++/policy.html ]
[ Comments? mailto:std-c++-request@ncar.ucar.edu                             ]

Max Polk <maxpolk@gte.net> wrote:

> It is unbelievable to me that I am forced to use copy constructors to
> add to a list, or else forced to have to always try to MANUALLY, in an
> ERROR-PRONE way, remember to catch all cases where the list goes out of
> scope and delete all its contents.

It seems that your problem is that you want to preserve value
semantics for your data, but you don't want the overhead associated
with copying it (I assume because it's big & bulky).

Adding your data to a list only happens to be one instance of the
general situation wherein these two forces are juxtaposed.

A relatively standard solution is to separate your class into a
handle and a reference-counted body, so that passing instances
around willy-nilly no longer becomes a performance problem.

It seems a bit rash to be complaining that list<T> wants to copy
T instances around.

- Scott

NOTE: replace "nospam" with "stormtech" in my email address to reply.

--------------------------------------------------------------------
Scott Howlett                               howlett@nospam.com
Storm Technology, Inc.                      http://www.stormtech.com
---
[ comp.std.c++ is moderated.  To submit articles: try just posting with      ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu         ]
[ FAQ:      http://reality.sgi.com/employees/austern_mti/std-c++/faq.html    ]
[ Policy:   http://reality.sgi.com/employees/austern_mti/std-c++/policy.html ]
[ Comments? mailto:std-c++-request@ncar.ucar.edu                             ]

Dietmar Kuehl wrote:
>
> Hi,
> Max Polk (maxpolk@gte.net) wrote:
> ...
> : Perhaps, I thought, I could use list<auto_ptr <mytype> >, but NO, it is
> : not possible since list requires things like operator== and operator>
> : and const functions which don't make sense or are not possible to
> : implement for auto_ptr.
>
> 'list<T>' does not require comparison operators for type 'T' unless you
> compare lists. However, it is a bug of at least two compilers I know to
> require this. But it is not standard conforming such that it is
> actually no problem.
>

    NOT a compiler bug. The standard as it stands DOES require these
operators. As I noted in another thread, this is a serious
over-specification in some cases.

On the original topic:

    The problem with copying the original value is part of the use of
a list representation.  You have to attach the list links some way.
It is conceptually simpler to build the object and put it in the list,
but it is often more effective to put the object in the list first and
then fill it in.

    There is a serious language design problem here. What is really
desired is a way to invoke ANY of the value constructors for the object
to be added to the list on demand without the template having to know
what constructors are available a priori.  To do it, templates would
have to be extended.  One possibility would be a kind of labeled ...
notation.  Something like '.insert( iter, val ...)' with a
allocator::construct(val) call passing all the ... parameters to the
appropriate constructor.  Since this is not currently part of the
language, using the copy constructor seems to be the best alternative.

mtew@cds.duke.edu
---
[ comp.std.c++ is moderated.  To submit articles: try just posting with      ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu         ]
[ FAQ:      http://reality.sgi.com/employees/austern_mti/std-c++/faq.html    ]
[ Policy:   http://reality.sgi.com/employees/austern_mti/std-c++/policy.html ]
[ Comments? mailto:std-c++-request@ncar.ucar.edu                             ]

Max TenEyck Woodbury wrote:
>
> [...]
>
> On the original topic:
>
>     The problem with copying the original value is part of the use of
> a list representation.  You have to attach the list links some way.
> It is conceptually simpler to build the object and put it in the list,
> but it is often more effective to put the object in the list first and
> then fill it in.
>
>     There is a serious language design problem here. What is really
> desired is a way to invoke ANY of the value constructors for the object
> to be added to the list on demand without the template having to know
> what constructors are available a priori.  To do it, templates would
> have to be extended.  One possibility would be a kind of labeled ...
> notation.  Something like '.insert( iter, val ...)' with a
> allocator::construct(val) call passing all the ... parameters to the
> appropriate constructor.  Since this is not currently part of the
> language, using the copy constructor seems to be the best alternative.
>

I agree that there is a language problem here; here's another kind of
solution:

Start by introducing a new type in the standard library space_for<T>,
which
represents some storage in which a T can be constructed.

Then add a function template placement operator new, which takes a
space_for<T>, and as usual returns a pointer to the address where the
new
object should go:

    template <class T>
    void *operator new(size_t sz, space_for<T> space);

Now add some functions to list<T> (and all the other containers) to
create
new elements:

    template <class T>
    class list
    {
    ....
        space_for<T> at_front();
        space_for<T> at_back();
    ....
    };


So now we can do things like:

    list<MyClass> myList;
    new(myList.at_back()) MyClass("This element gets constructed in
place!");

And it's all within the existing language.


The catch: The placement new above introduces a gaping type-safety hole.
For example, this would compile fine:

    list<MyClass> myList;
    new(myList.at_back()) MyOtherClass("Oh dear!");

The solution is a change to the language, so that it is possible to
define
an operator new that "knows" the type of object it is allocating for.
Here's
an initial suggestion: operator new can return void* (as before) or T*.
An
operator new returning T* must only be used in a new expression
constructing
an object of the (cv-qualified?) type T.

With this, operator new can be declared as:

template <class T>
T* operator new(size_t sz, space_for<T> space);

Which by the rule above is type-safe. And since currently operator new
must
return void*, this change would not alter the meaning of existing legal
C++
programs.


Of course, this description is only a rough outline, but are there any
fundamental
problems with this scheme?

Dave Wragg.
---
[ comp.std.c++ is moderated.  To submit articles: Try just posting with your
                newsreader.  If that fails, use mailto:std-c++@ncar.ucar.edu
  comp.std.c++ FAQ: http://reality.sgi.com/austern/std-c++/faq.html
  Moderation policy: http://reality.sgi.com/austern/std-c++/policy.html
  Comments? mailto:std-c++-request@ncar.ucar.edu
]

In article <33B8395F.16D01615@gatsby.u-net.com>,
  David Wragg <davew@gatsby.u-net.com.NOSPAM> wrote:
> Now add some functions to list<T> (and all the other containers) to
> create
> new elements:
>
>     template <class T>
>     class list
>     {
>     ....
>         space_for<T> at_front();
>         space_for<T> at_back();
>     ....
>     };
>
> So now we can do things like:
>
>     list<MyClass> myList;
>     new(myList.at_back()) MyClass("This element gets constructed in
> place!");
>
> And it's all within the existing language.
>
> The catch: The placement new above introduces a gaping type-safety hole.
> For example, this would compile fine:
The other catch is that to enable something like this would require
modification of all stl-compliant classes to add corresponding insert
member functions that inserted space_for<T> rather than T.  I proposed a
simple solution for this a while back in comp.lang.c++.moderated that is
pretty similar to the solution you're proposing (I even included in my
post code for a class uninitialized<T>). To find this article, you can
do a DejaNews search with the following keywords:

Ian Haggard uninitialized comp.lang.c++.moderated

To recap what I said, however, even given a class uninitialized<T> or
space_for<T>, you still need to decide what the copy, assignment, and
destruction semantics for it are.  Do you add some flag to your class
that says whether the object has been created yet or do you just assume
(shudder) that the user will initialize the object before any attempt is
made to copy, assign to/from, or destroy it?

Also, I personally find it simpler to create a
vector<uninitialized_with_semantics<T> > or a
list<uninitialized_with_semantics<T> > rather than to add new member
functions to the existing vector and list classes, which already have
large enough interfaces.  And if you want something that is represented
by a vector<uninitialized_with_semantics<T> > but acts for the most part
like a vector<T>, then just write a stl vector-like class that uses
vector<uninitialized_with_semantics<T> > as its representation and
merely forwards most operations to its representation -- if you do that
I'll throw in compatibility with all STL algorithms for free :^)

It should even be possible to write a generic adaptor,  perhaps called
uninitialized_sequence<T,Sequence>, in the style of the priority_queue
and stack adaptors.  If you do write something like this, I'd love to
have a copy.

Creating a space_for<T> or uninitialized class isn't the only solution,
however.  Another solution would be to do an insert, followed by a
swap.  For many large classes, it can be made very efficient to do, for
example:

vec.push_back(T()); swap(srcT,vec.back());

This sequence of operations should on many classes (for example, all STL
containers) be much faster than:

vec.push_back(srcT);

All you have to do is write a swap operation for your class in the style
of the swap operations for the STL containers and this solves your
problem.  Well, okay, you do need to have an efficient default
constructor, a copy-constructor which can efficiently copy a
default-constructed object, and destructor which can efficiently destroy
a default-constructed object.  These three additional requirements,
however, are desirable for many other reasons, and I know that I
personally always make it a point to write classes which meet these
requirements.  When using templates, I find that these three
requirements are almost as important as some of the things in Effective
C++ and MEC++.

But the story isn't over yet.  You can get around the requirement on the
copy constructor.   This is because of another idea, which is original
to a coworker of mine, Jeff Persch.  Jeff realized that even if you can
insert a large object into a vector or deque in the most efficient
possible way, that's not the end of the story.  Do you know what happens
when the vector or deque resizes?  You got it -- that darn old
copy-constructor again.  But what if we were to define a move operation
with semantics like so:

template<class T>
move(T& src,T& dest)
{ assert(&src!=&dest); new(&dest) T(src); src.~T(); }

Again, for large classes this operation can be implemented much more
efficiently than copy-construction.  In fact, you can implement swap in
terms of move with no loss in efficiency.  The only thing left to do now
is to make the vector and deque classes use move rather than
copy-construction for resizing.  And the nice thing about that is that
it requires no changes at all in the STL container interface, only in a
few isolated places in the implementation.

And one more thing -- if you use move in stead of copy-construction for
resizing, this is a big step towards fixing the vector<auto_ptr<T> >
conflict.
--
Ian Haggard  ||  ian@shellus.com (work)  ||  IanHaggard@juno.com (home)
GNU/Linux -- "Oh, no, Mr Bill!" || #define employer_opinion !my_opinion
---
[ comp.std.c++ is moderated.  To submit articles: Try just posting with your
                newsreader.  If that fails, use mailto:std-c++@ncar.ucar.edu
  comp.std.c++ FAQ: http://reality.sgi.com/austern/std-c++/faq.html
  Moderation policy: http://reality.sgi.com/austern/std-c++/policy.html
  Comments? mailto:std-c++-request@ncar.ucar.edu
]