[boost] Re: Formal Review: Indexed Set

From: Joaquin M Lopez Munoz (joaquin_at_[hidden])
Date: 2004-03-24 02:36:07

Jeremy Maitin-Shepard <jbms <at> attbi.com> writes:

> 
> I think there may be the problem that the various predicates used for
> the indices do not generally define comparison operators which compare
> predicates specialized on different types.

I think Gary and you are talking about different things.
As you point out, there are difficulties in using the
internal comparison objects of indices for defining
operator <. Moreover, the standard clearly dictates that
comparison between containers a and b be implemented as

lexicographical_compare(a.begin(),a.end(),b.begin(),b.end())

leaving no option to use other comparison predicate than
operator < between element objects (see std 23.1.5) A rationale
for the decision of not using the internal comparison
predicates is given in

http://www.sgi.com/tech/stl/FAQ.html
(section "Why doesn't map's operator< use the map's comparison
function?")

So, IMHO there's little doubt that operator < between indices
of an indexed_set must use value_type::operator <,
conterintuitive as it may seem. A similar reasoning applies
to equality comparison between indices.

Now, what Gary proposes (if I understand it right) is that
we extend operator == and < so that indices on different element
types can be compared. As I see it, this can be legally done, and
it should do no harm as it merely extends the current
functionality. It'd be something along these lines:

template<...(1),...(2)>
bool operator==(
  const *index class*<...(1)>& x,
  const *index class*<...(2)>& y)
{
  return x.size()==y.size()&&std::equal(x.begin(),x.end(),y.begin());
}

template<...>
bool operator<(
  const *index class*<...(1)>& x,
  const *index class*<...(2)>& y)
{
  return std::lexicographical_compare(x.begin(),x.end(),y.begin(),y.end());
}

where ...(1) and ...(2) are (possibly different) sets of
template intantiation arguments for *index class*.
Is this what's being proposed?

Joaquín M López Muñoz
Telefónica, Investigación y Desarrollo