golang/go

proposal: Add ordered_list (Order-Statistic Tree) to container Package in Go

Closed this issue · 1 comments

Mostafa-Khairy0 commented

Proposal Details

Proposal: Add ordered_list (Order-Statistic Tree) to container Package in Go

Author: Mostafa Khairy (proposal draft)
Goal: Add an ordered_list implementation (Order-Statistic Tree — OST) to the standard container family to provide an efficient, well-tested data structure that supports indexed access and order statistics in O(log n) time.

🧩 Problem Statement / Motivation

The Go container package currently includes heap, list, and ring.
However, none of these provide:

  • Fast indexed access by rank (e.g., “get the k-th smallest element”)
  • Fast computation of the rank of an existing key
  • Efficient ordered splits/joins
  • Stable O(log n) insertion and deletion while maintaining sorted order

Developers often need structures that maintain sorted sequences with fast selection and ranking — for example:

  • Maintaining a sorted leaderboard
  • Implementing paginated ordered sets
  • Querying median or percentile values dynamically
  • Supporting algorithms requiring the k-th element efficiently

An Order-Statistic Tree (a balanced BST like a Red-Black Tree or AVL tree, augmented with subtree sizes) naturally supports Select(k) and Rank(key) in O(log n) time.

Adding a canonical, well-documented implementation to Go’s standard library would reduce fragmentation and improve reliability.

🎯 Design Goals

  1. Performance: O(log n) for insert, delete, select, and rank.
  2. Simplicity: A minimal, idiomatic API consistent with other container types.
  3. Type Safety: Support for generics (Go 1.18+).
  4. Deterministic Iteration: Ordered traversal from smallest to largest.
  5. Non-Concurrent by Default: No internal synchronization.
  6. Compact API Surface: Only essential methods.
  7. Well Tested and Benchmarked.

📦 Proposed Package Name

  • Option A (Recommended): container/ordered
  • Option B: container/ost

This proposal uses container/ordered in examples.

🧱 Proposed API

package ordered

// OrderedList[T] is an order-statistic tree of values of type T.
type OrderedList[T any] struct {}

// Less defines the comparator function used to maintain order.
type Less[T any] func(a, b T) bool

// New creates an empty OrderedList with the specified comparator.
func New[T any](less Less[T]) *OrderedList[T]

// Insert adds a value to the list (duplicates allowed).
func (ol *OrderedList[T]) Insert(value T)

// RemoveOne deletes one instance of value if it exists.
func (ol *OrderedList[T]) RemoveOne(value T) bool

// RemoveAt removes the element at index i and returns it.
func (ol *OrderedList[T]) RemoveAt(i int) T

// Get returns the element at index i.
func (ol *OrderedList[T]) Get(i int) T

// Rank returns the number of elements strictly less than value.
func (ol *OrderedList[T]) Rank(value T) int

// Len returns the total number of elements.
func (ol *OrderedList[T]) Len() int

// Min and Max return the smallest and largest elements respectively.
func (ol *OrderedList[T]) Min() T
func (ol *OrderedList[T]) Max() T

// Iterate traverses elements in ascending order.
func (ol *OrderedList[T]) Iterate(fn func(i int, v T) bool)

// Clear removes all elements.
func (ol *OrderedList[T]) Clear()
seankhliao commented

see https://go.dev/doc/faq#x_in_std
right now there's no evidence that there's a strong need for this across the ecosystem.