Asymmetric lower_bound

classic Classic list List threaded Threaded
3 messages Options
Reply | Threaded
Open this post in threaded view
|

Asymmetric lower_bound

Jakob Stoklund Olesen
Hi C++ experts,

In X86FloatingPoint.cpp there is a struct TableEntry that can be compared to an unsigned:

    friend bool operator<(const TableEntry &TE, unsigned V) {
      return TE.from < V;
    }

This is used with std::lower_bound():

static int Lookup(const TableEntry *Table, unsigned N, unsigned Opcode) {
  const TableEntry *I = std::lower_bound(Table, Table+N, Opcode);
  ...
}

It looks like the GNU libstdc++ is happy with the asymmetric types in the comparison, but MSVC insists that the transposed operator< also be available:

    friend bool operator<(unsigned V, const TableEntry &TE) {
      return V < TE.from;
    }

It is not really clear from the draft C++0x standard what is required when the comparison function takes asymmetric types.

Is MSVC wrong here, and lower_bound should work with only one asymmetric comparison available?
Is it a bug in the standard that it isn't clearly specified?

/jakob


_______________________________________________
cfe-dev mailing list
[hidden email]
http://lists.cs.uiuc.edu/mailman/listinfo/cfe-dev
Reply | Threaded
Open this post in threaded view
|

Re: Asymmetric lower_bound

Howard Hinnant
On Aug 16, 2010, at 5:29 PM, Jakob Stoklund Olesen wrote:

> Hi C++ experts,
>
> In X86FloatingPoint.cpp there is a struct TableEntry that can be compared to an unsigned:
>
>    friend bool operator<(const TableEntry &TE, unsigned V) {
>      return TE.from < V;
>    }
>
> This is used with std::lower_bound():
>
> static int Lookup(const TableEntry *Table, unsigned N, unsigned Opcode) {
>  const TableEntry *I = std::lower_bound(Table, Table+N, Opcode);
>  ...
> }
>
> It looks like the GNU libstdc++ is happy with the asymmetric types in the comparison, but MSVC insists that the transposed operator< also be available:
>
>    friend bool operator<(unsigned V, const TableEntry &TE) {
>      return V < TE.from;
>    }
>
> It is not really clear from the draft C++0x standard what is required when the comparison function takes asymmetric types.
>
> Is MSVC wrong here, and lower_bound should work with only one asymmetric comparison available?
> Is it a bug in the standard that it isn't clearly specified?

The LWG has consistently affirmed over the years that lower_bound and upper_bound tolerate asymmetric compares (but in opposite senses).

  lower_bound only requires:

     *j < value or comp(*j, value)

  upper_bound only requires:

     (value < *j) or comp(value, *j)

-Howard


_______________________________________________
cfe-dev mailing list
[hidden email]
http://lists.cs.uiuc.edu/mailman/listinfo/cfe-dev
Reply | Threaded
Open this post in threaded view
|

Re: Asymmetric lower_bound

Jakob Stoklund Olesen

On Aug 16, 2010, at 2:40 PM, Howard Hinnant wrote:

>
> The LWG has consistently affirmed over the years that lower_bound and upper_bound tolerate asymmetric compares (but in opposite senses).
>
>  lower_bound only requires:
>
>     *j < value or comp(*j, value)
>
>  upper_bound only requires:
>
>     (value < *j) or comp(value, *j)
>
> -Howard

Thanks,

I guess we will have to keep the other operator< around for MSVC's sake.

/jakob


_______________________________________________
cfe-dev mailing list
[hidden email]
http://lists.cs.uiuc.edu/mailman/listinfo/cfe-dev