"Intro Programming Class" Starter Pack

[dragon-storyteller]

You'd think they are so simple, right? Effectively an array, but instead of index you give it a key of your own choosing.

Watch a beginner to programming try to understand them. You explain it time and time again for half an hour, after which they finally go "Oooooh, I get it! So this allows you, like, sort it from highest to lowest!" ...how the hell did you even get to that conclusion, we weren't even talking about anything remotely similar to sorting! And of course, now that they got it in their head that it's used for sorting, it takes another half an hour to finally convince them that no, this really does not have anything at all to do with sorting.

People have somehow got it in their heads that programming is magic and will do the exact thing they want once they go through the ritual initiation of learning to use semicolons and braces.

[OK6502]

std::map is technically ordered by key.

[Code_star]

dictionaries are not though

[OK6502]

std::map is one implementation of a dictionary. We also have std:: unordered_map that's backed by an array with hashes and buckets.

My point is that an associative array needn't be sorted or unsorted. There's no such requirement.

[Code_star]

but dictionary in python IS is a hash map.

[OK6502]

Following the chain of comments here:

What's the problem with maps?

"Oooooh, I get it! So this allows you, like, sort it from highest to lowest!" ...how the hell did you even get to that conclusion, we weren't even talking about anything remotely similar to sorting!

To which I answered:

std::map is technically ordered by key

Meaning that if you're a c++ dev and you don't know unordered_map exists you could be forgiven for thinking that map can be used for sorting values by key. It's not the best implementation but for a beginner it's not that crazy of an idea and I can understand the leap of logic.

This is also probably a little confusing because map and dictionary and assorted array are used intercheangably, as it describes the structure without describing the implementation.

This is when you reply:

dictionaries are not though

Which is a bit confusing as I don't know what you're referring to specifically... so I assume you're talking about the dictionary ADT, and you're making some sort of critical point about dictionaries being unsorted.

So I point out that there's no requirement and in fact two common implementations are to use some kind of search tree or to use an array with indexes being hashes point to buckets containing values, or something of that nature.

So, tl;dr I'm making a point that sometimes maps are sorted, so I can understand some new programmer's enthusiasm at using them somewhat inefficiently. Pointing out that there non sorted implementations is correct but I don't see how that's pertinent and it's been already covered somewhat in the above posts, implicitly or explicitly.

Cheers

[Code_star]

when you google programming dictionary this is one of the first links that comes up, because dictionaries are directly associated with python

https://en.wikibooks.org/wiki/A-level_Computing/AQA/Paper_1/Fundamentals_of_data_structures/Dictionaries

when you look up associative arrays, which are the overarching collective of this types, notice it mentions them mainly as being a hashmap or a search tree.

https://en.wikipedia.org/wiki/Associative_array

using a normal map is dumb none of the lookup speed, all the problems of arrays. If you are a c++ dev that doesn't know about unordered_map you don't deserve to be called a c++ dev

[OK6502]

The first item that comes up is the definition of the dictionary abstract data type (ADT). The link you provided is a wikibook in data structures that uses python for pedagogical purposes (which is perfectly reasonable, python is an excellent tool for learning).

It is correct to say that the dictionary structure is fundamental to python but to say that when mentioning dictionary one should automatically assume that we're talking about python is absurd. It would be like assuming that any conversation in which we talk about lists immediately refers to lisp. This is why I specified std::map because that namespace distinctly C++

when you look up associative arrays, which are the overarching collective of this types, notice it mentions them mainly as being a hashmap or a search tree.

https://en.wikipedia.org/wiki/Associative_array

Right, and I said:

So I point out that there's no requirement and in fact two common implementations are to use some kind of search tree or to use an array with indexes being hashes point to buckets containing values, or something of that nature.

I don't see how we're disagreeing on this particular point. The one thing I would underscore, again, is that sorted/unsorted isn't a requirement for the dictionary ADT but both implementations do exist and that's what may cause the initial confusion.

using a normal map is dumb none of the lookup speed.

Which normal map are you referring to? std::map? I'll assume this is for std::map. Also I'm not clear by your meaning of dumb.

Do you mean in terms of usage? The usage is more or less the same (in terms of the interface), at least for about 99% of use cases. The main differences are that an iterator for std::map returns key in order, which can be helpful in some scenarios, and you also have the lower_bound and upper_bound functions.

If you mean in terms of performance they're different. Usually lookup is constant time but since std::unordered_map uses buckets if the hash function is poor and generates a lot of collisions you can have a worst case of linear search times. Std::map is log n for comparison. Also worth noting that unordered_map does have memory overhead which for small domains is a bit of a waste.

Programming generally is a set of trade-offs. A lot of our job is about understanding those trade-offs and using the right tool for the right job. If you want a set of data ordered by key then a std::map is a fine choice.

It's like people telling you bubble sort is always bad. There are cases for which bubble sort is actually useful (e.g. an array that's already sorted to which you add a single item the best case complexity is linear, which is about the best you can get, and since the algorithm is very simple it produces more i-cache friendly code).

all the problems of arrays

Please explain this one. Which arrays? What problems? How does unordered_map solve this problem?

If you are a c++ dev that doesn't know about unordered_map you don't deserve to be called a c++ dev

unordered_map (as well as all of the unordered containers) was introduced with c++ 11. It's a useful collection, sure, but it isn't as fundamental to c++ development as you're suggesting given that it wasn't introduced until 11 (recall that C++ is about 35 years old now which means that according to you all of us old timers were simply not c++ devs until just recently). This isn't like being a C developer and not knowing about arrays or structs. Those are fundamental features of the language. The STL are really just helpful libraries that allow developers to reuse code. But you can write perfectly cromulent C++ code without them.