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. -- Dave Abrahams BoostPro Computing http://www.boostpro.com