The slices, maps, sort and cmp Packages in Go: Sorting, Searching, Grouping and Collection Work with Iterators

Version note: The code in this post was built and run with Go 1.27.4; the Bookstore module's go line is 1.26.0, and the code also compiles and passes its tests with Go 1.26.11. The slices, maps and cmp packages arrived in Go 1.21, the iterator-returning maps.Keys and slices.Sorted in Go 1.23, and strings.SplitSeq in Go 1.24. Turkish sorting uses golang.org/x/text v0.44.0; the json/v2 example is set apart with //go:build go1.27.

Guess First

In Bookstore, the online bookstore used as the shared example across this site's series, there is a small function that adds the bestseller to a shelf list. You extend the same shelf in two different places:

package main

import "fmt"

func withBestseller(shelf []string) []string {
    return append(shelf, "Dune")
}

func main() {
    shelf := make([]string, 2, 4)
    copy(shelf, []string{"Emma", "Persuasion"})
    a := withBestseller(shelf)
    b := append(shelf, "Foundation")
    fmt.Println(a, b)
}

a should end with "Dune" and b with "Foundation". Do they?

$ go run .
[Emma Persuasion Foundation] [Emma Persuasion Foundation]

They do not. shelf has capacity 4 and length 2; both append calls wrote to the third element of the same backing array without allocating a new one, and the second overwrote the first. The rule we saw with the slice header in post 03 shows up in every function that takes and returns a slice. This post covers collection work: sorting and searching with slices, cmp for multi-field sorting, maps and random iteration order, LINQ counterparts, and the older sort package. Bookstore gets categories, a ?sort= parameter and GET /api/categories.

Sorting with slices.SortFunc and cmp

In this post I added a Category field and two science fiction books (Foundation, The Left Hand of Darkness) to the catalog. For ordered types (numbers, strings), slices.Sort is enough; for structs, slices.SortFunc takes a comparison function. Like IComparer<T>.Compare in C#, the function returns a negative number, zero or a positive number:

func main() {
    books := catalog.Store{}.All()

    // Category ascending, then price descending, then title.
    slices.SortFunc(books, func(a, b catalog.Book) int {
        return cmp.Or(
            cmp.Compare(a.Category, b.Category),
            cmp.Compare(b.Price, a.Price), // b before a: descending
            cmp.Compare(a.Title, b.Title),
        )
    })
    for _, b := range books {
        fmt.Printf("%-16s %-26s %v\n", b.Category, b.Title, b.Price)
    }

    isbns := make([]string, 0, len(books))
    for _, b := range books {
        isbns = append(isbns, b.ISBN)
    }
    slices.Sort(isbns) // BinarySearch needs a sorted slice
    i, found := slices.BinarySearch(isbns, "9780441172719")
    j, missing := slices.BinarySearch(isbns, "9780000000002")
    fmt.Println(i, found, j, missing)

    cheapest := slices.MinFunc(books, func(a, b catalog.Book) int { return cmp.Compare(a.Price, b.Price) })
    k := slices.IndexFunc(books, func(b catalog.Book) bool { return b.Stock == 0 })
    fmt.Println(cheapest.Title, k, books[k].Title)
}

$ go run ./labs/17-sorting
Classics         Middlemarch                310.00 TRY
Classics         Sense and Sensibility      210.00 TRY
Classics         Emma                       199.00 TRY
Classics         Persuasion                 185.00 TRY
Fantasy          The Hobbit                 289.50 TRY
Science Fiction  Dune                       349.90 TRY
Science Fiction  The Left Hand of Darkness  310.00 TRY
Science Fiction  Foundation                 275.00 TRY
4 true 0 false
Persuasion 4 The Hobbit

cmp.Compare compares two values and returns -1, 0 or +1; cmp.Or returns its first non-zero argument. Together they are the counterpart of LINQ's OrderBy(...).ThenByDescending(...).ThenBy(...) chain. For descending order, swapping the arguments is enough. Because cmp.Or is an ordinary function, all of its arguments are evaluated on every comparison; if one comparison is expensive, an if c := ...; c != 0 { return c } chain is cheaper.

