I have an array of structures, sorted on a member of a structure, something like:
struct foo
{
int bar;
double baz;
};
// An array of foo, sorted on .bar
foo foos[] = { ........ };
// foos[0] = {0, 0.245}
// foos[1] = {1, -943.2}
// foos[2] = {2, 304.222}
// etc...
I want to find the element with a specific .bar value. It might or might not be in the array, and I'd like to do it in O(log(n)) time, since the array is sorted.
std::lower_bound is what I'd normally go for, but I need to specify a comparison function. However, the type of the members of the array (struct foo) and the searched value (int) are not the same, thus, my comparator is:
bool comp(foo a, int b)
{
// ...
}
// --- or ---
bool comp(int a, foo b)
{
// ...
}
It looks like the first will work with gcc, but I was wondering if the order of the arguments to the comparison function was specified by the standard, or if I'm relying on compiler behavior.
I'd like to avoid constructing a foo to pass to std::lower_bound here, as a full foo isn't required, and could be costly. My other option would be to wrap the foo * in a custom iterator that only exposed the .bar member.
wilhelmtell :
From the standard, 25.3.3.1/3, on std::lower_bound():\n\n\n Returns: The furthermost iterator i in the range [first, last] such\n that for any iterator j in the range\n [first, i) the following\n corresponding conditions hold: *j <\n value or comp(*j, value) != false.\n\n\nFrom that, you may use\n\nbool comp(foo a, int b)\n\n\nor you may compare two foo instances and then access bar in both of them.",
2011-02-21T23:03:58