On Mon, 22 Jan 2001 19:21:44 GMT, Harald Nowak wrote:
> this very case (the "ref counting if you like ref semantics" case). I talked
> to many programmers about that, and I can tell by now, that many DO use STL
> containers of pointers, but DON'T use smart pointers OR algorithms (since
> they won't work in the naive way)

This is interesting.  How many algorithms are we talking about here?  Off
the top of my head, I can think only of remove, remove_if, and unique (and
presumably their copying variants).  Are there others, or just these three?

Scott

---
[ 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    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.research.att.com/~austern/csc/faq.html                ]
[ Note that the FAQ URL has changed!  Please update your bookmarks.     ]

Hi,
Scott Meyers (smeyers@aristeia.com) wrote:
: This is interesting.  How many algorithms are we talking about here?  Off
: the top of my head, I can think only of remove, remove_if, and unique (and
: presumably their copying variants).  Are there others, or just these three?

I'm unsure what you are referring to but I read it as you are asking
which useful algorithms there are in the standard C++ library. Well,
I'm using 'std::copy()' a lot, eg. to read or write sequence,
'std::transform()' to do various conversions, eg. 'std::string' <->
'std::wstring', 'std::sort()', typically together with
'std::binary_search()' for "maps" stored as 'std::vector', and
'std::find()', eg. to skip illegal characters during input.

My guess is that articles written in news do not count when it comes
down to real world use but there you can add 'std::mismatch()',
'std::unique()', 'std::for_each()', 'std::count()', 'std::distance()',
'std::reverse()', 'std::adjacent_find()', and a bunch of others. Maybe
the reason I'm using these algorithms a lot is that I *know* what can
be done to make them *much* faster than typical naive loops doing the
same thing. I'm currently in the process of rewriting my library and
I'm planning to use loops if possible only for the implementation of,
well, the algorithms.
--
<mailto:dietmar_kuehl@yahoo.com> <http://www.dietmar-kuehl.de/>
Phaidros eaSE - Easy Software Engineering: <http://www.phaidros.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    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.research.att.com/~austern/csc/faq.html                ]
[ Note that the FAQ URL has changed!  Please update your bookmarks.     ]

I posted this befor in comp.lang.c++; maybe a forum concerned with the
standard is
a better place for this:

When using an STL container (like vector), which contains pointers to
elements which where allocated from the free store, and which shall
"own" these elements in a sense (meaning their destruction upon the
containers destruction AND proper destruction of the heap elements
during application of modifying algorithms on the container) you CANNOT
use basic algorithms like remove_if without causing memory leaks.
You either have to roll your own version of the algorithm (that does
memory management as needed), or you have to resort to other algorithms
(like "partition") to achieve your goal; like:

vector<Object *> v ;

v.push_back( new Object() ) ;
....

// Now remove some elements:
vector<Object *>::iterator last = partition( v.begin(), v.end(),
not1(predicate) ) ;
for( vector<Object *>::iterator i=last ; i<v.end() ; i++ )
{
    delete *i ;
}
v.erase( last, v.end() ) ;

To use remove_if instead of partition with the not-negatet predicate
would be wrong and lead to a crash.

I consider this situation rather bad, since it is hardly ever clearly
documented, ignoring the fact that containers of pointers to heap
objects occur very often in real world code - I even assume that such
containers occur more often then "direct value containers". If this is
true, we are in a situation, where most of the containers out there
cannot use basic functions like remove_if, if they do not employ smart
pointers - they have to apply "work arounds". Doesn't that object the
original philosophy of the STL a little bit - to take a container, take
an algorithm and simply plug them together?

I do realize, that this philosophy could be "reestablished" by using
smart pointers - it is to be hoped that the boost smart pointers make
their way
into the next standard. Apart from that, some people do not want to
swallow the
smart pointer overhead.

I think the whole situation could be much "enhanced" by providing
versions of the
(modifying) algorithms, that are in a way "compatible" with "owning"
containers
(in our established sense); such algorithms would need to fullfill
another
promise:
When the algorithm ends, the same set of pointers exists that existed
when the
algorithm started. The algorithm shall do nothing more to the container
than
reorder the pointers; if elements need to be removed this can be done in
the very
same fashion than "partition" does - by providing an iterator pointing
to the end
of the valid and the beginning of the invalid elements range's.

