{} OpenCSTL v1.0
OpenCSTL · API

API Reference.

Function signatures for every OpenCSTL container. Optional parameters are shown in brackets [...]. Comparator and hash function arguments are always optional — omitting them uses the built-in default for the type.

01 / 12
Sequence · contiguous

VECTOR<type>

Dynamic array with contiguous storage and amortized O(1) append. Supports v[i] index access — a real C array subscript, not a function call.

Construction

VECTOR(<type>) v = new_vector(<type>);Construct an empty vector.

Iterators

<type*> begin(v);Iterator to the first element.
<type*> end(v);Past-the-end iterator.
<type*> rbegin(v);Reverse iterator to the last element.
<type*> rend(v);Reverse past-the-beginning iterator.

Capacity

size_t size(v);Number of elements.
bool empty(v);true if the vector contains no elements.
size_t capacity(v);Allocated capacity in elements.

Element access

v[i]Direct subscript access — works like a plain C array.
<type> front(v);First element.
<type> back(v);Last element.

Modifiers

void push_back(v, value);Append value at the end.
void pop_back(v);Remove the last element.
void insert(v, iter, value);Insert value before iter.
void insert(v, iter, N, value);Insert N copies of value before iter.
void erase(v, iter);Remove the element at iter.
void erase(v, iter_begin, iter_end);Remove the range [iter_begin, iter_end).
void resize(v, N [, value]);Resize to N; fill new slots with value if given.
void assign(v, N [, value]);Replace contents with N copies of value.
void clear(v);Remove all elements.
void destroy(v);Free the vector's memory.

Search

<type*> find(v, value);Linear search from begin; returns end(v) if not found.
<type*> find(v, iter, value);Linear search starting at iter.
02 / 12
Sequence · linked

LIST<type>

Doubly linked list with O(1) insert/erase at any iterator position. Use next(it) / prev(it) to advance — never it++.

Construction

LIST(<type>) l = new_list(<type>);Construct an empty list.

Iterators

<type*> begin(l);Iterator to the first element.
<type*> end(l);Past-the-end iterator.
<type*> rbegin(l);Reverse iterator to the last element.
<type*> rend(l);Reverse past-the-beginning iterator.
<type*> next(iter);Advance one position. Use instead of it++.
<type*> prev(iter);Step back one position.

Capacity

size_t size(l);Number of elements.
bool empty(l);true if the list is empty.

Element access

<type> front(l);First element.
<type> back(l);Last element.

Modifiers

void push_back(l, value);Append value at the end.
void pop_back(l);Remove the last element.
void push_front(l, value);Prepend value at the front.
void pop_front(l);Remove the first element.
void insert(l, iter, value);Insert value before iter.
void insert(l, iter, N, value);Insert N copies of value.
void erase(l, iter);Remove the element at iter.
void erase(l, iter_begin, iter_end);Remove the range [iter_begin, iter_end).
void resize(l, N [, value]);Resize to N; fill new slots with value if given.
void assign(l, N [, value]);Replace contents with N copies of value.
void clear(l);Remove all elements.
void destroy(l);Free the list's memory.

Search

<type*> find(l, value);Linear search from begin.
<type*> find(l, iter, value);Linear search starting at iter.
03 / 12
Sequence · double-ended

DEQUE<type>

Double-ended queue with O(1) push/pop at both ends. Like vector, supports q[i] subscript access.

Construction

DEQUE(<type>) q = new_deque(<type>);Construct an empty deque.

Iterators

<type*> begin(q);Iterator to the first element.
<type*> end(q);Past-the-end iterator.
<type*> rbegin(q);Reverse iterator to the last element.
<type*> rend(q);Reverse past-the-beginning iterator.

Capacity

size_t size(q);Number of elements.
bool empty(q);true if the deque is empty.
size_t capacity(q);Allocated capacity in elements.

Element access

q[i]Direct subscript access — works like a plain C array.
<type> front(q);First element.
<type> back(q);Last element.

Modifiers

void push_back(q, value);Append value at the back.
void pop_back(q);Remove the last element.
void push_front(q, value);Prepend value at the front.
void pop_front(q);Remove the first element.
void insert(q, iter, value);Insert value before iter.
void insert(q, iter, N, value);Insert N copies of value.
void erase(q, iter);Remove the element at iter.
void erase(q, iter_begin, iter_end);Remove the range [iter_begin, iter_end).
void resize(q, N [, value]);Resize to N; fill new slots with value if given.
void assign(q, N [, value]);Replace contents with N copies of value.
void clear(q);Remove all elements.
void destroy(q);Free the deque's memory.

