2

I just want a data structure that acts similar to a Dictionary, but not only can I access the values using the keys, but also access the keys using the values.

So it would be something like this:

let dict: ReversibleDictionary<String, String> = 
    ["1" : "one", "2" : "two", "3" : "three"]
dict.valueFromKey("1") // "one"
dict.keyFromValue("two") // "2"

Is there something like that built-in swift?

If there isn't, how can I create something like this myself?

I tried to create one using 2 NSMutableOrderedSets and use a linear search to find the corresponding values. But I think it's too inefficient to use a linear search, which is O(n) complexity. Accessing a dictionary should be O(1) complexity, right?

Sweeper
  • 213,210
  • 22
  • 193
  • 313
  • time complexity of accessing a dictionary depends on its implementation. might be O(1) in case of arrays and O(n) in case of linked lists – mangusta May 10 '16 at 01:05
  • I'm pretty sure a dictionary is similar to a hash table. And a searching in a hash table is O(1). @mangusta – Sweeper May 10 '16 at 01:07
  • in broad sense dictionary is a data structure for accessing a value based on its key. it might be array or linked list or hash or tree or whatever – mangusta May 10 '16 at 01:11
  • This is a question many have asked. Take a look at this: http://stackoverflow.com/questions/376090/nsdictionary-with-ordered-keys – Stephenye May 10 '16 at 01:36

1 Answers1

6

No, there is no built in data structure that does this.

But you could easily create your own data structure that consists of two dictionaries. When you add to this "ReversableDictionary" you just make sure to also add the inverse to the second dictionary.

Then internally you can perform the look up on the appropriate of the two dictionaries by implementing your own dict.valueFromKey() and dict.keyFromValue() methods

Look up should be O(1) at the expense of using twice as much storage.

gadu
  • 1,816
  • 1
  • 17
  • 31