For searching, slices.BinarySearch returns the position in a sorted slice and whether the value was found; when it was not, the first value is where the element would have to be inserted. For unsorted slices there are Index, IndexFunc and Contains; MinFunc/MaxFunc are the counterparts of LINQ's MinBy/MaxBy and panic on an empty slice.

Stable Sorting and the ?sort= Parameter

slices.SortFunc is not stable: the order of elements that compare equal is not guaranteed. In an API's paged list, that means two books with the same price can swap places between pages. The new SortBooks in internal/catalog reads a spec such as "category,-price" and sorts with slices.SortStableFunc:

// bookOrders compares two books by one field, in ascending order.
var bookOrders = map[string]func(a, b Book) int{
    "title":    func(a, b Book) int { return cmp.Compare(a.Title, b.Title) },
    "author":   func(a, b Book) int { return cmp.Compare(a.Author, b.Author) },
    "category": func(a, b Book) int { return cmp.Compare(a.Category, b.Category) },
    "price":    func(a, b Book) int { return cmp.Compare(a.Price, b.Price) },
    "stock":    func(a, b Book) int { return cmp.Compare(a.Stock, b.Stock) },
}

// SortBooks sorts list in place by a spec such as "category,-price": fields
// separated by commas, a leading "-" for descending. The sort is stable, so
// books that compare equal keep their catalog order.
func SortBooks(list []Book, spec string) error {
    var keys []func(a, b Book) int
    for field := range strings.SplitSeq(spec, ",") {
        name, desc := strings.CutPrefix(strings.TrimSpace(field), "-")
        asc, ok := bookOrders[name]
        if !ok {
            return fmt.Errorf("%w: unknown field %q, want one of %s", ErrInvalidSort, name,
                strings.Join(slices.Sorted(maps.Keys(bookOrders)), ", "))
        }
        if desc {
            keys = append(keys, func(a, b Book) int { return asc(b, a) })
        } else {
            keys = append(keys, asc)
        }
    }
    slices.SortStableFunc(list, func(a, b Book) int {
        for _, key := range keys {
            if c := key(a, b); c != 0 {
                return c
            }
        }
        return 0
    })
    return nil
}

The fields live in a map, each one a small function that compares in ascending order. For descending order I wrap the function in a closure that passes the arguments the other way round; because asc is declared inside the loop body, every closure captures its own asc. Middlemarch and The Left Hand of Darkness both cost 310.00; the table test has a row that checks this tie keeps catalog order. The handler sorts the copy returned by All(), so the catalog itself does not change:

$ curl -s "http://127.0.0.1:52715/api/books?sort=category,-price&pageSize=2"
{"items":[{"isbn":"9780141439549","title":"Middlemarch","author":"George Eliot","category":"Classics","price":31000,"stock":4},{"isbn":"9780141439662","title":"Sense and Sensibility","author":"Jane Austen","category":"Classics","price":21000,"stock":5}],"page":1,"pageSize":2,"totalItems":8,"totalPages":4}
$ curl -s "http://127.0.0.1:52715/api/books?sort=rating"
invalid sort: unknown field "rating", want one of author, category, price, stock, title

The list in the error message is also built with slices.Sorted(maps.Keys(bookOrders)). Had I not sorted the list that comes from the map, the message would come out in a different order on every request; the next section explains why.

maps: Random Order, Keys and Sorted

The iteration order of Go maps is undefined, and the runtime changes it on purpose every time, so code that relies on an order breaks during testing:

