Deep Dive · Issue 11

How Go's container/ Package Finally Brings Ordered Maps and Sets to the Standard Library

For 16 years Go shipped no set and no ordered map. Generics and iterators finally made the library types worth building.

22 August 2026 The container package shelf with only list, ring, and heap filled

The 16-year gap

Three types, and nothing else

The container package shelf with only list, ring, and heap filled

Since its first release, Go's container/ package has shipped exactly three types: list, ring, and heap. No map. No set. No ordered collection of any kind. For a language whose built-in map is one of its best features, that absence has been strange for a long time.

So Go developers learned to fake it. A set becomes a map[T]bool or, to save the wasted byte, a map[T]struct{}. An ordered map becomes a map[K]V plus a separately sorted slice of keys that you re-sort whenever the map changes. It works, but every codebase reinvents it slightly differently and none of it composes.

set of strings, the idiomatic way:

  seen := map[string]struct{}{}
  seen["a"] = struct{}{}     // add
  _, ok := seen["a"]        // contains?
  delete(seen, "a")         // remove

  // union? intersection? ordered iteration?
  // write it all yourself, every time.

The map[T]struct{} pattern every Go project rebuilds

The pattern is fine for one lookup table. It falls apart the moment you want set algebra, deterministic iteration order, or a range query, because a Go map deliberately gives you none of those.

What unblocked it

Generics and iterators change the math

Generics and iterators as two gears enabling new collections

A library Set[T] was barely worth building before generics landed in Go 1.18: without them every collection was either interface{} and unsafe, or hand-written per element type. People started asking for a real ordered map the same month generics shipped, and a concrete tree-based Map/Set API was proposed a year later.

The second piece was range-over-func iterators in Go 1.23. They let a library type expose for k, v := range myMap.All() with the same feel as ranging a built-in map. Together, generics and iterators closed most of the ergonomics gap between a library type and a language built-in.

Go 1.18 (generics: type-safe Set[T])
Go 1.23 (iterators: range-over-func)
Go 1.28 (container/ collection types)

What turned scattered issues into one coherent addition was organizational. A Go Collections working group formed and produced an umbrella proposal, golang/go#80590, that bundles several concrete types under one shared set of API conventions and targets Go 1.28. Instead of shipping one-off types, they designed the whole family at once.

The type-system trick

The binary-method problem

A recursive Union method that refers back to its own set type

Designing a family of set types runs into a subtle wall. A method like Union(S) S refers back to its own type: a hash-based set's Union returns a hash-based set, and a tree-based set's Union returns a tree-based set. Those two Union signatures are not the same type, so one ordinary interface can't describe both.

The fix is F-bounded (recursive) polymorphism: an abstract constraint that is parameterized by the very type implementing it. Unexported constraints like _AbstractSet[E] carry the concrete set type S as a parameter, so Union(S) S type-checks for each family separately while both still satisfy one shared convention.

// each concrete set S constrains itself
type _AbstractSet[E comparable, S any] interface {
    All() iter.Seq[E]
    Contains(E) bool
    Len() int
    Union(S) S        // returns the same set kind
}

A recursive constraint that spans hash.Set and ordered.Set

These constraints stay internal for now. They exist so generic helpers and tests can range over every set type through one interface, without forcing a single public supertype the language can't cleanly express.

Two families

Hash-based and tree-based, on purpose

Hash bucket layout beside a balanced tree layout

The proposal ships two parallel families because they answer different questions. container/hash.Map and hash.Set give O(1) average lookups with no ordering, the same trade-off as the built-in map. container/ordered.Map keeps keys sorted so you get deterministic iteration, first/last, and range queries.

hash.Map / hash.Set

O(1) avg lookup, no order

ordered.Map / ordered.Set

sorted, log-time range queries

The ordered types are backed by a balanced binary tree in the initial implementation, though the design doesn't strictly require a BST. A tree keeps elements sorted at O(log n) per operation, which is exactly what lets an ordered set answer a range or a first-key query without scanning everything. Third-party ordered maps like wk8/go-ordered-map have filled this need for years; the point now is one canonical version in the standard library.

The hash family also needs a way to key on things == can't handle, like slices, or where builtin equality is wrong, like comparing types.Type by identity. A standard custom-hashing interface, released ahead of the rest in Go 1.27, supplies exactly that so both families share one hashing story.

The canonical set

One obvious way to spell a set

set.Set wrapping map of struct values, mapset helpers beside it

Alongside the hash and ordered families sits container/set.Set, the plain, canonical set. It is transparently a map[T]struct{} under the hood, and it is meant to become the default set type new Go APIs reach for. The goal is to end the map[T]bool ambiguity, where a stored false could mean either "present but false" or "absent".

C++ ran into the mirror image of this naming question, ending up with map and unordered_map after the ordered one got the short name first. Go is choosing its defaults deliberately so the common case, an unordered membership set, has the shortest, least surprising spelling.

s := set.Of("a", "b")
s.Add("c")
s.Contains("b")        // true
s.Union(other)          // returns a set.Set

set.Set: methods where you used to write raw map code

For the mountain of existing code that already stores sets as map[T]bool or map[T]struct{}, there is a parallel package of pure helper functions, container/mapset, offering Union, Intersection and friends over those legacy maps without forcing a type change. Its API is deliberately mirrored on set.Set's methods so switching later is mechanical.

Where the design gets sharp

Trade-offs measured, not guessed

A scale weighing interface minimalism against concrete performance

The interesting decisions are about what to keep in the interface and what to push out to generic helpers. DeleteFunc, which conditionally removes matching elements, stays a first-class method. Drop it and a caller has to filter-then-rebuild, turning a tree deletion from O(n) into O(n log n).

\text{DeleteFunc on a tree:}\quad O(n)\ \text{in-place}\ \;\;\text{vs}\;\; O(n\log n)\ \text{rebuild}

Why a convenience method is worth a slot in the interface

The core set-algebra operations, Union, Intersection, Difference, SymmetricDifference, are kept as real methods even though each is expressible generically from just All, Len, and Contains. Keeping them concrete lets a specialized type be clever: an ordered set can reject a disjoint-range subset test almost instantly instead of scanning.

Rare operations went the other way. Take, Arbitrary, Subset, and Superset were removed from the core interface and left to generic helper functions, because they don't need special implementations to be efficient. The working group documented, per operation, the minimal structural interface each helper actually requires, so nothing costs abstraction it doesn't earn.

The payoff

Sixteen years, one convention

Why it matters

Go is filling one of the standard library's oldest holes, and doing it as a coordinated family rather than a pile of one-off types. Once set.Set becomes the default set in new APIs, the map[T]bool and hand-sorted-keys patterns start to fade from real codebases, and library authors get a shared vocabulary for passing collections around. It only became worth building after generics and iterators made library types feel native, which is why it took until Go 1.28.

The short version

For 16 years `container/` had only `list`, `ring`, and `heap`; Go 1.28's proposal #80590 adds real maps and sets.
**Generics (1.18)** and **range-over-func iterators (1.23)** are what finally made library collections as ergonomic as built-ins.
Three families ship together: hash-based, tree-based `ordered` (sorted, log-time ranges), and a canonical `set.Set` backed by `map[T]struct{}`.
F-bounded constraint interfaces let one shared convention span types whose `Union(S) S` methods are self-referential.
Interface membership was chosen by cost: `DeleteFunc` and set algebra stay in to protect O(n) implementations; rare ops moved to generic helpers.