Issue with std::lower_bound

[mathieu]

hi there,

I do not understand why the following piece of code is not working
for me. I have a set of cstrings, where I am trying to find one 'UT'.
If I search from "AE" to "OB or OW" everything is fine, but when
searching from "AE" to "US or SS"... then the code stops working...

Anyone can shed some light on it ?

thanks a bunch !
-Mathieu

#include <sstream>
#include <iostream>

static const char *VRStringsTest[] = {
"??", // 0
"AE", // 1
"AS", // 2
"AT", // 3
"CS", // 4
"DA", // 5
"DS", // 6
"DT", // 7
"FD", // 8
"FL", // 9
"IS", // 10
"LO", // 11
"LT", // 12
"OB", // 13
"OF", // 14
"OW", // 15
"PN", // 16
"SH", // 17
"SL", // 18
"SQ", // 19
"SS", // 20
"ST", // 21
"TM", // 22
"UI", // 23
"UL", // 24
"UN", // 25
"US", // 26
"UT", // 27
"OB or OW", // 28
"US or SS", // 29
"US or SS or OW", //30
0
};
class MySort
{
public:
bool operator() (const char *a, const char *b)
{
if( a[0] == b[0] )
return a[1] < b[1];
return a[0] < b[0];
}
};

int main(int, char *[])
{
const char vr[] = "UT";
static const int N = 28; // only consider a subset
static const char **start = VRStringsTest+1; // let's start at
element #1
//static const char **end = VRStringsTest+N; // working !
static const char **end = VRStringsTest+N+1; // not working
const char **p =
std::lower_bound(start, end, vr, MySort());
if( (*p)[0] != vr[0] || (*p)[1] != vr[1] )
{
std::cerr << "INVALID" << std::endl;
}
else
{
std::cerr << *p << std::endl; // Yes, we found 'UT' !
}

return 0;
}

 

[Juha Nieminen]

I do not understand why the following piece of code is not working
for me.

It's because your array is not in the order specified by "MySort".

"OB or OW" does not come after "UT" according to your "MySort" comparison.

 

[Richard Herring]

In message

hi there,

I do not understand why the following piece of code is not working
for me. I have a set of cstrings, where I am trying to find one 'UT'.
If I search from "AE" to "OB or OW" everything is fine, but when
searching from "AE" to "US or SS"... then the code stops working...

Anyone can shed some light on it ?

std::lower_bound expects to work on a sequence which is already sorted
according to the strict weak ordering implied by the comparison functor
you pass it. Yours isn't.

#include <sstream>
#include <iostream>

static const char *VRStringsTest[] = {
"??", // 0
"AE", // 1 [snip]
"UT", // 27
"OB or OW", // 28

[...]

 

[Victor Bazarov]

I do not understand why the following piece of code is not working
for me. I have a set of cstrings, where I am trying to find one 'UT'.

The 'lower_bound' algorithm has a pre-condition: the supplied sequence
has to be ORDERED. Your sequence isn't. So, you need to sort it before
you can use 'lower_bound' on it. And if you sort it (using 'std::sort'
with 'MySort' as predicate, the element "UT" will be _outside_ of the
range you supply (start, end).

If I search from "AE" to "OB or OW" everything is fine, but when
searching from "AE" to "US or SS"... then the code stops working...

Anyone can shed some light on it ?

I hope I have.

thanks a bunch !
-Mathieu

#include <sstream>
#include <iostream>

static const char *VRStringsTest[] = {
"??", // 0
"AE", // 1
"AS", // 2
"AT", // 3
"CS", // 4
"DA", // 5
"DS", // 6
"DT", // 7
"FD", // 8
"FL", // 9
"IS", // 10
"LO", // 11
"LT", // 12
"OB", // 13
"OF", // 14
"OW", // 15
"PN", // 16
"SH", // 17
"SL", // 18
"SQ", // 19
"SS", // 20
"ST", // 21
"TM", // 22
"UI", // 23
"UL", // 24
"UN", // 25
"US", // 26
"UT", // 27
"OB or OW", // 28
"US or SS", // 29
"US or SS or OW", //30
0
};
class MySort
{
public:
bool operator() (const char *a, const char *b)
{
if( a[0] == b[0] )
return a[1] < b[1];
return a[0] < b[0];
}
};

int main(int, char *[])
{
const char vr[] = "UT";
static const int N = 28; // only consider a subset
static const char **start = VRStringsTest+1; // let's start at
element #1
//static const char **end = VRStringsTest+N; // working !
static const char **end = VRStringsTest+N+1; // not working
const char **p =
std::lower_bound(start, end, vr, MySort());
if( (*p)[0] != vr[0] || (*p)[1] != vr[1] )
{
std::cerr << "INVALID" << std::endl;
}
else
{
std::cerr << *p << std::endl; // Yes, we found 'UT' !
}

return 0;
}

V

 

[mathieu]

The 'lower_bound' algorithm has a pre-condition: the supplied sequence
has to be ORDERED. Your sequence isn't. So, you need to sort it before
you can use 'lower_bound' on it. And if you sort it (using 'std::sort'
with 'MySort' as predicate, the element "UT" will be _outside_ of the
range you supply (start, end).

D'oh ! I knew it would be obvious...

Thanks everybody.

-Mathieu