Dave Abrahams wrote:
on Wed Oct 05 2011, "Stephan T. Lavavej" <stl-AT-exchange.microsoft.com> wrote:
[Marshall Clow]
So, what do people prefer (and why?):
template<typename InputIterator, typename V> bool none_of_equal ( InputIterator first, InputIterator last, V const &val )
or
template<typename InputIterator, > bool none_of_equal ( InputIterator first, InputIterator last, iterator_traits<InputIterator>::value_type const &val )
In the first case, I think there's (possible) conversion from V to iterator_traits<InputIterator>::value_type each time through the loop. In the second case, there is not.
#1 is better. It follows the STL's conventions (e.g. look at std::find()) and permits heterogeneous comparisons.
Sorry, STL. The other STL's conventions are wrong. :-)
Consider vector<string> and val being "meow". string is directly comparable to const char *, without any conversions or temporaries.
You got lucky this time.
Even better, consider vector<const char *> and val being a string. Here, the element type is still directly comparable to val's type, but val's type is not implicitly convertible to the element type.
That's cute. IMO the principled thing to do in that case is to use the version that takes the additional predicate.
It is true that #1 can result in O(N) conversions, but that's really up to the element/value types involved. Typically, whenever the value type is implicitly convertible to the element type, and the element type is comparable with itself, a direct comparison between the two types could also be provided (as is the case with const char * and string), and will be provided when performance is important.
Heterogeneous comparisons are surprisingly popular, and the STL is moving to support them better. For example, std::lower_bound() didn't support them in C++03, and does in C++11.
/me realizes he is responsible for this change
But that's *totally* different.
/me fumbles around for the explanation
For the version that uses "<", it's an unintentional side-effect of making the specification uniform. The function signature already took an unconstrained object by reference, and my paper was not trying to change that. It just happened to make the /semantics/ of using a type different from the value type of the sequence meaningful in that case. It also make the specification *simpler* overall and easier to understand.
The _purpose_ was to support heterogeneity for the version that uses a function. The description in terms of partitioning is a more principled and generic way to describe the actual requirements of the algorithm. There was never any intention to promote the use of heterogeneous "<", which again, doesn't make sense.
From the standard:
// 25.2, non-modifying sequence operations: template <class InputIterator, class Predicate> bool none_of(InputIterator first, InputIterator last, Predicate pred); template<class InputIterator, class T> InputIterator find(InputIterator first, InputIterator last, const T& value); Given that I am used to how the STL works, at first I'd expect Boost.Algorithm to follow the same interface where it makes sense-- why would none_of_equal use an interface different from std::find? Now, if truly the STL interface is incorrect and Boost.Algorithm needs to use iterator_traits::value, wouldn't it make sense to also change the STL interface in the C++ standard? I think what I am trying to ask is: Does anyone know why std::find does not use use iterator_traits::value? BTW, I find none_equal /any_equal / all_equal / one_equal more readable than none_of_equal / any_of_equal / all_of_equal / one_of_equal. I'd keep the "of" postfix only for the predicate versions as the STL does (and similarly to find_if). What do you think? Thanks, --Lorenzo -- View this message in context: http://boost.2283326.n4.nabble.com/Boost-Algorithm-design-question-tp3876424... Sent from the Boost - Dev mailing list archive at Nabble.com.