C++Talk.NET

George van den Driessche · Guest

Standard algorithms such as std::lower_bound() can take a predicate for
ordering elements (such as std::less). This question concerns the
constraints on the types that such a predicate can use.

Suppose, for example, there is some UDT:

struct BigType
{
BigType( int i );
int i;
char someArbitraryData[FAIRLY_LARGE];
};

and a container of them:

std::vector< BigType > v;

Suppose also that I know that v is populated in an order such that its
elements are sorted according to the predicate:

struct BigTypeLess
{
bool operator()( BigType const& a, BigType const& b)
{
return (a.i < b.i);
}
};

The important point here is that someArbitraryData has no significance for
the ordering of BigTypes.

Now, suppose I want to find out whether v contains a value that matches a
particular i and s. I could write:

bool vContains42 = std::binary_search( v.begin(), v.end(), BigType( 42 ),
BigTypeLess() );

But BigType's constructor initialises someArbitraryData in an expensive way
and there's no need to do that because the ordering is dependent only on i.
So I'm wonddering then if it's legal to write the following:

struct BigTypeKeyComp
{
bool operator()( BigType const& a, int b )
{
return a.i < b;
}
bool operator()( int a, BigType const& b )
{
return a < b.i;
}
};

bool vContains42 = std::binary_search( v.begin(), v.end(), 42,
BigTypeKeyComp );

To iterate: is a specific example of a general question - the query applies
equally well to std::lower_bound(), std::equal_range(), std::map and plenty
of other things that involve predicates.

The question really boils down to: can a predicate supplied in such a
situation accept arguments of different types? One upshot of accepting
different types is that (as shown above) operator()() has to be defined with
both orderings of arguments, because at least one standard library
implementation uses expressions such as

less( a, b ) || less( b, a )

in various places.

George

[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]

Dietmar Kuehl · Guest

"George van den Driessche" <no-one (AT) nowhere (DOT) com> wrote:

Dhruv Matani · Guest

On Tue, 24 Feb 2004 14:29:54 -0500, George van den Driessche wrote:

Richard Smith · Guest

George van den Driessche wrote:
[...]

David Abrahams · Guest

[email]dietmar_kuehl (AT) yahoo (DOT) com[/email] (Dietmar Kuehl) writes: