5 ms·

Sets and maps do not required hashing. Specifically std::map and std::set in the C++ standard library are based on ordered trees.

jb1991 4y ago
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 how many working C++ developers don’t even realize the unnecessary performance cost they take when they decide to use std::map, because it’s not a proper hash map. ) But this thread is not about the finer differences in implementation of maps but rather whether or not they are basically just lists. They are not.
- glasshug 4y ago
  Agree broadly that this thread has gotten too long off what was basically a joke, but! Please measure before you make changes to your maps for perf reasons. Yeah this forum all knows their big-O, but B-tree maps like std::map often perform better than hash maps on real-world architectures.
- injidup 4y ago
  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 map and set structures just each version has other guarantees that in some scenarios may be more or less useful.
  - xigoi 4y ago
    > But they are both map and set structures just each version has other guarantees that in some scenarios may be more or less useful. And similarly, linked lists and arrays are just different "versions” of the same data structure: a list.
    - mirekrusin 4y ago
      Let's simplify it even more - everything is just ones and zeroes.
  - jb1991 4y ago
    You interpreted my reply as “all sets and maps require hashing“ instead of “sets and maps are examples of data structures that can require hashing”… which they are. Imagine someone says, every fruit in the world is sour, and someone answers, no there are plenty of fruits that are sweet, such as apples, and then an entire thread gets launched in an irrelevant direction pointing out that actually some apples are sour, which has no bearing on the original point.

jb1991 4y ago

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 how many working C++ developers don’t even realize the unnecessary performance cost they take when they decide to use std::map, because it’s not a proper hash map. ) But this thread is not about the finer differences in implementation of maps but rather whether or not they are basically just lists. They are not.

glasshug 4y ago
Agree broadly that this thread has gotten too long off what was basically a joke, but! Please measure before you make changes to your maps for perf reasons. Yeah this forum all knows their big-O, but B-tree maps like std::map often perform better than hash maps on real-world architectures.
injidup 4y ago
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 map and set structures just each version has other guarantees that in some scenarios may be more or less useful.
- xigoi 4y ago
  > But they are both map and set structures just each version has other guarantees that in some scenarios may be more or less useful. And similarly, linked lists and arrays are just different "versions” of the same data structure: a list.
  - mirekrusin 4y ago
    Let's simplify it even more - everything is just ones and zeroes.
- jb1991 4y ago
  You interpreted my reply as “all sets and maps require hashing“ instead of “sets and maps are examples of data structures that can require hashing”… which they are. Imagine someone says, every fruit in the world is sour, and someone answers, no there are plenty of fruits that are sweet, such as apples, and then an entire thread gets launched in an irrelevant direction pointing out that actually some apples are sour, which has no bearing on the original point.