[MultiIndex] STL algorithm support for multi_index_containers
Hello, we have added support for using multi_index ordered index iterators in lieu of random access iterators in standard algorithms that require sorted ranges, e.g. lower_bound, upper_bound, equal_range, and binary_search. This is useful when using these iterators in generic algorithms that internally call lower_bound/upper_bound/etc. Our implementation is attached. We are currently overloading std::lower_bound/... which is illegal. I propose introducing a boost::lower_bound/..., where we can ignore the C++ standard restriction, and where the standard implementation forwards to std::lower_bound. Runtime is O(log N), where N is the total number of elements in the container, rather than, as it would be optimal, the number of elements within the (sub)range on which the algorithm is called. The problem is that the red-black tree nodes do not store the tree level number, so we cannot find the parent node that encompasses the whole subrange in linear time. I am not sure this is practically relevant. In any case, using the sortedness of the tree rather than treating the iterators as arbitrary bidirectional iterators is a step forward. Any opinions? Regards, Arno -- Dr. Arno Schoedl · aschoedl@think-cell.com Technical Director think-cell Software GmbH · Invalidenstr. 34 · 10115 Berlin, Germany http://www.think-cell.com · phone +49-30-666473-10 · toll-free (US) +1-800-891-8091 Directors: Dr. Markus Hannebauer, Dr. Arno Schoedl · Amtsgericht Charlottenburg, HRB 85229
Arno Schödl <aschoedl <at> think-cell.com> writes:
Hello,
we have added support for using multi_index ordered index iterators in lieu of random access iterators in standard algorithms that require sorted ranges, e.g. lower_bound, upper_bound, equal_range, and binary_search. This is useful when using these iterators in generic algorithms that internally call lower_bound/upper_bound/etc. Our implementation is attached. We are currently overloading std::lower_bound/... which is illegal. I propose introducing a boost::lower_bound/..., where we can ignore the C++ standard restriction, and where the standard implementation forwards to std::lower_bound.
I think this can be a useful addition, and maybe other Boost containers (ptr_container, intrusive) can provide their own overloads too. boost::lower_bound is no different in this respect to other initiatives like boost::swap. BTW, why does the standard forbid overloading std functions for user-defined types? I'm sure thre's a a good reason for that, but never found a explicitly stated rationale. Joaquín M López Muñoz Telefónica, Investigación y Desarrollo
std::lower_bound/... which is illegal. I propose introducing a boost::lower_bound/..., where we can ignore the C++ standard restriction, and where the standard implementation forwards to std::lower_bound.
I think this can be a useful addition, and maybe other Boost containers (ptr_container, intrusive) can provide their own overloads too. boost::lower_bound is no different in this respect to other initiatives like boost::swap.
What is the state of Dave's proposal: http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2001/n1313.html If we have to introduce our own lower_bound/... anyway, I'd prefer having a single generic binary_partition( It, It, Unary ) function to override by iterator implementors. Then our lower_bound/... can be implemented in terms of that function. Arno -- Dr. Arno Schoedl · aschoedl@think-cell.com Technical Director think-cell Software GmbH · Invalidenstr. 34 · 10115 Berlin, Germany http://www.think-cell.com · phone +49-30-666473-10 · toll-free (US) +1-800-891-8091 Directors: Dr. Markus Hannebauer, Dr. Arno Schoedl · Amtsgericht Charlottenburg, HRB 85229
Arno Schödl escribió:
What is the state of Dave's proposal:
http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2001/n1313.html
It's accepted and part now of the C++0x standard draft. Anyway, the proposal is, AFAICS, orthogonal with your issue.
If we have to introduce our own lower_bound/... anyway, I'd prefer having a single generic binary_partition( It, It, Unary ) function to override by iterator implementors. Then our lower_bound/... can be implemented in terms of that function.
That would be a nice extension mechanism. Maybe you can write a short description of the whole scheme so as to raise interest in the list. Joaquín M López Muñoz Telefónica, Investigación y Desarrollo
That would be a nice extension mechanism. Maybe you can write a short description of the whole scheme so as to raise interest in the list.
So here we go: Some iterator implementations would benefit from special implementations for partition_point-type functions, in particular lower_bound, upper_bound, equal_range and binary_search. Although they are not able to provide random access, if properly implemented, they offer O(log N) lookup. Here are some examples: - multi-index container ordered index iterators can exploit the red-black tree. - filter_iterator can exploit random access on the base iterator, and after an element is found, search forward for the next unfiltered element. The efficiency would degrade gracefully with the degree of filtering performed. - [not in boost] union_iterator, which unifies two underlying sorted ranges, could do the look-up on both ranges independently and then do one final application of the predicate. - Other boost iterator adaptors would not directly benefit from this scheme, but would be able to pass through to their base_iterator by appropriately wrapping the predicate. So for example, partition_point( transform_iterator( filter_iterator( random_access iterator ))) would still be efficient. lower_bound, upper_bound, equal_range and binary_search can all be implemented on top of partition_point. So I propose a special base class, partition_point_facade, similar to iterator_facade, which when provided with a member function It::partition_point( It it, Pred pred ), implements the others as free functions. Is there any interest, and possibly willingness to include it into Boost.Iterator? Arno -- Dr. Arno Schoedl · aschoedl@think-cell.com Technical Director think-cell Software GmbH · Invalidenstr. 34 · 10115 Berlin, Germany http://www.think-cell.com · phone +49-30-666473-10 · toll-free (US) +1-800-891-8091 Directors: Dr. Markus Hannebauer, Dr. Arno Schoedl · Amtsgericht Charlottenburg, HRB 85229
Hello, I am posting this again with [Iterator] included in the subject. I am still hoping to raise some interest. If it does not work this time, I will give up, I promise. Some iterator implementations would benefit from special implementations for partition_point-type functions, in particular lower_bound, upper_bound, equal_range and binary_search. Although they are not able to provide random access, if properly implemented, they offer O(log N) lookup. Here are some examples: - multi-index container ordered index iterators can exploit the red-black tree. - filter_iterator can exploit random access on the base iterator, and after an element is found, search forward for the next unfiltered element. The efficiency would degrade gracefully with the degree of filtering performed. - [not in boost] union_iterator, which unifies two underlying sorted ranges, could do the look-up on both ranges independently and then do one final application of the predicate. - Other boost iterator adaptors would not directly benefit from this scheme, but would be able to pass through to their base_iterator by appropriately wrapping the predicate. So for example, partition_point( transform_iterator( filter_iterator( random_access iterator ))) would still be efficient if filter_iterator keeps most of the elements. lower_bound, upper_bound, equal_range and binary_search can all be implemented on top of partition_point. So I propose a special base class, partition_point_facade, similar to iterator_facade, which when provided with a member function It::partition_point( It it, Pred pred ), implements the others as free functions. Is there any interest, and possibly willingness to include it into Boost.Iterator? Arno -- Dr. Arno Schoedl · aschoedl@think-cell.com Technical Director think-cell Software GmbH · Invalidenstr. 34 · 10115 Berlin, Germany http://www.think-cell.com · phone +49-30-666473-10 · toll-free (US) +1-800-891-8091 Directors: Dr. Markus Hannebauer, Dr. Arno Schoedl · Amtsgericht Charlottenburg, HRB 85229
Arno Schödl escribió:
Hello,
I am posting this again with [Iterator] included in the subject. I am still hoping to raise some interest. If it does not work this time, I will give up, I promise.
Some iterator implementations would benefit from special implementations for partition_point-type functions, in particular lower_bound, upper_bound, equal_range and binary_search. Although they are not able to provide random access, if properly implemented, they offer O(log N) lookup. [...] lower_bound, upper_bound, equal_range and binary_search can all be implemented on top of partition_point. So I propose a special base class, partition_point_facade, similar to iterator_facade, which when provided with a member function It::partition_point( It it, Pred pred ), implements the others as free functions. Is there any interest, and possibly willingness to include it into Boost.Iterator?
Although I've commented on this a few days ago, let me restate that I am very interested in having something like this in Boost. IMHO the partition approach is a nice addition to the iterator framework, and fills in the gap by which associative containers have to provide lookup member functions instead of relying on <algorithm>, an ugly breach of genericity. Joaquín M López Muñoz Telefónica, Investigación y Desarrollo
on Tue Nov 18 2008, joaquin-AT-tid.es wrote:
Hello,
I am posting this again with [Iterator] included in the subject. I am still hoping to raise some interest. If it does not work this time, I will give up, I promise.
Some iterator implementations would benefit from special implementations for partition_point-type functions, in particular lower_bound, upper_bound, equal_range and binary_search. Although they are not able to provide random access, if properly implemented, they offer O(log N) lookup. [...] lower_bound, upper_bound, equal_range and binary_search can all be implemented on top of partition_point. So I propose a special base class, partition_point_facade, similar to iterator_facade, which when provided with a member function It::partition_point( It it, Pred pred ), implements the others as free functions. Is
Arno Schödl escribió: there any interest, and possibly willingness to include it into Boost.Iterator?
Although I've commented on this a few days ago, let me restate that I am very interested in having something like this in Boost. IMHO the partition approach is a nice addition to the iterator framework, and fills in the gap by which associative containers have to provide lookup member functions instead of relying on <algorithm>, an ugly breach of genericity.
a. that all sounds very interesting b. I'd like to see more detail c. I probably can't absorb it now, though; I'm buried under a deadline at the moment. -- Dave Abrahams BoostPro Computing http://www.boostpro.com
similar to iterator_facade, which when provided with a member function It::partition_point( It it, Pred pred ), implements the others as free functions. Is there any interest, and possibly willingness to include it into Boost.Iterator?
Although I've commented on this a few days ago, let me restate that I am very interested in having something like this in Boost. IMHO the partition approach is a nice addition to the iterator framework, and fills in the gap by which associative containers have to provide lookup member functions instead of relying on <algorithm>, an ugly breach of genericity.
a. that all sounds very interesting b. I'd like to see more detail c. I probably can't absorb it now, though; I'm buried under a deadline at the moment.
So here is the implementation, as it is running in our production code. As far as I can see, there is no boost::partition_point, so I rolled my own. The code is only half-boostified. Ignore the make_XXX_range functions. BOOST_CUSTOM_PARTITION is currently a macro, because IMO that is the only way to be able to add it to existing iterators. If Boost.Iterator and Boost.MultiIndex are both willing to include it into their iterators, I am happy to make it a base class a la iterator_facade and integrate it into the existing code base. Arno -- Dr. Arno Schoedl · aschoedl@think-cell.com Technical Director think-cell Software GmbH · Invalidenstr. 34 · 10115 Berlin, Germany http://www.think-cell.com · phone +49-30-666473-10 · toll-free (US) +1-800-891-8091 Directors: Dr. Markus Hannebauer, Dr. Arno Schoedl · Amtsgericht Charlottenburg, HRB 85229
Arno Schödl wrote:
So here is the implementation, as it is running in our production code. As far as I can see, there is no boost::partition_point, so I rolled my own. The code is only half-boostified. Ignore the make_XXX_range functions. BOOST_CUSTOM_PARTITION is currently a macro, because IMO that is the only way to be able to add it to existing iterators. If Boost.Iterator and Boost.MultiIndex are both willing to include it into their iterators, I am happy to make it a base class a la iterator_facade and integrate it into the existing code base.
Hi Arno, I've had a look at your code and am a bit puzzled about some details: Your BOOST_CUSTOM_PARTITION macro overloads lower_bound, etc for the iterator type of interest: as far as I can see, this is not necessary since boost::lower_bound could use partition_point through ADL, which is the only customization point we need. To put it more succintly, why can't you just have namespace boost{ template<typename _It,typename Val,typenameBinPred> _It lower_bound(_It itBegin,_It itEnd,const Val &x,BinPred pred){ using namespace boost; return partition_point(itBegin,itEnd,!boost::bind(pred,_1,x)); // ADL used } } and let users overload partition_point when needed? template<typename FilterPred,typename It,typename UnaryPred> filter_iterator<FilterPred,It> partition_point( filter_iterator<FilterPred,It> itBegin, filter_iterator<FilterPred,It> itEnd, UnaryPred pred ){ using namespace boost; return make_filter_iterator( itBegin.predicate(), partition_point( itBegin.base(), itEnd.base(), pred ), itBegin.end() ); } This would't have to use fancy overloading macros or base classes, and it covers all the use cases your current scaffolding does. Joaquín M López Muñoz Telefónica, Investigación y Desarrollo -- View this message in context: http://www.nabble.com/-MultiIndex--STL-algorithm-support-for-multi_index_con... Sent from the Boost - Dev mailing list archive at Nabble.com.
Your BOOST_CUSTOM_PARTITION macro overloads lower_bound, etc for the iterator type of interest: as far as I can see, this is not necessary since boost::lower_bound could use partition_point through ADL, which is the only customization point we need. To put it more succintly, why can't you just have
This would require the user to specify "using boost::lower_bound" if he wants to implement a custom_partition for one of his own iterators outside namespace boost, right? This may lead to ambiguities between std::lower_bound and boost::lower_bound if other non-boost libraries do using std::lower_bound; lowerbound( ... ) // unqualified, the well-intentioned implementor wants to allow ADL The Visual Studio 2008 std library makes such unqualified calls, so it suffers from this ambiguity. I think this is a defect, all calls are supposed to be prefixed. But there may be other 3rd party libraries that contain "using std::lower_bound". Arno -- Dr. Arno Schoedl · aschoedl@think-cell.com Technical Director think-cell Software GmbH · Invalidenstr. 34 · 10115 Berlin, Germany http://www.think-cell.com · phone +49-30-666473-10 · toll-free (US) +1-800-891-8091 Directors: Dr. Markus Hannebauer, Dr. Arno Schoedl · Amtsgericht Charlottenburg, HRB 85229
on Fri Nov 28 2008, Arno Schödl <aschoedl-AT-think-cell.com> wrote:
Your BOOST_CUSTOM_PARTITION macro overloads lower_bound, etc for the iterator type of interest: as far as I can see, this is not necessary since boost::lower_bound could use partition_point through ADL, which is the only customization point we need. To put it more succintly, why can't you just have
This would require the user to specify "using boost::lower_bound" if he wants to implement a custom_partition for one of his own iterators outside namespace boost, right?
Why do you say that a using declaration is needed? What's wrong with calling lower_bound with qualification?
This may lead to ambiguities between std::lower_bound and boost::lower_bound if other non-boost libraries do
using std::lower_bound; lowerbound( ... ) // unqualified, the well-intentioned implementor wants to allow ADL
The Visual Studio 2008 std library makes such unqualified calls, so it suffers from this ambiguity.
I don't see a problem. boost::lower_bound can be implemented inside namespace boost::lower_bound_:: and brought out with a using declaration so there's no ADL conflict. Note also that we have boost/detail/binary_search.hpp, for what it's worth. -- Dave Abrahams BoostPro Computing http://www.boostpro.com
AMDG David Abrahams wrote:
This may lead to ambiguities between std::lower_bound and boost::lower_bound if other non-boost libraries do
using std::lower_bound; lowerbound( ... ) // unqualified, the well-intentioned implementor wants to allow ADL
The Visual Studio 2008 std library makes such unqualified calls, so it suffers from this ambiguity.
I don't see a problem. boost::lower_bound can be implemented inside namespace boost::lower_bound_:: and brought out with a using declaration so there's no ADL conflict.
Didn't we agree that that doesn't work: http://lists.boost.org/Archives/boost/2008/07/140502.php In Christ, Steven Watanabe
on Fri Nov 28 2008, Steven Watanabe <watanabesj-AT-gmail.com> wrote:
AMDG
David Abrahams wrote:
This may lead to ambiguities between std::lower_bound and boost::lower_bound if other non-boost libraries do
using std::lower_bound; lowerbound( ... ) // unqualified, the well-intentioned implementor wants to allow ADL
The Visual Studio 2008 std library makes such unqualified calls, so it suffers from this ambiguity.
I don't see a problem. boost::lower_bound can be implemented inside namespace boost::lower_bound_:: and brought out with a using declaration so there's no ADL conflict.
Didn't we agree that that doesn't work: http://lists.boost.org/Archives/boost/2008/07/140502.php
Umm, right, sorry. Use a using-directive for that. -- Dave Abrahams BoostPro Computing http://www.boostpro.com
This would require the user to specify "using boost::lower_bound" if he wants to implement a custom_partition for one of his own iterators outside namespace boost, right?
Why do you say that a using declaration is needed? What's wrong with calling lower_bound with qualification?
Arguably, to be compatible with code that does not know anything about boost, in the spirit of ADL, the following lower_bound should redirect to partition_point( CustomIt, CustomIt, pred): using std::lower_bound; CustomIt itA, itB; lower_bound( itA, itB ); Do we agree that this is how the client side should work? 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? Arno -- Dr. Arno Schoedl · aschoedl@think-cell.com Technical Director think-cell Software GmbH · Invalidenstr. 34 · 10115 Berlin, Germany http://www.think-cell.com · phone +49-30-666473-10 · toll-free (US) +1-800-891-8091 Directors: Dr. Markus Hannebauer, Dr. Arno Schoedl · Amtsgericht Charlottenburg, HRB 85229
on Sun Nov 30 2008, Arno Schödl <aschoedl-AT-think-cell.com> wrote:
This would require the user to specify "using boost::lower_bound" if he wants to implement a custom_partition for one of his own iterators outside namespace boost, right?
Why do you say that a using declaration is needed? What's wrong with calling lower_bound with qualification?
Arguably, to be compatible with code that does not know anything about boost, in the spirit of ADL, the following lower_bound should redirect to partition_point( CustomIt, CustomIt, pred):
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.
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. -- Dave Abrahams BoostPro Computing http://www.boostpro.com
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?
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. 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. 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. Arno -- Dr. Arno Schoedl · aschoedl@think-cell.com Technical Director think-cell Software GmbH · Invalidenstr. 34 · 10115 Berlin, Germany http://www.think-cell.com · phone +49-30-666473-10 · toll-free (US) +1-800-891-8091 Directors: Dr. Markus Hannebauer, Dr. Arno Schoedl · Amtsgericht Charlottenburg, HRB 85229
on Mon Dec 01 2008, Arno Schödl <aschoedl-AT-think-cell.com> 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.
Agreed. -- Dave Abrahams BoostPro Computing http://www.boostpro.com
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.
CRTP it is.
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."
Hmmm. I see it this way: std::lower_bound has well-defined semantics, and we don't change them. We merely provide an implementation for a particular iterator. If that would be the end of the story, you would probably agree that ADL is the way to go and using std::lower_bound; lowerbound(customIt, customIt, ...); // unqualified is the right way to call the custom lower_bound. Now it happens that for some class of iterators, lower_bound/... can be implemented on top of partition_point. I consider this an implementation detail, which you specify by deriving this iterator from a particular base class. I think the situation is really the same as in Boost.Operators that implements operator+ via operator+=. -- Dr. Arno Schoedl · aschoedl@think-cell.com Technical Director think-cell Software GmbH · Invalidenstr. 34 · 10115 Berlin, Germany http://www.think-cell.com · phone +49-30-666473-10 · toll-free (US) +1-800-891-8091 Directors: Dr. Markus Hannebauer, Dr. Arno Schoedl · Amtsgericht Charlottenburg, HRB 85229
on Mon Dec 01 2008, Arno Schödl <aschoedl-AT-think-cell.com> wrote:
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.
CRTP it is.
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."
Hmmm. I see it this way: std::lower_bound has well-defined semantics, and we don't change them. We merely provide an implementation for a particular iterator.
But we have no way to provide an implementation of std::lower_bound. We can only provide an implementation of lower_bound (unqualified).
If that would be the end of the story, you would probably agree that ADL is the way to go and
using std::lower_bound; lowerbound(customIt, customIt, ...); // unqualified
is the right way to call the custom lower_bound.
Like I said, whether or not that is the right way to go IMO depends largely on whether lower_bound should be considered a fundamental operation akin to swap.
Now it happens that for some class of iterators, lower_bound/... can be implemented on top of partition_point.
Sorry, what is partition_point? Oh, it appears to be essentially std::lower_bound.
I consider this an implementation detail, which you specify by deriving this iterator from a particular base class. I think the situation is really the same as in Boost.Operators that implements operator+ via operator+=.
Unless I'm missing something, I think, in that case, that the fundamental operation is partition_point and not lower_bound or upper_bound. Can't the latter two be implemented in terms of partition_point? -- Dave Abrahams BoostPro Computing http://www.boostpro.com
But we have no way to provide an implementation of std::lower_bound. We can only provide an implementation of lower_bound (unqualified).
I think we should first agree on the fundamental question of how to provide a specialized implementation of any std algorithm. I agree with your scepticism about ADL. But we have to live with the C++ standard we have. The only way I know to implement overloads in bulk is using free friend functions in a base class a la iterator_facade/boost.operator. Free friend functions always live in the same namespace as the class in which they are defined. So to find them, we must invoke ADL. I think the only way to avoid ADL would be macros (yuck!). That said, I have nothing against a wrapper for invoking ADL: namespace boost { template< class ItA, class ItB, class Val > // two-template trick from boost::swap to avoid ambiguities It lower_bound( ItA a, ItB b, Val const& val ) { using std::lower_bound; return lower_bound(a,b,val); }; }; Then people have the choice of using std::lower_bound; lowerbound( ... ); or boost::lower_bound( ... );
Unless I'm missing something, I think, in that case, that the fundamental operation is partition_point and not lower_bound or upper_bound. Can't the latter two be implemented in terms of partition_point?
Yes, lower_bound and upper_bound can always be implemented via partition_point. There are some (albeit a little contrived) cases such as couting_iterator, where lower_bound and upper_bound can be implemented faster ( O(1) ) than partition_point, so to throw out lower_bound/upper_bound altogether and always replace them with a wrapper around partition_point seems very heavy-handed to me. Arno -- Dr. Arno Schoedl · aschoedl@think-cell.com Technical Director think-cell Software GmbH · Invalidenstr. 34 · 10115 Berlin, Germany http://www.think-cell.com · phone +49-30-666473-10 · toll-free (US) +1-800-891-8091 Directors: Dr. Markus Hannebauer, Dr. Arno Schoedl · Amtsgericht Charlottenburg, HRB 85229
on Thu Dec 18 2008, Arno Schödl <aschoedl-AT-think-cell.com> wrote:
But we have no way to provide an implementation of std::lower_bound. We can only provide an implementation of lower_bound (unqualified).
I think we should first agree on the fundamental question of how to provide a specialized implementation of any std algorithm.
Unless std provides the hooks to do so, there is no way -- at least, there is no way without establishing a name for the algorithm that is not "std::" qualified.
I agree with your scepticism about ADL. But we have to live with the C++ standard we have.
Nonetheless there are plenty of techniques available for algorithm customization.
The only way I know to implement overloads in bulk is using free friend functions in a base class a la iterator_facade/boost.operator. Free friend functions always live in the same namespace as the class in which they are defined. So to find them, we must invoke ADL. I think the only way to avoid ADL would be macros (yuck!).
That said, I have nothing against a wrapper for invoking ADL:
namespace boost {
template< class ItA, class ItB, class Val > // two-template trick from boost::swap to avoid ambiguities It lower_bound( ItA a, ItB b, Val const& val ) { using std::lower_bound; return lower_bound(a,b,val); };
};
Then people have the choice of
using std::lower_bound; lowerbound( ... );
or
boost::lower_bound( ... );
One problem I have with the above is that the likelihood of ambiguity is too high, and either technique has the same problem (in the latter case the ambiguity shows up in the Boost implementation).
Unless I'm missing something, I think, in that case, that the fundamental operation is partition_point and not lower_bound or upper_bound. Can't the latter two be implemented in terms of partition_point?
Yes, lower_bound and upper_bound can always be implemented via partition_point.
In that case I don't think lower_bound itself should be considered an ADL hook.
There are some (albeit a little contrived) cases such as couting_iterator, where lower_bound and upper_bound can be implemented faster ( O(1) ) than partition_point,
How so?
so to throw out lower_bound/upper_bound altogether and always replace them with a wrapper around partition_point seems very heavy-handed to me.
Nobody's talking about throwing them out. They make good sense as high-level algorithms. However, I don't believe they should be customized directly. Maybe partition_point should be customized, and exactly how to do that is a possible subject for discussion. -- Dave Abrahams BoostPro Computing http://www.boostpro.com
Yes, lower_bound and upper_bound can always be implemented via partition_point.
In that case I don't think lower_bound itself should be considered an ADL hook.
There are some (albeit a little contrived) cases such as couting_iterator, where lower_bound and upper_bound can be implemented faster ( O(1) ) than partition_point,
How so?
I should have said "for counting_iterator<int> or some other fundamental type", by calculating with the bounds.
so to throw out lower_bound/upper_bound altogether and always replace them with a wrapper around partition_point seems very heavy-handed to me.
Nobody's talking about throwing them out. They make good sense as high-level algorithms. However, I don't believe they should be customized directly. Maybe partition_point should be customized, and exactly how to do that is a possible subject for discussion.
To get a bit more specific, are you suggesting introducing a boost::lower_bound? Do you want it to always forward to boost::partition_point? Or should it by default forward to std::lower_bound, and only be overloaded for those specific iterators for which a custom boost::partition_point is implemented? I think we agree that we must introduce a default boost::partition_point. How should the customization happen there? Via ADL on partition_point, or again via overloading boost::partition_point? Or do you want something else? What specifically?
namespace boost {
template< class ItA, class ItB, class Val > // two-template trick from boost::swap to avoid ambiguities It lower_bound( ItA a, ItB b, Val const& val ) { using std::lower_bound; return lower_bound(a,b,val); };
};
Then people have the choice of
using std::lower_bound; lowerbound( ... );
or
boost::lower_bound( ... );
One problem I have with the above is that the likelihood of ambiguity is too high, and either technique has the same problem (in the latter case the ambiguity shows up in the Boost implementation).
If someone does not use using std::lower_bound; in their code and instead calls the boost::lower_bound wrapper, I only see a risk of ambiguity if existing code has its own lower_bound, a) which has different semantics, so calling our lower_bound found by ADL is wrong. I think the chances for that are pretty remote. Reusing names from std, but giving them different semantics should not have been done in the first place, particularly in large projects where any change is difficult to manage, but which should have code guidelines in place to prevent such name reuse. In small projects, the other function can just be renamed, and the code gets better for it. b) or, the code has overloaded lower_bound for boost iterator types, and thus it is ambiguous which lower_bound is preferred. If the semantics are the same, the reason for the overload was presumably better performance, which we now provide. The extra overload can be removed. Our implementation should be good enough. I think these scenarios are preferable over the problem that another library ("some_lib") supplies iterators and custom lower_bounds for them. Even if some_lib uses ADL to implement their custom lower_bound, how is a user of both boost and some_lib going to invoke the right lower_bound in generic code? With ADL on lower_bound, that would happen automatically. That's why I like ADL so much (among the choices we have with existing C++). Arno -- Dr. Arno Schoedl · aschoedl@think-cell.com Technical Director think-cell Software GmbH · Invalidenstr. 34 · 10115 Berlin, Germany http://www.think-cell.com · phone +49-30-666473-10 · toll-free (US) +1-800-891-8091 Directors: Dr. Markus Hannebauer, Dr. Arno Schoedl · Amtsgericht Charlottenburg, HRB 85229
on Mon Dec 22 2008, Arno Schödl <aschoedl-AT-think-cell.com> wrote:
There are some (albeit a little contrived) cases such as couting_iterator, where lower_bound and upper_bound can be implemented faster ( O(1) ) than partition_point,
How so?
I should have said "for counting_iterator<int> or some other fundamental type", by calculating with the bounds.
Maybe so, but I'm obviously missing something, because I still can't guess what you have in mind.
so to throw out lower_bound/upper_bound altogether and always replace them with a wrapper around partition_point seems very heavy-handed to me.
Nobody's talking about throwing them out. They make good sense as high-level algorithms. However, I don't believe they should be customized directly. Maybe partition_point should be customized, and exactly how to do that is a possible subject for discussion.
To get a bit more specific, are you suggesting introducing a boost::lower_bound? Do you want it to always forward to boost::partition_point? Or should it by default forward to std::lower_bound, and only be overloaded for those specific iterators for which a custom boost::partition_point is implemented?
My current thinking is: boost::lower_bound -> partition_point (via ADL) -> std::lower_bound (by default) Make sense?
I think we agree that we must introduce a default boost::partition_point. How should the customization happen there? Via ADL on partition_point, or again via overloading boost::partition_point?
Inviting users to overload in your namespace is simply not a viable customization approach in general, so ADL is it. -- Dave Abrahams BoostPro Computing http://www.boostpro.com
I should have said "for counting_iterator<int> or some other fundamental type", by calculating with the bounds.
Maybe so, but I'm obviously missing something, because I still can't guess what you have in mind.
counting_iterator<int> lower_bound( counting_iterator<int> begin, counting_iterator<int> end, int n ) { if( n<begin ) return begin; else if( n<end ) return counting_iterator<int>(n); else return end; }
To get a bit more specific, are you suggesting introducing a boost::lower_bound? Do you want it to always forward to boost::partition_point? Or should it by default forward to std::lower_bound, and only be overloaded for those specific iterators for which a custom boost::partition_point is implemented?
My current thinking is: boost::lower_bound -> partition_point (via ADL) -> std::lower_bound (by default) Make sense?
Do you mean this? namespace boost { template< ... > It lower_bound( It begin, It end, T value ) { using boost::partition_point; return partition_point( begin, end, boost::bind( ... ) ); } template< ... > It partition_point( It begin, It end, Pred pred ) { return std::lower_bound( begin, end, boost::bind( ... ) ); } // a custom implementation of partition_point: template< ... > transform_iterator<It,Func> partition_point(transform_iterator<It,Func> begin, transform_iterator<It,Func> end, Pred pred ) { ... } ... more custom implementations ... } Is implementing partition_point by std::lower_bound possible? I remember seeing a paper of yours that pointed out that in template< class It, class T, class Pred ) lower_bound( It begin, It end, T value, Pred pred ) T must be It::value_type. Then, how do you do the forwarding? Instead, I suggest providing our own implementation of partition_point.
I think we agree that we must introduce a default boost::partition_point. How should the customization happen there? Via ADL on partition_point, or again via overloading boost::partition_point?
Inviting users to overload in your namespace is simply not a viable customization approach in general, so ADL is it.
O.k., agreed. Why do you think ADL is o.k. for customizing boost::partition_point (soon std::partition_point, N2666), but not for customizing std::lower_bound? AFAIK, the same arguments apply to both. Arno -- Dr. Arno Schoedl · aschoedl@think-cell.com Technical Director think-cell Software GmbH · Invalidenstr. 34 · 10115 Berlin, Germany http://www.think-cell.com · phone +49-30-666473-10 · toll-free (US) +1-800-891-8091 Directors: Dr. Markus Hannebauer, Dr. Arno Schoedl · Amtsgericht Charlottenburg, HRB 85229
on Wed Dec 24 2008, Arno Schödl <aschoedl-AT-think-cell.com> wrote:
I should have said "for counting_iterator<int> or some other fundamental type", by calculating with the bounds.
Maybe so, but I'm obviously missing something, because I still can't guess what you have in mind.
counting_iterator<int> lower_bound( counting_iterator<int> begin, counting_iterator<int> end, int n ) { if( n<begin ) return begin; else if( n<end ) return counting_iterator<int>(n); else return end; }
OK, yes. It works when the counting iterator is random-access. This is not a very significant optimization, IMO, but I see that it is one nonetheless.
To get a bit more specific, are you suggesting introducing a boost::lower_bound? Do you want it to always forward to boost::partition_point? Or should it by default forward to std::lower_bound, and only be overloaded for those specific iterators for which a custom boost::partition_point is implemented?
My current thinking is: boost::lower_bound -> partition_point (via ADL) -> std::lower_bound (by default) Make sense?
Do you mean this?
namespace boost {
template< ... > It lower_bound( It begin, It end, T value ) { using boost::partition_point; return partition_point( begin, end, boost::bind( ... ) ); }
template< ... > It partition_point( It begin, It end, Pred pred ) { return std::lower_bound( begin, end, boost::bind( ... ) ); }
// a custom implementation of partition_point: template< ... > transform_iterator<It,Func> partition_point(transform_iterator<It,Func> begin, transform_iterator<It,Func> end, Pred pred ) { ... }
Something like that, yes.
... more custom implementations ...
}
Is implementing partition_point by std::lower_bound possible? I remember seeing a paper of yours that pointed out that in
template< class It, class T, class Pred ) lower_bound( It begin, It end, T value, Pred pred )
T must be It::value_type.
That is no longer the case. See http://www.open-std.org/jtc1/sc22/wg21/docs/lwg-defects.html#270 Also, see boost/detail/binary_search.hpp, which was introduced precisely to work around one implementation's strict concept checking.
Then, how do you do the forwarding? Instead, I suggest providing our own implementation of partition_point.
Equivalent.
I think we agree that we must introduce a default boost::partition_point. How should the customization happen there? Via ADL on partition_point, or again via overloading boost::partition_point?
Inviting users to overload in your namespace is simply not a viable customization approach in general, so ADL is it.
O.k., agreed.
Why do you think ADL is o.k. for customizing boost::partition_point (soon std::partition_point, N2666), but not for customizing std::lower_bound? AFAIK, the same arguments apply to both.
Because nobody wants to customize lower_bound, upper_bound, equal_range, and binary_search when they could instead customize partition point alone. -- Dave Abrahams BoostPro Computing http://www.boostpro.com
Do you mean this?
namespace boost {
template< ... > It lower_bound( It begin, It end, T value ) { using boost::partition_point; return partition_point( begin, end, boost::bind( ... ) ); }
template< ... > It partition_point( It begin, It end, Pred pred ) { return std::lower_bound( begin, end, boost::bind( ... ) ); }
// a custom implementation of partition_point: template< ... > transform_iterator<It,Func> partition_point(transform_iterator<It,Func> begin, transform_iterator<It,Func> end, Pred pred ) { ... }
Something like that, yes.
See http://www.open-std.org/jtc1/sc22/wg21/docs/lwg-defects.html#270 Also, see boost/detail/binary_search.hpp, which was introduced precisely to work around one implementation's strict concept checking.
Ok.
Why do you think ADL is o.k. for customizing boost::partition_point (soon std::partition_point, N2666), but not for customizing std::lower_bound? AFAIK, the same arguments apply to both.
Because nobody wants to customize lower_bound, upper_bound, equal_range, and binary_search when they could instead customize partition point alone.
The counting_iterator example above shows that people may want to, for special cases and not inside a library, but as an optimization for their special iterator implementation. It feels funny to me to use different techniques for different functions. And you pay the overhead of boost::bind for any call to lower_bound, customized or not. I am willing to do it, though, if that's what you prefer. Arno -- Dr. Arno Schoedl · aschoedl@think-cell.com Technical Director think-cell Software GmbH · Invalidenstr. 34 · 10115 Berlin, Germany http://www.think-cell.com · phone +49-30-666473-10 · toll-free (US) +1-800-891-8091 Directors: Dr. Markus Hannebauer, Dr. Arno Schoedl · Amtsgericht Charlottenburg, HRB 85229
on Thu Dec 25 2008, Arno Schödl <aschoedl-AT-think-cell.com> wrote:
Do you mean this?
namespace boost {
template< ... > It lower_bound( It begin, It end, T value ) { using boost::partition_point; return partition_point( begin, end, boost::bind( ... ) ); }
template< ... > It partition_point( It begin, It end, Pred pred ) { return std::lower_bound( begin, end, boost::bind( ... ) ); }
// a custom implementation of partition_point: template< ... > transform_iterator<It,Func> partition_point(transform_iterator<It,Func> begin, transform_iterator<It,Func> end, Pred pred ) { ... }
Something like that, yes.
Please make an effort to use proper quoting. Thanks.
Why do you think ADL is o.k. for customizing boost::partition_point (soon std::partition_point, N2666), but not for customizing std::lower_bound? AFAIK, the same arguments apply to both.
Because nobody wants to customize lower_bound, upper_bound, equal_range, and binary_search when they could instead customize partition point alone.
The counting_iterator example above shows that people may want to, for special cases and not inside a library, but as an optimization for their special iterator implementation. It feels funny to me to use different techniques for different functions. And you pay the overhead of boost::bind for any call to lower_bound, customized or not. I am willing to do it, though, if that's what you prefer.
You don't have to use boost::bind. Just use the standard binders. Furthermore, if you publish the type of the function object used, people can still customize all of those individual variants if they're crazy enough to want to do that. -- Dave Abrahams BoostPro Computing http://www.boostpro.com
The counting_iterator example above shows that people may want to, for special cases and not inside a library, but as an optimization for their special iterator implementation. It feels funny to me to use different techniques for different functions. And you pay the overhead of boost::bind for any call to lower_bound, customized or not. I am willing to do it, though, if that's what you prefer.
You don't have to use boost::bind. Just use the standard binders.
Are they preferable over boost/std::bind if the extra functionality of more general boost/std::bind is not needed? I think one of my functors worked with boost::bind, but didn't with std::bind1st/2nd. Maybe some typedef was missing? I have to look.
Furthermore, if you publish the type of the function object used, people can still customize all of those individual variants if they're crazy enough to want to do that.
I don't understand what you mean.
where partition_point is a fundamental operation similar to swap,
Yes
and lower_bound/... implementations must invoke ADL for partition_point, just like C++0x requires it for swap.
Yes
As a start, we are now adding such a lower_bound/... into boost. Is that your thinking?
Sorta.
O.k., I am happy we finally have agreement:-) I will send out the new version. Do you want to include it into Boost.Iterator (my preference), or as a separate library? Arno -- Dr. Arno Schoedl · aschoedl@think-cell.com Technical Director think-cell Software GmbH · Invalidenstr. 34 · 10115 Berlin, Germany http://www.think-cell.com · phone +49-30-666473-10 · toll-free (US) +1-800-891-8091 Directors: Dr. Markus Hannebauer, Dr. Arno Schoedl · Amtsgericht Charlottenburg, HRB 85229
on Fri Dec 26 2008, Arno Schödl <aschoedl-AT-think-cell.com> wrote:
The counting_iterator example above shows that people may want to, for special cases and not inside a library, but as an optimization for their special iterator implementation. It feels funny to me to use different techniques for different functions. And you pay the overhead of boost::bind for any call to lower_bound, customized or not. I am willing to do it, though, if that's what you prefer.
You don't have to use boost::bind. Just use the standard binders.
Are they preferable over boost/std::bind if the extra functionality of more general boost/std::bind is not needed?
If you don't want to pay the compilation overhead of boost::bind, then yes. ?? You're the one who brought that up.
I think one of my functors worked with boost::bind, but didn't with std::bind1st/2nd. Maybe some typedef was missing? I have to look.
Furthermore, if you publish the type of the function object used, people can still customize all of those individual variants if they're crazy enough to want to do that.
I don't understand what you mean.
The customizer simply writes a partition_point overload where the function object type is specific, e.g. something like binder2nd<std::less<T>, T> (I forget the real signatures)
O.k., I am happy we finally have agreement:-) I will send out the new version. Do you want to include it into Boost.Iterator (my preference), or as a separate library?
I'm sorry, but what component(s) are you proposing should be included into Boost.Iterator? Not the default partition_point, boost::lower_bound, et. al.? -- Dave Abrahams BoostPro Computing http://www.boostpro.com
Furthermore, if you publish the type of the function object used, people can still customize all of those individual variants if they're crazy enough to want to do that.
I don't understand what you mean.
The customizer simply writes a partition_point overload where the function object type is specific, e.g. something like binder2nd<std::less<T>, T> (I forget the real signatures)
Ah, ok. We may want to turn the bind function objects into C++0x lambdas later. I am not sure you can overload on lambda types.
O.k., I am happy we finally have agreement:-) I will send out the new version. Do you want to include it into Boost.Iterator (my preference), or as a separate library?
I'm sorry, but what component(s) are you proposing should be included into Boost.Iterator? Not the default partition_point, boost::lower_bound, et. al.?
Yes, that was the idea, to have all tools to implement a new iterator in one place. If you don't like that, how do you want to do it? Separate library "partition_point" with - algorithms.hpp for default partition_point and lower_bound et. al., and - transform_iterator.hpp - ... for the various partition_point overloads? Or only have the default implementation in a separate library and implement the partition_point overloads in Boost.Iterator/Boost.MultiIndexContainer's iterator-specific header files, such as transform_iterator.hpp? Arno -- Dr. Arno Schoedl · aschoedl@think-cell.com Technical Director think-cell Software GmbH · Invalidenstr. 34 · 10115 Berlin, Germany http://www.think-cell.com · phone +49-30-666473-10 · toll-free (US) +1-800-891-8091 Directors: Dr. Markus Hannebauer, Dr. Arno Schoedl · Amtsgericht Charlottenburg, HRB 85229
on Sat Dec 27 2008, Arno Schödl <aschoedl-AT-think-cell.com> wrote:
Furthermore, if you publish the type of the function object used, people can still customize all of those individual variants if they're crazy enough to want to do that.
I don't understand what you mean.
The customizer simply writes a partition_point overload where the function object type is specific, e.g. something like binder2nd<std::less<T>, T> (I forget the real signatures)
Ah, ok. We may want to turn the bind function objects into C++0x lambdas later. I am not sure you can overload on lambda types.
O.k., I am happy we finally have agreement:-) I will send out the new version. Do you want to include it into Boost.Iterator (my preference), or as a separate library?
I'm sorry, but what component(s) are you proposing should be included into Boost.Iterator? Not the default partition_point, boost::lower_bound, et. al.?
Yes, that was the idea, to have all tools to implement a new iterator in one place.
You *generally* don't need to customize partition_point in order to implement a new iterator.
If you don't like that, how do you want to do it? Separate library "partition_point" with
- algorithms.hpp for default partition_point and lower_bound et. al.,
and
- transform_iterator.hpp - ...
for the various partition_point overloads?
Something like that seems likely. I'm still having trouble understanding how you can implement a specialization for transform_iterator without knowing more than actually possible about the semantics of the transformation function.
Or only have the default implementation in a separate library and implement the partition_point overloads in Boost.Iterator/Boost.MultiIndexContainer's iterator-specific header files, such as transform_iterator.hpp?
I'm getting confused, sorry. -- Dave Abrahams BoostPro Computing http://www.boostpro.com
AMDG David Abrahams wrote:
- transform_iterator.hpp - ...
for the various partition_point overloads?
Something like that seems likely. I'm still having trouble understanding how you can implement a specialization for transform_iterator without knowing more than actually possible about the semantics of the transformation function.
I think the idea is that if an optimized partition_point exists for the underlying iterator, the partition_point specialization for transform_iterator should use it. This has nothing to do with the specific transformation function. In Christ, Steven Watanabe
on Sat Dec 27 2008, Steven Watanabe <watanabesj-AT-gmail.com> wrote:
AMDG
David Abrahams wrote:
- transform_iterator.hpp - ...
for the various partition_point overloads?
Something like that seems likely. I'm still having trouble understanding how you can implement a specialization for transform_iterator without knowing more than actually possible about the semantics of the transformation function.
I think the idea is that if an optimized partition_point exists for the underlying iterator, the partition_point specialization for transform_iterator should use it. This has nothing to do with the specific transformation function.
Sorry, I still don't get it. Here's the declaration of partition_point as given by www.open-std.org/jtc1/sc22/wg21/docs/papers/2008/n2666.pdf: template <class ForwardIterator, class Predicate> ForwardIterator partition_point( ForwardIterator first, ForwardIterator last, Predicate pred); Let's say ForwardIterator is a transform_iterator whose transformation function is f(x) => x >= 5 ? 1 : 0 and the underlying sequence is 0 1 2 3 4 5 6 7 8 9 so the transformed sequence is 0 0 0 0 0 1 1 1 1 1 and pred is p(x) => x < 1 How will the specialization of partition_point for transform_iterator come up with a predicate to pass on to the partition_point that applies to the underlying iterator type? In general, it can't reverse engineer the transformation function and figure out how to get from p(x) above to p'(y) => y < 5 can it? -- Dave Abrahams BoostPro Computing http://www.boostpro.com
Argh. There is a problem with implementing boost::lower_bound/upper_bound. The Dinkumware std library as in MSVC 9 makes unqualified calls to lower_bound/upper_bound in their implementation of equal_range, probably with the intent of letting people ADL-overload them. I read somewhere that this is now considered a defect. The fix in boost::swap for this problem is equivalent to defining boost::lower_bound as template< class It, class ItR /*extra template*/, class Val > It lower_bound(It itBegin,ItR itEnd,Val const& x); The extra template parameter ensures that std::lower_bound is preferred over the then-weaker boost::lower_bound, avoiding ambiguity. But at the same time, IMO it would be nice to have range implementations of boost::lower_bound et. al., which among others have the signature template<class Rng, class Val, class BinPred> typename boost::range_iterator<const Rng>::type lower_bound(Rng const& rng,Val const& x,BinPred pred); creating ambiguity. Without the fix for Dinkumware, there is no ambiguity, because when the iterator implementation is invoked, both iterators have the same type, so the iterator implementation is preferred. IMO, it is pretty safe to assume that for calls with range, Rng and Val won't have the same type. I see the following solutions: a) different name for lower_bound(range). For good reason, Boost.RangeEx already named all range algorithms like their iterator counterparts, which is intuitive. I would hate to make an exception for lower_bound. b) forgo boost::lower_bound/upper_bound and ADL-overload std::lower_bound/upper_bound. Pretty big design change as well, would basically go back to partition_point_facade to provide bulk ADL overloads. c) put boost::lower_bound into a different namespace to shield it from ADL d) Hope that nobody mixes MSVC std::equal_range with boost partition_point algorithms. e) make Dinkumware fix their library:-) I think c) is the least-bad option. Any more ideas/opinions? Arno -- Dr. Arno Schoedl · aschoedl@think-cell.com Technical Director think-cell Software GmbH · Invalidenstr. 34 · 10115 Berlin, Germany http://www.think-cell.com · phone +49-30-666473-10 · toll-free (US) +1-800-891-8091 Directors: Dr. Markus Hannebauer, Dr. Arno Schoedl · Amtsgericht Charlottenburg, HRB 85229
on Tue Dec 30 2008, Arno Schödl <aschoedl-AT-think-cell.com> wrote:
Argh. There is a problem with implementing boost::lower_bound/upper_bound. The Dinkumware std library as in MSVC 9 makes unqualified calls to lower_bound/upper_bound in their implementation of equal_range, probably with the intent of letting people ADL-overload them. I read somewhere that this is now considered a defect.
And has been so for a long time. I think it's been fixed in Dinkumware's official release for a long time, too.
The fix in boost::swap for this problem is equivalent to defining boost::lower_bound as
template< class It, class ItR /*extra template*/, class Val > It lower_bound(It itBegin,ItR itEnd,Val const& x);
The extra template parameter ensures that std::lower_bound is preferred over the then-weaker boost::lower_bound, avoiding ambiguity. But at the same time, IMO it would be nice to have range implementations of boost::lower_bound et. al., which among others have the signature
template<class Rng, class Val, class BinPred> typename boost::range_iterator<const Rng>::type lower_bound(Rng const& rng,Val const& x,BinPred pred);
creating ambiguity.
Without the fix for Dinkumware, there is no ambiguity, because when the iterator implementation is invoked, both iterators have the same type, so the iterator implementation is preferred. IMO, it is pretty safe to assume that for calls with range, Rng and Val won't have the same type.
I see the following solutions:
a) different name for lower_bound(range). For good reason, Boost.RangeEx already named all range algorithms like their iterator counterparts, which is intuitive. I would hate to make an exception for lower_bound. b) forgo boost::lower_bound/upper_bound and ADL-overload std::lower_bound/upper_bound. Pretty big design change as well, would basically go back to partition_point_facade to provide bulk ADL overloads. c) put boost::lower_bound into a different namespace to shield it from ADL d) Hope that nobody mixes MSVC std::equal_range with boost partition_point algorithms. e) make Dinkumware fix their library:-)
f) "make" Microsoft ship the latest Dinkumware code, or even something reasonably recent.
I think c) is the least-bad option. Any more ideas/opinions?
Agree. You can make it look like it's in boost:: with a using-directive. -- Dave Abrahams BoostPro Computing http://www.boostpro.com
I think c) is the least-bad option. Any more ideas/opinions?
Agree. You can make it look like it's in boost:: with a using-directive.
Do you mean namespace boost { using ::boost_partition_algorithms_adl_barrier::lower_bound; using ::boost_partition_algorithms_adl_barrier::upper_bound; using ::boost_partition_algorithms_adl_barrier::binary_search; using ::boost_partition_algorithms_adl_barrier::equal_range; } // namespace boost That does not work for me, and neither if the namespace is nested boost::partition_algorithms_adl_barrier. Without the using directives, all is good. With them, lower_bound is again found from inside std via ADL (on a multi_index iterator that is defined in boost namespace). If that does not work, I could implement an additional lower_bound_ (with trailing underscore), and do not implement lower_bound for broken std libraries. Pretty ugly as well. Arno -- Dr. Arno Schoedl · aschoedl@think-cell.com Technical Director think-cell Software GmbH · Invalidenstr. 34 · 10115 Berlin, Germany http://www.think-cell.com · phone +49-30-666473-10 · toll-free (US) +1-800-891-8091 Directors: Dr. Markus Hannebauer, Dr. Arno Schoedl · Amtsgericht Charlottenburg, HRB 85229
On Wed, 31 Dec 2008 10:42:43 +0100, Arno Schödl <aschoedl@think-cell.com> wrote:
I think c) is the least-bad option. Any more ideas/opinions?
Agree. You can make it look like it's in boost:: with a using-directive. ^^^^^^^^^
Do you mean
namespace boost {
using ::boost_partition_algorithms_adl_barrier::lower_bound; using ::boost_partition_algorithms_adl_barrier::upper_bound; using ::boost_partition_algorithms_adl_barrier::binary_search; using ::boost_partition_algorithms_adl_barrier::equal_range;
} // namespace boost
Those are using-declarations. Different beast. -- David Abrahams Boostpro Computing http://www.boostpro.com
Agree. You can make it look like it's in boost:: with a using-directive. ^^^^^^^^^
It works, thank you for teaching me C++! I found this in http://svn.boost.org/svn/boost/sandbox/swap/boost/utility/swap.hpp: namespace boost { namespace swap_adl_barrier { template<class T> void swap(T& left, T& right) { ::boost_swap_impl::swap_impl(left, right); } } using swap_adl_barrier::swap; } Wrong as well? Arno -- Dr. Arno Schoedl · aschoedl@think-cell.com Technical Director think-cell Software GmbH · Invalidenstr. 34 · 10115 Berlin, Germany http://www.think-cell.com · phone +49-30-666473-10 · toll-free (US) +1-800-891-8091 Directors: Dr. Markus Hannebauer, Dr. Arno Schoedl · Amtsgericht Charlottenburg, HRB 85229
What’s wrong? The file simply doesn't exist. I am using Visual Studio 9.0.30729.1 SP and Boost 1.37.0. Everything but posix_time.hpp works.
Jiri Pik wrote:
What’s wrong? The file simply doesn't exist. I am using Visual Studio 9.0.30729.1 SP and Boost 1.37.0. Everything but posix_time.hpp works.
Two questions: * Did you build the date-time library with VC9? * Did you build using the bjam --build-type=complete option? HTH, John.
John - thanks for your kind response. Yes, I did use the supplied script for building the library. I believe it used "bjam --build-type=complete option". I am just escalating this if somebody has the same problem with 1.37, or if it's an isolated issue. I downgraded to 1.36 and no problem. All the best. -----Original Message----- From: boost-bounces@lists.boost.org [mailto:boost-bounces@lists.boost.org] On Behalf Of John Maddock Sent: 31 December 2008 12:44 To: boost@lists.boost.org Subject: Re: [boost] #include <boost/date_time/posix_time/posix_time.hpp> -fatal error LNK1104: cannot open file'libboost_date_time-vc90-mt-gd-1_37.lib' Jiri Pik wrote:
What’s wrong? The file simply doesn't exist. I am using Visual Studio 9.0.30729.1 SP and Boost 1.37.0. Everything but posix_time.hpp works.
Two questions: * Did you build the date-time library with VC9? * Did you build using the bjam --build-type=complete option? HTH, John. _______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
I downgraded to 1.36 and it works. Thanks. -----Original Message----- From: Jiri Pik [mailto:cplusplus@jiripik.com] Sent: 31 December 2008 10:57 To: 'boost@lists.boost.org' Subject: #include <boost/date_time/posix_time/posix_time.hpp> - fatal error LNK1104: cannot open file 'libboost_date_time-vc90-mt-gd-1_37.lib' What’s wrong? The file simply doesn't exist. I am using Visual Studio 9.0.30729.1 SP and Boost 1.37.0. Everything but posix_time.hpp works.
I'm still having trouble understanding how you can implement a specialization for transform_iterator without knowing more than actually possible about the semantics of the transformation function.
Am I missing something? namespace boost { template< typename UnaryFunction, typename It, typename UnaryPred > transform_iterator<UnaryFunction, It> partition_point( transform_iterator<UnaryFunction, It> itBegin, transform_iterator<UnaryFunction, It> itEnd, UnaryPred pred ) { using boost::partition_point; return make_transform_iterator( partition_point( itBegin.base(), itEnd.base(), bind( pred, boost::bind( itBegin.functor(), _1 ) ) ), itBegin.functor() ); } }; /* namespace */
Or only have the default implementation in a separate library and implement the partition_point overloads in Boost.Iterator/Boost.MultiIndexContainer's iterator-specific header files, such as transform_iterator.hpp?
I'm getting confused, sorry.
You a) either implement all custom partition_points together in a library, or b) only put the infrastructure for such custom partition_points into a library and put the iterator-specific custom partition-points close to the respective iterator implementations. Arno -- Dr. Arno Schoedl · aschoedl@think-cell.com Technical Director think-cell Software GmbH · Invalidenstr. 34 · 10115 Berlin, Germany http://www.think-cell.com · phone +49-30-666473-10 · toll-free (US) +1-800-891-8091 Directors: Dr. Markus Hannebauer, Dr. Arno Schoedl · Amtsgericht Charlottenburg, HRB 85229
on Sun Dec 28 2008, Arno Schödl <aschoedl-AT-think-cell.com> wrote:
I'm still having trouble understanding how you can implement a specialization for transform_iterator without knowing more than actually possible about the semantics of the transformation function.
Am I missing something?
namespace boost {
template< typename UnaryFunction, typename It, typename UnaryPred > transform_iterator<UnaryFunction, It> partition_point( transform_iterator<UnaryFunction, It> itBegin, transform_iterator<UnaryFunction, It> itEnd, UnaryPred pred ) { using boost::partition_point; return make_transform_iterator( partition_point( itBegin.base(), itEnd.base(), bind( pred, boost::bind( itBegin.functor(), _1 ) ) ), itBegin.functor() ); }
}; /* namespace */
OK, but for which iterator can we implement an optimized partition_point that works for arbitrary predicates? I thought the point of "specializing" partition_point was to be able to do something smart with iterators over sorted values (e.g. something like std::set iterators)
Or only have the default implementation in a separate library and implement the partition_point overloads in Boost.Iterator/Boost.MultiIndexContainer's iterator-specific header files, such as transform_iterator.hpp?
I'm getting confused, sorry.
You a) either implement all custom partition_points together in a library, or b) only put the infrastructure for such custom partition_points into a library and put the iterator-specific custom partition-points close to the respective iterator implementations.
b). -- Dave Abrahams BoostPro Computing http://www.boostpro.com
OK, but for which iterator can we implement an optimized partition_point that works for arbitrary predicates? I thought the point of "specializing" partition_point was to be able to do something smart with iterators over sorted values (e.g. something like std::set iterators)
partition_point performance improves from O(N) to O(log N) for - Boost.MultiIndex ordered index iterators (by exploiting the red-black tree), and - filter_iterator based on any random-access iterator (by exploiting the random-access property of the unfiltered range). transform_iterator, indirect_iterator, reverse_iterator, and shared_container_iterator partition_points can be implemented such that any performance gain of the underlying iterator's partition_point is preserved. std library implementors could write a fast partition_point for std::set/multiset iterators, but this requires implementation knowledge, so we cannot do it in boost. Arno -- Dr. Arno Schoedl · aschoedl@think-cell.com Technical Director think-cell Software GmbH · Invalidenstr. 34 · 10115 Berlin, Germany http://www.think-cell.com · phone +49-30-666473-10 · toll-free (US) +1-800-891-8091 Directors: Dr. Markus Hannebauer, Dr. Arno Schoedl · Amtsgericht Charlottenburg, HRB 85229
on Mon Dec 29 2008, Arno Schödl <aschoedl-AT-think-cell.com> wrote:
OK, but for which iterator can we implement an optimized partition_point that works for arbitrary predicates? I thought the point of "specializing" partition_point was to be able to do something smart with iterators over sorted values (e.g. something like std::set iterators)
partition_point performance improves from O(N) to O(log N) for
- Boost.MultiIndex ordered index iterators (by exploiting the red-black tree),
OK, I see it now. Sorry for being dense. The predicate is required to partition the range, so it can work. -- Dave Abrahams BoostPro Computing http://www.boostpro.com
Inviting users to overload in your namespace is simply not a viable customization approach in general, so ADL is it.
O.k., agreed.
Why do you think ADL is o.k. for customizing boost::partition_point (soon std::partition_point, N2666), but not for customizing std::lower_bound? AFAIK, the same arguments apply to both.
Because nobody wants to customize lower_bound, upper_bound, equal_range, and binary_search when they could instead customize partition point alone.
I thought about what you are really after. You are probably envisioning future standardization, where partition_point is a fundamental operation similar to swap, and lower_bound/... implementations must invoke ADL for partition_point, just like C++0x requires it for swap. As a start, we are now adding such a lower_bound/... into boost. Is that your thinking? Arno -- Dr. Arno Schoedl · aschoedl@think-cell.com Technical Director think-cell Software GmbH · Invalidenstr. 34 · 10115 Berlin, Germany http://www.think-cell.com · phone +49-30-666473-10 · toll-free (US) +1-800-891-8091 Directors: Dr. Markus Hannebauer, Dr. Arno Schoedl · Amtsgericht Charlottenburg, HRB 85229
on Thu Dec 25 2008, Arno Schödl <aschoedl-AT-think-cell.com> wrote:
Inviting users to overload in your namespace is simply not a viable customization approach in general, so ADL is it.
O.k., agreed.
Why do you think ADL is o.k. for customizing boost::partition_point (soon std::partition_point, N2666), but not for customizing std::lower_bound? AFAIK, the same arguments apply to both.
Because nobody wants to customize lower_bound, upper_bound, equal_range, and binary_search when they could instead customize partition point alone.
I thought about what you are really after. You are probably envisioning future standardization,
I wasn't thinking about standardization.
where partition_point is a fundamental operation similar to swap,
Yes
and lower_bound/... implementations must invoke ADL for partition_point, just like C++0x requires it for swap.
Yes
As a start, we are now adding such a lower_bound/... into boost. Is that your thinking?
Sorta. -- Dave Abrahams BoostPro Computing http://www.boostpro.com
Here is the CRTP implementation. I commented some design decisions. Dave, do you still have reservations about the approach? Otherwise I could start implementing some partition_point_ methods in Boost.Iterator and Boost.MultiIndex and send you the patches. On top of http://svn.boost.org/svn/boost/trunk? Arno -- Dr. Arno Schoedl · aschoedl@think-cell.com Technical Director think-cell Software GmbH · Invalidenstr. 34 · 10115 Berlin, Germany http://www.think-cell.com · phone +49-30-666473-10 · toll-free (US) +1-800-891-8091 Directors: Dr. Markus Hannebauer, Dr. Arno Schoedl · Amtsgericht Charlottenburg, HRB 85229
on Thu Nov 27 2008, Joaquin M Lopez Munoz <joaquin-AT-tid.es> wrote:
why can't you just have
namespace boost{
template<typename _It,typename Val,typenameBinPred> _It lower_bound(_It itBegin,_It itEnd,const Val &x,BinPred pred){ using namespace boost; return partition_point(itBegin,itEnd,!boost::bind(pred,_1,x)); // ADL used }
}
One reason is that the above uses identifiers reserved to the implementation. ;-) -- Dave Abrahams BoostPro Computing http://www.boostpro.com
participants (7)
-
Arno Schödl -
David Abrahams -
Jiri Pik -
Joaquin M Lopez Munoz -
joaquin＠tid.es
-
John Maddock -
Steven Watanabe