They might be called somthing like xxxxx_reorder_if, analogue to the
xxxx_copy_if
family. So we'd have algorithms like:

remove_reorder_if
unique_reorder_if

and similar. It would then be

1. possible to create owning containers without making use of smart
pointers and
yet making use of standard algorithms (though you would have to be
careful which
version of the algorithms you take - a situation that exists now
anyways)

2. necessary for book and documentation authors to document this
function family
and at the same time alert the reader to the problem associated with
owning
pointer containers.

Just a thought I wanted to share with you... any idea on that is
welcome!

regards,
Harald Nowak

---
[ 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    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.research.att.com/~austern/csc/faq.html                ]
[ Note that the FAQ URL has changed!  Please update your bookmarks.     ]

Harald Nowak wrote:
>
> I posted this befor in comp.lang.c++; maybe a forum concerned with the
> standard is
> a better place for this:
>
> When using an STL container (like vector), which contains pointers to
> elements which where allocated from the free store, and which shall
> "own" these elements in a sense

A reference counted object to hold the pointer sounds like it is in order.

---
[ 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    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.research.att.com/~austern/csc/faq.html                ]
[ Note that the FAQ URL has changed!  Please update your bookmarks.     ]

You're right of course - this would be the cleanest solution. But, I do wonder
if we really should settle with such a solution alone - as I was saying, many
programmers do not want to buy the performance overhead of reference counting.
Especially, if you want to write high performance code, you do use pointer
lists and (hopefully) do use STL. So, I do believe, the STL should also
provide another solution (similar to the one I presented in the posting)

