forest

A small, header-only C++ implementation of the disjoint-set (union–find) data structure, with pluggable algorithms for the find and union operations and a pluggable underlying container.

Everything lives in forest.hpp and namespace pidhii. Just #include "forest.hpp" — no build step required.

Overview

The library provides two public, ready-to-use types:

Type	Set identifiers	Underlying container	Use case
pidhii::forest	size_t (dense indices)	std::vector (default)	Fast, array-based union-find over a known range of integer elements
pidhii::dict_forest<Key>	arbitrary Key	std::unordered_map (default)	Union-find over arbitrary, non-contiguous identifiers (strings, pointers, custom types, etc.)

Both are thin wrappers around a common internal implementation, pidhii::detail::forest<Key, Traits, Container>, and both expose the same two template parameters for tuning behavior:

• Traits — selects the algorithms used for find and join (union).
• Container — selects the container type used to store per-element data (parent pointer + rank/size bookkeeping).

Quick start

#include "forest.hpp"

int main()
{
  // Index-based forest over a known number of elements.
  pidhii::forest<> f;
  f.resize(5);          // creates elements 0..4, each its own set

  f.join(0, 1);
  f.join(1, 2);

  bool same = f.find(0) == f.find(2); // true
}

#include "forest.hpp"
#include <string>

int main()
{
  // Key-based forest for arbitrary identifiers.
  pidhii::dict_forest<std::string> f;
  f.make_set("a");
  f.make_set("b");
  f.make_set("c");

  f.join("a", "b");

  bool same = f.find("a") == f.find("b"); // true
}

API

pidhii::forest<Traits, Container>

Index-based disjoint-set forest. Set identifiers are size_t values assigned sequentially, starting from 0, as new sets are created.

template <
  typename Traits = forest_traits<find_method::path_halving, union_method::by_size>,
  template <typename T> typename Container = std::vector>
struct forest;

Member	Description
size_t make_set()	Creates a new singleton set and returns its identifier (the next unused index).
void resize(size_t size)	Clears the forest and (re)creates size singleton sets, 0 through size - 1.
size_t find(const size_t &id)	Returns the representative (root) identifier of the set containing id.
void join(const size_t &x, const size_t &y)	Merges the sets containing x and y.
const size_t& parent(const size_t &id) const	Returns the current, raw (not necessarily root) parent pointer stored for id.

pidhii::dict_forest<Key, Traits, Container>

Key-based disjoint-set forest. Set identifiers are arbitrary values of type Key, stored in an associative container.

template <
  typename Key,
  typename Traits = forest_traits<find_method::path_halving, union_method::by_size>,
  template <typename, typename> typename Container = std::unordered_map>
struct dict_forest;

Member	Description
void make_set(const Key &key)	Registers key as a new singleton set.
Key find(const Key &id)	Returns the representative (root) identifier of the set containing id.
void join(const Key &x, const Key &y)	Merges the sets containing x and y.
const Key& parent(const Key &id) const	Returns the current, raw (not necessarily root) parent pointer stored for id.

Note: find, join, and parent are inherited from the common detail::forest base and behave identically for both forest and dict_forest.

Customizing the algorithm: Traits

Both forest and dict_forest take a Traits type as their first template parameter, which selects the find and union strategies:

template <typename FindMethod, typename UnionMethod>
struct forest_traits {
  typedef FindMethod find_type;
  typedef UnionMethod union_type;
};

Provided algorithm tags:

pidhii::find_method (path-compression strategies)

Tag	Behavior
naive	Walks up to the root with no compression. O(tree height) per call.
path_compression	Finds the root, then re-points id directly to it.
path_halving	While walking to the root, makes every other node point to its grandparent.
path_splitting	While walking to the root, makes every node point to its grandparent.

pidhii::union_method (union strategies)

Tag	Behavior
naive	Always attaches the root of y's set under the root of x's set.
by_rank	Attaches the shorter tree under the taller one, tracking a rank per element.
by_size	Attaches the smaller tree under the larger one, tracking a size per element.

The default used by both forest and dict_forest when Traits is omitted is:

forest_traits<find_method::path_halving, union_method::by_size>

which gives close to inverse-Ackermann amortized complexity for both operations.

Example: choosing a different strategy

using my_traits = pidhii::forest_traits<
    pidhii::find_method::path_compression,
    pidhii::union_method::by_rank>;

pidhii::forest<my_traits> f;

Customizing the storage: Container

The second template parameter selects the container type used to store per-element bookkeeping (parent, and — depending on UnionMethod — rank or size).

• pidhii::forest expects a container template of shape Container<T> (e.g. std::vector, std::deque) indexed by size_t.
• pidhii::dict_forest expects a container template of shape Container<Key, T> (e.g. std::unordered_map, std::map) providing operator[], at(), and emplace().

// Use std::deque instead of std::vector.
pidhii::forest<pidhii::forest_traits<
    pidhii::find_method::path_halving, pidhii::union_method::by_size>,
    std::deque> f;

// Use std::map instead of std::unordered_map.
pidhii::dict_forest<std::string,
    pidhii::forest_traits<
        pidhii::find_method::path_halving, pidhii::union_method::by_size>,
    std::map> f;

Because the container is fully user-supplied, any type that satisfies the minimal interface used by forest/dict_forest (operator[], at(), emplace()/emplace_back(), size(), clear(), reserve()) can be plugged in — including non-standard, custom containers.

Persistent disjoint-set via pvector

This implementation is compatible with pidhii/pvector, a persistent (immutable, versioned) vector data structure. Since Container is a free template parameter, simply plugging pvector in as the container for pidhii::forest turns the whole structure into a persistent disjoint-set: every join/find (that mutates parent/rank/size data) produces a new version of the forest while old versions remain valid and accessible, with structural sharing between versions.

#include "forest.hpp"
#include "pvector.hpp" // from https://github.com/pidhii/pvector

// Persistent, index-based disjoint-set forest.
using persistent_traits =
    pidhii::forest_traits<pidhii::find_method::path_halving,
                           pidhii::union_method::by_size>;

pidhii::forest<persistent_traits, pidhii::pvector> f;

The exact alias/template name exported by pvector may differ slightly — see that repository's README for the precise container type to use here.

Requirements

• A C++ compiler with C++11 (or later) support.
• No external dependencies beyond the standard library (<cstddef>, <utility>, <vector>, <unordered_map>).

License

No license specified.