Skip to content
coadyPublic

About

Go set library based on maps and iterators.

Topics

Resources

Stars

5 stars

Watchers

2 watching

Forks

Repository files navigation

build codecov CodeQL go ref

iterset

A set library based on maps and iterators. A set type is not necessary to have set operations.

There are many mapset implementations available, but they restrict the values to struct{} or bool. Although it seems like the right abstract data type, in practice it limits the usability.

  • Maps must be copied even though they already support iteration and O(1) lookup.
  • Map values are lost.
  • Slices must be copied even if they would have only been iterated.
  • Slice ordering is lost.
  • Copying effectively means no early exits, e.g., in a subset check.

Since sets are not built-in, they realistically will always be a secondary type. Even in languages with built-in sets, it is common to call set operations on keys while still keeping data in a map, and common to want to retain ordering.

So iterset is built around generic maps with any value type. Inspired by Python sets, its methods support iterators. This integrates well with functions in maps and slices, and addresses the typical mapset issues.

  • Maps can be casted instead of copied.
  • Map values are kept without affecting set operations.
  • Slices can be iterated using slices.Values without copying.
  • Slice iterators retain ordering.
  • Iterators are lazily evaluated, inherently supporting early exits.

Roadmap

golang.org/x/exp/collection/set is accepted (map[E]struct{}). container/mapset is still a proposal.

iterset mirrors that vocabulary where compatible, while keeping:

  • map[K]V with any value type (no copy)
  • iter.Seq as first-class input to set algebra (lazy evaluation)

Usage

Constructors

There are constructors for all common use cases.

  • Cast a map
  • Unique{By} iterates keys in order
  • Compact{By} iterates consecutive grouped keys
  • Collect with default value
  • Set / Of from variadic args
  • Index retains original position
  • Count stores key counts
  • IndexBy stores values by key function
  • Group{By} stores slices grouped by keys
  • Reduce combines values grouped by keys
  • Memoize caches function call

Methods

Methods support iterators, compatible with slices.Values and maps.Keys. Implementations are asymptotically optimal, and exit early where relevant.

  • Equal
  • ContainsAll
  • SubsetOf
  • Intersects
  • Union{With}
  • Intersection{Count,With}
  • Difference{With}
  • ReverseDifference
  • SymmetricDifference{With}
  • Toggle

As of Go 1.27, generic methods also accept slices and maps when that adds value: better performance, or compatibility with the standard set interface. Slices and maps may exit early based on size; maps may use an asymptotically better algorithm.

  • Equal
  • SubsetOf
  • Intersects
  • Intersection{Count,With}
  • Difference{With}
  • SymmetricDifference
  • Union{With}
  • Overlap

Functions

Some operations are also functions, to avoid making unnecessary maps. Note there is a trade-off between early exits versus iteration overhead. If one sequence is expected to be smaller, it is often faster to collect it into a map anyway. Slice parameters are also optimized where possible.

  • Equal{Counts}
  • SubsetOf
  • Intersects
  • Intersection
  • Difference
  • Sorted{Union,Intersection,Difference}

Includes general sequence utilities which complement the set operations. These are subject to change as iter patterns progress.

  • IsEmpty
  • Size
  • Keys
  • Sorted
  • Min
  • Max
  • GoIter

Iterators avoid eager collection and preserve early exits. They are only single-use if their input was.

Installation

No dependencies. Go >=1.25 required; at least the past two Go releases supported.

go get github.com/coady/iterset

Tests

100% code coverage.

go test -cover
go test -bench=.

About

Go set library based on maps and iterators.

Topics

Resources

Stars

5 stars

Watchers

2 watching

Forks

Releases

Packages

Used by

Contributors

Languages