pedwards@cs.wright.edu (Phil Edwards) writes:

 |> CD2 doesn't specify one way or the other that I can find, but it seems
 |> that the HP-as-modified-for-DEC implementation of the algorithms in
 |> 25.2, [lib.alg.modifying.operations], are behaving very non-intuitively.
 |>
 |> Specifically, "deleting" members of a container, by whatever method, only
 |> copies the remaining elements "up" a place in the container, leaving
 |> copies of the last element in the container.  It seems that this would be
 |> fine (lazy deallocation), BUT the extraneous copy at the end is still
 |> being included in the container's membership.

This is correct.  The motivation, if I understand it correctly, is to
avoid invalidating iterators.  Another motivation might be to make it
work with builtin arrays (which have a fixed size that can't be
changed).

 |> As example, this:
 |>
 |>  deque<int>    foo;
 |>  for (int i=0; i<20; i++)  foo.push_back(i);
 |>
 |>  cerr << "Original foo:\n";
 |>  copy (foo.begin(), foo.end(), ostream_iterator<int>(cerr, " "));
 |>
 |>  remove (foo.begin(), foo.end(), 14);
 |>
 |>  cerr << "\n\nNew foo:\n";
 |>  copy (foo.begin(), foo.end(), ostream_iterator<int>(cerr, " "));
 |>  cerr << endl;
 |>
 |> results in:
 |>
 |>  Original foo:
 |>  0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
 |>
 |>  New foo:
 |>  0 1 2 3 4 5 6 7 8 9 10 11 12 13 15 16 17 18 19 19
 |>                                                        ^^-- ugh
 |>
 |> I realize that remove() and similar algorithms return "the end of the
 |> resulting range".  Does this mean that after a remove(), we can no
 |> longer reliably use end(), and instead must declare and carry around
 |> our own "actual_end" iterator for a final bound??

More likely, it means that the idiom you want is to call object.erase()
with the iterator returned by remove().

 |> I would have thought that the end() iterator would no longer include
 |> that final, "nonexistant" copy of 19, but mark the end of the visibly
 |> real container -- I myself am not interested in looking at all of the
 |> extraneous crap at the end of a container that /might/ be used someday!

So get rid of it.  All of the containers in the library have an erase
function.

And yes, I agree that it is not a particularly intuitive interface, even
if I think I understand the motivation.

--
James Kanze      home:     kanze@gabi-soft.fr        +33 (0)1 39 55 85 62
                 office:   kanze@vx.cit.alcatel.fr   +33 (0)1 69 63 14 54
GABI Software, Sarl., 22 rue Jacques-Lemercier, F-78000 Versailles France
     -- Conseils en informatique industrielle --
---
[ 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                             ]

James Kanze <james-albert.kanze@vx.cit.alcatel.fr> writes:

>  |> CD2 doesn't specify one way or the other that I can find, but it seems
>  |> that the HP-as-modified-for-DEC implementation of the algorithms in
>  |> 25.2, [lib.alg.modifying.operations], are behaving very non-intuitively.
>  |>
>  |> Specifically, "deleting" members of a container, by whatever method, only
>  |> copies the remaining elements "up" a place in the container, leaving
>  |> copies of the last element in the container.  It seems that this would be
>  |> fine (lazy deallocation), BUT the extraneous copy at the end is still
>  |> being included in the container's membership.
>
> This is correct.  The motivation, if I understand it correctly, is to
> avoid invalidating iterators.  Another motivation might be to make it
> work with builtin arrays (which have a fixed size that can't be
> changed).

It's not just a matter of motivation: it's a matter of what is and
isn't logically possible.

remove()'s argument is a range of iterators, not a container.  That
means that remove() can't possibly erase any of the container's
elements; it would need to have access to the container itself in
order to do that.

Note, by the way: there's nothing wrong with an algorithm that
actually erases a container's elements.  In fact, there probably
should be such an algorithm in the STL.  It's just that that algorithm
couldn't possibly have the same interface that remove() does.  One
of its arguments would have to be a container.

In general, container-based generic algorithms are a fairly big hole
in the STL.  There are other missing features, some of which are
even more important.
---
[ 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
]

On 28 May 97 09:12:37 GMT, pedwards@cs.wright.edu (Phil Edwards)
wrote:

>CD2 doesn't specify one way or the other that I can find, but it seems
>that the HP-as-modified-for-DEC implementation of the algorithms in
>25.2, [lib.alg.modifying.operations], are behaving very non-intuitively.
>
>Specifically, "deleting" members of a container, by whatever method, only
>copies the remaining elements "up" a place in the container, leaving
>copies of the last element in the container.  It seems that this would be
>fine (lazy deallocation), BUT the extraneous copy at the end is still
>being included in the container's membership.
>
>As example, this:
>
> deque<int>    foo;
> for (int i=0; i<20; i++)  foo.push_back(i);
>
> cerr << "Original foo:\n";
> copy (foo.begin(), foo.end(), ostream_iterator<int>(cerr, " "));
>
> remove (foo.begin(), foo.end(), 14);
>
> cerr << "\n\nNew foo:\n";
> copy (foo.begin(), foo.end(), ostream_iterator<int>(cerr, " "));
> cerr << endl;
>
>results in:
>
> Original foo:
> 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
>
> New foo:
> 0 1 2 3 4 5 6 7 8 9 10 11 12 13 15 16 17 18 19 19
>                                                       ^^-- ugh
>
>I realize that remove() and similar algorithms return "the end of the
>resulting range".
>...

With the iterator returned from remove( ), you can call erase( ) on
the deque itself to actually delete the elements.

(The generic algorithms, acting through iterators, don't have access
to the original container and so can't remove the elements from the
container)

,Brian Parker (bparker@gil.com.au)
---
[ 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
]