Map - finding nearest value?

Question

I am trying find nearest RGB value in QMap (I know it probably should be HSV, but that is not the problem). Here is what I got so far:

        it = images_map.find(current_rgb);

        if(it != images_map.begin()){
            mi = images_map.lowerBound(current_rgb).value();
        }
        else{
            mi = images_map.upperBound(current_rgb).value();
        }

My map looks like this has that indexes:

images_map[ 4283914078 ] 
images_map[ 4284046165 ] 
images_map[ 4284902241 ] 
images_map[ 4289239953 ] 
images_map[ 4282200377 ] 
images_map[ 4289440688 ] 

When my current_rgb is for example 4285046165 it is OK, but if there is some value greater than greatest index, program crashes. What am I doing wrong?

Sheetfed

Are you using a custom comparison in your map? – Quinate

nope, anyway it is QMap from QT lib. – Sheetfed

Ok, removed STL tag (QMap is from Qt lib, not STL) – Quinate

Answer 1

Possibly because .value() tries to de-reference a non-existing item?

This looks like your own custom map implementation (or wrapper), but your logic appears to be incorrect

1. You call lowerBound every time - except if the item you are looking for is the first in the map
2. If it is the first in the map, you do a search again???
3. If it's not you search again (which if already found is repeating the operation again), else if not found, looks for nearest (which is okay), however do you handle the case where there is none (i.e. in lowerBound)?

The logic should be something like:

it = images_map.find(current_rgb);

if(it == images_map.end())
{
  it = images_map.lowerBound(current_rgb);
  if (it == images_map.begin())
  {
    it = images_map.upperBound(current_rgb);
    if (it == images_map.end()) 
      // throw error
  }
  // now you know you have a valid iterator - de-reference
  mi = *it.value();
}

Expound

Thanks it is better now, but in what condition error could occured? – Sheetfed

most likely because of the following, find() returns end(), in and therefore you end up doing an upperBound() - which also returns end() - which is de-referenced (.value()), causing the problem. – Expound

but I asked about your code, you do onlny lowerBound so maybe we should check for begin()? – Sheetfed

yeah - I didn't fully write it out... I think you get the idea? If not I can fix the example... – Expound

Answer 2

Call

images_map.upperBound(current_rgb) 

May return

images_map.end()

In that case you should not call value().

Opinionative

Answer 3

You can solve the iterator out of range problem by adding sentinel values 0x000000 and 0xFFFFFF (once). That way, you always have a valid lower- and upperbound. Of course, this may affect the outcome of your algorithm. E.g. if your "smallest" real color was pure blue (0x0000FF), then dark blue (0x00007F) will now find black, not pure blue. This is easily fixed by two comparisons, of course.

With the sentinels in place, call QMap::lower_bound. You need to check whether you've actually found a precise match: if *lower_bound is the value you want, return it. Else, lower_bound points to the first element that's bigger than your input. Therefore, --lowerbound points to the last element that's smaller than your input. Check which of the two is closer.

Note that the only way lower_bound can point to begin is when your input is precisely 0x000000 (the sentinel), in which case you won't get to --lower_bound. No range error there. By the same logic, the end sentinel 0xFFFFFF means you'll always find an lower_bound.

Quinate