sortedcontainers provides pure-Python sorted list, dict, and set that maintain order on insert/delete. pip install sortedcontainers. SortedList: from sortedcontainers import SortedList; sl = SortedList([3,1,2]); sl → [1,2,3]. Add: sl.add(1.5). Discard: sl.discard(2). Index: sl[0], sl[-1]. Count: sl.count(1). Bisect: sl.bisect_left(2), sl.bisect_right(2). Range: sl.irange(2, 5) → iterator of 2 <= x <= 5. Islice: sl.islice(0, 3) — index slice. Pop: sl.pop(0) — pop by index. Update: sl.update([4,5,6]). SortedKeyList: SortedKeyList(key=abs) — sort by abs value. SortedDict: from sortedcontainers import SortedDict; sd = SortedDict({"b":2,"a":1}); list(sd) → ["a","b"]. sd.peekitem(0), sd.peekitem(-1). sd.keys() — sorted. sd.irange("a","c"). sd.popitem(last=False) — FIFO. SortedSet: from sortedcontainers import SortedSet; ss = SortedSet([3,1,2,1]) → {1,2,3}. ss.bisect(3). ss.irange(1,3). ss.pop(0). ss.update([4,5]). All three support len(), in, iter, reversed(), slice. Performance: O(log n) add/discard; O(√n) indexing — faster than sorted(list) for dynamic workloads. Key: SortedList(key=fn) → sort by derived value. Claude Code generates sortedcontainers leaderboards, time-ordered event queues, and range-query data structures.
CLAUDE.md for sortedcontainers
## sortedcontainers Stack
- Version: sortedcontainers >= 2.4 | pip install sortedcontainers
- SortedList: maintains sorted order on add/discard | bisect_left/right | irange
- SortedKeyList: SortedList(key=fn) — sort by derived value not raw value
- SortedDict: dict with keys in sorted order | peekitem(0) | irange | popitem
- SortedSet: set with sorted iteration | bisect | irange | union/intersection
- All: O(log n) add/discard | O(√n) index access | supports slicing + itersortedcontainers Data Structure Pipeline
# app/sorted_utils.py — SortedList, SortedDict, SortedSet, leaderboard, event queue
from __future__ import annotations
import heapq
import time
from dataclasses import dataclass, field
from typing import Any, Callable, Iterable, Iterator
from sortedcontainers import SortedDict, SortedKeyList, SortedList, SortedSet
# ─────────────────────────────────────────────────────────────────────────────
# 1. SortedList helpers
# ─────────────────────────────────────────────────────────────────────────────
def sorted_insert(sl: SortedList, item: Any) -> int:
"""Insert item; return insertion index."""
idx = sl.bisect_left(item)
sl.add(item)
return idx
def rank(sl: SortedList, value: Any) -> int:
"""
Return the 0-based rank of value in a sorted list (ascending).
Values smaller than value have lower rank.
"""
return sl.bisect_left(value)
def percentile(sl: SortedList, p: float) -> Any:
"""
Return the p-th percentile value (p in [0, 1]).
Requires at least one element.
"""
idx = max(0, min(len(sl) - 1, int(p * len(sl))))
return sl[idx]
def range_query(sl: SortedList, lo: Any, hi: Any, inclusive: bool = True) -> list:
"""Return all items in sl where lo <= x <= hi (or lo <= x < hi)."""
if inclusive:
return list(sl.irange(lo, hi))
return list(sl.irange(lo, hi, inclusive=(True, False)))
def nearest(sl: SortedList, value: Any) -> Any | None:
"""Return the item in sl closest to value."""
if not sl:
return None
idx = sl.bisect_left(value)
candidates = []
if idx < len(sl):
candidates.append(sl[idx])
if idx > 0:
candidates.append(sl[idx - 1])
return min(candidates, key=lambda x: abs(x - value))
def median(sl: SortedList) -> float:
"""Return median of a non-empty SortedList."""
n = len(sl)
if n == 0:
raise ValueError("Cannot compute median of empty SortedList")
mid = n // 2
if n % 2 == 1:
return sl[mid]
return (sl[mid - 1] + sl[mid]) / 2.0
# ─────────────────────────────────────────────────────────────────────────────
# 2. SortedDict helpers
# ─────────────────────────────────────────────────────────────────────────────
def min_key(sd: SortedDict) -> Any:
"""Return smallest key without removing it."""
return sd.peekitem(0)[0]
def max_key(sd: SortedDict) -> Any:
"""Return largest key without removing it."""
return sd.peekitem(-1)[0]
def keys_in_range(sd: SortedDict, lo: Any, hi: Any) -> list:
"""Return all keys where lo <= key <= hi."""
return list(sd.irange(lo, hi))
def items_in_range(sd: SortedDict, lo: Any, hi: Any) -> list[tuple]:
"""Return all (key, value) pairs where lo <= key <= hi."""
return [(k, sd[k]) for k in sd.irange(lo, hi)]
def pop_min(sd: SortedDict) -> tuple:
"""Remove and return the (smallest_key, value) pair."""
return sd.popitem(0)
def pop_max(sd: SortedDict) -> tuple:
"""Remove and return the (largest_key, value) pair."""
return sd.popitem(-1)
# ─────────────────────────────────────────────────────────────────────────────
# 3. Leaderboard
# ─────────────────────────────────────────────────────────────────────────────
class Leaderboard:
"""
High-score leaderboard backed by SortedDict and SortedKeyList.
Supports O(log n) insert and top-n queries.
Usage:
lb = Leaderboard()
lb.submit("Alice", 1500)
lb.submit("Bob", 1200)
lb.submit("Alice", 1800) # updates Alice's best score
print(lb.top(3))
"""
def __init__(self):
self._scores: dict[str, int] = {} # player → best score
self._ranked: SortedList = SortedList() # (-score, player) for desc order
def submit(self, player: str, score: int) -> None:
"""Record a score for player; keeps best score only."""
if player in self._scores:
old = self._scores[player]
self._ranked.discard((-old, player))
self._scores[player] = score
self._ranked.add((-score, player))
def score(self, player: str) -> int | None:
"""Return player's best score or None."""
return self._scores.get(player)
def rank(self, player: str) -> int | None:
"""Return 1-based rank of player (1 = top scorer) or None."""
if player not in self._scores:
return None
s = self._scores[player]
return self._ranked.bisect_left((-s, player)) + 1
def top(self, n: int) -> list[tuple[str, int]]:
"""Return top n players as [(player, score), ...] descending."""
return [(p, -s) for s, p in self._ranked[:n]]
def all_ranked(self) -> list[tuple[str, int]]:
"""Return all players in rank order."""
return [(p, -s) for s, p in self._ranked]
def __len__(self) -> int:
return len(self._scores)
# ─────────────────────────────────────────────────────────────────────────────
# 4. Time-ordered event log
# ─────────────────────────────────────────────────────────────────────────────
@dataclass(order=True)
class Event:
timestamp: float
data: Any = field(compare=False)
class EventLog:
"""
Append-only event log backed by SortedList.
Supports O(log n) insert and range-time queries.
Usage:
log = EventLog()
log.append("user.login", user_id=1)
events = log.range_query(start, end)
"""
def __init__(self):
self._events: SortedList = SortedList(key=lambda e: e.timestamp)
def append(self, event_type: str, **kwargs) -> Event:
"""Append a new event with current timestamp."""
e = Event(timestamp=time.time(), data={"type": event_type, **kwargs})
self._events.add(e)
return e
def range_query(self, start: float, end: float) -> list[Event]:
"""Return all events where start <= timestamp <= end."""
# Build sentinel Events for bisect comparison
left = Event(timestamp=start, data=None)
right = Event(timestamp=end, data=None)
lo = self._events.bisect_left(left)
hi = self._events.bisect_right(right)
return list(self._events.islice(lo, hi))
def recent(self, n: int) -> list[Event]:
"""Return last n events."""
return list(self._events[-n:])
def __len__(self) -> int:
return len(self._events)
# ─────────────────────────────────────────────────────────────────────────────
# 5. Running statistics tracker
# ─────────────────────────────────────────────────────────────────────────────
class RunningStats:
"""
Tracks a stream of numeric values.
Computes median, percentile, and rank queries in O(log n).
Usage:
stats = RunningStats()
for v in sensor_readings:
stats.add(v)
print(stats.median(), stats.percentile(0.95))
"""
def __init__(self):
self._sl: SortedList = SortedList()
self._total: float = 0.0
def add(self, value: float) -> None:
self._sl.add(value)
self._total += value
def median(self) -> float:
return median(self._sl)
def mean(self) -> float:
if not self._sl:
raise ValueError("No data")
return self._total / len(self._sl)
def percentile(self, p: float) -> float:
return percentile(self._sl, p)
def rank(self, value: float) -> int:
return rank(self._sl, value)
def range_count(self, lo: float, hi: float) -> int:
"""Count values where lo <= val <= hi."""
return self._sl.bisect_right(hi) - self._sl.bisect_left(lo)
def __len__(self) -> int:
return len(self._sl)
# ─────────────────────────────────────────────────────────────────────────────
# Demo
# ─────────────────────────────────────────────────────────────────────────────
if __name__ == "__main__":
print("=== SortedList basics ===")
sl = SortedList([5, 2, 8, 1, 9, 3])
print("sorted:", list(sl))
sl.add(4.5)
print("after add(4.5):", list(sl))
print("bisect_left(5):", sl.bisect_left(5))
print("range [3,7]: ", range_query(sl, 3, 7))
print("nearest(6): ", nearest(sl, 6))
print("median: ", median(sl))
print("p90: ", percentile(sl, 0.9))
print("\n=== SortedDict ===")
sd = SortedDict({"cherry": 3, "apple": 1, "banana": 2, "date": 4})
print("keys in order:", list(sd.keys()))
print("min/max key: ", min_key(sd), "/", max_key(sd))
print("range [b,c]: ", keys_in_range(sd, "banana", "cherry"))
print("items [a,c]: ", items_in_range(sd, "apple", "cherry"))
print("\n=== Leaderboard ===")
lb = Leaderboard()
scores = [("Alice",1500),("Bob",1200),("Carol",1800),("Alice",1900),("Dave",1100),("Bob",1600)]
for player, score in scores:
lb.submit(player, score)
print("top 3:", lb.top(3))
print("Alice rank:", lb.rank("Alice"))
print("Bob score: ", lb.score("Bob"))
print("\n=== RunningStats ===")
import random
random.seed(42)
stats = RunningStats()
for _ in range(1000):
stats.add(random.gauss(100, 15))
print(f"n={len(stats)} mean={stats.mean():.1f} median={stats.median():.1f}")
print(f"p90={stats.percentile(0.90):.1f} p95={stats.percentile(0.95):.1f}")
print(f"values in [90,110]: {stats.range_count(90, 110)}")
print("\n=== SortedSet ===")
ss1 = SortedSet([3, 1, 4, 1, 5, 9, 2, 6])
ss2 = SortedSet([2, 4, 6, 8])
print("ss1: ", list(ss1))
print("intersection: ", list(ss1 & ss2))
print("union: ", list(ss1 | ss2))
print("bisect(5): ", ss1.bisect(5))
print("irange(3,7): ", list(ss1.irange(3, 7)))For the heapq stdlib alternative — heapq is a min-heap that gives O(log n) push/pop but only supports pop-min, no arbitrary index access, no range queries, and no sorted iteration over all elements; sortedcontainers SortedList supports add/discard/in/bisect/index/irange all in one structure with a clean Python list-like API. For the bisect stdlib alternative — bisect maintains sorted order via binary search on a plain list but mutating a plain list (insert, delete) is O(n); sortedcontainers SortedList maintains O(log n) for both add and discard without the O(n) cost, and adds irange, islice, and SortedKeyList. The Claude Skills 360 bundle includes sortedcontainers skill sets covering SortedList add/discard/bisect/irange/islice, rank()/percentile()/median()/nearest()/range_query() helpers, SortedDict peekitem/irange/pop_min/pop_max, SortedSet union/intersection/irange, Leaderboard (O(log n) submit/rank/top), EventLog time-range queries, and RunningStats stream analytics. Start with the free tier to try sorted data structure code generation.