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" <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-tp3876424p3878340.html
Sent from the Boost - Dev mailing list archive at Nabble.com.

Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk