Re: [boost] Heterogeneous comparisons in binary search [was: A small holiday gift, I hope]

From: David Abrahams (abrahams_at_[hidden])
Date: 2000-12-26 14:03:01

----- Original Message -----
From: "Jeremy Siek" <jsiek_at_[hidden]>

> I like this formulation of the requirements... it is certainly much
> simpler. I've also been thinking in this direction, but have a
> couple worries:
>
> One thing that concerns me is that as a result (I think) we get a
> disconect between what it means for something to be sorted, and for
> something to be binary-searchable.

I submit that there always was such a disconnect. If you insist on
connecting them, you can do it. It just limits the range of legal uses of
the fundamental binary search

> To put it another way, we may need to have some notion to describe that a
> range is in such a state so that the binary search will work for *any*
> value object that is used with the comparison functor or operator <.

Surely you don't mean that. For example, I think calling f(v, s) below is
currently legal for most values of s:

struct cmp {
  bool operator()(const char* s1, const char* s2) const
     { return std::strcmp(s1, s2) < 0; }
};

std::size_t f(std::vector<const char*>& c, const char* s)
{
   std::sort(c, cmp());
   return std::lower_bound(c.begin(), c.end(), s, cmp()) - c.begin();
}

It's clearly not legal if s is 0, or if it doesn't point to a ntbs. Are you
saying that the above code should be illegal under all circumstances?

> Normally, the definition of "sorted" ensures this. Related to this, I'm
> worried that requirements based on a comparison "expression"  hide the
> separation between the comparison function and the value object.
>
> For a particular single call to binary search this may not be an issue,
> but how would you specify the requirements for a sorted_vector class?

I don't think I understand. Do you mean a sorted_vector map? Which
particular requirements are you interested in? All of them? Writing those is
a tedious but largely trivial job whose direct bearing on the validity of my
proposed changes I'm afraid I just don't see.

-Dave