# Datastructure for two-way map

**URL:** <https://discourse.julialang.org/t/datastructure-for-two-way-map/52735>\
**Category:** General Usage\
**Created:** [January 2, 2021, 2:43pm UTC](https://discourse.julialang.org/t/datastructure-for-two-way-map/52735 "2021-01-02T14:43:45Z")\
**Posts on this page:** 13\
**Page:** 1

<div class="post-metadata">

**Author:** ![rikh](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/rikh/32/204104_2.png) [@rikh](https://discourse.julialang.org/u/rikh)\
**Post date:** [January 2, 2021, 2:43pm UTC](https://discourse.julialang.org/t/datastructure-for-two-way-map/52735/1 "2021-01-02T14:43:45Z")

</div>

Say that I have two vectors `U` and `V` defined as

```julia
U = ["A", "D", "B"]
V = ["F", "G", "B"]

```

and I want to map from `U` to `V`, and `V` to `U`. Both vectors contain only unique elements. For a one-way mapping, this is easy via a `Dict`:

```julia
julia> U_V = Dict(zip(U, V))
Dict{String,String} with 3 entries:
  "B" => "B"
  "A" => "F"
  "D" => "G"

julia> U_V["A"]
"F"

```

Is there also a data structure to have a two-way mapping? As I see it, the problem with two Dictionaries is that they duplicate the data and can get out of sync.

---

<div class="post-metadata">

**Author:** ![Henrique\_Becker](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/henrique_becker/32/15443_2.png) [@Henrique\_Becker](https://discourse.julialang.org/u/Henrique_Becker)\
**Post date:** [January 2, 2021, 3:03pm UTC](https://discourse.julialang.org/t/datastructure-for-two-way-map/52735/2 "2021-01-02T15:03:33Z")

</div>

I am not sure if I understand your problem. What prevents you from associating the first element in the first vector with the first element in the second vector and so on?

I think your problem is, in fact, that you want to be able to find the elements in `O(1)` (or `O(log n)`) **and** associate both sets _without_ replicating data. In this case I would suggest having both arrays ordered (what allows for `O(log n)` binary search) and each of the two arrays has its own auxiliary array of indexes that points to the associated index in the other array. However, this can become a nightmare to maintain if queries are interleaved with insertion and removal of elements.

I am not aware of any out-of-the-box solution solution for this. Did you look at [`DataStructures.jl`](https://github.com/JuliaCollections/DataStructures.jl)?

---

<div class="post-metadata">

**Author:** ![rikh](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/rikh/32/204104_2.png) [@rikh](https://discourse.julialang.org/u/rikh)\
**Post date:** [January 2, 2021, 3:21pm UTC](https://discourse.julialang.org/t/datastructure-for-two-way-map/52735/3 "2021-01-02T15:21:48Z")

</div>

> [@Henrique\_Becker](#):
>
> I am not sure if I understand your problem. What prevents you from associating the first element in the first vector with the first element in the second vector and so on?

The problem is not runtime but avoiding inconsistent states. Your mention of DataStructures.jl made me realize that this is a general problem indeed. It appears to be called a BiMap:

- Haskell: [Data.Bimap](http://hackage.haskell.org/package/bimap-0.4.0/docs/Data-Bimap.html)
- Java: [BiMap (Guava: Google Core Libraries for Java 19.0 API)](https://guava.dev/releases/19.0/api/docs/com/google/common/collect/BiMap.html)
- R: [bimap: Create a new 'bimap' in datastructures: Implementation of Core Data Structures](https://rdrr.io/cran/datastructures/man/bimap.html)

From the Haskell docs:

> An implementation of bidirectional maps between values of two key types. A Bimap is essentially a bijection between subsets of its two argument types.
> 
> Each element of the left-hand type is associated with an element of the right-hand type, and vice-versa, such that the two mappings are inverses. Deleting an element will cause its twin to be deleted, and inserting a pair of elements will cause any overlapping bindings to be deleted.

There is a package created and last updated in 2015 at [GitHub - bicycle1885/BiMaps.jl: bijective mapping](https://github.com/bicycle1885/BiMaps.jl).

I should probably make a PR at DataStructures.jl

---

<div class="post-metadata">

**Author:** ![Henrique\_Becker](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/henrique_becker/32/15443_2.png) [@Henrique\_Becker](https://discourse.julialang.org/u/Henrique_Becker)\
**Post date:** [January 2, 2021, 3:26pm UTC](https://discourse.julialang.org/t/datastructure-for-two-way-map/52735/4 "2021-01-02T15:26:42Z")

</div>

> [@rikh](#):
>
> The problem is not runtime but avoiding inconsistent states.

Again, I do not understand what you mean by this. Do you mean you can insert/remove an element from one vector and forgot to do the same to the associated element? In this case you can wrap your vectors inside a `struct BiMap` and only interact with them by means of safe methods.

Unfortunately, so often I find Julia kinda of lacking in advanced DataStructures. I myself have written [TrackingHeaps.jl](https://github.com/henriquebecker91/TrackingHeaps.jl) to overcome some limitations I found.

---

<div class="post-metadata">

**Author:** ![tro3](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/tro3/32/12355_2.png) [@tro3](https://discourse.julialang.org/u/tro3)\
**Post date:** [January 3, 2021, 6:17pm UTC](https://discourse.julialang.org/t/datastructure-for-two-way-map/52735/5 "2021-01-03T18:17:22Z")

</div>

If you just need a short-term solution to be optimized for speed later, a simple reverse lookup is plenty fast:

```julia
julia> function get_rev(src, val)
         for key in keys(src)
           src[key] == val && return key
         end
         throw(KeyError("$val"))
       end
get_rev (generic function with 1 method)

julia> get_rev(U_V, "F")
"A"

```

But if you need serious performance, you’d have to have to have a single structure with two hash tables and maintain consistency internal to the api. Personally, I wouldn’t do this up front until I was sure this was going to be my bottleneck.

---

<div class="post-metadata">

**Author:** ![CameronBieganek](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/cameronbieganek/32/6915_2.png) [@CameronBieganek](https://discourse.julialang.org/u/CameronBieganek)\
**Post date:** [January 3, 2021, 6:27pm UTC](https://discourse.julialang.org/t/datastructure-for-two-way-map/52735/6 "2021-01-03T18:27:54Z")

</div>

If you’re looking for a bijection, look no further:

[https://github.com/scheinerman/Bijections.jl](https://github.com/scheinerman/Bijections.jl)

Example:

```julia
julia> using Bijections

julia> d = Dict("A" => "F", "D" => "G", "B" => "B")
Dict{String,String} with 3 entries:
  "B" => "B"
  "A" => "F"
  "D" => "G"

julia> b = Bijection(d)
Bijection{String,String} (with 3 pairs)

julia> b["A"]
"F"

julia> b("G")
"D"

```

---

<div class="post-metadata">

**Author:** ![colintbowers](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/colintbowers/32/8033_2.png) [@colintbowers](https://discourse.julialang.org/u/colintbowers)\
**Post date:** [January 4, 2021, 3:44am UTC](https://discourse.julialang.org/t/datastructure-for-two-way-map/52735/7 "2021-01-04T03:44:52Z")

</div>

I wanted this a few years back and ended up just implementing my own type with two dicts, as at the time anything else just seemed like too much hassle (plus I didn’t have any performance critical applications).

---

<div class="post-metadata">

**Author:** ![rikh](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/rikh/32/204104_2.png) [@rikh](https://discourse.julialang.org/u/rikh)\
**Post date:** [January 4, 2021, 1:23pm UTC](https://discourse.julialang.org/t/datastructure-for-two-way-map/52735/8 "2021-01-04T13:23:38Z")

</div>

> [@colintbowers](#):
>
> my own type with two dicts

I just did the same and put it in a package: [GitHub - rikhuijzer/BidirectionalMaps.jl: Immutable bidirectional map](https://github.com/rikhuijzer/BidirectionalMaps.jl). Only implemented the immutable one for now because that’s good enough for my use case.

> [@CameronBieganek](#):
>
> If you’re looking for a bijection, look no further:

Awesome suggestion. I did my own thing, though, because I found the reverse syntax a bit weird for my use-case

```julia
julia> b = Bijection{Int,String}()
Bijection{Int64,String} (with 0 pairs)

julia> b[1] = "alpha";

julia> inv = active_inv(b);

julia> inv["alpha"]
1

```

versus

```julia
julia> using BidirectionalMaps

julia> U = ["alpha"];

julia> V = [1];

julia> b = ImmutableBimap{String,Int}(U, V);

julia> b.left["alpha"]
1

julia> b.right[1]
"alpha"

```

---

<div class="post-metadata">

**Author:** ![rikh](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/rikh/32/204104_2.png) [@rikh](https://discourse.julialang.org/u/rikh)\
**Post date:** [January 4, 2021, 1:32pm UTC](https://discourse.julialang.org/t/datastructure-for-two-way-map/52735/9 "2021-01-04T13:32:07Z")

</div>

> [@Henrique\_Becker](#):
>
> Do you mean you can insert/remove an element from one vector and forgot to do the same to the associated element?

Yes, exactly. When training a statistical model, I sometimes need to convert my labels (strings) to integer. After training the model, I want to be absolutely 100% sure that my conversion is right to avoid messing up the conclusions.

---

<div class="post-metadata">

**Author:** ![Henrique\_Becker](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/henrique_becker/32/15443_2.png) [@Henrique\_Becker](https://discourse.julialang.org/u/Henrique_Becker)\
**Post date:** [January 4, 2021, 1:50pm UTC](https://discourse.julialang.org/t/datastructure-for-two-way-map/52735/10 "2021-01-04T13:50:57Z")

</div>

The syntax of the `Bijection` was probably created with the objective of writing general code that does not care which is domain and which is image. If you want a function using yours implementation to work both from `left` to `right` as well as `right` to `left` you will probably need to create an wrapper or put `if`s all over it. This `active_inv` method will probably work again over `inv` giving back the original direction, so there is no concept of a _natural_ direction and you can just call `active_inv` before passing the `Bijection` to a function if you want it to work in the opposite direction.

---

<div class="post-metadata">

**Author:** ![CameronBieganek](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/cameronbieganek/32/6915_2.png) [@CameronBieganek](https://discourse.julialang.org/u/CameronBieganek)\
**Post date:** [January 4, 2021, 4:00pm UTC](https://discourse.julialang.org/t/datastructure-for-two-way-map/52735/11 "2021-01-04T16:00:48Z")

</div>

@rikh It seems like you might have overlooked the convenient syntax that Bijections.jl provides for accessing the maps in _both_ directions:

```julia
julia> using Bijections

julia> b = Bijection("alpha", 1)
Bijection{String,Int64} (with 1 pairs)

julia> b["alpha"]
1

julia> b(1)
"alpha"

```

Notice that a `Bijection` is callable. So, to access the “left” map, you _index_ the bijection, and to access the “right” map, you _call_ the bijection.

The only small downside to this is that there is not much visual distinction between `b["a"]` and `b("a")`.

---

<div class="post-metadata">

**Author:** ![CameronBieganek](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/cameronbieganek/32/6915_2.png) [@CameronBieganek](https://discourse.julialang.org/u/CameronBieganek)\
**Post date:** [January 4, 2021, 4:03pm UTC](https://discourse.julialang.org/t/datastructure-for-two-way-map/52735/12 "2021-01-04T16:03:06Z")

</div>

> [@rikh](#):
>
> When training a statistical model, I sometimes need to convert my labels (strings) to integer.

As a side note, isn’t this what [CategoricalArrays.jl](https://github.com/JuliaData/CategoricalArrays.jl) is for?

---

<div class="post-metadata">

**Author:** ![rikh](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/rikh/32/204104_2.png) [@rikh](https://discourse.julialang.org/u/rikh)\
**Post date:** [January 4, 2021, 4:18pm UTC](https://discourse.julialang.org/t/datastructure-for-two-way-map/52735/13 "2021-01-04T16:18:47Z")

</div>

Probably! Thanks!