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.
This is true, but your second point is difficult to do in C. You would have to have a set template and a separate lookup template to search the set based on a key type. This is actually how heterogeneous lookup is implemented in C++: it's a template within a template. This is not a big deal in C++ because templates are instantiated automatically but we're instantiating templates manually in C. It's also only available as of C++14 and only on ordered containers, not hash tables.
It's more straightforward to combine these templates: make map the fundamental type, but make values contain their keys and make the key type default to the value type if omitted. This way it's both a map and a set. My own C hash table template does it this way [1]: it stores only a value type and not keys, but there is an optional separate key type used for lookups, hashes and comparisons. To make it a map, you provide both a key comparison expression and an expression to convert values to keys.
There's a 4th requirement: that the set has some way to return colliding entries on insertion (or provides access to the entry itself), which most don't. Otherwise lookup requires iterating the entire set.
> It's straightforward
It's really not. Straightforward is the other way around, this is convoluted and involved. It makes the library much harder to use for rather limited gains.
> Either the set type allows mutation of the objects so long as the parts relevant to comparison don't change
This sounds like a footgun requirement at best, I'm pleasantly surprised (for once) that C++ doesn't just let you mutate the entire thing at will.
To be honest, that doesn't sound so straightforward to me. Going the other way and implementing Set on top of HashMap is comparably trivial, making those kind of API acrobatics unnecessary.
* 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.