Boost logo

Boost :

Subject: Re: [boost] [Iterator][MultiIndex]iterator-specificpartition_point-relatedfunctions
From: David Abrahams (dave_at_[hidden])
Date: 2008-12-01 12:24:16

on Mon Dec 01 2008, Arno Schödl <> wrote:

>>> using std::lower_bound;
>>> CustomIt itA, itB;
>>> lower_bound( itA, itB );
>>> Do we agree that this is how the client side should work?
>>No, I don't think so. I'm not sure exactly the implications but at
>>first glance it looks too clever by half.
> How is that clever? It follows the same pattern as the one for a custom swap:
> using std::swap;
> CustomType tA, tB;
> swap( tA, tB );
> What do you propose instead?

I think if you want to call lower_bound in the most efficient way, it
should be possible to do so with qualification. If the algorithm in
std:: isn't sufficiently "hookable," one should create a different one
that is. The universe of names to be found by ADL should be limited to
fundamental operations like swap, since ADL reserves names "globally."

I guess if you told me (and I can believe that it's true) that for these
other iterators types, the entire implementation of lower_bound needs to
be replaced in order to be most efficient, I might have to reconsider
lower_bound as a fundamental operation, but it still "feels wrong."

>>> The only way to achieve that, as far as I can see, is to implement a
>>> lower_bound for each and every iterator that defines its own
>>> partition_point. Or do you have an idea?
>>You can always provide a CRTP base class template people can use, and
>>implement lower_bound for that.
> The reason I used a macro is that CRTP requires that library
> maintainers are willing to change their code.

Yes, it's an intrusive solution, but implementing lower_bound for a
particular iterator type requires knowledge of the implementation
details, doesn't it?

If you want to be non-intrusive, you can always use traits and tag
dispatching or enable_if.

> Specifically for my application, you (as maintainer of
> boost.Iterator?) would have to change
> boost::transform_iterator/filter_iterator and Joaquin
> multi_index_container. If we can agree on that, I will change the code
> to CRTP.

I am willing to consider such changes.

> Instead, I could derive from the existing classes and implement CRTP
> on top, but that creates two versions of each iterator, which is IMO
> unwarranted if the semantics of the two are the same, the only
> difference being performance.


Dave Abrahams
BoostPro Computing

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