Defined in header <ctl/set.h>, CTL prefix set, parent for map.
static inline int
int_cmp(int *a, int *b) {
return *a < *b;
}
#define POD
#define T int
#include <ctl/set.h>
int i = 0;
set_int a = set_int_init (int_cmp);
for (i=0; i<1000; i++) {
set_int_insert (&a, i);
}
foreach(set_int, &a, it) { i = it.ref->key); }
printf("last key %d, ", i);
printf("min {\"%s\", %d} ", set_int_min (a));
printf("max {\"%s\", %d}\n", set_int_max (a));
set_int_free(&a);
set is a sorted associative container that contains unique values.
Values are sorted by using the custom comparison function compare. Search, removal,
and insertion operations have logarithmic complexity. set is implemented as red-black tree.
The function names are composed of the prefix set_, the user-defined type
T and the method name. E.g set_int with #define T int.
Everywhere the CTL uses the Compare requirements, uniqueness is
determined by using the equivalence relation. In imprecise terms, two objects
a and b are considered equivalent (not unique) if neither compares less than the
other: !compare(a, b) && !compare(b, a). (Which obviously fails with double nan)
Note that find does not use this double comparison, rather a single compare
or optional equal call. For simple integral types this always works, as the
default equal method is always set, but for non-POD types with the default 2-way
compare method (*a < *b) you may want to set a proper equal method by yourself.
Three-way comparison (<=>, i.e. *a < *b ? -1 : *a == *b ? 0 : 1) is
permitted only with pure set functions (find, erase), but not with any generic
algorithm methods. Supporting three-way comparison bedises the default two-way
operator< comparison is too costly there.
T value type
A being set_T container type
B being set_T_node node type
I being set_T_it iterator type
A init (int compare(T*, T*))
constructs the set.
free (A* self)
destructs the set.
assign (A* self, A* other)
replaces the contents of the container.
A copy (A* self)
returns a copy of the container.
T* at (A* self, size_t index)
access specified element with bounds checking
I begin (A* self)
constructs an iterator to the beginning
I end (A* self)
constructs an iterator to the end.
I* next (I* iter)
Advances the iterator by 1 forwards. There's no prev yet.
I* advance (I* iter, long i)
All our variants accepts negative i to move back. The return value may be ignored.
See iterators for more.
int empty (A* self)
checks whether the container is empty
size_t size (A* self)
returns the number of elements
size_t max_size ()
returns the maximum possible number of elements, hard-coded to 2GB (32bit).
clear (A* self)
clears the contents
B* insert (A* self, T value)
B* insert_found (A* self, T value, int *foundp)
insert_range (A* self, I* range)
inserts the element(s). (C++17)
insert_generic (A* self, GI* range2)
inserts copies of values from generic range2. (NYI)
emplace (A* self, T* value)
constructs elements in-place. (NYI)
emplace_hint (A* self, B* pos, T* value)
constructs elements in-place at position. (NYI)
erase (A* self, T value)
erases the element by value.
erase_it (I* pos)
erases the element at pos.
I* erase_range (I* range)
erases elements.
erase_generic (A* self, GI* range)
erases elements by value from another container.
swap (A* self, A* other)
swaps the contents
extract (A* self, T key)
extracts a node from the container. (NYI)
extract_it (I* pos)
extracts nodes from the container. (NYI)
merge (A* self)
splices nodes from another container (NYI)
size_t count (A* self)
returns the number of elements matching specific key.
I find (A* self, T key)
B* find_node (A* self, T key)
finds element with specific key. does not consume/delete the key. see above the problem with a simple 2-way compare method.
bool find_range (I* range, T key)
finds element in range, and sets range to the found element or the end. it does not iterate over the range, but checks if the found element is within the range.
bool contains (A* self, T key)
checks if the container contains an element with specific key. (C++20)
equal_range (A* self, T key, I* lower_bound, I* upper_bound)
returns lower_bound and upper_bound ranges for the key. Different to the
algorithm equal_range function.
I lower_bound (A* self, T key)
returns an iterator to the first element not less than the given key.
I upper_bound (A* self, T key)
returns an iterator to the first element greater than the given key.
FN value_comp (A* self)
Returns the function that compares keys in objects of type value_type T. (NYI)
swap (A* self)
specializes the swap algorithm
size_t remove_if (A* self, int match(T*))
Removes all elements satisfying specific criteria.
size_t erase_if (A* self, int match(T*))
erases all elements satisfying specific criteria. (C++20) (NYI)
A intersection (A* self, A* other)
A union (A* self, A* other)
A difference (A* self, A* other)
A symmetric_difference (A* self, A* other)
bool all_of (A* self, int _match(T*)) (C++11)
bool any_of `(A* self, int _match(T*)) (C++11)
bool none_of (A* self, int _match(T*)) (C++11)
bool all_of_range (I* range, int _match(T*))
bool any_of_range (I* range, int _match(T*))
bool none_of_range (I* range, int _match(T*))
foreach (A, self, iter) {...}
foreach_range (A, iter, first, last) {...}
foreach_range_ (A, iter, range) {...}
size_t count (A* self, T value)
size_t count_if (A* self, int _match(T*))
size_t count_range (I* range, T value) (C++20)
size_t count_if_range (I* range, int _match(T*)) (C++20)
find (A* self, T key)
find_if (A* self, int _match(T*))
find_if_not (A* self, int _match(T*)) (C++11)
find_range (I* range, T key) (C++20)
find_if_range (I* range, int _match(T*)) (C++20)
find_if_not_range (I* range, int _match(T*)) (C++20)
bool find_first_of_range (I* range1, GI* range2)
remove (A* self, T key) _(NYI)_
size_t remove_if (A* self, int match(T*))
merge (A* self, A* other) _(NYI)_
int equal (A* self, A* other)
A transform (A* self, T unop(T*))
A transform_it (A* self, I* pos, T _binop(T*, T*))
I transform_range (I* range1, I dest, T _unop(T*))
I transform_it_range (I* range1, I* pos, I dest, T _binop(T*, T*))
applies a function to a range of elements. Returning results in a copy, or for
the range variants in an output iterator dest. unop takes the iterator
element, binop takes as 2nd argument the 2nd iterator pos.
generate (A* self, T _gen(void))
generate_range (I* range, T _gen(void)) (C++20) (NY)
assigns the results of successive function calls to every element in a range.
generate_n (A* self, size_t count, T _gen(void))
generate_n_range (I* first, size_t n, T _gen(void))
assigns the results of successive function calls to N elements in a range.
Unlike with the STL, generate_n shrinks to n elements.
See algorithm for more.