Search

<type*> find(q, value);Linear search from begin.
<type*> find(q, iter, value);Linear search starting at iter.
04 / 12
Sequence · fixed-size

ARRAY<type, N>

Fixed-size contiguous container — the C analogue of std::array<T, N>. Like vector, supports a[i] subscript access, but the length is locked at construction.

Construction

ARRAY(<type>) a = new_array(<type>, N);Construct a fixed-length array of N elements.

Iterators

<type*> begin(a);Iterator to the first element.
<type*> end(a);Past-the-end iterator.
<type*> rbegin(a);Reverse iterator to the last element.
<type*> rend(a);Reverse past-the-beginning iterator.
<type*> next(iter);Advance one position.
<type*> prev(iter);Step back one position.

Capacity

size_t size(a);Number of elements (equals N).
size_t max_size(a);Maximum size — same as size for a fixed array.
size_t capacity(a);Allocated capacity.

Element access

a[i]Direct subscript access — works like a plain C array.

Operations

void reverse(a);Reverse the elements in place.
size_t count(a, value);Number of elements equal to value.
size_t count_if(a, predicate);Number of elements for which predicate returns true.
void destroy(a);Free the array's memory.

Search

<type*> find(a, iter, value);Linear search starting at iter.
<type*> lower_bound(a, value, cmp);First position where value could be inserted without breaking sort order.
<type*> upper_bound(a, value, cmp);One past the last position equal to value in a sorted range.
05 / 12
Associative · ordered

SET<type>

Sorted set backed by a red-black tree. O(log n) insert, erase, and lookup. Comparator argument is optional — defaults to memcmp over the element bytes.

Construction

SET(<type>) s = new_set(<type> [, cmp]);Construct an empty set. cmp is optional.

Iterators

<type*> begin(s);Iterator to the smallest element.
<type*> end(s);Past-the-end iterator.
<type*> rbegin(s);Reverse iterator to the largest element.
<type*> rend(s);Reverse past-the-beginning iterator.
<type*> next(iter);In-order successor. Use instead of it++.
<type*> prev(iter);In-order predecessor.

Capacity

size_t size(s);Number of elements.
bool empty(s);true if the set is empty.

Modifiers

void insert(s, value);Insert value; no-op if already present.
void erase(s, iter);Remove the element at iter.
void clear(s);Remove all elements.
void destroy(s);Free the set's memory.

Search

<type*> find(s, value);O(log n) lookup; returns end(s) if not found.
06 / 12
Associative · ordered

MAP<key, value>

Sorted key→value map backed by a red-black tree. Iterators yield key pointers; use first(it) and second(it, V) to read the key and value.

Construction

MAP(<key>) m = new_map(<key>, <value> [, cmp]);Construct an empty map. cmp is optional.

Iterators

<key*> begin(m);Iterator to the smallest key.
<key*> end(m);Past-the-end iterator.
<key*> rbegin(m);Reverse iterator to the largest key.
<key*> rend(m);Reverse past-the-beginning iterator.
<key*> next(iter);In-order successor.
<key*> prev(iter);In-order predecessor.

Capacity

size_t size(m);Number of entries.
bool empty(m);true if the map is empty.

Element access

<key> first(iter);Extract the key from an iterator.
<value> second(iter, <value>);Extract the value from an iterator. Value type must be supplied.

Modifiers

void insert(m, key, value);Insert or assign the entry key → value.
void erase(m, iter);Remove the entry at iter.
void clear(m);Remove all entries.
void destroy(m);Free the map's memory.

Search

<key*> find(m, key);O(log n) lookup by key.
07 / 12
Unordered associative

UNORDERED_SET<type>

Hash set with O(1) average insert, erase, and lookup. rbegin/rend walk buckets in reverse — not sorted order. Hash function argument is optional.

Construction

UNORDERED_SET(<type>) h = new_unordered_set(<type> [, hash_fn]);Construct an empty hash set.

Iterators

<type*> begin(h);Iterator to the first occupied bucket.
<type*> end(h);Past-the-end iterator.
<type*> rbegin(h);Reverse bucket-order iterator.
<type*> rend(h);Reverse past-the-beginning iterator.
<type*> next(iter);Advance to the next occupied bucket.
<type*> prev(iter);Step back one occupied bucket.

Capacity

size_t size(h);Number of stored elements.
bool empty(h);true if the set is empty.
size_t capacity(h);Number of buckets.

