On Mon, Jul 27, 2009 at 22:39, Giovanni Piero Deretta<gpderetta@gmail.com> 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