README
¶
flatset
This is a golang module that provides the sorted associative containers 'FlatSet' and 'FlatMultiSet' (similar to C++ std::flat_set and std::flat_multiset).
These containers store their data in contiguous memory instead of using a traditional binary-tree structure or hash-table.
This has many advantages over standard associative containers:
- Faster lookup
- Much faster iteration
- Random-access to the underlying array
- Less memory consumption
- Improved cache performance
The disadvantages are:
- previous indices are invalidated following insertion or deletion.
- insertion can be slower, especially when inserting near the beginning of a large collection
The module implements an algorithm that can iterate over other types of containers, traversing the flatset so that it can be accessed and updated more efficiently than processing each value individually (making use of golang's 'range over functions' to do this).
Simple example
import (
"fmt"
"github.com/blackbox-tech/flatset"
)
func lessInt(lhs, rhs int) bool {
return lhs < rhs
}
func main() {
// insertion
a := flatset.NewFlatSet[int](lessInt)
a.Insert(8)
a.Insert(5)
a.Insert(10)
a.Insert(6)
// find and erase
idx := a.Find(6)
fmt.Printf("a contains %d at index %d\n", a.At(idx), idx)
a.Erase(idx)
fmt.Printf("a erased value at index %d\n", idx)
fmt.Printf("a contains 6 == %t\n", a.Contains(6))
// array intersection
b := flatset.InitFlatSet[int]([]int{6, 8, 10}, lessInt)
c := a.Intersection(b.All())
for value := range c.All() {
fmt.Printf("%d is in a and b\n", value)
}
}
Output:
a contains 6 at index 1
a erased value at index 1
a contains 6 == false
8 is in a and b
10 is in a and b
For more information see the API Reference
License
This project is licensed under the terms of the MIT license
Documentation
¶
Overview ¶
Package flatset provides the sorted associative containers 'FlatSet' and 'FlatMultiSet' that store data in continuous memory instead of a binary tree (similar to C++ std::flat_set and std::flat_multiset).
Both the FlatSet and FlatMultiSet implement stable ordering, but the previous indices for values are invalidated following an method that modifies the container.
Compared to a binary tree, flatsets are considerably faster to read as they avoid the cache misses from pointer referencing. On modern CPUs it is also surprisingly fast to insert into a flatset, especially if the collection is small, or if you frequently update the end of the flatset. For larger collections you can optimize write operations by using a flatset of pointers to structures instead of values, although you must be careful not to modify the data inside the flatset as it might affect how the data is sorted.
This package uses 'range over functions' so it requires golang >= 1.23
Index ¶
- type Compare
- type FlatMultiSet
- func (self *FlatMultiSet) All() iter.Seq[V]
- func (self *FlatMultiSet) At(index int) V
- func (self *FlatMultiSet) Backward() iter.Seq[V]
- func (self *FlatMultiSet) Clear()
- func (self *FlatMultiSet) Contains(value V) bool
- func (self *FlatMultiSet[V]) Erase(from, upto int)
- func (self *FlatMultiSet[V]) Find(value V) (int, int)
- func (self *FlatMultiSet) HasAll(values iter.Seq[V]) bool
- func (self *FlatMultiSet) HasAny(values iter.Seq[V]) bool
- func (self *FlatMultiSet[V]) Insert(value V) int
- func (self *FlatMultiSet) LowerBound(value V) int
- func (self *FlatMultiSet[V]) Merge(other *FlatMultiSet[V])
- func (self *FlatMultiSet[V]) Remove(value V) int
- func (self *FlatMultiSet[V]) Replace(index int, value V) bool
- func (self *FlatMultiSet) Size() int
- func (self *FlatMultiSet[V]) Update(values iter.Seq[V])
- func (self *FlatMultiSet) UpperBound(value V) int
- type FlatSet
- func (self *FlatSet) All() iter.Seq[V]
- func (self *FlatSet) At(index int) V
- func (self *FlatSet) Backward() iter.Seq[V]
- func (self *FlatSet) Clear()
- func (self *FlatSet) Contains(value V) bool
- func (self *FlatSet[V]) Difference(values iter.Seq[V]) *FlatSet[V]
- func (self *FlatSet[V]) Erase(index int)
- func (self *FlatSet[V]) Find(value V) int
- func (self *FlatSet) HasAll(values iter.Seq[V]) bool
- func (self *FlatSet) HasAny(values iter.Seq[V]) bool
- func (self *FlatSet[V]) Insert(value V) (int, bool)
- func (self *FlatSet[V]) Intersection(values iter.Seq[V]) *FlatSet[V]
- func (self *FlatSet) LowerBound(value V) int
- func (self *FlatSet[V]) Merge(other *FlatSet[V])
- func (self *FlatSet[V]) Remove(value V) bool
- func (self *FlatSet[V]) Replace(index int, value V) bool
- func (self *FlatSet) Size() int
- func (self *FlatSet[V]) Union(values iter.Seq[V]) *FlatSet[V]
- func (self *FlatSet[V]) Update(values iter.Seq[V])
- func (self *FlatSet) UpperBound(value V) int
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
This section is empty.
Types ¶
type Compare ¶
This is the interface for the comparison function that is passed to the FlatSet and FlatMultiSet which defines how the data will be sorted. For example, to sort the data in ascending order the comparison function would implement less than.
type FlatMultiSet ¶
type FlatMultiSet[V any] struct { // contains filtered or unexported fields }
A FlatMultiSet is a sorted associative container of values using a comparison function. Unlike a FlatSet, a FlatMultiSet allows equivalent values to be stored in the same container and order stability of these values is guaranteed.
func InitFlatMultiSet ¶
func InitFlatMultiSet[V any](values []V, cmp Compare[V]) *FlatMultiSet[V]
Create a new FlatMultiSet and initialize it with some values. The order of equivalent values will be maintained.
func MakeFlatMultiSet ¶ added in v0.1.2
func MakeFlatMultiSet[V any](cmp Compare[V]) FlatMultiSet[V]
Make an empty FlatMultiSet.
func NewFlatMultiSet ¶
func NewFlatMultiSet[V any](cmp Compare[V]) *FlatMultiSet[V]
Create a new empty FlatMultiSet.
func (*FlatMultiSet) At ¶
func (self *FlatMultiSet) At(index int) V
Returns a copy of the value at the given index.
func (*FlatMultiSet) Backward ¶ added in v0.2.0
Returns an iterator that iterates in reverse order returning a copy of each value.
func (*FlatMultiSet) Clear ¶ added in v0.2.1
func (self *FlatMultiSet) Clear()
Efficiently empty the set keeping any previously allocated memory for future insertions.
func (*FlatMultiSet) Contains ¶
func (self *FlatMultiSet) Contains(value V) bool
Returns true if this container has this value or false if it does not.
func (*FlatMultiSet[V]) Erase ¶
func (self *FlatMultiSet[V]) Erase(from, upto int)
Delete values from this index (inclusive) upto this index (exclusive) from this container. If from == -1 this method is a no-op in order that you can pass the indices from Find as arguments. This method will invalidate any previous indices.
func (*FlatMultiSet[V]) Find ¶
func (self *FlatMultiSet[V]) Find(value V) (int, int)
Searches for equivalent values within this container, it will return the index of the first value (inclusive) and index of the last value exclusive(). If no equivalent value is found this method will return -1, -1.
func (*FlatMultiSet) HasAll ¶ added in v0.2.0
This method takes an iterator and returns true if this container is a superset of these values.
func (*FlatMultiSet) HasAny ¶ added in v0.2.0
This method takes an iterator and will returns true if any of these equivalent values are contained within this container.
func (*FlatMultiSet[V]) Insert ¶
func (self *FlatMultiSet[V]) Insert(value V) int
Insert a new value at the upper bound and return the index of the new value. This method will invalidate any previous indices.
func (*FlatMultiSet) LowerBound ¶
func (self *FlatMultiSet) LowerBound(value V) int
Returns an index to the first value in the range where the comparison is not less than.
func (*FlatMultiSet[V]) Merge ¶
func (self *FlatMultiSet[V]) Merge(other *FlatMultiSet[V])
Append another FlatMultiSet into this one. It is also possible to merge FlatMultiSets that have a different comparison function. Values from the other container will be inserted at the upper bound so equivalent values will be ordered after the one in this container other ones. This method is similar but more efficient than Update because it is able to preallocate the array. This method will invalidate any previous indices.
func (*FlatMultiSet[V]) Remove ¶
func (self *FlatMultiSet[V]) Remove(value V) int
Delete any values equivalent to this value and return the number of values that were removed. This method will invalidate any previous indices.
func (*FlatMultiSet[V]) Replace ¶
func (self *FlatMultiSet[V]) Replace(index int, value V) bool
Try to replace the value at this index. If the previous value was replaced return true, otherwise return false if the new value would result in data being out of sequence. This method allow you to quickly modify a value if you know its index, without the need to erase the previous value and insert the new one. This method will not invalidate previous indices.
func (*FlatMultiSet) Size ¶
func (self *FlatMultiSet) Size() int
Returns the number of values stored in this container.
func (*FlatMultiSet[V]) Update ¶
func (self *FlatMultiSet[V]) Update(values iter.Seq[V])
Insert these values into this container at the upper bound to maintain order stability. This method is more flexible but less efficient than Merge because it takes a generic iterator of values. This method updates this container so it will invalidate any previous indices.
func (*FlatMultiSet) UpperBound ¶
func (self *FlatMultiSet) UpperBound(value V) int
Returns an index to the first value in the range where the comparison is greater.
type FlatSet ¶
type FlatSet[V any] struct { // contains filtered or unexported fields }
A FlatSet is a sorted associative container of unique values using a comparison function.
func InitFlatSet ¶
Create a new FlatSet and initialize it with some values. Values that are repeated will be discarded.
func MakeFlatSet ¶ added in v0.1.2
Make an empty FlatSet.
func (*FlatSet) At ¶
func (self *FlatSet) At(index int) V
Returns a copy of the value at the given index.
func (*FlatSet) Backward ¶ added in v0.2.0
Returns an iterator that iterates in reverse order returning a copy of each value.
func (*FlatSet) Clear ¶ added in v0.2.1
func (self *FlatSet) Clear()
Efficiently empty the set keeping any previously allocated memory for future insertions.
func (*FlatSet) Contains ¶
func (self *FlatSet) Contains(value V) bool
Returns true if this container has this value or false if it does not.
func (*FlatSet[V]) Difference ¶
Return a new FlatSet containing the values that exist in this container but not in these other values. This method does not modify this container so it will not invalidate previous indices.
func (*FlatSet[V]) Find ¶
Searches for a value within this container, and returns the index for the location of the value or -1 if not found.
func (*FlatSet) HasAll ¶ added in v0.2.0
This method takes an iterator and returns true if this container is a superset of these values.
func (*FlatSet) HasAny ¶ added in v0.2.0
This method takes an iterator and will returns true if any of these equivalent values are contained within this container.
func (*FlatSet[V]) Insert ¶
Insert a new value. If this value is already contained within this container it will return the index of the existing value and false, otherwise it will return the index of the new value and true. If insertion is successful it will invalidate any previous indices.
func (*FlatSet[V]) Intersection ¶
Return a new FlatSet containing the common values in this container with these other values. To maintain order stability the original values from this container will be returned. This method does not modify this container so it will not invalidate previous indices.
func (*FlatSet) LowerBound ¶
func (self *FlatSet) LowerBound(value V) int
Returns an index to the first value in the range where the comparison is not less than.
func (*FlatSet[V]) Merge ¶
Append another FlatSet into this one. It is also possible to merge FlatSets that have a different comparison function. If a value already exists in this container the new value from the other FlatSet will be discarded to maintain order stability. This method is similar but more efficient than Update because it is able to preallocate the array. This method updates this container so it will invalidate any previous indices.
func (*FlatSet[V]) Remove ¶
Remove this value if it exists in this container and return true, otherwise return false if it was not found.
func (*FlatSet[V]) Replace ¶
Try to replace the value at this index. If the previous value was replaced return true, otherwise return false if the new value would result in data being out of sequence. This method allow you to quickly modify a value if you know its index, without the need to erase the previous value and insert the new one. This method will not invalidate previous indices.
func (*FlatSet) Size ¶
func (self *FlatSet) Size() int
Returns the number of values stored in this container.
func (*FlatSet[V]) Union ¶
Return a new FlatSet combining all the values in this container with these other values. If a value already exists in the new value will not be included in the resulting FlatSet. This method does not modify this container so it will not invalidate previous indices.
func (*FlatSet[V]) Update ¶
Insert these values into this container. This method is more flexible but less efficient than Merge because it takes a generic iterator of values. If a value already exists in this container the new value will be discarded to maintain order stability. This method updates this container so it will invalidate any previous indices.
func (*FlatSet) UpperBound ¶
func (self *FlatSet) UpperBound(value V) int
Returns an index to the first value in the range where the comparison is greater.
Source Files