Element access

h[i]Direct bucket-slot access — 0 means empty.

Modifiers

void insert(h, value);Insert value; no-op if already present.
void erase(h, iter);Remove the element at iter.
void clear(h);Remove all elements.
void destroy(h);Free the set's memory.

Search

<type*> find(h, value);O(1) average lookup.
08 / 12
Unordered associative

UNORDERED_MAP<key, value>

Hashed key→value map with O(1) average access. Uses first(it) and second(it, V) to read entries, just like MAP.

Construction

UNORDERED_MAP(<key>) m = new_unordered_map(<key>, <value> [, hash_fn]);Construct an empty hash map.

Iterators

<key*> begin(m);Iterator to the first occupied bucket.
<key*> end(m);Past-the-end iterator.
<key*> rbegin(m);Reverse bucket-order iterator.
<key*> rend(m);Reverse past-the-beginning iterator.
<key*> next(iter);Advance to the next occupied bucket.
<key*> prev(iter);Step back one occupied bucket.

Capacity

size_t size(m);Number of stored entries.
bool empty(m);true if the map is empty.
size_t capacity(m);Number of buckets.

Element access

<key> first(iter);Extract the key from an iterator.
<value> second(iter, <value>);Extract the value from an iterator. Value type must be supplied.

Modifiers

void insert(m, key, value);Insert or assign the entry key → value.
void erase(m, iter);Remove the entry at iter.
void clear(m);Remove all entries.
void destroy(m);Free the map's memory.

Search

<key*> find(m, key);O(1) average lookup by key.
09 / 12
Adaptor · LIFO

STACK<type>

Last-in / first-out adaptor. Exposes the canonical push / pop / top trio.

Construction

STACK(<type>) s = new_stack(<type>);Construct an empty stack.

Capacity

size_t size(s);Number of elements.
bool empty(s);true if the stack is empty.

Element access

<type> top(s);Peek at the top element.

Modifiers

void push(s, value);Push value onto the top.
void pop(s);Remove the top element.
void clear(s);Remove all elements.
void destroy(s);Free the stack's memory.
10 / 12
Adaptor · FIFO

QUEUE<type>

First-in / first-out adaptor. push appends at the back; pop removes from the front.

Construction

QUEUE(<type>) q = new_queue(<type>);Construct an empty queue.

Capacity

size_t size(q);Number of elements.
bool empty(q);true if the queue is empty.

Element access

<type> front(q);Peek at the front element.
<type> back(q);Peek at the back element.

Modifiers

void push(q, value);Enqueue value at the back.
void pop(q);Dequeue the front element.
void clear(q);Remove all elements.
void destroy(q);Free the queue's memory.
11 / 12
Adaptor · heap

PRIORITY_QUEUE<type>

Binary-heap adaptor. push and pop are both O(log n). Comparator argument is optional — defaults to max-heap ordering.

Construction

PRIORITY_QUEUE(<type>) pq = new_priority_queue(<type> [, cmp]);Construct an empty priority queue.

Capacity

size_t size(pq);Number of elements.
bool empty(pq);true if the queue is empty.

Element access

<type> top(pq);Peek at the highest-priority element.

Modifiers

void push(pq, value);Insert value — O(log n).
void pop(pq);Remove the top — O(log n).
void clear(pq);Remove all elements.
void destroy(pq);Free the queue's memory.
12 / 12
Special · bit sequence

BITSET<N>

Fixed-size sequence of N bits — the C analogue of std::bitset<N>. Operations are accessed through the bitset. namespace, a struct of function pointers that gives the call sites a method-like shape.

Construction

BITSET b = new_bitset(N);Construct a bitset of N bits, all zero.

Capacity

size_t bitset.nbits(b);Number of bits in the set.

Bit query

bool bitset.test(b, idx);true if bit idx is 1.
size_t bitset.count(b);Number of bits set to 1.
bool bitset.all(b);true if every bit is 1.
bool bitset.any(b);true if at least one bit is 1.
bool bitset.none(b);true if every bit is 0.

Modifiers

void bitset.set(b);Set every bit to 1.
void bitset.reset(b);Set every bit to 0.
void bitset.set_at(b, idx, val);Set bit idx to val.
void bitset.flip(b);Flip every bit.
void bitset.flip_at(b, idx);Flip the bit at idx.

Conversion

char* bitset.to_string(b);Render as a string with MSB first — matches std::bitset::to_string.

Destruction

void destroy(b);Free the bitset's memory.
Notes

One handful of rules covers every container.