[cfe-dev] 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