Earlier quoted context omitted.
They’re often called “hash sets” or “hash maps” in other languages - they are called this for a reason, and certainly not because they could be implemented as a list. std::map is not a good example anyway, you want to consider std::unordered_map for a more appropriate comparison. C++ is weird that way. (What C++ calls a map is not what most languages call a map. std::map doesn’t even satisfy O(1). You’d be surprised…
You said "requires" hashing. Sets and Maps do not require hashing. Through it is correct to observe the unfortunate naming convention in the c++ std lib. std::set and std::map should be std::ordered_set and std::ordered_map sts::unordered_set and std::unordered_map should be std::hash_set and std::hash_map If this were so then it might make the incorrect usage of these two options less prevalent. But they are both ma…
And similarly, linked lists and arrays are just different "versions” of the same data structure: a list.