Is there a better way to store a twoway dictionary than to store its reverse separate?

Question

If a one-to-one dictionary (= bijection) is given, generated à la

for key, value in someGenerator: myDict[key] = value 

a reverse lookup dictionary can be created trivially by adding

  invDict[value] = key 

in a for loop. But is this Putin's? Should I instead write a class Bijection(dict) that additionally manages this inverted dictionary and provides a second search function? Or does such a structure (or similar) already exist?

Answer 1

What I did in the past created a reversedict function that takes a dict and returns the opposite mapping, either the values ​​for the keys, if I knew that it was one to one (throwing exceptions when viewing the same value twice) or values ​​for key lists if this is not the case. Thus, instead of creating two dicts each time I need a reverse lookup, I could create my dicts as regular ones and just call the generic reversedict function at the end.

However, it seems that the bidict solution that John mentioned in the comments is probably better. (My reversedict function is represented by its bidict ~ operator).

Answer 2

if you want O (log (n)) time to access the values, you will need both a map view and a reverse mapping view.

otherwise, the best you can do is O (log (n)) in one direction and O (n) in the other.

Edit: not O (log (n)), thanks Claudiu, but you still need two data structures to implement quick access. And it will be more or less the same space as the dict and the inverse dict.