Golang Data Structures

1---2name: golang-data-structures3description: "Golang data structures — slices (internals, capacity growth, preallocation, slices package), maps (internals, hash buckets, maps package), arrays, container/list/heap/ring, strings.Builder vs bytes.Buffer, generic collections, pointers (unsafe.Pointer, weak.Pointer), and copy semantics. Use when choosing or optimizing Go data structures, implementing generic containers, using container/ packages, unsafe or weak pointers, or questioning slice/map internals."4user-invocable: true5license: MIT6compatibility: Designed for Claude Code or similar AI coding agents, and for projects using Golang.7metadata:8  author: samber9  version: "1.1.1"10  openclaw:11    emoji: "🗃️"12    homepage: https://github.com/samber/cc-skills-golang13    requires:14      bins:15        - go16    install: []17allowed-tools: Read Edit Write Glob Grep Bash(go:*) Bash(golangci-lint:*) Bash(git:*) Agent18---19 20**Persona:** You are a Go engineer who understands data structure internals. You choose the right structure for the job — not the most familiar one — by reasoning about memory layout, allocation cost, and access patterns.21 22# Go Data Structures23 24Built-in and standard library data structures: internals, correct usage, and selection guidance. For safety pitfalls (nil maps, append aliasing, defensive copies) see `samber/cc-skills-golang@golang-safety` skill. For channels and sync primitives see `samber/cc-skills-golang@golang-concurrency` skill. For string/byte/rune choice see `samber/cc-skills-golang@golang-design-patterns` skill.25 26## Best Practices Summary27 281. **Preallocate slices and maps** with `make(T, 0, n)` / `make(map[K]V, n)` when size is known or estimable — avoids repeated growth copies and rehashing292. **Arrays** SHOULD be preferred over slices only for fixed, compile-time-known sizes (hash digests, IPv4 addresses, matrix dimensions)303. **NEVER rely on slice capacity growth timing** — the growth algorithm changed between Go versions and may change again; your code should not depend on when a new backing array is allocated314. **Use `container/heap`** for priority queues, **`container/list`** only when frequent middle insertions are needed, **`container/ring`** for fixed-size circular buffers325. **`strings.Builder`** MUST be preferred for building strings; **`bytes.Buffer`** MUST be preferred for bidirectional I/O (implements both `io.Reader` and `io.Writer`)336. Generic data structures SHOULD use the **tightest constraint** possible — `comparable` for keys, custom interfaces for ordering347. **`unsafe.Pointer`** MUST only follow the 6 valid conversion patterns from the Go spec — NEVER store in a `uintptr` variable across statements358. **`weak.Pointer[T]`** (Go 1.24+) SHOULD be used for caches and canonicalization maps to allow GC to reclaim entries36 37## Slice Internals38 39A slice is a 3-word header: pointer, length, capacity. Multiple slices can share a backing array (→ see `samber/cc-skills-golang@golang-safety` for aliasing traps and the header diagram).40 41### Capacity Growth42 43- < 256 elements: capacity doubles44- > = 256 elements: grows by ~25% (`newcap += (newcap + 3*256) / 4`)45- Each growth copies the entire backing array — O(n)46 47### Preallocation48 49```go50// Exact size known51users := make([]User, 0, len(ids))52 53// Approximate size known54results := make([]Result, 0, estimatedCount)55 56// Pre-grow before bulk append (Go 1.21+)57s = slices.Grow(s, additionalNeeded)58```59 60### `slices` Package (Go 1.21+)61 62Key functions: `Sort`/`SortFunc`, `BinarySearch`, `Contains`, `Compact`, `Grow`. For `Clone`, `Equal`, `DeleteFunc` → see `samber/cc-skills-golang@golang-safety` skill.63 64**[Slice Internals Deep Dive](./references/slice-internals.md)** — Full `slices` package reference, growth mechanics, `len` vs `cap`, header copying, backing array aliasing.65 66## Map Internals67 68Maps are hash tables with 8-entry buckets and overflow chains. They are reference types — assigning a map copies the pointer, not the data.69 70### Preallocation71 72```go73m := make(map[string]*User, len(users)) // avoids rehashing during population74```75 76### `maps` Package Quick Reference (Go 1.21+)77 78| Function          | Purpose                      |79| ----------------- | ---------------------------- |80| `Collect` (1.23+) | Build map from iterator      |81| `Insert` (1.23+)  | Insert entries from iterator |82| `All` (1.23+)     | Iterator over all entries    |83| `Keys`, `Values`  | Iterators over keys/values   |84 85For `Clone`, `Equal`, sorted iteration → see `samber/cc-skills-golang@golang-safety` skill.86 87**[Map Internals Deep Dive](./references/map-internals.md)** — How Go maps store and hash data, bucket overflow chains, why maps never shrink (and what to do about it), comparing map performance to alternatives.88 89## Arrays90 91Fixed-size, value types. Copied entirely on assignment. Use for compile-time-known sizes:92 93```go94type Digest [32]byte           // fixed-size, value type95var grid [3][3]int             // multi-dimensional96cache := map[[2]int]Result{}   // arrays are comparable — usable as map keys97```98 99Prefer slices for everything else — arrays cannot grow and pass by value (expensive for large sizes).100 101## container/ Standard Library102 103| Package | Data Structure | Best For |104| --- | --- | --- |105| `container/list` | Doubly-linked list | LRU caches, frequent middle insertion/removal |106| `container/heap` | Min-heap (priority queue) | Top-K, scheduling, Dijkstra |107| `container/ring` | Circular buffer | Rolling windows, round-robin |108| `bufio` | Buffered reader/writer/scanner | Efficient I/O with small reads/writes |109 110Container types use `any` (no type safety) — consider generic wrappers. **[Container Patterns, bufio, and Examples](./references/containers.md)** — When to use each container type, generic wrappers to add type safety, and `bufio` patterns for efficient I/O.111 112## strings.Builder vs bytes.Buffer113 114Use `strings.Builder` for pure string concatenation (avoids copy on `String()`), `bytes.Buffer` when you need `io.Reader` or byte manipulation. Both support `Grow(n)`. **[Details and comparison](./references/containers.md)**115 116## Generic Collections (Go 1.18+)117 118Use the tightest constraint possible. `comparable` for map keys, `cmp.Ordered` for sorting, custom interfaces for domain-specific ordering.119 120```go121type Set[T comparable] map[T]struct{}122 123func (s Set[T]) Add(v T)          { s[v] = struct{}{} }124func (s Set[T]) Contains(v T) bool { _, ok := s[v]; return ok }125```126 127**[Writing Generic Data Structures](./references/generics.md)** — Using Go 1.18+ generics for type-safe containers, understanding constraint satisfaction, and building domain-specific generic types.128 129## Pointer Types130 131| Type | Use Case | Zero Value |132| --- | --- | --- |133| `*T` | Normal indirection, mutation, optional values | `nil` |134| `unsafe.Pointer` | FFI, low-level memory layout (6 spec patterns only) | `nil` |135| `weak.Pointer[T]` (1.24+) | Caches, canonicalization, weak references | N/A |136 137**[Pointer Types Deep Dive](./references/pointers.md)** — Normal pointers, `unsafe.Pointer` (the 6 valid spec patterns), and `weak.Pointer[T]` for GC-safe caches that don't prevent cleanup.138 139## Copy Semantics Quick Reference140 141| Type | Copy Behavior | Independence |142| --- | --- | --- |143| `int`, `float`, `bool`, `string` | Value (deep copy) | Fully independent |144| `array`, `struct` | Value (deep copy) | Fully independent |145| `slice` | Header copied, backing array shared | Use `slices.Clone` |146| `map` | Reference copied | Use `maps.Clone` |147| `channel` | Reference copied | Same channel |148| `*T` (pointer) | Address copied | Same underlying value |149| `interface` | Value copied (type + value pair) | Depends on held type |150 151## Third-Party Libraries152 153For advanced data structures (trees, sets, queues, stacks) beyond the standard library:154 155- **`emirpasic/gods`** — comprehensive collection library (trees, sets, lists, stacks, maps, queues)156- **`deckarep/golang-set`** — thread-safe and non-thread-safe set implementations157- **`gammazero/deque`** — fast double-ended queue158 159When using third-party libraries, refer to their official documentation and code examples for current API signatures. Context7 can help as a discoverability platform.160 161## Cross-References162 163- → See `samber/cc-skills-golang@golang-performance` skill for struct field alignment, memory layout optimization, and cache locality164- → See `samber/cc-skills-golang@golang-safety` skill for nil map/slice pitfalls, append aliasing, defensive copying, `slices.Clone`/`Equal`165- → See `samber/cc-skills-golang@golang-concurrency` skill for channels, `sync.Map`, `sync.Pool`, and all sync primitives166- → See `samber/cc-skills-golang@golang-design-patterns` skill for `string` vs `[]byte` vs `[]rune`, iterators, streaming167- → See `samber/cc-skills-golang@golang-structs-interfaces` skill for struct composition, embedding, and generics vs `any`168- → See `samber/cc-skills-golang@golang-code-style` skill for slice/map initialization style169 170## Common Mistakes171 172| Mistake | Fix |173| --- | --- |174| Growing a slice in a loop without preallocation | Each growth copies the entire backing array — O(n) per growth. Use `make([]T, 0, n)` or `slices.Grow` |175| Using `container/list` when a slice would suffice | Linked lists have poor cache locality (each node is a separate heap allocation). Benchmark first |176| `bytes.Buffer` for pure string building | Buffer's `String()` copies the underlying bytes. `strings.Builder` avoids this copy |177| `unsafe.Pointer` stored as `uintptr` across statements | GC can move the object between statements — the `uintptr` becomes a dangling reference |178| Large struct values in maps (copying overhead) | Map access copies the entire value. Use `map[K]*V` for large value types to avoid the copy |179 180## References181 182- [Go Data Structures (Russ Cox)](https://research.swtch.com/godata)183- [The Go Memory Model](https://go.dev/ref/mem)184- [Effective Go](https://go.dev/doc/effective_go)