Two new STL Questions

25 views
Skip to first unread message

Scott Meyers

unread,
Mar 8, 2000, 3:00:00 AM3/8/00
to
First off, I apologize for yesterday's question about the return type of
insert(iter, value) for associative containers. Shortly after submitting
the post, I found the answer to my question on page 184 of Josuttis. I
tried to cancel the post, but the far-too-efficient newsgroup moderators
has already reviewed it.

Josuttis is a remarkably useful, book, BTW. If you don't own it, you
should really get a copy.

Today I have two new questions:

- In sequence containers, if you have a valid iterator and you insert
something at that position, the inserted value goes BEFORE the element
the iterator points to. If you call insert for an associative
container, however, and you pass an iterator as a positional "hint,"
the best hint is one where the inserted value will go AFTER the element
the iterator points to. Why? Aside from being inconsistent with the
usual relationship between an iterator and its corresponding insertion
point, it means there's no way to suggest an element be inserted at the
beginning, and insert(container.end(), value) is NOT the way to suggest
that value be inserted at the end.

{ <http://anubis.dkuug.dk/jtc1/sc22/wg21/docs/lwg-closed.html#192>
-mod/jep }

- The other night I had an epiphany about the whole tawdry remove/erase
mess. We start with std::remove, which can be applied only to sequence
containers, because the elements in associative containers can't be
assigned. Hence std::remove is applicable only to vector, string,
deque, and list. Of these, if you really want to get rid of something
in a vector, string, or deque, you must (in the general case) shuffle
things around in memory, so the way std::remove works is about as good
as it gets. That's not true for list, because we can get rid of things
without having to move anything anywhere -- we just play with pointers.
Hence, std::remove applied to list -- and only to list -- is
ridiculously inefficient, so list provides member functions that remove
the elements the efficient way. The semantics of list::remove are
different from those for std::remove, because std::remove can't
actually perform the erasures needed to get rid of the elements.
Rather, it's expected that users of std::remove will apply the
"erase(remove, end)" idiom. There's no need for such an idiom with
list::remove, because it knows how to get rid of the elements, so it
does.

In other words, list::remove is just a more efficient version of
std::remove, and this efficiency manifests itself in two ways:
- Faster at runtime.
- Faster for programmers, because they don't have to bother to follow
the call to remove with the obligatory and annoying call to erase.

To me, this actually makes sense...except for list::remove's return
type. If list::remove is supposed to be a specialization for
std::remove, why doesn't it return an iterator like std::remove does?
If it's supposed to be a shorthand for the "erase(remove, end)" idiom,
why doesn't it return an iterator like erase does for sequence
containers? If it's supposed to be more like erase for associative
containers, why doesn't it return the number of erased elements? In
short, why doesn't list::remove return SOMETHING?

All enlightenment greatly appreciated,

Scott

--
"Effective STL" Seminar June 7-9 Portland, Oregon
Details at http://www.trekservices.com/estl/

[ Send an empty e-mail to c++-...@netlab.cs.rpi.edu for info ]
[ about comp.lang.c++.moderated. First time posters: do this! ]


Todd Greer

unread,
Mar 10, 2000, 3:00:00 AM3/10/00
to
sme...@aristeia.com (Scott Meyers) writes:

> - The other night I had an epiphany about the whole tawdry remove/erase
> mess. We start with std::remove, which can be applied only to sequence
> containers, because the elements in associative containers can't be
> assigned. Hence std::remove is applicable only to vector, string,

This is perhaps a nitpick...

The correctness of the statement 'elements in associative containers
can't be assigned', is questionable. The standard clearly says that
they are assignable, and that the associative containers support
bidirectional iterators, which satisfy the requirements for
std::remove. Unfortunately, the standard also says the exact opposite
of this. Thus, any statements about such as the above are essentially
meaningless.

Alternatively, anyone who knows standard logic knows that a
contradiction implies anything, so the standard clearly states (by
implication) that this bit of the standard needs badly to be fixed.

Is this likely to resolve in favor of the associative containers being
non-assignable, with a new iterator type (non-assignable
bidirectional?) created for the associatives? Will the offending
const in value_type go away?

--
Todd Greer <tgr...@acm.org>

Reply all
Reply to author
Forward
0 new messages