[Second try after 24 hours]

On 2011-03-09 15:10, Olaf Krzikalla wrote:
>
> Hi,
>
> I have trouble figuring out the exact requirements imposed to the
> predicate of std:::upper_bound (and similar function) in the case of
> mixed types. The function in question is in 25.0.0.1 (c++ 2003):
>
> template<class ForwardIterator, class T, class Compare>
> ForwardIterator upper_bound(ForwardIterator first, ForwardIterator last,
> const T& value, Compare comp);
>
> 25.0.0.8 describes requirements on a BinaryPredicate (which appears in
> 25.0.0.1 at different places), but requirements on Compare are nowhere
> specified (at least I couldn't find anything). If Compare should be
> treated equal to BinaryPredicate then it should be probably renamed.

Both are related but not the same. In C++03 you find Compare to be
defined in 25.3 [lib.alg.sorting] p. 1-3:

"1 All the operations in 25.3 have two versions: one that takes a
function object of type Compare and one that uses an operator<.

2 Compare is used as a function object which returns true if the first
argument is less than the second, and false otherwise. Compare comp is
used throughout for algorithms assuming an ordering relation. It is
assumed that comp will not apply any non-constant function through the
dereferenced iterator.

3 For all algorithms that take Compare, there is a version that uses
operator< instead. That is, comp(*i, *j) != false defaults to *i < *j
!= false. For the algorithms to work correctly, comp has to induce a
strict weak ordering on the values."

The further text explains what a strict weak ordering is and in which
sense the term "equivalent" is understood.

Thus, a type satisfying the Compare requirements is a refinement of a
BinaryPredicate, because the latter is not required to induce special
orderings.

C++0x has clarified the situation somewhat: Now it's clearer, that any
Compare object must be a function object type. Further more cleanup
has been done such that it is clear now that upper_bound does not
unconditionally require that the value type meets the
LessThanComparable requirements.

But I think the most relevant fix that happened in C++0x is that p. 3
has changed the last sentence to (emphasis mine):

"**For algorithms other than those described in 25.4.3 to work
correctly,** comp has to induce a strict weak ordering on the values."

which was an outcome of the library issue

http://www.open-std.org/jtc1/sc22/wg21/docs/lwg-defects.html#270

A consequence of the strict weak ordering requirements is that both
comp(a, b) and comp(b, a) need to be defined, which is the circle to
your problem.

> Otherwise a clarification seems to be needed.
> The practical background:
>
> class CompareClass
> {
> // this one is needed anyway:
> bool operator()(ForwardIterator::value_type, T) const;
>
> // according to 25.0.0.8 this one is not needed
> // MSVC insist on its existence, the std is unclear though:
> bool operator()(T, ForwardIterator::value_type) const;
>
> // oops: MSVC 9 (not 10!) in debug mode needs this too:
> bool operator()(ForwardIterator::value_type,
> ForwardIterator::value_type) const;
> };

MSVC 9 seems to take advantage of what C++03 allowed, namely to assume
that Compare induces a strict weak ordering, which again implies that
symmetric calls are indirectly part of the requirements, meaning you
need to provide all three combinations:

bool operator()(ForwardIterator::value_type, T) const;
bool operator()(T, ForwardIterator::value_type) const;
bool operator()(ForwardIterator::value_type, ForwardIterator::value_type) const;

In C++0x this restriction has been lifted and that seems to have been
reflected in MSVC 10: We have now an algorithm-specified requirement:

"The elements e of [first,last) shall be partitioned with respect to
the expression !(value < e) or !comp(value, e)."

In combination with the effects of upper_bound it is now sufficient
for the Compare object to be callable with the single signature

bool operator()(T, ForwardIterator::value_type) const;

in your example.

HTH & Greetings from Bremen,

Daniel Kr   gler


--
[ comp.std.c++ is moderated.  To submit articles, try posting with your ]
[ newsreader.  If that fails, use mailto:std-cpp-submit@vandevoorde.com ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.comeaucomputing.com/csc/faq.html                      ]

Hi,

I have trouble figuring out the exact requirements imposed to the
predicate of std:::upper_bound (and similar function) in the case of
mixed types. The function in question is in 25.0.0.1 (c++ 2003):

template<class ForwardIterator, class T, class Compare>
ForwardIterator upper_bound(ForwardIterator first, ForwardIterator last,
                           const T& value, Compare comp);

25.0.0.8 describes requirements on a BinaryPredicate (which appears in
25.0.0.1 at different places), but requirements on Compare are nowhere
specified (at least I couldn't find anything). If Compare should be
treated equal to BinaryPredicate then it should be probably renamed.
Otherwise a clarification seems to be needed.
The practical background:

class CompareClass
{
 // this one is needed anyway:
 bool operator()(ForwardIterator::value_type, T) const;

 // according to 25.0.0.8 this one is not needed
 // MSVC insist on its existence, the std is unclear though:
 bool operator()(T, ForwardIterator::value_type) const;

 // oops: MSVC 9 (not 10!) in debug mode needs this too:
 bool operator()(ForwardIterator::value_type,
                 ForwardIterator::value_type) const;
};


Best regards
Olaf Krzikalla


--
[ comp.std.c++ is moderated.  To submit articles, try posting with your ]
[ newsreader.  If that fails, use mailto:std-cpp-submit@vandevoorde.com ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.comeaucomputing.com/csc/faq.html                      ]