func main() {
    stock := map[string]int{"Dune": 12, "Emma": 7, "Foundation": 9, "Middlemarch": 4, "Persuasion": 3}
    for range 3 {
        var order []string
        for title := range stock {
            order = append(order, title)
        }
        fmt.Println(order)
    }

    fmt.Println(slices.Sorted(maps.Keys(stock))) // keys returns an iterator, Sorted collects it
    fmt.Println(slices.Collect(maps.Values(map[string]int{"Dune": 12})))

    low := maps.Clone(stock)
    maps.DeleteFunc(low, func(_ string, n int) bool { return n >= 5 })
    fmt.Println(low, len(stock))
}

$ go run ./labs/17-maps
[Emma Foundation Middlemarch Persuasion Dune]
[Dune Emma Foundation Middlemarch Persuasion]
[Persuasion Dune Emma Foundation Middlemarch]
[Dune Emma Foundation Middlemarch Persuasion]
[12]
map[Middlemarch:4 Persuasion:3] 5

The same map was walked three times in three different orders. C#'s Dictionary<K,V> usually keeps insertion order but does not guarantee it; Go shows on every run that it does not guarantee it either. maps.Keys and maps.Values return iterators, not slices; slices.Sorted collects the iterator and sorts it, slices.Collect only collects. fmt, on the other hand, prints maps in key order, which is why the last line looks sorted.

JSON has a similar detail. v1 writes map keys sorted; json/v2 in Go 1.27 sorts them only when you pass json.Deterministic(true):

$ go run ./labs/17-jsonmap
v1 {"Dune":12,"Emma":7,"Foundation":9,"Middlemarch":4,"Persuasion":3}
v2 {"Foundation":9,"Middlemarch":4,"Persuasion":3,"Dune":12,"Emma":7}
v2 deterministic {"Dune":12,"Emma":7,"Foundation":9,"Middlemarch":4,"Persuasion":3}
...

One more item for the json/v2 migration plan from post 14: tests that compare a response byte by byte, and code that computes an ETag from the response, need this option under v2. Bookstore's category list is grouped with a map, but the response is a sorted slice:

// Categories groups the catalog by category, sorted by name.
func (Store) Categories() []CategorySummary {
    byName := make(map[string]*CategorySummary)
    for _, b := range books {
        s, ok := byName[b.Category]
        if !ok {
            s = &CategorySummary{Name: b.Category, Cheapest: b.Price}
            byName[b.Category] = s
        }
        s.Titles++
        s.Stock += b.Stock
        s.Cheapest = min(s.Cheapest, b.Price)
    }
    out := make([]CategorySummary, 0, len(byName))
    for _, name := range slices.Sorted(maps.Keys(byName)) { // map order is random
        out = append(out, *byName[name])
    }
    return out
}

$ curl -s http://127.0.0.1:52715/api/categories
[{"name":"Classics","titles":4,"stock":19,"cheapest":18500},{"name":"Fantasy","titles":1,"stock":0,"cheapest":28950},{"name":"Science Fiction","titles":3,"stock":23,"cheapest":27500}]

For Those Coming from LINQ: GroupBy, Sum, Distinct

In post 06 we talked about why Go has no culture of chained LINQ. In practice, most queries you would write with LINQ are a loop, a map and a few if statements:

// GroupBy collects the values of seq under their key, like ToLookup in C#.
func GroupBy[K comparable, V any](seq iter.Seq[V], key func(V) K) map[K][]V {
    groups := make(map[K][]V)
    for v := range seq {
        k := key(v)
        groups[k] = append(groups[k], v)
    }
    return groups
}

func main() {
    store := catalog.Store{}

    // books.GroupBy(b => b.Author).Where(g => g.Count() > 1)
    byAuthor := GroupBy(store.Books(), func(b catalog.Book) string { return b.Author })
    for _, author := range slices.Sorted(maps.Keys(byAuthor)) {
        if n := len(byAuthor[author]); n > 1 {
            fmt.Println(author, n)
        }
    }

    // books.Where(b => b.Stock > 0).Sum(b => b.Price * b.Stock)
    var value catalog.Money
    for b := range store.Books() {
        if b.Stock > 0 {
            value += b.Price * catalog.Money(b.Stock)
        }
    }
    fmt.Println("stock value:", value)

    // books.Select(b => b.Category).Distinct()
    seen := make(map[string]struct{}) // a set: struct{} takes no memory
    var categories []string
    for b := range store.Books() {
        if _, ok := seen[b.Category]; !ok {
            seen[b.Category] = struct{}{}
            categories = append(categories, b.Category)
        }
    }
    fmt.Println(categories)
}

