8 ms·
I'm working on a game. I have a templated 2D vector implementation. Tile positions use Vector2<int>, entity positions and such use Vector2<float>. I wanted a m
by mort96 7y ago
I'm working on a game. I have a templated 2D vector implementation. Tile positions use Vector2<int>, entity positions and such use Vector2<float>.
I wanted a map from tile position to something else. I found that I had to implement operator<, because std::map uses operator<. That's an issue, because:
1. I didn't want to implement every single possible comparison operator just to put vectors in an array, but also didn't want to arbitrarily make `foo < bar` legal but `foo > bar` illegal.
2. What does it even mean for one vector to be "bigger than" another vector? For vector math purposes, I'd maybe expect operator< to compare magnitudes, but that would be absolutely terrible for std::map. Not everything has an unambiguous concept of "smaller than".
In the end I just made a std::map<std::pair<int, int>> and added an implicit conversion from Vector2<T> to std::pair<T, T>.
- stkdump 7y agoOh, that is simple: in associative containers, you can pass an external comparator as additional template parameter. Use that. Don't implicitly convert, it will bite you.
- mort96 7y agoOh thanks, I somehow didn't see that. That does sound better yeah.
- de_watcher 7y agoAnd also see if you're better off with an std::unordered_map or a custom sorted-array implementation of a map.
- masterjack 7y agoIn addition to the sibling’s comment on explicitly passing inna comparator, note that std::map is an ordered dictionary and requires an ordering on your elements. It sounds like you may have preferred hash_map
- mort96 7y agoI don't know, the way std::pair works is that it compares the two elements' `first`, or their `second` if `first` happens to be equal. That seems pretty good; lookup should still be O(n). I'll keep hash_map in mind though, and maybe do some performance testing to see which is actually faster.
- jcelerier 7y agostd::map is incredibly slow (and allocates willy-nilly), see https://martin.ankerl.com/2019/04/01/hashmap-benchmarks-01-overview/ https://martin.ankerl.com/2019/04/01/hashmap-benchmarks-01-o... for a comparison of modern hash maps. Or at least boost::flat_map if you need ordering but don't do many insertions / removals and care instead for fast iteration on the map. Note: when I say "incredibly slow", it is relative to what is possible to achieve in C++ - it will still roll over many other languages's map implementations.
- Const-me 7y agoIn some cases, the performance of std::unordered_map is fixable with a custom allocator: https://github.com/Const-me/CollectionMicrobench https://github.com/Const-me/CollectionMicrobench
- fpoling 7y agoChromium advised for their typical use cases to use std::map in favor of std::unordered_map. And they also provide own version of flat_map. [1] - https://chromium.googlesource.com/chromium/src/+/master/base/containers/README.md https://chromium.googlesource.com/chromium/src/+/master/base...