> A reference counted object to hold the pointer sounds like it is in order.
>
> ---
> [ 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    ]
> [              --- Please see the FAQ before posting. ---               ]
> [ FAQ: http://www.research.att.com/~austern/csc/faq.html                ]
> [ Note that the FAQ URL has changed!  Please update your bookmarks.     ]


======================================= MODERATOR'S COMMENT:
 Please don't quote the .sig.  It will be appended anyhow.

---
[ 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    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.research.att.com/~austern/csc/faq.html                ]
[ Note that the FAQ URL has changed!  Please update your bookmarks.     ]

In article <3A65D7D2.9AEDE8C9@infrasoft.co.at>, Harald Nowak wrote:
> I consider this situation rather bad, since it is hardly ever clearly
> documented, ignoring the fact that containers of pointers to heap
> objects occur very often in real world code - I even assume that such
> containers occur more often then "direct value containers".

Every book I have read regarding the C++ and the STL takes great pains to
point out that the library provides value semantics, not reference
semantics. Every book then goes on to explain that you can use a smart
pointer class (some call it a counted pointer) if you really need reference
semantics (which you don't need as often as you imply).

Every book then goes on to provide complete source code for such a smart
pointer. You can get two good versions from "The C++ Programming Language"
by Bjarne Stroustrup or "The C++ Standard Library" by Nicolai M. Josuttis.

Or you can do a google search for "smart pointers C++".

Or you can read section 32 of the C++ FAQ and follow some of the links.

> I do realize, that this philosophy could be "reestablished" by using
> smart pointers - it is to be hoped that the boost smart pointers make
> their way
> into the next standard. Apart from that, some people do not want to
> swallow the
> smart pointer overhead.

Properly implemented smart pointers with a good compiler (which g++
frequently isn't) incur little overhead. There has been testing to back this
up.

> 1. possible to create owning containers without making use of smart
> pointers and
> yet making use of standard algorithms (though you would have to be
> careful which
> version of the algorithms you take - a situation that exists now
> anyways)

Exchange one situation for another similar situation? How does that help?
You change the standard library and arrive at a situation not unlike the one
you have now.

> 2. necessary for book and documentation authors to document this
> function family
> and at the same time alert the reader to the problem associated with
> owning
> pointer containers.

Every good C++ book already warns of the problems associated with containers
storing pointers.

---
[ 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    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.research.att.com/~austern/csc/faq.html                ]
[ Note that the FAQ URL has changed!  Please update your bookmarks.     ]

In article <3A687447.AE75C81F@infrasoft.co.at>, Harald Nowak
<ishn@infrasoft.co.at> writes
>You're right of course - this would be the cleanest solution. But, I do wonder
>if we really should settle with such a solution alone - as I was saying, many
>programmers do not want to buy the performance overhead of reference counting.
>Especially, if you want to write high performance code, you do use pointer
>lists and (hopefully) do use STL. So, I do believe, the STL should also
>provide another solution (similar to the one I presented in the posting)

What, for all the algorithms that alter containers? You see many of them
rely on copy assignment and copy ctors I would be very surprised if your
solutions actually proved to be more efficient than the standard ones
applied to reference counting smart pointers. The standard ones use all
kinds of tricks based on value based semantics with over-writing with
assignment.



Francis Glassborow      Association of C & C++ Users
64 Southfield Rd
Oxford OX4 1PA          +44(0)1865 246490
All opinions are mine and do not represent those of any organisation

---
[ 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    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.research.att.com/~austern/csc/faq.html                ]
[ Note that the FAQ URL has changed!  Please update your bookmarks.     ]

In article <3A65D7D2.9AEDE8C9@infrasoft.co.at>,
Harald Nowak  <ishn@infrasoft.co.at> wrote:
>I think the whole situation could be much "enhanced" by providing
>versions of the
>(modifying) algorithms, that are in a way "compatible" with "owning"
>containers
>(in our established sense); such algorithms would need to fullfill
>another
>promise:
>When the algorithm ends, the same set of pointers exists that existed
>when the
>algorithm started. The algorithm shall do nothing more to the container
>than
>reorder the pointers; if elements need to be removed this can be done in
>the very
>same fashion than "partition" does - by providing an iterator pointing
>to the end
>of the valid and the beginning of the invalid elements range's.

As an alternative, would it be possible to provide versions of these
operations that automatically delete the object?  The memory leak that you
were originally describing only occurs if the vector contains the only live
pointers to the objects, and in this case it would be safe to delete them.

--
Barry Margolin, barmar@genuity.net
Genuity, Burlington, MA
*** DON'T SEND TECHNICAL QUESTIONS DIRECTLY TO ME, post them to newsgroups.
Please DON'T copy followups to me -- I'll assume it wasn't posted to the group.

---
[ 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    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.research.att.com/~austern/csc/faq.html                ]
[ Note that the FAQ URL has changed!  Please update your bookmarks.     ]

I would assume that reference semantics (in the form of pointers ar smart
pointers / handles) IS in fact the most common case for a container, especially
if it is to be sorted. At least my experience shows that, and most programmers I
talked to (including Stroustroup and P.J.Plauger) where in line with that - they
told me that their containers also contained (most of the time) either pointers
or handles (including, of course, "string"s).

So, I assume your point is: use your own smart pointers.
If this is the solution, I have to ask: what advice would you give a beginner,
that wants to use STL to make a container of objects, that can be
1. quickly sorted and
2. elements can be easily removed, depending on a certain creterion
?

"Roll your own smart pointer and use that" seems a bit to hefty for a beginner;
"download the BOOST smart pointer or you won't be able to do want you want" does
also not seem satisfactory to me.
As you may have heard of, there is a new school of teaching C++, that confronts
the C++ student with STL containers from the very beginning - so I guess they'll
stumble into this quite soon, at a time, where they do propably NOT yet have the
conceptual understanding to write their own (functionally correct!) smart
pointer.

Concerning the performance issue:
I have difficulties in believing, that sorting a smart pointer vector incurs
little overhead compared to sorting a native pointer vector; taking into
consideration that in the native pointe case we have a memory copy operation
only and in the smart pointer case we have a memory copy operation, an increase
or decrease operation AND a (possible) branch.

What strikes me most, is that each and every STL book does not fail to point out
the performance advantage of using predicate objects for the sort function,
thereby enabling the compiler to inline the sort predicate code. Yet, at the
same time, the overhead imposed by reference counting is taken for granted.

STL's design philosophy always seemed to be, NOT to impose such performance
penalties on the user, since this might prevent it's widespread use. Except in
this very case (the "ref counting if you like ref semantics" case). I talked to
many programmers about that, and I can tell by now, that many DO use STL
containers of pointers, but DON'T use smart pointers OR algorithms (since they
won't work in the naive way) - I fear that this development is contrary to the
intented one.

---
[ 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    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.research.att.com/~austern/csc/faq.html                ]
[ Note that the FAQ URL has changed!  Please update your bookmarks.     ]

I think it would be possible and possibly could be done in a performant way -
actually I would hope, that for each modifying algorithm there would also exist a
version that does memory cleanup, assuming each contained pointer is unique and
further assuming the objects live on the free store and the only references to
these are contained in the container in question. Though, I don't have much hope
that this will ever be implemented, since many people still do not really believe
that such "pointer-containers" are important (which I personally do not
understand).


> As an alternative, would it be possible to provide versions of these
> operations that automatically delete the object?  The memory leak that you
> were originally describing only occurs if the vector contains the only live
> pointers to the objects, and in this case it would be safe to delete them.

---
[ 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    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.research.att.com/~austern/csc/faq.html                ]
[ Note that the FAQ URL has changed!  Please update your bookmarks.     ]

> STL's design philosophy always seemed to be, NOT to impose such
performance
> penalties on the user, since this might prevent it's widespread use.
Except in
> this very case (the "ref counting if you like ref semantics" case). I
talked to
> many programmers about that, and I can tell by now, that many DO use
STL
> containers of pointers, but DON'T use smart pointers OR algorithms
(since they
> won't work in the naive way) - I fear that this development is
contrary to the
> intented one.

In my experience, that's very true.  I almost always use pointers in my
containers because of memory/efficiency issues, and I don't think I've
ever used an STL algorithm, the pointer issue being probably the
biggest impediment.


Sent via Deja.com
http://www.deja.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    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.research.att.com/~austern/csc/faq.html                ]
[ Note that the FAQ URL has changed!  Please update your bookmarks.     ]

On Mon, 22 Jan 2001 19:24:15 GMT, Harald Nowak <ishn@infrasoft.co.at>
wrote:

>I think it would be possible and possibly could be done in a performant way -
>actually I would hope, that for each modifying algorithm there would also exist a
>version that does memory cleanup, assuming each contained pointer is unique and
>further assuming the objects live on the free store and the only references to
>these are contained in the container in question. Though, I don't have much hope
>that this will ever be implemented, since many people still do not really believe
>that such "pointer-containers" are important (which I personally do not
>understand).

Wouldn't it be easier to make versions of the algorithms that
preserved elements - e.g. remove would make sure there was a copy of
each removed element at the end of the sequence, as would unique.
Perhaps remove_reorder, unique_reorder could be the names. Only a few
algorithms would even need special versions, since most algorithms
just reorder and so don't cause any problems for pointers.

With this change, you could safely use a "pointainer" (a sequence
container adapter that deletes on erase calls, etc) with the
algorithms.

Tom

---
[ 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    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.research.att.com/~austern/csc/faq.html                ]
[ Note that the FAQ URL has changed!  Please update your bookmarks.     ]

On Wed, 31 Jan 2001 02:40:29 GMT, Dietmar Kuehl wrote:
> I'm unsure what you are referring to but I read it as you are asking
> which useful algorithms there are in the standard C++ library.

No, I'm asking which standard algorithms lead to a "net loss" in values when
applied to containers of pointers.  Are there some that don't have "remove" or
"unique" in their names?

Scott

---
[ 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    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.research.att.com/~austern/csc/faq.html                ]
[ Note that the FAQ URL has changed!  Please update your bookmarks.     ]

Tom wrote:

> Wouldn't it be easier to make versions of the algorithms that
> preserved elements - e.g. remove would make sure there was a copy of
> each removed element at the end of the sequence

Oh, you mean std::partition()? That already exists.


--
Michiel Salters
Michiel.Salters@cmg.nl
salters@lucent.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    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.research.att.com/~austern/csc/faq.html                ]
[ Note that the FAQ URL has changed!  Please update your bookmarks.     ]

On Mon, 22 Jan 2001 19:24:15 GMT, Harald Nowak <ishn@infrasoft.co.at>
wrote:

>I think it would be possible and possibly could be done in a performant way -
>actually I would hope, that for each modifying algorithm there would also exist a
>version that does memory cleanup, assuming each contained pointer is unique and
>further assuming the objects live on the free store and the only references to
>these are contained in the container in question. Though, I don't have much hope
>that this will ever be implemented, since many people still do not really believe
>that such "pointer-containers" are important (which I personally do not
>understand).

Wouldn't it be easier to make versions of the algorithms that
preserved elements - e.g. remove would make sure there was a copy of
each removed element at the end of the sequence, as would unique.
Perhaps remove_reorder, unique_reorder could be the names. Only a few
algorithms would even need special versions, since most algorithms
just reorder and so don't cause any problems for pointers.

With this change, you could safely use a "pointainer" (a sequence
container adapter that deletes on erase calls, etc) with the
algorithms.

Tom

---
[ 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    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.research.att.com/~austern/csc/faq.html                ]
[ Note that the FAQ URL has changed!  Please update your bookmarks.     ]

Congratulations Tom - finally at least one other person in the forum arrived at a
similar idea than the one I originally posted in the forum. As you, I would like to
see these special, "pointer enabled" versions of the algorithms - actually I choose
the same names for them - xxxx_reorder, though I already heard some complaints about
this naming scheme.
The biggest advantage of having such algorithms in the standard instead of relying on
the intuition of the standard users and their ability to use partition would be, that
they would have to be documented - thereby forcing book authors, documentation authors
and C++ runtime writers to bring the problem with pointer containers to the readers
attention; something that seems to be done rarely nowadays.
At the same time, much time could be spared for the users of the C++ runtime, which
they might take to find out, that "partition" is the only algorithm they really want
to apply to such a container.

> Wouldn't it be easier to make versions of the algorithms that
> preserved elements - e.g. remove would make sure there was a copy of
> each removed element at the end of the sequence, as would unique.
> Perhaps remove_reorder, unique_reorder could be the names. Only a few
> algorithms would even need special versions, since most algorithms
> just reorder and so don't cause any problems for pointers.
>
> With this change, you could safely use a "pointainer" (a sequence
> container adapter that deletes on erase calls, etc) with the
> algorithms.



---
[ 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    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.research.att.com/~austern/csc/faq.html                ]
[ Note that the FAQ URL has changed!  Please update your bookmarks.     ]

> > No, I'm asking which standard algorithms lead to a "net loss" in values when
> > applied to containers of pointers.  Are there some that don't have "remove" or
> > "unique" in their names?
>
> Yes.  For example, std::copy.  If x1 and x2 are containers of pointers,
> then std::copy(x1.begin(), x1.end(), x2.begin()) will result in the
> values in x2 getting overwritten and lost.  If you want to avoid a
> memory leak, and you don't want to use a "smart pointer" class, then
> you'll need a version of std::copy that deletes the pointed-to objects
> before overwriting the pointers.

This is a highly interesting new perspective on the problem - we could of course
have a version of the copy algorithm, say copy_ptr, that deletes the pointers in the
iterator range following x2.begin() befor overwriting them. Here, the problem has to
be solved in a way that doesn't have anything to do with reordering - which suggests
that for our unique and remove algorithms we also want to use a postfix like ptr
(instead of the originally proposed _reorder). We would therefor have (until now):

remove_ptr
remove_if_ptr
unique_ptr
copy_ptr
remove_copy_ptr (the inverse of copy_ptr concerning it's predicate)

any further?

This naming scheme might come towards some people who found the idea compelling but
not the names.

---
[ 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    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.research.att.com/~austern/csc/faq.html                ]
[ Note that the FAQ URL has changed!  Please update your bookmarks.     ]

Harald Nowak wrote:
[...]
> remove_ptr
> remove_if_ptr
> unique_ptr
> copy_ptr
> remove_copy_ptr (the inverse of copy_ptr concerning it's predicate)
>
> any further?
>
> This naming scheme might come towards some people who found the idea compelling but
> not the names.

Well, I don't like those _ptr names, because they suggest
that all containers containing pointers own the data pointed
to by the pointer.  We need a name that says or suggests an
Owned Pointer, not just any pointer.

Dennis Yelle
--
I am a computer programmer and I am looking for a job.
There is a link to my resume here:
http://table.jps.net/~vert/

---
[ 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    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.research.att.com/~austern/csc/faq.html                ]
[ Note that the FAQ URL has changed!  Please update your bookmarks.     ]