$ go run ./labs/17-linq
Jane Austen 3
stock value: 11531.80 TRY
[Science Fiction Fantasy Classics]

There is no separate set type; map[string]struct{} is used, and a struct{} value takes no memory. Writing small generic helpers such as GroupBy for the few operations you use often is reasonable; do not try to rewrite all of LINQ. The counterparts:

Shared Slices: Clip, Delete, Compact

Back to Guess First. The functions in the slices package that modify a slice also share the backing array, and you need to know that:

c := withBestseller(slices.Clip(shelf)) // cap == len: append must copy
d := append(slices.Clip(shelf), "Foundation")
fmt.Println(c, d)

titles := []string{"Dune", "Emma", "Middlemarch", "Persuasion"}
rest := slices.Delete(titles, 1, 2) // removes "Emma"
fmt.Printf("%q %q\n", rest, titles) // the old tail is zeroed (Go 1.22)

tags := []string{"classic", "classic", "romance", "classic"}
fmt.Println(slices.Compact(slices.Clone(tags))) // only neighbours
slices.Sort(tags)
fmt.Println(slices.Compact(tags)) // sorted first: real distinct
fmt.Println(slices.Insert([]string{"Dune", "Emma"}, 1, "Foundation"))

$ go run ./labs/17-aliasing
[Emma Persuasion Foundation] [Emma Persuasion Foundation]
[Emma Persuasion Dune] [Emma Persuasion Foundation]
["Dune" "Middlemarch" "Persuasion"] ["Dune" "Middlemarch" "Persuasion" ""]
[classic romance classic]
[classic romance]
[Dune Foundation Emma]

slices.Clip reduces the capacity to the length; the append that follows has to allocate a new array, and the two results separate. Using Clip or Clone when you hand a slice out, or take one in and keep it, rules out this kind of bug from the start. slices.Delete returns the result as a new slice and, since Go 1.22, zeroes the element of the old slice that is no longer used: the last element of titles became the empty string. Code that keeps using the old slice reads wrong data without noticing; assign the returned value to the same variable (titles = slices.Delete(titles, 1, 2)). Compact only removes repeats that sit next to each other; for a real distinct, sort first.

The sort Package and Turkish Sorting

In older code you will see sort.Slice and sort.Strings. The sort package's own documentation recommends slices for new code. Two benchmarks that sort 10,000 books by price:

func BenchmarkSortSlice(b *testing.B) {
    src := shuffled()
    books := make([]catalog.Book, len(src))
    for b.Loop() {
        copy(books, src)
        sort.Slice(books, func(i, j int) bool { return books[i].Price < books[j].Price })
    }
}

$ go test -run '^$' -bench . -benchmem -cpu 1 -count 3 ./labs/17-sortbench
BenchmarkSortSlice          1315    868117 ns/op    152 B/op    3 allocs/op
BenchmarkSortSlice          1393    865762 ns/op    152 B/op    3 allocs/op
BenchmarkSortSlice          1326    897244 ns/op    152 B/op    3 allocs/op
BenchmarkSlicesSortFunc     1386    849663 ns/op      0 B/op    0 allocs/op
BenchmarkSlicesSortFunc     1431    946248 ns/op      0 B/op    0 allocs/op
BenchmarkSlicesSortFunc     1146    882797 ns/op      0 B/op    0 allocs/op

