jpotter@falcon.lhup.edu (John Potter) wrote in message news:<z%smc.6763$8S1.1191@newsread2.news.atl.earthlink.net>...
> On Tue, 4 May 2004 18:02:43 +0000 (UTC), pjp@dinkumware.com ("P.J.
> Plauger") wrote:
..
> > I'd find it easier to support you if you let go of this
> > absolutist viewpoint. Particularly since I've yet to see
> > you substantiate any of the alleged falsehoods in the STL
> > spec.
>
> Perhaps the wrong newsgroup?  I discuss claims for the framework
> called STL.  You discuss the C++ standard specification of the
> library.
>
> The framework claim is that algorithms are everything and need be
> written only once not once per container.  Your support for member
> algorithms shows the falsehood of the claim.

Where is this "framework claim" made? I think you've invented a
straw-man argument, just so you can knock it down.

A more reasonable assertion would be that algorithms are ubiquitous
(not "everything"), and that algorithms need to be written only once
for containers that meet the requirements you choose to impose upon
them for that algorithm. However, it's routinely the case that
algorithms need to be specialized for particular types to achieve
maximum efficiency with those types. It's also routinely the case that
the generic algorithm needs to be specialized for particular types
because it makes assumptions not valid for those types.

Any description of the STL that ignored those complications should be
considered a summary that needs to be expanded on to get the full
details, not a promise that has somehow been reneged upon because of
those details.

..
> So, the hype is false and the library is still nicely useful.

Anything can be hyped; unless the hypester is someone responsible for
the STL, the blame should apply to the hypester, not the STL. Who's
the hypester in this case?

---
[ 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.jamesd.demon.co.uk/csc/faq.html                       ]

jpotter@falcon.lhup.edu (John Potter) writes:

> The framework claim is that algorithms are everything and need be
> written only once not once per container.  Your support for member
> algorithms shows the falsehood of the claim.
>
> template <class Container, class Predicate>
> void erase_if (Container& c, Predicate p) {
>    c.erase(remove_if(c.begin(), c.end(), p), c.end());
>    }
>
> Works well for random access containers.  Works poorly for list.

I don't think that's precisely the claim for the STL framework
approach.  More precisely, it is that: many algorithms on
one-dimensional sequences of objects can be expressed in terms of
ranges of iterators, and iterator-based algorithms can be expressed
independently of the container that holds those objects.

Obviously there are many algorithms that can't or shouldn't be
expressed in terms of iterators.  The generic programming approach
still makes sense for those algorithms, but you'll need different
abstractions for them, not just 'iterator'.  Once you step outside of
algorithms that can be expressed in terms of iterators, you're
largely outside the STL.

You've given an example of a container-based algorithm.  There are no
container-based generic algorithms, either in the original STL
proposal or in the C++ standard library, just as (for example) there
are no floating-point numerical algorithms in the STL.

Perhaps the STL framework should be expanded to have container-based
generic algorithms : it would be nice to be able to write
std::remove_if(my_container, my_predicate).  A good framework for
container-based algorithms isn't all that hard, but it also isn't
completely trivial.  Among other things, it would mean revisiting the
standard's container requirements (which are not written as carefully
as the iterator requirements---no surprise, considering that they're
unused) and writing some container_traits machinery.

---
[ 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.jamesd.demon.co.uk/csc/faq.html                       ]

