The Bloom Filter is a probabilistic data structure for set membership.

The filter can be used as an inexpensive first step when querying the actual data is quite costly (e.g: as a first check for expensive cache lookups or large data seeks).

The Gap Buffer is a popular data structure for text editors to represent files and editable buffers. The most famous of them probably being GNU Emacs.

This time, let’s talk about the Trie, which is a tree-based mapping structure most often used for string keys.

To kickoff the series of posts about algorithms and data structures I find interesting, I will be talking about my favorite one: the Disjoint Set. Also known as the Union-Find data structure, so named because of its two main operations: ds.union(lhs, rhs) and ds.find(elem).

A great feature that can be used in more dynamic languages is multiple dispatch. Here’s an example in Julia taken from the Wikipedia article.

abstract type SpaceObject end

struct Asteroid <: SpaceObject
    # Asteroid fields
end
struct Spaceship <: SpaceObject
    # Spaceship fields
end

collide_with(::Asteroid, ::Spaceship) = # Asteroid/Spaceship collision
collide_with(::Spaceship, ::Asteroid) = # Spaceship/Asteroid collision
collide_with(::Spaceship, ::Spaceship) = # Spaceship/Spaceship collision
collide_with(::Asteroid, ::Asteroid) = # Asteroid/Asteroid collision

collide(x::SpaceObject, y::SpaceObject) = collide_with(x, y)

The collide function calls collide_with which, at runtime, will inspect the types of its arguments and dispatch to the appropriate implementation.

Julia was created with multiple dispatch as a first-class citizen, it is used liberally in its ecosystem. C++ does not have access to such a feature natively, but there are alternatives that I will be presenting in this article, and try to justify there uses and limitations.