proposal: add tree-based OrderedMap/OrderedSet

[leaxoy]

There are at least several thousand related implementations OrderedMap/OrderedSet, although we have generics, there are no related containers in the standard library, so people have to implement their own sorting containers.

So I propose add OrderedMap/OrderedSet into std, maybe container package is a suitable place.

The main API are:

type OrderedMap[K, V any] struct{ /* private fields */ }

// Constructor function
func NewOrderedMap[K, V any](cmp func(K, K) int) *OrderedMap[K, V] {}

// And Ordered type version, but the name is a bit long 😂
func NewOrderedMapOfOrderedType[K cmp.Ordered, V any]() *OrderedMap[K, V] {
    return NewOrderedMap(cmp.Compare[K])
}

// Method set
// Insert new pair and return previous value if present.
func (m *OrderedMap[K, V]) Insert(k K, v V) (V, bool) {}
// Get get value associated with k, else return empty and false.
func (m *OrderedMap[K, V]) Get(k K) (V, bool) {}
// Contains judge k in OrderedMap ?
func (m *OrderedMap[K, V]) Contains(k K) bool {}
// Delete entry by key and return stored value if present.
func (m *OrderedMap[K, V]) Delete(k K) (V, bool) {}
// Keys return all keys in ascending order.
func (m *OrderedMap[K, V]) Keys() []K {}
// Values return all values in ascending order by key.
func (m *OrderedMap[K, V]) Values() []V {}
// Clear clear the whole map.
func (m *OrderedMap[K, V]) Clear() {}
// Retain will keep those entry which satisfy the given predicate function.
func (m *OrderedMap[K, V]) Retain(f func(K, V) bool) {}
// Len return number of entries of map
func (m *OrderedMap[K, V]) Len() int {}
// First return the minimum entry.
func (m *OrderedMap[K, V]) First() (Entry[K, V], bool) {}
// Last return the maximum entry.
func (m *OrderedMap[K, V]) Last() (Entry[K, V], bool) {}
// Reverse reverse order of all entries.
func (m *OrderedMap[K, V]) Reverse() *Ordered[K, V] {}
// Merge with another OrderedMap, if key exists, replace it
func (m *OrderedMap[K, V]) Merge(o *OrderedMap[K, V]) {}
// SubMap copy entries between start and end to a new OrderedMap.
func (m *OrderedMap[K, V]) SubMap(start K, end K) *OrderedMap[K, V] {}

// Iter API should after it landing in go.
// ForEach iterate over all entries in the map.
func (m *OrderedMap[K, V]) ForEach(f func(K, V) bool) {}
// Range iterate over range [start, end), this maybe replaced by [SubMap]
func (m *OrderedMap[K, V]) Range(start K, end K, f func(K, V)) {}

// Wrapper of OrderedMap with unit value.
type OrderedSet[T any] struct{ inner *OrderedMap[T, struct{}] }

// Constrcutor function
func NewOrderedSet[T any](cmp func(T, T) int) *OrderedSet[T] {}

// Method set
func (s *OrderedSet[T]) Contains(v T) bool {}
func (s *OrderedSet[T]) ContainsAll(elems ...T) bool {}
func (s *OrderedSet[T]) ContainsAny(elems ...T) bool {}
func (s *OrderedSet[T]) Insert(v T) {}
func (s *OrderedSet[T]) InsertMany(elems ...T) {}
func (s *OrderedSet[T]) Delete(elems ...T) {}
func (s *OrderedSet[T]) First() (T, bool) {}
func (s *OrderedSet[T]) Last() (T, bool) {}
func (s *OrderedSet[T]) Reverse() *OrderedSet[T] {}
func (s *OrderedSet[T]) Len() int {}
func (s *OrderedSet[T]) Retain(f func(T) bool) {}
func (s *OrderedSet[T]) SuperSetOf(o *OrderedSet[T]) bool {}
func (s *OrderedSet[T]) SubSetOf(o *OrderedSet[T]) bool {}
func (s *OrderedSet[T]) InterSection(o *OrderedSet[T]) *OrderedSet[T] {}
func (s *OrderedSet[T]) UnionInPlace(o *OrderedSet[T]) {}
func (s *OrderedSet[T]) Union(o *OrderedSet[T]) *OrderedSet[T] {}
func (s *OrderedSet[T]) Difference(o *OrderedSet[T]) *OrderedSet[T] {}
func (s *OrderedSet[T]) SymmetricDifference(o *OrderedSet[T]) *OrderedSet[T] {}

// Iter API should after it landing in go.
func (s *OrderedSet[T]) ForEach(f func(T)) {}

Appendix A

1. In C++, there are ordered_set/ordered_set based on rb-tree
2. In Java, there are SortedMap and SortedSet.
3. In Rust, there are BTreeMap and BTreeSet

Appendix B

If we land sum type in go, those return a bool flag would be instead by Option or Maybe, it's intuitive and more suitable.
Sum type is more suitable than Product Type here.

Appendix C

Since Iter should be a separate issue, so this proposal would not include Iter api. So move Iter API to end of section.

[ianlancetaylor]

1. We aren't going to add any general purpose containers until we have an idea of how to implement iterators, aka how to find all the elements in the container. Iterators are pending resolution of #56413, which itself is pending the forward/backward compatibility work that will be part of Go 1.21.
2. This should perhaps be a discussion first.

[carlmjohnson]

There's already a set proposal that is snagged on iteration. This seems related to that. This could be containers/ordered.Set and containers/ordered.Map and have overlapping methods with containers/set.

[leaxoy]

1. We aren't going to add any general purpose containers until we have an idea of how to implement iterators, aka how to find all the elements in the container. Iterators are pending resolution of user-defined iteration using range over func values #56413, which itself is pending the forward/backward compatibility work that will be part of Go 1.21.
2. This should perhaps be a discussion first.

@ianlancetaylor I'm agree that Iter is a important feature to iterate over all element in container as you explained, but there also many features does't relay on Iter, such as: map.Get/Insert/Delete/Contains/Clear/IsEmpty/First/Last and set.Insert(Many)/Contains(All/Any)/Delete/Clear/IsEmpty. They are useful in many scenarios.

A benefit is map's Key and set's Elem can any type, not limited to cmp.Ordered.

For those internal maybe relay on Iter, like set.SuperSetOf/SubSetOf/Difference/Union/InterSection and map.Merge/Keys/Values, not exposing implementation details can leave room for the introduction of Iter later.

The rest are Iter related, like: Iter can be ecognized by the compiler and can be used in for-loop, and iterate operations can based on this, including but not limited to ForEach/Map/Filter/Reduce/Fold/Max/Min/AllOf/AnyOf/Take/Skip/Cmp/Zip/Unzip/Chunk/GroupBy ...

At least for CPP, operations on containers can be split into several parts, Iterators/Element Access/Capacity/Modifiers/List Operations/Lookup.. at Containers, Iterators works with std::ranges.

If I understand correctly, what you care about above is the Iterators part