Partitions

template<typename I>
using Partition = Store<partition<I>>;      // DisjointSets (union-find)

class Partition

A partition: Store<partition<I>>. The name Partition stands for the resolved Store type on this page.

A partition groups indices into disjoint classes, reached by merge and find. It is not iterated: enumerating a class would need a link per element that every partition would pay for.

Template parameters

I

indexable.

Member functions

void insert(const key_type &element)

Makes element an element (and, for dense keys, every smaller index not yet one).

bool merge(const key_type &lhs, const key_type &rhs)

Joins the classes; false where they were one already.

key_type find(const key_type &element) const

The element that names the class of element.

bool contains(const key_type &element) const

Whether element is an element: its index is below size(). O(1).

Two elements are in one class where find names the same element for both.

std::size_t size() const

void clear()

Complexity

insert O(1)*; find, merge O(α(n))* with path compression and union by size; clear O(1); memory n parents + n sizes.

Representation	lookup	insert	merge	memory	holds
disjoint_sets: disjoint sets (union-find by size, path halving)	O(1)*	O(1)*	O(1)*	O(n), 3.8 words	a parent and a size per element

* amortized, ~ expected; n elements, U the key range, r a row’s length, k a delta’s changes. Memory is the heap it holds (urd::memory_usage): what it grows in, and per element (or key, or slot) at most so many words, each the size of an element and at least a machine word. The declared costs; what they measure to is in Benchmarks.