SortedSet

SortedContainers is an Apache2 licensed Python sorted collections library, written in pure-Python, and fast as C-extensions. SortedSet API documentation is detailed below. The introduction is the best way to get started.

SortedSet(iterable=None, load=1000, _set=None):

A SortedSet provides the same methods as a set. Additionally, a SortedSet maintains its items in sorted order, allowing the SortedSet to be indexed.

An optional iterable provides an initial series of items to populate the SortedSet.

An optional key argument defines a callable that, like the key argument to Python’s sorted function, extracts a comparison key from each set item. If no function is specified, the default compares the set items directly.

An optional load specifies the load-factor of the set. The default load factor of ‘1000’ works well for sets from tens to tens of millions of elements. Good practice is to use a value that is the square or cube root of the set size. With billions of elements, the best load factor depends on your usage. It’s best to leave the load factor at the default until you start benchmarking. See implementation details for more information.

Unlike a set, a SortedSet requires items be hashable and comparable. SortedSet implements the MutableSet and Sequence Abstract Base Class types.

x in S

Return True if and only if x is an element in the set.

Return type:bool
del S[i]

Remove the element located at index i from the set.

del S[i:j]

Remove the elements from i to j from the set.

S < S2

Test whether the set is a proper subset of S2, that is, S <= S2 and S != other.

Return type:bool
S > S2

Test whether the set is a proper superset of S2, that is, S >= S2 and S != S2.

Return type:bool
S[i]

Return the element at position i.

Return type:item
S[i] = v

Remove the element located at index i from the set and insert element v. Supports slice notation. Raises a ValueError if the sort order would be violated.

S[i:j]

Return a new SortedSet containing the elements from i to j.

Return type:SortedSet
sortedcontainers.iter(S)

Return an iterator over the Set. Elements are iterated in their sorted order.

Iterating the Set while adding or deleting values may raise a RuntimeError or fail to iterate over all entries.

Return type:iterator
sortedcontainers.len(S)

Return the number of elements in the set.

Return type:int
sortedcontainers.reversed(S)

Return an iterator over the Set. Elements are iterated in their reverse sorted order.

Iterating the Set while adding or deleting values may raise a RuntimeError or fail to iterate over all entries.

Return type:iterator
S.add(value)

Add the element value to the set.

L.bisect_left(value)

Similar to the bisect module in the standard library, this returns an appropriate index to insert value in L. If value is already present in L, the insertion point will be before (to the left of) any existing entries.

Return type:int
L.bisect(value)

Same as bisect_right.

Return type:int
L.bisect_right(value)

Same as bisect_left, but if value is already present in L, the insertion point will be after (to the right of) any existing entries.

Return type:int
d.bisect_key_left(key)

Similar to the bisect module in the standard library, this returns an appropriate index to insert a value with a given key. If values with key are already present, the insertion point will be before (to the left of) any existing entries. This method is present only if the sorted set was constructed with a key function.

Return type:int
d.bisect_key(key)

Same as bisect_key_right.

Return type:int
d.bisect_key_right(key)

Same as bisect_key_left, but if key is already present, the insertion point will be after (to the right of) any existing entries.

Return type:int
S.clear()

Remove all elements from the set.

S.copy()

Create a shallow copy of the set.

Return type:SortedSet
S.count(value)

Return the number of occurrences of value in the set.

Return type:int
S.difference(S2, ...)
S - S2 - ...

Return a new set with elements in the set that are not in the others.

Return type:SortedSet
S.difference_update(S2, ...)
S -= S2 | ...

Update the set, removing elements found in keeping only elements found in any of the others.

S.discard(value)

Remove the first occurrence of value. If value is not a member, does nothing.

S.index(value[, start[, stop]])

Return the smallest k such that S[k] == x and i <= k < j. Raises ValueError if value is not present. stop defaults to the end of the set. start defaults to the beginning. Negative indexes are supported, as for slice indices.

Return type:int
S.intersection(S2, ...)
S & S2 & ...

Return a new set with elements common to the set and all others.

Return type:SortedSet
S.intersection_update(S2, ...)
S &= S2 & ...

Update the set, keeping only elements found in it and all others.

S.isdisjoint(S2)

Return True if the set has no elements in common with S2. Sets are disjoint if and only if their intersection is the empty set.

Return type:bool
S.issubset(S2)
S <= S2

Test whether every element in the set is in S2

Return type:bool
S.issuperset(S2)
S >= S2

Test whether every element in S2 is in the set.

Return type:bool
S.symmetric_difference(S2)
S ^ S2

Return a new set with elements in either set but not both.

Return type:SortedSet
S.symmetric_difference_update(S2)
S ^= S2

Update the set, keeping only elements found in either set, but not in both.

S.pop([index])

Remove and return item at index (default last). Raises IndexError if set is empty or index is out of range. Negative indexes are supported, as for slice indices.

Return type:item
S.remove(value)

Remove first occurrence of value. Raises ValueError if value is not present.

S.union(S2, ...)
S | S2 | ...

Return a new SortedSet with elements from the set and all others.

Return type:SortedSet
S.update(S2, ...)
S |= S2 | ...

Update the set, adding elements from all others.

S.islice(start=None, stop=None, reverse=False)

Returns an iterator that slices self from start to stop index, inclusive and exclusive respectively.

When reverse is True, values are yielded from the iterator in reverse order.

Both start and stop default to None which is automatically inclusive of the beginning and end.

Return type:iterator
S.irange(minimum=None, maximum=None, inclusive=(True, True), reverse=False)

Create an iterator of values between minimum and maximum.

inclusive is a pair of booleans that indicates whether the minimum and maximum ought to be included in the range, respectively. The default is (True, True) such that the range is inclusive of both minimum and maximum.

Both minimum and maximum default to None which is automatically inclusive of the start and end of the list, respectively.

When reverse is True the values are yielded from the iterator in reverse order; reverse defaults to False.

When initialized with a key-function, an irange_key method is also provided with similar semantics.

Return type:iterator