4 ms·

> I challenge you to find a single correct use of std::map to begin with. Before C++11, you only had std::map, so every use was correct. After C++11, you may s

by zvrba 9y ago

> I challenge you to find a single correct use of std::map to begin with. Before C++11, you only had std::map, so every use was correct. After C++11, you may still care about iterator invalidation or actually maintaining ordering. These properties are too useful to be deprecated. As for beginners, their priority should be learning the core language and making a habit of browsing the std documentation to see what's there. Then they'll stumble upon unordered map too. EDIT: as for cache coherency, std mandates use of separate chaining. If you really care about cache, you'll have to implement open addressing yourself.

kllrnohj 9y ago
> Before C++11, you only had std::map, so every use was correct. After C++11, you may still care about iterator invalidation or actually maintaining ordering. These properties are too useful to be deprecated. There's no shortage of 3rd party map implementations. Nothing forced you to use std::map pre-C++11, so it still isn't correct to use std::map prior to C++11 it was just easier to use std::map prior to that. If you need ordered access a hashmap + key list is a superior implementation to red-black trees, so std::map still loses there. The only thing std::map does have is iterators stay valid during inserts, but this doesn't really seem useful and indeed it's something most maps in most languages don't have. Heck, Java's red-black java.util.TreeMap doesn't even bother to keep iterators valid during inserts even though it could. How is this a useful property in practice much less one "too useful to be deprecated"? Do you have any examples?
- zvrba 9y ago
  > If you need ordered access a hashmap + key list is a superior implementation to red-black trees, so std::map still loses there. Superior in what way? > Do you have any examples? It's a couple of years since, but I remember having relied on both ordering and iterator stability in certain algorithms related to topological meshes. Basically, I'd traverse a map and delete some elements during traversal. Could I have done it in some way with a hash table? Yes. Would it have been more complicated? Yes.
  - kllrnohj 9y ago
    > Superior in what way? Superior in performance, and you can pick if you want to optimize for iteration (put the keys in a sorted vector) or insertion (linked list). Either way you'll trivially beat traversing, inserting, and removing elements from a red-black tree in runtime. > Basically, I'd traverse a map and delete some elements during traversal. That works fine with unordered_map, too. You can keep the iterator when you remove. It's only inserts where map's iterators stays valid but unordered_map's doesn't.
- slavik81 9y ago
  If we're just complaining about performance and third-party libraries are an in-scope solution, I don't see why anyone would settle for std::unordered_map. It trails on every hashmap benchmark. Chandler Carruth blames it on the C++ standard, which mandates chaining for collision handling. I mean, I wouldn't complain if with C++23 we introduce std2 and make things better. While we're at it, we could also try to fix std::list and std::deque which are nearly useless too.

by zvrba 9y ago

kllrnohj 9y ago

> Before C++11, you only had std::map, so every use was correct. After C++11, you may still care about iterator invalidation or actually maintaining ordering. These properties are too useful to be deprecated. There's no shortage of 3rd party map implementations. Nothing forced you to use std::map pre-C++11, so it still isn't correct to use std::map prior to C++11 it was just easier to use std::map prior to that. If you need ordered access a hashmap + key list is a superior implementation to red-black trees, so std::map still loses there. The only thing std::map does have is iterators stay valid during inserts, but this doesn't really seem useful and indeed it's something most maps in most languages don't have. Heck, Java's red-black java.util.TreeMap doesn't even bother to keep iterators valid during inserts even though it could. How is this a useful property in practice much less one "too useful to be deprecated"? Do you have any examples?

zvrba 9y ago
> If you need ordered access a hashmap + key list is a superior implementation to red-black trees, so std::map still loses there. Superior in what way? > Do you have any examples? It's a couple of years since, but I remember having relied on both ordering and iterator stability in certain algorithms related to topological meshes. Basically, I'd traverse a map and delete some elements during traversal. Could I have done it in some way with a hash table? Yes. Would it have been more complicated? Yes.
- kllrnohj 9y ago
  > Superior in what way? Superior in performance, and you can pick if you want to optimize for iteration (put the keys in a sorted vector) or insertion (linked list). Either way you'll trivially beat traversing, inserting, and removing elements from a red-black tree in runtime. > Basically, I'd traverse a map and delete some elements during traversal. That works fine with unordered_map, too. You can keep the iterator when you remove. It's only inserts where map's iterators stays valid but unordered_map's doesn't.
slavik81 9y ago
If we're just complaining about performance and third-party libraries are an in-scope solution, I don't see why anyone would settle for std::unordered_map. It trails on every hashmap benchmark. Chandler Carruth blames it on the C++ standard, which mandates chaining for collision handling. I mean, I wouldn't complain if with C++23 we introduce std2 and make things better. While we're at it, we could also try to fix std::list and std::deque which are nearly useless too.