3 ms·
> 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 y
by 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.