Boost logo

Boost :

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.


Boost list run by bdawes at, gregod at, cpdaniel at, john at