Interface¶
slist from initializer list¶
slist({1,2,3,4})
Precondition: All the elements in the list must have the same type.
slist_from_container¶
slist_from_container (C)
Requires C be an STL container with a begin() method returning an input iterator and an end() method returning an end iterator. Returns a list of all the elements in the container in the sequence found from the iterator.
slist_from_iterators¶
slist_from_iterators<T> (begin,end)
Requires begin, end be valid iterators for a sequence. Returns all the values in the range of the begin iterator up to but excluding the end iterator. T::value_type must specify the container value type.
uniq¶
uniq(x)
x.uniq()
Returns true if x s empty or is the only reference to the underlying list and all tails thereof. Implies the reference counts of all nodes of the underlying list are 1.
cons¶
cons (h,t)
t.cons(h)
returns list t with value h added to front. Unique if and only if t is unique.
tail¶
tail (x)
x.tail()
Precondition non-empty list. Returns list with first value removed. Unique if x is unique, may be unique even if x is not.
join¶
join (x,y)
x + y
Returns the list which is the concatenation of lists x and y. Unique if y is unique.
make_unique¶
TODO. Returns the list if it is unique, or a copy otherwise. Result is always unique.
map¶
map<U> (f,x)
x.map(f)
Returns a list with elements of type U, the result of applying f to each element of x. Always unique. Cost N allocations.
filter¶
filter (f,x)
x.filter(f)
Returns a sublist of elements of x satifying predicate f(v). Always unique.
fold_left¶
fold_left (f,init,x)
TODO. Uses f to fold each value of x starting at the front into init. Returns final result. f must accept two arguments, the first of type U, the type of init, and the second of type T, the type of the elements of x.
zip¶
zip(x,y)
TODO. Precondition, x and y have the same length. Returns a list of std::pair of corresponding element from x and y.
unzip¶
unzip(x)
TODO. Splits a list of pairs into a pair of lists. Precondition, the value type of x must be a std::pair.
begin¶
x.begin()
Returns forward list iterator starting at head of list. This iterator uses a strong pointer to the head of the list but scans the list using a weak pointer, avoiding the overhead of managing the reference count at the expense of retaining the whole list during the scan.
begin_input¶
x.begin_input()
Returns input list iterator starting at the head of the list. This iterator uses a strong pointer to scan the list. Reference counts are adjusted during the scan. If the list is unique, then a scan will consume the list, freeing memory during the scan.
get_back_inserter¶
x.get_back_inserter()
Fetches an output iterator for the list x. The list should be unique. If not, the handle x detaches its current list and is set to a copy, making it unique. A prefix of the previous list may be lost because the head node’s refcount is decremented. Note the whole list cannot be lost because it would have to be unique for that to happen, there must be at least one other reference to some non-empty suffix of the list.
Writes to the output iterator append elements to the end of the list. The pre-increment and post-increment operators have no effect. The dereference operator returns a proxy which accepts an assignment from the list value type, which causes a new node to be appended to the end of the list and the output iterator then advances.
Note, the iterator returned by this method is faster than
std::back_inserter(x)
however at present it is not fully safe. If the iterator is retained and the list shared, subsequent insertions will also be shared.