On Fri, 7 May 2004 16:25:59 +0000 (UTC), pjp@dinkumware.com ("P.J.
Plauger") wrote:

> "John Potter" <jpotter@falcon.lhup.edu> wrote in message
> news:z%smc.6763$8S1.1191@newsread2.news.atl.earthlink.net...

> > Fails to compile for associatives.

> And rightly so. remove_if requires writable iterators, which the
> associatives don't provide.

Proving inconsistency?  If it compiled, it would work correctly.

> This also fails to compile for
> const vectors. Another framework failure?

Hardly.

> Right. Another algorithm you made up, not supplied by STL.
> You have to be careful what you choose to put forth as a
> general algorithm. Stepanov and Musser winnowed their list
> over many years.

To a list of mostly useless things?  I don't think so, but
the generalization just does not happen.

Are you claiming that the impossibility of an erase_if alrgorithm
is a good thing?

John

---
[ 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.jamesd.demon.co.uk/csc/faq.html                       ]

On Fri, 7 May 2004 21:07:08 +0000 (UTC), austern@well.com (Matt Austern)
wrote:

> std::remove_if(my_container, my_predicate).

I am really disappointed that you used remove to do erase.

John

---
[ 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.jamesd.demon.co.uk/csc/faq.html                       ]

On Fri, 7 May 2004 17:53:43 +0000 (UTC), kuyper@wizard.net (James
Kuyper) wrote:

> A more reasonable assertion would be that algorithms are ubiquitous
> (not "everything"), and that algorithms need to be written only once
> for containers that meet the requirements you choose to impose upon
> them for that algorithm. However, it's routinely the case that
> algorithms need to be specialized for particular types to achieve
> maximum efficiency with those types. It's also routinely the case that
> the generic algorithm needs to be specialized for particular types
> because it makes assumptions not valid for those types.

A nice restatement of "Algorithms plus data structures equals programs."
The purpose of the STL is to generalize algorithms.  The specializstion
of the algorithms for specific containers is an admission of failure.

John

---
[ 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.jamesd.demon.co.uk/csc/faq.html                       ]

"John Potter" <jpotter@falcon.lhup.edu> wrote in message
news:%oXmc.8911$8S1.5283@newsread2.news.atl.earthlink.net...

> On Fri, 7 May 2004 16:25:59 +0000 (UTC), pjp@dinkumware.com ("P.J.
> Plauger") wrote:
>
> > "John Potter" <jpotter@falcon.lhup.edu> wrote in message
> > news:z%smc.6763$8S1.1191@newsread2.news.atl.earthlink.net...
>
> > > Fails to compile for associatives.
>
> > And rightly so. remove_if requires writable iterators, which the
> > associatives don't provide.
>
> Proving inconsistency?  If it compiled, it would work correctly.

I don't think so. If you were to rewrite the elements of an
associative container, you would destroy its integrity. People
make things const when they don't want them altered.

> > This also fails to compile for
> > const vectors. Another framework failure?
>
> Hardly.

Then I fail to see the distinction you make between a map and a
const vector. Both have elements made const for some good reason,
and the compiler tells you that. You try to apply a mutating
algorithm and you deserve to be brought up short.

> > Right. Another algorithm you made up, not supplied by STL.
> > You have to be careful what you choose to put forth as a
> > general algorithm. Stepanov and Musser winnowed their list
> > over many years.
>
> To a list of mostly useless things?  I don't think so, but
> the generalization just does not happen.

Perhaps not in your eyes, but YMMV.

> Are you claiming that the impossibility of an erase_if alrgorithm
> is a good thing?

No, I'm saying that you can't just toss off something like that,
then complain that your oversights caused problems. The algorithms
that did survive Stepanov and Musser's winnowing show quite a
bit of engineering. If you want to put forth something in the
same league, you have to do the same. But don't fault the STL
"framework" for that.

P.J. Plauger
Dinkumware, Ltd.
http://www.dinkumware.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.jamesd.demon.co.uk/csc/faq.html                       ]

John Potter <jpotter@falcon.lhup.edu> writes:

> On Fri, 7 May 2004 17:53:43 +0000 (UTC), kuyper@wizard.net (James
> Kuyper) wrote:
>
>> A more reasonable assertion would be that algorithms are ubiquitous
>> (not "everything"), and that algorithms need to be written only once
>> for containers that meet the requirements you choose to impose upon
>> them for that algorithm. However, it's routinely the case that
>> algorithms need to be specialized for particular types to achieve
>> maximum efficiency with those types. It's also routinely the case that
>> the generic algorithm needs to be specialized for particular types
>> because it makes assumptions not valid for those types.
>
> A nice restatement of "Algorithms plus data structures equals programs."
> The purpose of the STL is to generalize algorithms.  The specializstion
> of the algorithms for specific containers is an admission of failure.

This claim rests on a false premise.  std::list::remove is not a
specialization of std::remove.

--
Dave Abrahams
Boost Consulting
http://www.boost-consulting.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.jamesd.demon.co.uk/csc/faq.html                       ]

John Potter <jpotter@falcon.lhup.edu> wrote in message news:<HvXmc.8916$8S1.2830@newsread2.news.atl.earthlink.net>...
> On Fri, 7 May 2004 17:53:43 +0000 (UTC), kuyper@wizard.net (James
> Kuyper) wrote:
>
> > A more reasonable assertion would be that algorithms are ubiquitous
> > (not "everything"), and that algorithms need to be written only once
> > for containers that meet the requirements you choose to impose upon
> > them for that algorithm. However, it's routinely the case that
> > algorithms need to be specialized for particular types to achieve
> > maximum efficiency with those types. It's also routinely the case that
> > the generic algorithm needs to be specialized for particular types
> > because it makes assumptions not valid for those types.
>
> A nice restatement of "Algorithms plus data structures equals programs."
> The purpose of the STL is to generalize algorithms.  The specializstion
> of the algorithms for specific containers is an admission of failure.

What you've failed at depends upon what you were trying to do. If the
developers of STL had been stupid enough to set themselves a goal of
developing algorithms that would never needed specialization, and tbat
would never even benefit from specialization, than they would have
been incompetent to produce the STL. Do you have evidence that they
ever set themselves that goal?

---
[ 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.jamesd.demon.co.uk/csc/faq.html                       ]

On Mon, 10 May 2004 07:35:59 +0000 (UTC), pjp@dinkumware.com ("P.J.
Plauger") wrote:

> "John Potter" <jpotter@falcon.lhup.edu> wrote in message
> news:%oXmc.8911$8S1.5283@newsread2.news.atl.earthlink.net...

> > On Fri, 7 May 2004 16:25:59 +0000 (UTC), pjp@dinkumware.com ("P.J.
> > Plauger") wrote:

> > > "John Potter" <jpotter@falcon.lhup.edu> wrote in message
> > > news:z%smc.6763$8S1.1191@newsread2.news.atl.earthlink.net...

> > > > Fails to compile for associatives.

> > > And rightly so. remove_if requires writable iterators, which the
> > > associatives don't provide.

> > Proving inconsistency?  If it compiled, it would work correctly.

> I don't think so. If you were to rewrite the elements of an
> associative container, you would destroy its integrity. People
> make things const when they don't want them altered.

Here is a little program that you can test with your library.  It
uses a special iterator to remove the constipation of set.  Works
fine because remove_if maintains the order of the elements which
are not removed and set::erase requires no knowledge of the keys.
Strictly technical.

#include <algorithm>
#include <functional>
#include <iostream>
#include <iterator>
#include <set>
using namespace std;
template <class Fiter>
struct Exlax {
    typedef typename iterator_traits<Fiter>::iterator_category
            iterator_category;
    typedef typename iterator_traits<Fiter>::difference_type
            difference_type;
    typedef typename iterator_traits<Fiter>::value_type
        value_type;
    typedef value_type& reference;
    typedef value_type* pointer;
    Fiter p;
    Exlax () { }
    Exlax (Fiter p) : p(p) { }
    reference operator* () const {
        return const_cast<reference>(*p);
        }
    Exlax& operator++ () {
        ++ p;
        return *this;
        }
    };
template <class Fiter>
Exlax<Fiter> operator++ (Exlax<Fiter>& it, int) {
    Exlax<Fiter> tit(it);
    ++ it;
    return tit;
    }
template <class Fiter>
bool operator== (Exlax<Fiter> const& lhs, Exlax<Fiter> const& rhs) {
    return lhs.p == rhs.p;
    }
template <class Fiter>
bool operator!= (Exlax<Fiter> const& lhs, Exlax<Fiter> const& rhs) {
    return ! (lhs == rhs);
    }
struct Ap {
    int v;
    Ap (int v) : v(v) { }
    int operator() () { return v ++; }
    };
typedef set<int>::iterator Sit;
int main () {
    set<int> s;
    generate_n(inserter(s, s.end()), 20, Ap(0));
    copy(s.begin(), s.end(), ostream_iterator<int>(cout, " "));
    cout << "\n";
    s.erase(remove_if(Exlax<Sit>(s.begin()), Exlax<Sit>(s.end()),
            bind2nd(modulus<int>(), 2)).p, s.end());
    copy(s.begin(), s.end(), ostream_iterator<int>(cout, " "));
    cout << "\n";
    }

John

---
[ 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.jamesd.demon.co.uk/csc/faq.html                       ]

On 1/5/04 11:28 pm, in article
kOOkc.993$a47.448@newsread3.news.atl.earthlink.net, "John Potter"
<jpotter@falcon.lhup.edu> wrote:

>> But for vector, yes, you're right. However, it gets worse with list:
>>
>>     list::erase( iterator )
>>     list::remove( value ) // removes all matching values
>
> Yes, list shows the general failure of the STL.  The algorithms were
> written for vector/array and claimed to work for other containers.
> Since they are very inefficient on node based containers, they were
> incorporated as members making a lie of all STL claims.  Vector has
> no member to erase items because the algorithms remove and remove_if
> can efficiently move things and then erase can reduce the size.  The
> associatives have the erase(key) member which was originally misnamed
> remove(key) but lack erase_if.  List has misnamed remove(value) and
> remove_if members as well as the strange unique which all erase.
>
> John


I can imagine trying to 'fix' these problems by renaming the functions is
simply not a viable solution - it would break too much code.

Are there other solutions in the pipeline which might standardise these
container methods for C++0x ?


Steve.

---
[ 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.jamesd.demon.co.uk/csc/faq.html                       ]

"John Potter" <jpotter@falcon.lhup.edu> wrote in message
news:kOOkc.993$a47.448@newsread3.news.atl.earthlink.net...

> On Fri, 30 Apr 2004 22:48:05 +0000 (UTC), ng@spfweb.co.uk (Steve Folly)
> wrote:
>
> > On 30/4/04 8:56 pm, in article
jm859094d1s9vfe76v04928k53ugt7d1mc@4ax.com,
> > "Walter Tross" <walter@waltertross.com> wrote:
>
> > > unfortunately your mistake tells us something about the choice of some
> > > names in the STL... But anyhow, here is how I remember which is which:
> > > remove containts "move", which in a sense is what it actually does
>
> > That's a good way to remember it, thanks! :)
>
> Yes, remove moves things around and erase changes size.
>
> > But for vector, yes, you're right. However, it gets worse with list:
> >
> >     list::erase( iterator )
> >     list::remove( value ) // removes all matching values
>
> Yes, list shows the general failure of the STL.  The algorithms were
> written for vector/array and claimed to work for other containers.

Some algorithms require random-access iterators and work with vector,
deque, and array. Some require bidirectional iterators, or weaker,
and work with all containers. That was the claim, and it's true.

> Since they are very inefficient on node based containers,

Really? Aren't you the one who keeps telling people to measure
before making sweeping claims of efficiency? If you're talking
about trying to make work for list algorithms that require
random-access iterators, then I agree with you. But you certainly
don't make that clear.

>                                                          they were
> incorporated as members making a lie of all STL claims.

I consider that a bit of an overstatement. You might notice that
*some* people are using STL and finding it satisfactory, which
sort of, uh, makes a lie of your claim.

>                                                       Vector has
> no member to erase items because the algorithms remove and remove_if
> can efficiently move things and then erase can reduce the size.  The
> associatives have the erase(key) member which was originally misnamed
> remove(key) but lack erase_if.  List has misnamed remove(value) and
> remove_if members as well as the strange unique which all erase.

I'll grant that there are naming inconsistencies in STL. Some are
historic and some the result of C++ committee tinkering. But you'd
be hard pressed to find a software package of comparable complexity
(and usefulness) that's any better.

In sooth, list would not suffer much from the removal of remove,
remove_if, and unique. The main thing you'd have to give up is
the ability to implement list for element types that don't support
assignment (but that goes beyond what the C++ Standard requires
anyway). Same is true for reverse, but see below.

It's easy to change stable_sort to work with bidirectional
iterators instead of random-access iterators, so you could use it to
sort lists. Again, you'd have to assign between nodes instead of
just constructing them and resplicing them.

That leaves only merge and splice as essential member functions.
They take advantage of the special properties of list in ways
that are hard to match. Nevertheless I'd be reluctant to drop the
member functions sort and reverse from list because they also take
excellent advantage of these special properties.

In summary, I think your harangue is misdirected. Aside from a
few ill considered names, most of the irregularities among the
STL containers are pretty defensible.

P.J. Plauger
Dinkumware, Ltd.
http://www.dinkumware.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.jamesd.demon.co.uk/csc/faq.html                       ]

""P.J. Plauger"" <pjp@dinkumware.com> wrote in message
news:xZ7lc.68212$G_.44653@nwrddc02.gnilink.net...

> In sooth, list would not suffer much from the removal of remove,
> remove_if, and unique. The main thing you'd have to give up is
> the ability to implement list for element types that don't support
> assignment (but that goes beyond what the C++ Standard requires
> anyway). Same is true for reverse, but see below.

Sorry to answer my own post, but upon further reflection I realize
that list offers distinct advantages to internal implementations
of remove, remove_if, and unique. Single-node erasures are so cheap
that these functions can go much faster than the general algorithms
that copy down to compress a sequence.

In fact, I think a case can be made for adding these functions to
the eight template classes [unordered_][muilti]{map set}.

P.J. Plauger
Dinkumware, Ltd.
http://www.dinkumware.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.jamesd.demon.co.uk/csc/faq.html                       ]

On Mon, 3 May 2004 22:26:25 +0000 (UTC), pjp@dinkumware.com ("P.J.
Plauger") wrote:

> Sorry to answer my own post, but upon further reflection I realize
> that list offers distinct advantages to internal implementations
> of remove, remove_if, and unique. Single-node erasures are so cheap
> that these functions can go much faster than the general algorithms
> that copy down to compress a sequence.

> In fact, I think a case can be made for adding these functions to
> the eight template classes [unordered_][muilti]{map set}.

Which supports my complaint.  The algorithms work on node based
containers; however, members are much more efficient proving that
the STL claim for algorithms is false.  If I change container type
from vector to list, I may need to change the code from general
algorithms to members.

The claim of the STL is false.  It is still very useful.

Thanks for the support.

John

---
[ 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.jamesd.demon.co.uk/csc/faq.html                       ]

pjp@dinkumware.com ("P.J. Plauger") writes:

> ""P.J. Plauger"" <pjp@dinkumware.com> wrote in message
> news:xZ7lc.68212$G_.44653@nwrddc02.gnilink.net...
>
>> In sooth, list would not suffer much from the removal of remove,
>> remove_if, and unique. The main thing you'd have to give up is
>> the ability to implement list for element types that don't support
>> assignment (but that goes beyond what the C++ Standard requires
>> anyway). Same is true for reverse, but see below.
>
> Sorry to answer my own post, but upon further reflection I realize
> that list offers distinct advantages to internal implementations
> of remove, remove_if, and unique. Single-node erasures are so cheap
> that these functions can go much faster than the general algorithms
> that copy down to compress a sequence.
>
> In fact, I think a case can be made for adding these functions to
> the eight template classes [unordered_][muilti]{map set}.

It seems to me a specialized [multi]{map set}::remove() (but not
    remove_if) could require only in O(lg(n)) operations.

---
[ 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.jamesd.demon.co.uk/csc/faq.html                       ]

jpotter@falcon.lhup.edu (John Potter) writes:

> On Mon, 3 May 2004 22:26:25 +0000 (UTC), pjp@dinkumware.com ("P.J.
> Plauger") wrote:
>
>> Sorry to answer my own post, but upon further reflection I realize
>> that list offers distinct advantages to internal implementations
>> of remove, remove_if, and unique. Single-node erasures are so cheap
>> that these functions can go much faster than the general algorithms
>> that copy down to compress a sequence.
>
>> In fact, I think a case can be made for adding these functions to
>> the eight template classes [unordered_][muilti]{map set}.
>
> Which supports my complaint.  The algorithms work on node based
> containers; however, members are much more efficient proving that
> the STL claim for algorithms is false.  If I change container type
> from vector to list, I may need to change the code from general
> algorithms to members.
>
> The claim of the STL is false.  It is still very useful.

Not sure which claim, precisely you mean.  Certainly this doesn't
"make a lie of all claims", as you claimed earlier.  I should point
out, also, that members involving node erasures don't have equivalent
semantics to the sequence algorithms, which never destroy elements.

That said, I'm well and truly convinced that a "whole-sequence-based"
design would be superior for some purposes.

--
Dave Abrahams
Boost Consulting
http://www.boost-consulting.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.jamesd.demon.co.uk/csc/faq.html                       ]

"John Potter" <jpotter@falcon.lhup.edu> wrote in message
news:KvClc.3958$8S1.3291@newsread2.news.atl.earthlink.net...

> On Mon, 3 May 2004 22:26:25 +0000 (UTC), pjp@dinkumware.com ("P.J.
> Plauger") wrote:
>
> > Sorry to answer my own post, but upon further reflection I realize
> > that list offers distinct advantages to internal implementations
> > of remove, remove_if, and unique. Single-node erasures are so cheap
> > that these functions can go much faster than the general algorithms
> > that copy down to compress a sequence.
>
> > In fact, I think a case can be made for adding these functions to
> > the eight template classes [unordered_][muilti]{map set}.
>
> Which supports my complaint.  The algorithms work on node based
> containers; however, members are much more efficient proving that
> the STL claim for algorithms is false.

The claims made by STL involve time complexity. They're still
maintained. By taking advantages of the special properties of a
node-based container, you can improve the *multiplier* but you
don't alter the *complexity*. (list::sort may have better
time complexity than stable sort -- I'm not certain without
looking closer -- but that simply makes it an acceptable
substitute. STL never prohibits an implementation from doing
*better* than it has to on any given algorithm.)

>                                        If I change container type
> from vector to list, I may need to change the code from general
> algorithms to members.

If you've been using algorithms that require random-access
iterators, then that change should be expected. If not,
then you shouldn't have to change anything. You may *choose*
to change somethink, just because your code can measurably benefit
from the increase in speed. But you're not likely to see any
setback in time complexity if you don't, and that's what STL
*claims* to guarantee.

> The claim of the STL is false.  It is still very useful.
>
> Thanks for the support.

I'd find it easier to support you if you let go of this
absolutist viewpoint. Particularly since I've yet to see
you substantiate any of the alleged falsehoods in the STL
spec.

P.J. Plauger
Dinkumware, Ltd.
http://www.dinkumware.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.jamesd.demon.co.uk/csc/faq.html                       ]

jpotter@falcon.lhup.edu (John Potter) wrote in message news:<KvClc.3958$8S1.3291@newsread2.news.atl.earthlink.net>...
..
> The claim of the STL is false.  It is still very useful.

Could express clearly the claim that you think STL makes, which you
believe to be false? I have no idea what you're referring to. Your
statements contain facts that correspond fairly well to my own
understanding of STL, and I see no cause for complaint in those facts.

---
[ 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.jamesd.demon.co.uk/csc/faq.html                       ]

On Tue, 4 May 2004 18:02:43 +0000 (UTC), pjp@dinkumware.com ("P.J.
Plauger") wrote:

> "John Potter" <jpotter@falcon.lhup.edu> wrote in message
> news:KvClc.3958$8S1.3291@newsread2.news.atl.earthlink.net...

> > On Mon, 3 May 2004 22:26:25 +0000 (UTC), pjp@dinkumware.com ("P.J.
> > Plauger") wrote:

> > > Sorry to answer my own post, but upon further reflection I realize
> > > that list offers distinct advantages to internal implementations
> > > of remove, remove_if, and unique. Single-node erasures are so cheap
> > > that these functions can go much faster than the general algorithms
> > > that copy down to compress a sequence.

> > > In fact, I think a case can be made for adding these functions to
> > > the eight template classes [unordered_][muilti]{map set}.

> > Which supports my complaint.  The algorithms work on node based
> > containers; however, members are much more efficient proving that
> > the STL claim for algorithms is false.

> The claims made by STL involve time complexity. They're still
> maintained. By taking advantages of the special properties of a
> node-based container, you can improve the *multiplier* but you
> don't alter the *complexity*. (list::sort may have better
> time complexity than stable sort -- I'm not certain without
> looking closer -- but that simply makes it an acceptable
> substitute. STL never prohibits an implementation from doing
> *better* than it has to on any given algorithm.)

> >                                        If I change container type
> > from vector to list, I may need to change the code from general
> > algorithms to members.

> If you've been using algorithms that require random-access
> iterators, then that change should be expected. If not,
> then you shouldn't have to change anything. You may *choose*
> to change somethink, just because your code can measurably benefit
> from the increase in speed. But you're not likely to see any
> setback in time complexity if you don't, and that's what STL
> *claims* to guarantee.

> > The claim of the STL is false.  It is still very useful.

> > Thanks for the support.

> I'd find it easier to support you if you let go of this
> absolutist viewpoint. Particularly since I've yet to see
> you substantiate any of the alleged falsehoods in the STL
> spec.

Perhaps the wrong newsgroup?  I discuss claims for the framework
called STL.  You discuss the C++ standard specification of the
library.

The framework claim is that algorithms are everything and need be
written only once not once per container.  Your support for member
algorithms shows the falsehood of the claim.

template <class Container, class Predicate>
void erase_if (Container& c, Predicate p) {
   c.erase(remove_if(c.begin(), c.end(), p), c.end());
   }

Works well for random access containers.  Works poorly for list.
Fails to compile for associatives.

   for (Container::iterator it(c.begin()); it != c.end(); )
      if (p(*it))
         c.erase(it ++);
      else
         ++ it;

Works well for list and associatives and has undefined behavior
for random access.

   for (Container::iterator it(c.begin()); it != c.end(); )
      if (p(*it))
         it = c.erase(it);
      else
         ++ it;

Works well for list.  Does not compile for associatives, by choice
not accident.  Is O(N^2) for random access.

The terms standardized are inconsistent.  Remove does not erase
unless it is a misnamed member of list.  A bug which can't be
fixed and has no justification.

The standard offers meaningless guarantees.  Vector push_back is
O(N) but could be O(N^2) for real uses in a conforming library.

   new_capacity = 1.000001 * old_capacity + 1;

So, the hype is false and the library is still nicely useful.

John

---
[ 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.jamesd.demon.co.uk/csc/faq.html                       ]

I have always understood that vector::erase() does not actually remove
elements from a vector but works by using copy assignment to change the
values stored followed by resetting the value returned by end(). Actual
removal I understood had to be done by applying std::remove().

So am I wrong? If so it would appear that I am in good company including
Scott Meyers and Nico Josuttis.

If I am correct what is the meaning of 23.2.4.3 vector modifiers para
3&4:

Invalidates all the iterators and references after the point of the
erase.

The destructor of T is called the number of times equal to the number of
the elements erased, but the assignment operator of T is called the
number of times equal to the number of elements in the vector after the
erased elements.



--
Francis Glassborow      ACCU
Author of 'You Can Do It!' see http://www.spellen.org/youcandoit
For project ideas and contributions: http://www.spellen.org/youcandoit/projects

---
[ 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.jamesd.demon.co.uk/csc/faq.html                       ]

francis@robinton.demon.co.uk (Francis Glassborow) writes:

> I have always understood that vector::erase() does not actually remove
> elements from a vector but works by using copy assignment to change
> the values stored followed by resetting the value returned by
> end(). Actual removal I understood had to be done by applying
> std::remove().
[snip]

I think you have it backward. vector<>::erase() really does
    erase. It's std::remove() which does not remove.

>
> So am I wrong? If so it would appear that I am in good company
> including Scott Meyers and Nico Josuttis.

Re-read Meyers, _Effective STL_ item 32, in particular:

# [...] Think for a moment about how one eliminates elements from a
# container. The only way to do it is to call a member function on
# that container, almost always some form of erase. [...]

---
[ 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.jamesd.demon.co.uk/csc/faq.html                       ]

On Fri, 30 Apr 2004 16:38:32 +0000 (UTC), Francis Glassborow wrote:
> I have always understood that vector::erase() does not actually remove
> elements from a vector but works by using copy assignment to change the
> values stored followed by resetting the value returned by end(). Actual
> removal I understood had to be done by applying std::remove().

It's the other way around.

> So am I wrong? If so it would appear that I am in good company including
> Scott Meyers and Nico Josuttis.

If I've published something where I got this wrong, please tell me about
it!  Item 32 in Effective STL is where I discuss std::remove
vs. container::erase.

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.jamesd.demon.co.uk/csc/faq.html                       ]

On Fri, 30 Apr 2004 16:38:32 +0000 (UTC), francis@robinton.demon.co.uk
(Francis Glassborow) wrote:

>
>I have always understood that vector::erase() does not actually remove
>elements from a vector but works by using copy assignment to change the
>values stored followed by resetting the value returned by end(). Actual
>removal I understood had to be done by applying std::remove().

unfortunately your mistake tells us something about the choice of some
names in the STL... But anyhow, here is how I remember which is which:
remove containts "move", which in a sense is what it actually does

---
[ 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.jamesd.demon.co.uk/csc/faq.html                       ]

On 30/4/04 8:56 pm, in article jm859094d1s9vfe76v04928k53ugt7d1mc@4ax.com,
"Walter Tross" <walter@waltertross.com> wrote:

> On Fri, 30 Apr 2004 16:38:32 +0000 (UTC), francis@robinton.demon.co.uk
> (Francis Glassborow) wrote:
>
>>
>> I have always understood that vector::erase() does not actually remove
>> elements from a vector but works by using copy assignment to change the
>> values stored followed by resetting the value returned by end(). Actual
>> removal I understood had to be done by applying std::remove().
>
> unfortunately your mistake tells us something about the choice of some
> names in the STL... But anyhow, here is how I remember which is which:
> remove containts "move", which in a sense is what it actually does

That's a good way to remember it, thanks! :)

But for vector, yes, you're right. However, it gets worse with list:

    list::erase( iterator )
    list::remove( value ) // removes all matching values



Steve.

---
[ 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.jamesd.demon.co.uk/csc/faq.html                       ]

In article <MPG.1afc2e7d533f8af498974a@news.hevanet.com>, Scott Meyers
<Usenet@aristeia.com> writes
>On Fri, 30 Apr 2004 16:38:32 +0000 (UTC), Francis Glassborow wrote:
>> I have always understood that vector::erase() does not actually remove
>> elements from a vector but works by using copy assignment to change the
>> values stored followed by resetting the value returned by end(). Actual
>> removal I understood had to be done by applying std::remove().
>
>It's the other way around.
>
>> So am I wrong? If so it would appear that I am in good company including
>> Scott Meyers and Nico Josuttis.
>
>If I've published something where I got this wrong, please tell me about
>it!  Item 32 in Effective STL is where I discuss std::remove
>vs. container::erase.

Thanks, I managed to get confused, too many days burning the candle at
both ends.


--
Francis Glassborow      ACCU
Author of 'You Can Do It!' see http://www.spellen.org/youcandoit
For project ideas and contributions: http://www.spellen.org/youcandoit/projects

---
[ 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.jamesd.demon.co.uk/csc/faq.html                       ]

"Francis Glassborow" <francis@robinton.demon.co.uk> wrote in message
news:uHDkvzBy+hkAFwP3@robinton.demon.co.uk...
>
> I have always understood that vector::erase() does not actually remove
> elements from a vector but works by using copy assignment to change the
> values stored followed by resetting the value returned by end(). Actual
> removal I understood had to be done by applying std::remove().

This description seems a bit mixed up:

  std::remove is the global algorithm which removes items of a sequence
that compare equal to a provided parameter, and does so by 'moving down'
the remaining elements onto the removed ones (using assignment).
The result is 'stale' items are left at the end of the original
sequence, and typically need to be deleted.

  vector::erase is a member functions which actually erases a range
from the controlled sequence. Trailing items are shifted down, and
the 'stale' items at the end are destroyed and removed.

So given a unsorted std::vector<int> v, you would remove all items
equal to 5 by calling:
  v.erase(  intVec.remove(v.begin(),v.end(),5)  , v.end()  );


The erase call actually deletes and destroys the specified range.
For example, v.clear() is specified to be equivalent to
v.erase( v.begin(), v.end() ).


> So am I wrong? If so it would appear that I am in good company including
> Scott Meyers and Nico Josuttis.

I believe that what they wrote matches the desciption above.
You might have confused some features of the the two functions...

> If I am correct what is the meaning of 23.2.4.3 vector modifiers para
> 3&4:
>
> Invalidates all the iterators and references after the point of the
> erase.
>
> The destructor of T is called the number of times equal to the number of
> the elements erased, but the assignment operator of T is called the
> number of times equal to the number of elements in the vector after the
> erased elements.

Elements beyond the range to be eased are shifted down using assignment,
then the stale elements are destroyed. No relocation of the whole
vector is allowed.


Kind regards,
Ivan
--
http://ivan.vecerina.com/contact/?subject=NG_POST <- e-mail contact form


---
[ 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.jamesd.demon.co.uk/csc/faq.html                       ]

Francis Glassborow wrote:

>
> I have always understood that vector::erase() does not actually remove
> elements from a vector but works by using copy assignment to change the
> values stored followed by resetting the value returned by end(). Actual
> removal I understood had to be done by applying std::remove().

Isn't that the wrong way around?  remove() copy-assigns over the 'removed'
elements but does not change the size of the container.  erase() actually
does the deleting.

Standard ideom is

vec.erase(remove(first, last, some_element), vec.end());

to remove all instances of some_element from the range [first,last) and
shrink the container.

Josuttis seems to agree with this; for example
http://www.josuttis.com/libbook/stl/remove2.cpp.html

Cheers,
Ian McCulloch


---
[ 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.jamesd.demon.co.uk/csc/faq.html                       ]

On Fri, 30 Apr 2004 22:48:05 +0000 (UTC), ng@spfweb.co.uk (Steve Folly)
wrote:

> On 30/4/04 8:56 pm, in article jm859094d1s9vfe76v04928k53ugt7d1mc@4ax.com,
> "Walter Tross" <walter@waltertross.com> wrote:

> > unfortunately your mistake tells us something about the choice of some
> > names in the STL... But anyhow, here is how I remember which is which:
> > remove containts "move", which in a sense is what it actually does

> That's a good way to remember it, thanks! :)

Yes, remove moves things around and erase changes size.

> But for vector, yes, you're right. However, it gets worse with list:
>
>     list::erase( iterator )
>     list::remove( value ) // removes all matching values

Yes, list shows the general failure of the STL.  The algorithms were
written for vector/array and claimed to work for other containers.
Since they are very inefficient on node based containers, they were
incorporated as members making a lie of all STL claims.  Vector has
no member to erase items because the algorithms remove and remove_if
can efficiently move things and then erase can reduce the size.  The
associatives have the erase(key) member which was originally misnamed
remove(key) but lack erase_if.  List has misnamed remove(value) and
remove_if members as well as the strange unique which all erase.

John

---
[ 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.jamesd.demon.co.uk/csc/faq.html                       ]