Re: [boost] Boost.Algorithm design question

Subject: Re: [boost] Boost.Algorithm design question
From: Stephan T. Lavavej (stl_at_[hidden])
Date: 2011-10-05 18:53:27

[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.

Consider vector<string> and val being "meow". string is directly comparable to const char *, without any conversions or temporaries.

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.

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. std::map still doesn't, and users complain about it from time to time.

STL