2

I have a std::unordered_set of elements of type T, and a function U key_of(const T& t). Now, I want to have a C++ construct which:

  • supports some of std::unordered_map's methods; at the very least: operator[] const, find, and the iterators.
  • does not incur the storage of actually building the map (not even with T*s)
  • is backed by the set, i.e. there's one map entry for every element e in the set, there's a map entry (key_of(e),e).

What's the idiomatic way (if any) to do this with (modern) C++?

Notes: - The map facade will not be used to insert, delete or change any data. - Answers about ordered map and ordered set are also relevant, although less so. - Performance can be lacking, if I wanted something fast I would just build the map. Simplicity is more important. - The set is constant in the sense that the map facade may assume it never changes. - You may assume there are no redundancies in the set (i.e. no elements with the same key) or suggest a multimap solution.

Claudio
  • 10,614
  • 4
  • 31
  • 71
einpoklum
  • 118,144
  • 57
  • 340
  • 684
  • 1
    What kind of performance guarantees are you after? – Matteo Italia Dec 09 '15 at 10:00
  • Ary you saying you want your map to use a reference to the set to store keys and something else to store the values to avoid storing the keys twice? Please be explicit on relationship between the set and the map. – Lærne Dec 09 '15 at 10:01
  • @MatteoItalia: Not much of a guarantee, see edit. – einpoklum Dec 09 '15 at 10:06
  • is it just a fancy way of saying implement a std::unordered_map using std::unordered_set? – UmNyobe Dec 09 '15 at 10:15
  • @UmNyobe: You could [say that](https://en.wikipedia.org/wiki/Facade_pattern) I suppose. But it doesn't necessarily have to implement every single method of `std::unordered_map`. – einpoklum Dec 09 '15 at 11:24
  • 1
    I doubt you will find a clean idiomatic way to go about this. The elegance of such an implementation is inversely proportional to the level of compatibility with the "real" STL container. See e.g. [this answer](http://stackoverflow.com/a/34168509/1600898) that implements a simple mapping that maintains insertion order. Regardless of how simple the concept is, supporting all `std::map` operations and all optional template arguments invariably bloats up the code. – user4815162342 Dec 09 '15 at 11:24
  • @user4815162342: So, specified a low(ish) level of compatibility. – einpoklum Dec 09 '15 at 11:47

2 Answers2

0

I feel very short sighted, but where is the problem with using the iterators of unordered set, using std::find to mimick maps find, and with find the implementation of operator[] is trivial. Sure performance is not good, however wihout beeing willing to even store an additional pointer, I do not see how you can get better performance.

Or use a map, and modify insertion to check for duplicate entries which should be trivial since the key is key_of(value) and block that.

Pseudocode (C++14 for the lambda, can be worked around easily by having a helper function):

template<typename S, typename K> //set contained type, key type
class mapView { 
        typedef std::unordered_set<S> set_t;
        set_t& set;
    public:
        mapView(const set_t& set) : set(set) {}
        set_t::iterator find(const K& key) {
            return std::find(set.begin(), set.end(), [&](element){return key_of(element)==key;});
        }
        S& operator[](U&& key) {
            return *find(key);
        }
        //const declarations of above
        //forward begin/end etc. to return sets iterators i.e.
        set::iterator begin() {
            return set.begin();
        }
};
ted
  • 4,791
  • 5
  • 38
  • 84
0

The notion that given std::unordered_set<T>, we construct a std::unordered_map<K, V> such that K = key_of(const T& t), V = T puts a huge constraint on key_of.

  • key_of is bijective. The injectivity, ie for any x, y E T : key_of(x) == key_of(y) -> x == y is necessary to satisfy the key uniqueness of the map. The surjectivity may also be required, otherwise your map cannot contain an element z which is not computed using key_of. You didn't specify how that structure is going to be constructed, so lets drop it.
  • key_of should preserve the collision probability of Hash_v(T x). This is not such a big of a deal because if bijective, you can build Hash_u(U k) such that the probability of collision is the exact same.

Once these criteria are satisfied, it is not that different from building a std::unordered_map<K, V> using a std::unordered_set<std::pair<K, V>>. Which btw is totally possible, given that both requires Container, AllocatorAwareContainer, UnorderedAssociativeContainer.

note: equality is KeyEqual_u = std::equal_to<U>, KeyEqual_v = std::equal_to<V>

UmNyobe
  • 22,539
  • 9
  • 61
  • 90
  • 1
    Has your account been hacked? – erip Dec 09 '15 at 12:11
  • this is technically algebra :P – UmNyobe Dec 09 '15 at 12:13
  • @UmNyobe: 1. The first constraint is injectivity, not bijectivity. You don't actually need key_of to be surjective. 2. If key_of is not surjective, just replace unordered_map with unordered_multimap. 3. Come on, who's going to unwittingly attack the has probability distribution with something like projecting from some complex structure to a name field, or an index, or what-not? That's not a concern... – einpoklum Dec 09 '15 at 13:05
  • @einpoklum thanks you are correct about 1. about 2 is not an attack in the crypt sense, but a property of hash (http://en.cppreference.com/w/cpp/utility/hash), which is required to provide the expected average constant-time complexity of most operations – UmNyobe Dec 09 '15 at 13:09
  • @UmNyobe: But let's be pseudo-concrete. T is MyLargeClass and key_of is t -> t.name . Are you worried about the hash value probability distribution? – einpoklum Dec 09 '15 at 14:38