6 ms·

Be nice to see a hash map here.

• glouwbug 6y ago
  Due to popular demand, I will implement unordered_set after the holidays, once the new year is in full swing.
  • a-dub 6y ago
    hooray for hashes!
  • MrBuddyCasino 6y ago
    In the Java stdlib, Set is implemented on top of HashMap. I don't see how the opposite is possible?
    • glouwbug 6y ago
      Sets (and maps) are implemented as red black trees in the STL. The STL unordered_set (and unordered_map) is what I believe Java would call a HashMap, unless I am mistaken (I am not a Java guru).
      • masklinn 6y ago
        I don't know that the STL requires rbtrees for map and set, but you're correct that `std::unordered_map` is the STL's hashmap. The Java version of std::map would be java.util.TreeMap (and std::set => java.util.TreeSet).
        • tom_mellior 6y ago
          The STL's complexity requirements pretty much dictate a balanced binary search tree as the underlying representation for map and set. The choice then is essentially between red-black trees and AVL trees.
    • masklinn 6y ago
      Yes, that part of the readme: > STL std::map will not be implemented in CTL because maps only provide slight syntactic improvements over sets. makes no sense to me. It's the other way around: a set is a map with a irrelevant / ignored value (or singleton / ZST if available), with built-in functions for set-oriented operations (union/difference/subset/superset/disjoint). So if you're only going to provide one of them, you provide a map (that's what Go does). You don't have to implement sets in terms of maps though, it can be useful to provide different implementations of them as their usage patterns can be different and thus it might make sense to use a different underlying data structure (not sure about trees there but definitely a possible consideration for hashes). It also makes sense to have a bespoke set implementation if the language doesn't have ZSTs, to avoid wasting space (between 1 byte and 1 word per key depending on the storage details). Finally it can make sense to have a bespoke set implementation due to language visibility rules, so you can e.g. hit the hashes directly (rather than have to recompute them) when performing operations involving multiple sets.
      • gpderetta 6y ago
        a map is a set indexed only on a subset of the fields of your type. This maps directly to the relational model, where a table (or relation) being a set of tuples is the fundamental concept: for your typical programming language set the uniqueness constraint (and key), would be comprised by all the columns, while for a map it would only be comprised by a subset (just one at the limit), while the remaining columns would be the mapped type. Set operations (union, intersection, difference) do make sense for maps as well in fact. Given a powerful enough language, you can generalize your sets and maps with multiple uniqueness constraints and secondary indices. See boost.multindex for example. edit: and BTW, most STL implementations use the same underlying implementation for std::set and std::map which has a set-like interface with the ability to specify the key mapping function.
      • quietbritishjim 6y ago
        It's straightforward to use a set type as a mapping type, so long as it provides three things: * Comparisons don't have to use all members of the type e.g. if I have two Employee objects then I'm allowed to create a comparison function that only compares their employee IDs and ignores the name fields (perhaps because the name ought to be derived from employee ID). (I know this article is not about C++, but as a reference point this has always been possible in C++'s STL.) * Comparisons don't need a full-blown instance of the contained type e.g. in our employee example, the set can make use of a comparison function between int and Employee without having to construct an Employee with that ID. (This has been possible in C++ since C++11, and is often called heterogeneous lookup.) * The last point is a bit fiddly: Either the set type allows mutation of the objects so long as the parts relevant to comparison don't change, or you only wanted to store const values anyway. I mention this because in C++ if you have a std::set<Foo> then you can't mutate the Foo elements at all, even if it has no effect on the comparison of the elements with other elements. (Unless there are const methods that actually mutate it... yuck!) So long as you have those three things, you can have a set of (key, value) pairs where the comparitor only compares keys, and bingo you have a mapping type.
    • wffurr 6y ago
      A map is a set of key,value pairs, and the set lookup function only considers the key in the comparison.
  • einpoklum 6y ago
    Remember that C++'s unordered_set is quite slow (e.g. due to the use of lists for hash buckets.)
    • glouwbug 6y ago
      I will keep this in mind when I implement unordered_set. Thank you, and happy holidays
  • bufo 6y ago
    I recommend looking at the khash implementation https://github.com/attractivechaos/klib/blob/master/khash.h https://github.com/attractivechaos/klib/blob/master/khash.h It's very competitive to optimized implementations like abseil and much, much better than the C++ STL one.