Boost logo

Boost :

Subject: Re: [boost] Boost.Algorithm design question
From: lcaminiti (lorcaminiti_at_[hidden])
Date: 2011-10-06 09:51:57

Dave Abrahams wrote:
> on Wed Oct 05 2011, "Stephan T. Lavavej" <>
> 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?


View this message in context:
Sent from the Boost - Dev mailing list archive at

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