In this measurement the time difference stayed within the noise; Book is an 80-byte struct and most of the time goes into moving elements. The difference is in allocations: sort.Slice builds a swap function with reflection and allocates 3 times per call, the generic slices.SortFunc not at all. The real gain is readability: instead of sort.Slice's index-based less function, there is a comparison that takes two elements.

String sorting has one more trap: slices.Sort compares UTF-8 bytes, and Turkish letters are larger as bytes than every English letter:

func main() {
    authors := []string{"Zülfü Livaneli", "Şükrü Erbaş", "Sabahattin Ali", "Çetin Altan", "Cemal Süreya", "Ömer Seyfettin", "Orhan Pamuk", "İlhan Berk"}

    byteOrder := slices.Clone(authors)
    slices.Sort(byteOrder) // compares UTF-8 bytes
    fmt.Println(byteOrder)

    tr := collate.New(language.Turkish)
    trOrder := slices.Clone(authors)
    tr.SortStrings(trOrder)
    fmt.Println(trOrder)

    fmt.Println(tr.CompareString("ılık", "ilik"), tr.CompareString("Çay", "Cay"))
}

$ go run ./labs/17-collate
[Cemal Süreya Orhan Pamuk Sabahattin Ali Zülfü Livaneli Çetin Altan Ömer Seyfettin İlhan Berk Şükrü Erbaş]
[Cemal Süreya Çetin Altan İlhan Berk Orhan Pamuk Ömer Seyfettin Sabahattin Ali Şükrü Erbaş Zülfü Livaneli]
-1 1

In byte order, Çetin Altan fell behind Zülfü Livaneli. golang.org/x/text/collate applies the Turkish alphabetical order: Ç after C, Ö after O, ı and i as separate letters. The Go team keeps this module outside the standard library; in Bookstore it was an indirect dependency so far, became a direct one with this lab, and was upgraded to the latest release (v0.44.0). Use a collator for Turkish lists shown to users, such as author lists; for machine values such as keys, ISBNs and codes, byte order is right and much faster.

Production Notes

Make the sort stable and complete in every paged list. Adding a unique field (ISBN, order number) after the fields the user asked for reliably stops equal records from moving between pages. For lists from the database, ORDER BY ... , Isbn does the same job.

Check a sort parameter from outside against a whitelist. The bookOrders map is both the whitelist and the implementation; on the SQL side, putting the sort field into the query by concatenating strings opens the door to the SQL injection from post 11.

Measure allocations on large slices. slices.Clone, Collect and Sorted allocate a new slice every time; on a hot path, sorting in place and giving capacity up front with make([]T, 0, n) reduce the load on the GC.

Common Pitfalls

Appending from two places to a slice whose capacity is not full. Both write to the same array; separate the slice you hand out with slices.Clip or Clone.

Relying on map iteration order. The test passes in one run and fails in the next; if you need an order, use slices.Sorted(maps.Keys(m)).

Using slices.SortFunc for a paged list. The order of equal elements can change; use SortStableFunc and a unique last field.

Using the old slice after slices.Delete. The last elements have been zeroed; assign the returned value.

Sorting a Turkish list with slices.Sort. Ç, Ö, Ş and İ go to the end of the list; use x/text/collate.

A Small Experiment

★☆☆ Add an isbn field to GET /api/books?sort= and make SortBooks append isbn to every spec by itself. Does the tie row in the table test still pass, and why?

★★☆ In labs/17-linq, write a generic CountBy[K comparable, V any](seq iter.Seq[V], key func(V) K) map[K]int, the counterpart of LINQ's CountBy, and print the number of books per category in sorted order.

★★★ Add ?sort=name to GET /api/authors and do the sorting with collate.New(language.Turkish). Measure the cost of creating the collator on every request with a benchmark; check in its documentation whether a collate.Collator can be used from several goroutines at once.

We sorted, grouped and searched, but the data was always in memory. The next post moves to files: the io.Reader and io.Writer interfaces, reading line by line with bufio, encoding/csv, and the embed promised in post 11.