News for hackers. Stuff that matters.
Re:Why databases use ordered indexes but programming uses ha... by overgard on Monday December 09, 2019 @10:15PM (#21749273)
In C++ if you’re using the STL, std::map (tree) usage is way more common than a hash (std::unordered_map). I couldn’t tell you if its for a good reason though, or if its just because “map” is a lot shorter than “unordered_map”
Re:Why databases use ordered indexes but programming uses ha... by taneq on Monday December 09, 2019 @10:23PM (#21749311)
std::unordered_map was only added in C++11, which explains why it's not used in legacy code. Habit, inertia and a desire to keep codebases internally consistent explains why it's less common now.
Re:Why databases use ordered indexes but programming uses ha... by bnegreve on Tuesday December 10, 2019 @01:48AM (#21750278)
Developers primarily use sorted maps because the sorted map is the default map type in C++, by name. (I would be different if you had map/sorted_map instead).

The real question, is why C++ designers chose to prioritize sorted maps (RBTrees) over unsorted maps (Hash Maps).

I don't think it's a matter of speed though. I think it's because RBTrees are safer to use. Things can go really wrong with a hashmap if you have a poor hashing function (worst case search is O(n) vs. O(log(n)) for a RBTree)

Re:Why databases use ordered indexes but programming uses ha... by adrianN on Monday December 09, 2019 @11:41PM (#21749640)
Also std::unordered_map suffers from a design flaw that forces a poor implementation.
Re:Why databases use ordered indexes but programming uses ha... by yuushi on Tuesday December 10, 2019 @01:44AM (#21750264)
Depending on what you required, it can still be significantly faster than std::map. Any tree-based data structure is going to play havoc with cache. Also, it will perform an allocation for every single node inserted, which can become rather expensive (unless you're using some customized allocator for this).

Honestly, sorted vectors can often be a good replacement, depending on the workload, if you must have ordered data (this is what boost flat_map uses). All 3 (map, unordered_map, sorted vector) can have their uses, depending on what you are doing with the data.

If you need a better performing hash map, there's always Abseil as well.

Re:Why databases use ordered indexes but programming uses ha... by adrianN on Tuesday December 10, 2019 @02:58AM (#21750561)
Unfortunately unordered_map also requires lots and lots of allocations, because it's forced to use linked-list buckets.
Re:Why databases use ordered indexes but programming uses ha... by taneq on Tuesday December 10, 2019 @01:04AM (#21750058)
Would you be willing to expand on that? I couldn't find any obvious well-known issues with a quick search.
Re:Why databases use ordered indexes but programming uses ha... by abhishekjha on Tuesday December 10, 2019 @01:16AM (#21750111)
Apparently the standard imposes a set of requirements that the implementation must abide by thus making it a lot slower.

[0] : https://www.reddit.com/r/programming/comments/5pwgtn/hash_ma...

[1] : https://stackoverflow.com/questions/42588264/why-is-stdunord...

[2] : https://www.youtube.com/watch?v=ncHmEUmJZf4

Re:Why databases use ordered indexes but programming uses ha... by adrianN on Tuesday December 10, 2019 @01:18AM (#21750122)
The interface forces an implementation as a map with linked-list buckets which is suboptimal for many use cases. So people who care about performance usually just implement their own hash map or use a library.
Re:Why databases use ordered indexes but programming uses ha... by taneq on Tuesday December 10, 2019 @02:07AM (#21750342)
Ah, that makes sense. Thanks!
Re:Why databases use ordered indexes but programming uses ha... by repsilat on Monday December 09, 2019 @10:46PM (#21749424)
It probably varies by company, and by team. In my old hobby code there was a lot of std::map, but in my more recent professional experience I see a lot more absl::flat_hash_map and friends.
Re:Why databases use ordered indexes but programming uses ha... by darwingr on Monday December 09, 2019 @10:22PM (#21749306)
Is this something you’ve actually seen? I’ve often wondered.
Re:Why databases use ordered indexes but programming uses ha... by overgard on Monday December 09, 2019 @10:45PM (#21749415)
Well, it was the case at my last three jobs and most open source i’ve seen. It is anecdotal though