computer science Computer science is the study of computation, automation, and information. Computer science spans theoretical disciplines (such as algorithms, theory of computation, information theory, and automation) to Applied science, practical discipli ...

, a bidirectional map is an associative data structure in which the

(key, value)

pairs form a

one-to-one correspondence In mathematics, a bijection, also known as a bijective function, one-to-one correspondence, or invertible function, is a function between the elements of two sets, where each element of one set is paired with exactly one element of the other s ...

. Thus the

binary relation In mathematics, a binary relation associates elements of one set, called the ''domain'', with elements of another set, called the ''codomain''. A binary relation over Set (mathematics), sets and is a new set of ordered pairs consisting of ele ...

functional Functional may refer to: * Movements in architecture: ** Functionalism (architecture) ** Form follows function * Functional group, combination of atoms within molecules * Medical conditions without currently visible organic basis: ** Functional sy ...

in each direction: each

value

can also be mapped to a unique

key

. A pair

(a, b)

thus provides a unique coupling between

a

and

b

so that

b

can be found when

a

is used as a key and

a

can be found when

b

is used as a key. Mathematically, a bidirectional map can be defined a

bijection In mathematics, a bijection, also known as a bijective function, one-to-one correspondence, or invertible function, is a function between the elements of two sets, where each element of one set is paired with exactly one element of the other s ...

f: X \to Y

between two different sets of keys

X

and

Y

of equal

cardinality In mathematics, the cardinality of a set is a measure of the number of elements of the set. For example, the set A = \ contains 3 elements, and therefore A has a cardinality of 3. Beginning in the late 19th century, this concept was generalized ...

, thus constituting an

injective In mathematics, an injective function (also known as injection, or one-to-one function) is a function that maps distinct elements of its domain to distinct elements; that is, implies . (Equivalently, implies in the equivalent contrapositiv ...

and

surjective In mathematics, a surjective function (also known as surjection, or onto function) is a function that every element can be mapped from element so that . In other words, every element of the function's codomain is the image of one element of i ...

function:

\begin
 & \forall x, x' \in X, f(x) = f(x') \Rightarrow x = x' \\ 
 & \forall y \in Y, \exists x \in X : y=f(x)
\end \Rightarrow \exists f^(x)

External links

Boost.org

Codeproject.com

bidict (bidirectional map implementation for Python)
Associative arrays {{datastructure-stub