Re: [boost] AlRangeExandrescu?

Subject: Re: [boost] AlRangeExandrescu?
From: Rogier van Dalen (rogiervd_at_[hidden])
Date: 2009-07-28 05:05:10

On Mon, Jul 27, 2009 at 22:39, Giovanni Piero
Deretta<gpderetta_at_[hidden]> wrote:
> Other containers are another story though, while I'm not surprised by
> the inefficiency of map and set iterators (it generates calls to non
> inlined functions), deque is a sore thumb: every copy constructor and
> assignment in the source code is explicitly translated to a copy in
> the generated assembler. Maybe it is because deque iterators are
> fairly large and GCC gives up optimizing away moves to and from
> memory.

BTW, are you using pairs of iterators for each of those? But is that
always the best way of implementing a range in a red-black tree (e.g.,
a set or a map)?

I don't know whether this goes for all conceivable implementations,
but when I implemented a red-black tree long ago, its iterator would
know its end. In that case, ranges until the end of the container
would require only one iterator, and possibly a pointer to the
container. This would require, however, that r.pop_back() (whatever
its spelling) is allowed to return a different type than r itself is.

So I think one-way iteration over a map or set could actually be
faster with ranges than with iterators, if the implementation of the
ranges knows the container's innards.

Cheers,
Rogier