3

I'm having quite a hard time trying to debug my little piece of code:

std::map<glm::ivec3,int> myMap;
glm::ivec3 myVec(3, 3, 3);
myMap.find(myVec);

I get the following error:

c:\program files (x86)\codeblocks\mingw\bin\..\lib\gcc\mingw32\4.7.1\include\c++\bits\stl_function.h|237|error: no match for 'operator<' in '__x < __y'

Does that mean I can't check whether a glm::ivec3 is smaller than another?
I think that because a stl::map is ordered, the compiler wants to check which pair comes first. I tried to make the key a pointer and it worked.

Isn't there a way to keep the key a value instead of a pointer? This makes me ask another question: how can compare with a greater than operation something that cannot be compared or that is slow to be compared?

Thank you! :)

Nicol Bolas
  • 449,505
  • 63
  • 781
  • 982
Benoît Dubreuil
  • 650
  • 1
  • 11
  • 27

2 Answers2

3

You can implement a comparison function:

bool operator<(const glm::ivec& lhs, const glm::ivec& rhs)
{
    return lhs.x < rhs.x ||
           lhs.x == rhs.x && (lhs.y < rhs.y || lhs.y == rhs.y && lhs.z < rhs.z);
}

(change .x, .y, .z to [0], [1], [2] / .first(), .second(), .third() etc as necessary.

how can compare with a greater than operation something that cannot be compared or that is slow to be compared?

Your pointer hack isn't uncommon but isn't always useful and has to be done with care - specifically, if someone comes along to search in the map and wants to find an existing element, they need a pointer to the same existing object that was earlier stored in the map. Or, choose some arbitrary ordering even if it makes no particular sense in the real world - as long as it's consistent.

If a comparison is just slow, you can potentially do things like compare a hash value first then fall back on the slower comparison for rare collisions (or if your hash is long/strong enough, return false on the assumption they're equal).

Tony Delroy
  • 102,968
  • 15
  • 177
  • 252
  • 3
    +1: Or,`return std::tie(lhs.x,lhs.y,lhs.z) < std::tie(rhs.x,rhs.y,rhs.z);` if you want to save keystrokes and have a compliant C++11 impl. – WhozCraig May 27 '14 at 02:43
  • 1
    I don't know exactly what but my guts tell me s.th. smells about this solution. Looking at `lhs`,`rhs` being topographical vector representations the comparison operation might just mean the real _'lengths'_ of the vectors! – πάντα ῥεῖ May 27 '14 at 02:44
  • 1
    @πάνταῥεῖ I agree. You need *some* kind of strict weak ordering to use `std::map`, but there is no "natural" ordering for a 3D vector, so it should probably be a comparison functor, not `operator <`. – juanchopanza May 27 '14 at 05:50
1

I'm not familiar with glm, but mathematically this doesn't surprise me as vectors don't have a natural ordering; I.e. What would it mean u < v when the two can be at any location in a 3d space. When you used pointers, it was using address ordering, often isn't a good idea as the addresses have nothing to do with the "values" of the keys. You can't really order on magnitude since you can end up with two completely different vectors being equal. If it is important to have an order you could order them lexicographically, comparing one dimension, then the next, etc. but you might want to consider an unordered_map (a hash table) unless there is some need for an ordering in your problem.

Here is a link that discusses the Java hashCode() function with some discussion of various approaches to hashing for compound objects.

http://www.javamex.com/tutorials/collections/hash_function_guidelines.shtml

For a class that has three ints as it's state, I'd probably do (((x*p)+y)*p)+z where p Is a small prime, say 31. (There are many variations on this and much more complex has functions depending on the structure of the data, etc.)

Here are some more links from SO on C++ hashing.

unordered_map hash function c++

C++ unordered_map using a custom class type as the key

Community
  • 1
  • 1
sfjac
  • 7,119
  • 5
  • 45
  • 69
  • Do you know a good tutorial for unordered_map and custom keys (homemade classes)? I have no idea how to make a hash function. Every tutorial I find shows me how to use an unordered_map with an int or a string... – Benoît Dubreuil May 28 '14 at 17:50