array.h

This file contains the implementation of the array data structure, which is a resizeable ordered collection of elements with generic type T. In addition, the file contains global helper functions for working with arrays, such as resizing, linear and binary search, insertion sort, and quicksort. The pair structure is also defined here.

This file also contains functions that perform set operations on sorted arrays and native arrays, such as union, intersection, subtraction, and subset.

Classes, functions, and variables in this file
#defineRESIZE_FACTOR
structis_resizeable
boolresize (T *& data, const SizeType & new_capacity)
voidexpand_capacity (SizeType & capacity, size_t new_length)
boolexpand (T *& data, SizeType & capacity, size_t new_length)
boolensure_capacity (T *& data, SizeType & capacity, size_t new_length)
unsigned intindex_of (const T & element, const T * data, const SizeType & length, const SizeType & start = 0)
unsigned intlast_index_of (const T & element, const T * data, const SizeType & length)
structarray
boolarray_init (array< T > & m, unsigned int initial_capacity)
size_tsize (const array< T > & m)
voidswap (array< T > & a, array< T > & b)
booloperator == (const array< T > & a, const array< T > & b)
booloperator != (const array< T > & a, const array< T > & b)
voidinsertion_sort (T * keys, unsigned int length)
voidinsertion_sort (T * keys, unsigned int length, const Sorter & sorter)
voidinsertion_sort (K * keys, V * values, unsigned int length)
voidinsertion_sort (K * keys, V * values, unsigned int length, const Sorter & sorter)
voidinsertion_sort (array< T > & keys)
voidinsertion_sort (array< T > & keys, const Sorter & sorter)
voidinsertion_sort (array< K > & keys, array< V > & values)
voidinsertion_sort (array< K > & keys, array< V > & values, const Sorter & sorter)
voidreverse (T * array, unsigned int length)
voidreverse (array< T > & array)
voidquick_sort (T * keys, unsigned int length)
voidquick_sort (T * keys, unsigned int length, const Sorter & sorter)
voidquick_sort (K * keys, V * values, unsigned int length)
voidquick_sort (K * keys, V * values, unsigned int length, const Sorter & sorter)
voidquick_sort (array< T > & keys)
voidquick_sort (array< T > & keys, const Sorter & sorter)
voidquick_sort (array< K > & keys, array< V > & values)
voidquick_sort (array< K > & keys, array< V > & values, const Sorter & sorter)
voidsort (T * keys, unsigned int length)
voidsort (T * keys, unsigned int length, const Sorter & sorter)
voidsort (K * keys, V * values, unsigned int length)
voidsort (K * keys, V * values, unsigned int length, const Sorter & sorter)
voidsort (array< T > & keys)
voidsort (array< T > & keys, const Sorter & sorter)
voidsort (array< K > & keys, array< V > & values)
voidsort (array< K > & keys, array< V > & values, const Sorter & sorter)
structdefault_sorter
unsigned intunique (T * array, size_t length)
voidunique (array< T > & a)
voidshuffle (T * array, unsigned int length)
voidshuffle (K * keys, V * values, unsigned int length)
voidshuffle (array< T > & items)
unsigned intlinear_search (const T * a, const T & b, unsigned int start, unsigned int end)
unsigned intstrict_linear_search (const T * a, const T & b, unsigned int start, unsigned int end)
unsigned intreverse_strict_linear_search (const T * a, const T & b, unsigned int start, unsigned int end)
unsigned intbinary_search (const T * a, const T & b, unsigned int min, unsigned int max)
structpair
voidshift_right (T * list, unsigned int length, unsigned int index)
voidshift_left (T * list, unsigned int index)
voidset_union (UnionBoth union_both, UnionFirst union_first, UnionSecond union_second, const T * first, unsigned int first_length, const T * second, unsigned int second_length)
voidset_union (T * dst, SizeType & dst_length, const T * first, unsigned int first_length, const T * second, unsigned int second_length)
boolset_union (array< T > & dst, const T * first, unsigned int first_length, const T * second, unsigned int second_length)
boolset_union (array< T > & dst, const array< T > & first, const array< T > & second)
boolset_union (array< T > & dst, const ArraySetCollection & arrays, unsigned int array_count)
boolset_intersect (Intersect intersect, const T * first, unsigned int first_length, const T * second, unsigned int second_length)
boolset_intersect (T * intersection, SizeType & intersection_length, const T * first, unsigned int first_length, const T * second, unsigned int second_length)
boolset_intersect (array< T > & intersection, const T * first, unsigned int first_length, const T * second, unsigned int second_length)
boolset_intersect (array< T > & intersection, const array< T > & first, const array< T > & second)
voidset_intersect (T * first, SizeType & first_length, const T * second, unsigned int second_length)
voidset_intersect (array< T > & first, const T * second, unsigned int second_length)
voidset_intersect (array< T > & first, const array< T > & second)
boolhas_intersection (const T * first, unsigned int first_length, const T * second, unsigned int second_length)
boolhas_intersection (const array< T > & first, const array< T > & second)
boolis_subset (const T * first, unsigned int first_length, const T * second, unsigned int second_length)
voidset_subtract (EmitFunction emit, const T * first, unsigned int first_length, const T * second, unsigned int second_length)
voidset_subtract (T * dst, SizeType & dst_length, const T * first, unsigned int first_length, const T * second, unsigned int second_length)
boolset_subtract (array< T > & dst, const T * first, unsigned int first_length, const T * second, unsigned int second_length)
boolset_subtract (array< T > & dst, const array< T > & first, const array< T > & second)
voidset_subtract (T * first, SizeType & first_length, const T * second, unsigned int second_length)
voidset_subtract (array< T > & first, const array< T > & second)
#define RESIZE_FACTOR 2

The multiplicative factor by which array capacity is changed.

struct is_resizeable

template<typename T>

This type trait is true_type if and only if T is class with a public function void on_resize().

template<typename T, typename SizeType>
bool resize(
T *&data,
const SizeType &new_capacity)

Resizes the given native array data with the requested capacity new_capacity.

Template parameters
SizeType

a type that satisfies is_integral.

T

the generic type of the elements in data.

Parameters
data

the array to resize.

new_capacity

the requested size.

Returns

true on success; data may point to a different memory address.

false on failure; data is unchanged.

template<typename SizeType>
void expand_capacity(
SizeType &capacity,
size_tnew_length)

This function multiplies capacity by RESIZE_FACTOR. It then repeats this until capacity >= new_length.

template<typename T, typename SizeType>
bool expand(
T *&data,
SizeType &capacity,
size_tnew_length)

For a given requested length new_length, this function calls expand_capacity() to determine the new capacity of the native array data. The function then attempts to resize the array with this capacity. Note this function does not check whether new_length <= capacity.

template<typename T, typename SizeType>
bool ensure_capacity(
T *&data,
SizeType &capacity,
size_tnew_length)

For a given requested length new_length, this function expands the native array data by factors of RESIZE_FACTOR until capacity >= new_length. If initially new_length <= capacity, this function does nothing.

template<typename T, typename SizeType>
unsigned int index_of(
const T &element,
const T *data,
const SizeType &length,
const SizeType &start = 0)

Performs a linear search through the array data to find the smallest index i such that element == data[i].

Template parameters
T

a generic type for which the operator == is defined.

Returns

an index in start, start + 1, ..., length - 1 if the element was found.

length if the element was not found.

template<typename T, typename SizeType>
unsigned int last_index_of(
const T &element,
const T *data,
const SizeType &length)

Performs a linear search through the array data to find the largest index i such that element == data[i].

Template parameters
T

a generic type for which the operator == is defined.

Returns

an index in 0, 1, ..., length - 1 if the element was found.

static_cast<unsigned int>(-1) if the element was not found.

struct array

template<typename T>

A resizeable sequence of objects, stored contiguously, each with generic type T. This structure does not automatically initialize or free its elements, and so the user must appropriately free each element before the array is destroyed.

In the following example, we demonstrate a simple use-case of array. Here, a is automatically freed by the destructor since it was initialized on the stack. The expected output is -1 -1 0 3.

#include <core/array.h>
#include <stdio.h>
using namespace core;

int main() {
    array<int> a = array<int>(8);
    a.add(-1); a.add(-4);
    a.add(3); a.add(0);
    a.remove(1);

    printf("%d ", a[0]);
    for (int element : a)
        printf("%d ", element);
}

However, if a is not allocated on the stack, the destructor will not be automatically called, and so it must be freed manually using core::free or array::free.

#include <core/array.h>
#include <stdio.h>
using namespace core;

int main() {
    array<int>& a = *((array<int>*) alloca(sizeof(array<int>)));
    array_init(a, 8);
    a.add(-1); a.add(-4);
    a.add(3); a.add(0);
    a.remove(1);

    printf("%d ", a[0]);
    for (int element : a)
        printf("%d ", element);
    free(a);
}

Also note that a number of member functions require that T be CopyAssignable. In other cases, elements should be added manually to the underlying native array array::data. This structure also defines array::begin and array::end, similar to Standard Template Library iterators, which enables the use of the range-based for loop in the example below. In this example, the expected output is first second.

#include <core/array.h>
#include <stdio.h>
#include <string.h>
using namespace core;

struct custom_string {
    char* buffer;

    static void free(custom_string& s) {
        core::free(s.buffer);
    }
};

bool init(custom_string& s, const char* src) {
    s.buffer = (char*) malloc(sizeof(char) * (strlen(src) + 1));
    if (s.buffer == NULL)
        return false;
    memcpy(s.buffer, src, sizeof(char) * (strlen(src) + 1));
    return true;
}

int main() {
    array<custom_string> a = array<custom_string>(8);
    init(a[0], "first");
    init(a[1], "second");
    a.length = 2;

    for (const custom_string& s : a)
        printf("%s ", s.buffer);
    for (custom_string& s : a)
        free(s);
}
Note in the above example that since the array struct does not automatically free its elements, they must be freed manually.

Public members
T *data
size_tlength
size_tcapacity
array (size_t initial_capacity)
T &operator [] (unsigned int index)
const T &operator [] (unsigned int index) const
voidclear ()
voidremove (unsigned int index)
boolensure_capacity (size_t new_length)
boolappend (const T * elements, size_t size)
boolcontains (const T & element) const
unsigned intindex_of (const T & element) const
T &first ()
const T &first () const
T &last ()
const T &last () const
booladd (const T & element)
Tpop ()
T *begin ()
T *end ()
const T *begin () const
const T *end () const
static voidmove (const array< T > & src, array< T > & dst)
static voidfree (array< T > & a)
T * array::data

The underlying native array of elements.

size_t array::length

The length of the array.

size_t array::capacity

The capacity of array::data.

array::array(
size_tinitial_capacity)

Constructs an array with zero size and the given initial_capacity.

T & array::operator [] (
unsigned intindex)

Returns a reference to the element at the given index. No bounds-checking is performed.

const T & array::operator [] (
unsigned intindex) const

Returns a const reference to the element at the given index. No bounds-checking is performed.

void array::clear()

Sets the length of the array to 0. Any elements are not freed.

void array::remove(
unsigned intindex)

Moves the last element in the array to the position given by index and decrements array::length by 1. The element initially at index is not freed.

template<typename C = T>
bool array::ensure_capacity(
size_tnew_length)

For a given requested length new_length, this function expands the array by factors of RESIZE_FACTOR until array::capacity >= new_length. If initially new_length <= array::capacity, this function does nothing. If the resize operation moved array::data to a new memory address, and T satisfies is_resizeable, then x.on_resize() is called for every element x in the array.

bool array::append(
const T *elements,
size_tsize)

Adds the given native array of elements to this structure. This function uses memcpy, and so it should not be used if the elements are not TriviallyCopyable. In such a case, addition should be performed manually using the public fields.

Template parameters
T

is TriviallyCopyable.

bool array::contains(
const T &element) const

Calls array::index_of to determine whether element exists in this array.

unsigned int array::index_of(
const T &element) const

Performs a linear search of the array to find the smallest index i such that element == array::data[i].

Returns

an index in 0, 1, ..., array::length - 1 if the element was found.

array::length if the element was not found.

T & array::first()

Returns a reference to array::data[0], ignoring any bounds.

const T & array::first()

Returns a const reference to array::data[0], ignoring any bounds.

T & array::last()

Returns a reference to array::data[array::length - 1], ignoring any bounds.

const T & array::last()

Returns a const reference to array::data[array::length - 1], ignoring any bounds.

bool array::add(
const T &element)

Adds the given element to this array, increasing its capacity if necessary. The assignment operator performs the addition, and so this function should not be used if T is not CopyAssignable. In such a case, addition should be performed manually using the public fields.

Template parameters
T

is CopyAssignable.

T array::pop()

Returns the element at array::length - 1 and decrements array::length by 1, ignoring any bounds.

T * array::begin()

Returns an iterator to the beginning of the array.

T * array::end()

Returns an iterator to the end of the array.

const T * array::begin()

Returns a const iterator to the beginning of the array.

const T * array::end()

Returns a const iterator to the end of the array.

static void array::move(
const array< T > &src,
array< T > &dst)

Copies the underlying fields from src into dst, effectively moving the array from src into dst.

static void array::free(
array< T > &a)

Frees array::data. This should not be used if a was constructed on the stack, as the destructor will automatically free array::data. The elements of a are not freed.

template<typename T>
bool array_init(
array< T > &m,
unsigned intinitial_capacity)

Initializes the array m with the given initial_capacity.

template<typename T>
size_t size(
const array< T > &m)

Returns array::length of m.

template<typename T>
void swap(
array< T > &a,
array< T > &b)

Swaps the underlying buffers of the given arrays.

template<typename T>
bool operator == (
const array< T > &a,
const array< T > &b)

Compares the two given arrays and returns true if and only if a.length == b.length and there is no index i such that a.data[i] != b.data[i].

template<typename T>
bool operator != (
const array< T > &a,
const array< T > &b)

Compares the two given arrays and returns true if and only if a.length != b.length or there is some index i such that a.data[i] != b.data[i].

template<typename T>
void insertion_sort(
T *keys,
unsigned intlength)

Performs insertion sort on the given native array keys with given length.

Template parameters
T

is CopyAssignable, CopyConstructible, and LessThanComparable.

template<typename T, typename Sorter>
void insertion_sort(
T *keys,
unsigned intlength,
const Sorter &sorter)

Performs insertion sort on the given native array keys with given length and sorter.

Template parameters
T

satisfies is_moveable, and for which a function bool less_than(const T&, const T&, const Sorter&) is defined.

template<typename K, typename V>
void insertion_sort(
K *keys,
V *values,
unsigned intlength)

Performs insertion sort on the given native arrays keys and values with given length.

Template parameters
K

is CopyAssignable, CopyConstructible, and LessThanComparable.

V

is CopyAssignable, CopyConstructible.

template<typename K, typename V, typename Sorter>
void insertion_sort(
K *keys,
V *values,
unsigned intlength,
const Sorter &sorter)

Performs insertion sort on the given native arrays keys and values with given length and sorter.

Template parameters
K

satisfies is_moveable, and for which a function bool less_than(const K&, const K&, const Sorter&) is defined.

V

satisfies is_moveable.

template<typename T>
void insertion_sort(
array< T > &keys)

Performs insertion sort on the given array keys.

Template parameters
T

is CopyAssignable, CopyConstructible, and LessThanComparable.

template<typename T, typename Sorter>
void insertion_sort(
array< T > &keys,
const Sorter &sorter)

Performs insertion sort on the given array keys with the given sorter.

Template parameters
T

satisfies is_moveable, and for which a function bool less_than(const T&, const T&, const Sorter&) is defined.

template<typename K, typename V>
void insertion_sort(
array< K > &keys,
array< V > &values)

Performs insertion sort on the given arrays keys and values.

Template parameters
K

is CopyAssignable, CopyConstructible, and LessThanComparable.

V

is CopyAssignable, CopyConstructible.

template<typename K, typename V, typename Sorter>
void insertion_sort(
array< K > &keys,
array< V > &values,
const Sorter &sorter)

Performs insertion sort on the given arrays keys and values with the given sorter.

Template parameters
K

satisfies is_moveable, and for which a function bool less_than(const K&, const K&, const Sorter&) is defined.

V

satisfies is_moveable.

template<typename T>
void reverse(
T *array,
unsigned intlength)

Reverses the order of the elements in the given native array with given length.

Template parameters
T

satisfies is_swappable.

template<typename T>
void reverse(
array< T > &array)

Reverses the order of the elements in the given array.

Template parameters
T

satisfies is_swappable.

template<typename T>
void quick_sort(
T *keys,
unsigned intlength)

Performs Quicksort on the given native array keys with given length. This function assumes length > 0. If the preprocessor NDEBUG is not defined, this function outputs a warning when length == 0.

Template parameters
T

is CopyConstructible, LessThanComparable, and is_swappable.

template<typename T, typename Sorter>
void quick_sort(
T *keys,
unsigned intlength,
const Sorter &sorter)

Performs Quicksort on the given native array keys with given length and sorter. This function assumes length > 0. If the preprocessor NDEBUG is not defined, this function outputs a warning when length == 0.

Template parameters
T

a generic type that satisfies is_swappable, and for which a function bool less_than(const T&, const T&, const Sorter&) is defined.

template<typename K, typename V>
void quick_sort(
K *keys,
V *values,
unsigned intlength)

Performs Quicksort on the given native arrays keys and values with given length. This function assumes length > 0. If the preprocessor NDEBUG is not defined, this function outputs a warning when length == 0.

Template parameters
K

is CopyConstructible, LessThanComparable, and is_swappable.

V

satisfies is_swappable.

template<typename K, typename V, typename Sorter>
void quick_sort(
K *keys,
V *values,
unsigned intlength,
const Sorter &sorter)

Performs Quicksort on the given native arrays keys and values with given length and sorter. This function assumes length > 0. If the preprocessor NDEBUG is not defined, this function outputs a warning when length == 0.

Template parameters
K

a generic type that satisfies is_swappable, and for which a function bool less_than(const K&, const K&, const Sorter&) is defined.

V

satisfies is_swappable.

template<typename T>
void quick_sort(
array< T > &keys)

Performs Quicksort on the given array keys. This function assumes length > 0. If the preprocessor NDEBUG is not defined, this function outputs a warning when length == 0.

Template parameters
T

is CopyConstructible, LessThanComparable, and is_swappable.

template<typename T, typename Sorter>
void quick_sort(
array< T > &keys,
const Sorter &sorter)

Performs Quicksort on the given native array keys with the given sorter. This function assumes length > 0. If the preprocessor NDEBUG is not defined, this function outputs a warning when length == 0.

Template parameters
T

a generic type that satisfies is_swappable, and for which a function bool less_than(const T&, const T&, const Sorter&) is defined.

template<typename K, typename V>
void quick_sort(
array< K > &keys,
array< V > &values)

Performs Quicksort on the given arrays keys and values. This function assumes length > 0. If the preprocessor NDEBUG is not defined, this function outputs a warning when length == 0.

Template parameters
K

is CopyConstructible, LessThanComparable, and is_swappable.

V

satisfies is_swappable.

template<typename K, typename V, typename Sorter>
void quick_sort(
array< K > &keys,
array< V > &values,
const Sorter &sorter)

Performs Quicksort on the given arrays keys and values with the given sorter. This function assumes length > 0. If the preprocessor NDEBUG is not defined, this function outputs a warning when length == 0.

Template parameters
K

a generic type that satisfies is_swappable, and for which a function bool less_than(const K&, const K&, const Sorter&) is defined.

V

satisfies is_swappable.

template<typename T>
void sort(
T *keys,
unsigned intlength)

Performs hybrid Quicksort-insertion sort on the given native array keys with given length. To improve performance, the Quicksort switches to insertion sort for small partitions. This function assumes length > 0. If the preprocessor NDEBUG is not defined, this function outputs a warning when length == 0.

Template parameters
T

is CopyAssignable, CopyConstructible LessThanComparable, and is_swappable.

template<typename T, typename Sorter>
void sort(
T *keys,
unsigned intlength,
const Sorter &sorter)

Performs hybrid Quicksort-insertion sort on the given native array keys with given length and sorter. To improve performance, the Quicksort switches to insertion sort for small partitions. This function assumes length > 0. If the preprocessor NDEBUG is not defined, this function outputs a warning when length == 0.

Template parameters
T

a generic type that satisfies is_swappable and is_moveable, and for which a function bool less_than(const T&, const T&, const Sorter&) is defined.

template<typename K, typename V>
void sort(
K *keys,
V *values,
unsigned intlength)

Performs hybrid Quicksort-insertion sort on the given native arrays keys and values with given length. To improve performance, the Quicksort switches to insertion sort for small partitions. This function assumes length > 0. If the preprocessor NDEBUG is not defined, this function outputs a warning when length == 0.

Template parameters
K

is CopyAssignable, CopyConstructible LessThanComparable, and is_swappable.

V

satisfies is_swappable and is_moveable.

template<typename K, typename V, typename Sorter>
void sort(
K *keys,
V *values,
unsigned intlength,
const Sorter &sorter)

Performs hybrid Quicksort-insertion sort on the given native arrays keys and values with given length and sorter. To improve performance, the Quicksort switches to insertion sort for small partitions. This function assumes length > 0. If the preprocessor NDEBUG is not defined, this function outputs a warning when length == 0.

Template parameters
K

a generic type that satisfies is_swappable and is_moveable, and for which a function bool less_than(const K&, const K&, const Sorter&) is defined.

V

satisfies is_swappable and is_moveable.

template<typename T>
void sort(
array< T > &keys)

Performs hybrid Quicksort-insertion sort on the given array keys. To improve performance, the Quicksort switches to insertion sort for small partitions. This function assumes length > 0. If the preprocessor NDEBUG is not defined, this function outputs a warning when length == 0.

Template parameters
T

is CopyAssignable, CopyConstructible LessThanComparable, and is_swappable.

template<typename T, typename Sorter>
void sort(
array< T > &keys,
const Sorter &sorter)

Performs hybrid Quicksort-insertion sort on the given array keys with the given sorter. To improve performance, the Quicksort switches to insertion sort for small partitions. This function assumes length > 0. If the preprocessor NDEBUG is not defined, this function outputs a warning when length == 0.

Template parameters
T

a generic type that satisfies is_swappable and is_moveable, and for which a function bool less_than(const T&, const T&, const Sorter&) is defined.

template<typename K, typename V>
void sort(
array< K > &keys,
array< V > &values)

Performs hybrid Quicksort-insertion sort on the given arrays keys and values. To improve performance, the Quicksort switches to insertion sort for small partitions. This function assumes length > 0. If the preprocessor NDEBUG is not defined, this function outputs a warning when length == 0.

Template parameters
K

is CopyAssignable, CopyConstructible LessThanComparable, and is_swappable.

V

satisfies is_swappable and is_moveable.

template<typename K, typename V, typename Sorter>
void sort(
array< K > &keys,
array< V > &values,
const Sorter &sorter)

Performs hybrid Quicksort-insertion sort on the given arrays keys and values with the given sorter. To improve performance, the Quicksort switches to insertion sort for small partitions. This function assumes length > 0. If the preprocessor NDEBUG is not defined, this function outputs a warning when length == 0.

Template parameters
K

a generic type that satisfies is_swappable and is_moveable, and for which a function bool less_than(const K&, const K&, const Sorter&) is defined.

V

satisfies is_swappable and is_moveable.

struct default_sorter

The default_sorter provides a default implementation of bool less_than(const T&, const T&, const default_sorter&) where the comparison is done using the operator <.

template<typename T>
unsigned int unique(
T *array,
size_tlength)

Deletes consecutive duplicates in the given native array with given length and returns the new length. Note the deleted elements are not freed.

Template parameters
T

is CopyAssignable.

template<typename T>
void unique(
array< T > &a)

Deletes consecutive duplicates in the given array with given and returns the new length. Note the deleted elements are not freed.

Template parameters
T

is CopyAssignable.

template<typename T>
void shuffle(
T *array,
unsigned intlength)

Performs a Knuth shuffle on the given native array with given length.

Template parameters
T

satisfies is_swappable.

template<typename K, typename V>
void shuffle(
K *keys,
V *values,
unsigned intlength)

Performs a Knuth shuffle on the given native arrays keys and values with given length.

Template parameters
T

satisfies is_swappable.

template<typename T>
void shuffle(
array< T > &items)

Performs a Knuth shuffle on the given array.

Template parameters
T

satisfies is_swappable.

template<typename T>
unsigned int linear_search(
const T *a,
const T &b,
unsigned intstart,
unsigned intend)

Given sorted array a, this function finds the smallest index i such that a[i] >= b and i >= start and i < end.

template<typename T>
unsigned int strict_linear_search(
const T *a,
const T &b,
unsigned intstart,
unsigned intend)

Given sorted array a, this function finds the smallest index i such that a[i] > b and i >= start and i < end.

template<typename T>
unsigned int reverse_strict_linear_search(
const T *a,
const T &b,
unsigned intstart,
unsigned intend)

Given sorted array a, this function finds the smallest index i such that a[i] > b and i >= start and i < end.

template<typename T>
unsigned int binary_search(
const T *a,
const T &b,
unsigned intmin,
unsigned intmax)

Given sorted array a, this function finds the smallest index i such that a[i] >= b and i >= min and i <= max.

struct pair

template<typename K, typename V>

A simple pair data structure.

Public members
Kkey
Vvalue
K pair::key

The key object in the field.

V pair::value

The value object in the field.

template<typename T>
void shift_right(
T *list,
unsigned intlength,
unsigned intindex)

For every index i >= index, this function moves each element at i to index i + 1.

Template parameters
T

satisfies is_moveable.

template<typename T>
void shift_left(
T *list,
unsigned intindex)

For every index i < index, this function moves each element at i + 1 to index i.

Template parameters
T

satisfies is_moveable.

template<typename T, typename UnionBoth, typename UnionFirst, typename UnionSecond, bool RemoveDuplicates = true>
void set_union(
UnionBothunion_both,
UnionFirstunion_first,
UnionSecondunion_second,
const T *first,
unsigned intfirst_length,
const T *second,
unsigned intsecond_length)

Given ordered native arrays first and second, this function visits their elements sequentially, and:

  1. For every element x that appears in both arrays, union_both(x, i, j) is called where first[i] == x and second[j] == x.

  2. For every element x that appears in first but not second, union_first(x, i, j) is called where first[i] == x, and j is the smallest such index where second[j] > x.

  3. For every element x that appears in second but not first, union_second(x, i, j) is called where second[j] == x, and i is the smallest such index where first[i] > x.

The visited elements are also ordered.

Template parameters
T

a generic type for which the operators ==, != and < are implemented.

RemoveDuplicates

if true, this function will avoid calling the union functions more than once for each element.

template<typename T, typename SizeType, bool RemoveDuplicates = true>
void set_union(
T *dst,
SizeType &dst_length,
const T *first,
unsigned intfirst_length,
const T *second,
unsigned intsecond_length)

Given ordered native arrays first and second, compute their union and appends the result to dst. The union is also ordered. This function assumes dst has sufficient capacity to store the union.

Template parameters
T

satisfies CopyAssignable and implements the operators == and <.

RemoveDuplicates

if true, this function ignore duplicate elements.

template<typename T, bool RemoveDuplicates = true>
bool set_union(
array< T > &dst,
const T *first,
unsigned intfirst_length,
const T *second,
unsigned intsecond_length)

Given ordered native arrays first and second, compute their union and appends the result to dst. The union is also ordered.

Template parameters
T

satisfies CopyAssignable and implements the operators == and <.

RemoveDuplicates

if true, this function ignore duplicate elements.

template<typename T, bool RemoveDuplicates = true>
bool set_union(
array< T > &dst,
const array< T > &first,
const array< T > &second)

Given ordered arrays first and second, compute their union and appends the result to dst. The union is also ordered.

Template parameters
T

satisfies CopyAssignable and implements the operators == and <.

RemoveDuplicates

if true, this function ignore duplicate elements.

template<typename T, typename ArraySetCollection>
bool set_union(
array< T > &dst,
const ArraySetCollection &arrays,
unsigned intarray_count)

Given a collection of ordered arrays arrays, compute their union and appends the result to dst. The union is also ordered. NOTE: this function assumes the given arrays are all non-empty.

Template parameters
T

satisfies CopyAssignable and implements the operators == and <.

ArraySetCollection

a collection type where each element is accessed using arrays[i] and the size of each array can be obtained using size(arrays[i]). The element at index j for array i is accessed using arrays[i][j].

template<typename T, typename Intersect, bool BinarySearch = false>
bool set_intersect(
Intersectintersect,
const T *first,
unsigned intfirst_length,
const T *second,
unsigned intsecond_length)

Given ordered native arrays first and second, this function visits their elements sequentially, and for every element x that exists in both arrays, intersect(i, j) is called where first[i] == x and second[j] == x. The visited elements are also ordered.

Template parameters
T

a generic type for which the operators == and < are implemented.

BinarySearch

if true, binary search is used to find indices of identical elements rather than linear search.

template<typename T, typename SizeType, bool BinarySearch = false>
bool set_intersect(
T *intersection,
SizeType &intersection_length,
const T *first,
unsigned intfirst_length,
const T *second,
unsigned intsecond_length)

Given ordered native arrays first and second, compute the intersection and append it to the native array intersection. The computed intersection is also ordered. This function assumes intersection has sufficient capacity.

Template parameters
T

satisfies CopyAssignable and implements the operators == and <.

BinarySearch

if true, binary search is used to find indices of identical elements rather than linear search.

template<typename T, bool BinarySearch = false>
bool set_intersect(
array< T > &intersection,
const T *first,
unsigned intfirst_length,
const T *second,
unsigned intsecond_length)

Given ordered native arrays first and second, compute the intersection and append it to the array intersection. The computed intersection is also ordered.

Template parameters
T

satisfies CopyAssignable and implements the operators == and <.

BinarySearch

if true, binary search is used to find indices of identical elements rather than linear search.

template<typename T, bool BinarySearch = false>
bool set_intersect(
array< T > &intersection,
const array< T > &first,
const array< T > &second)

Given ordered arrays first and second, compute the intersection and append it to the array intersection. The computed intersection is also ordered.

Template parameters
T

satisfies CopyAssignable and implements the operators == and <.

BinarySearch

if true, binary search is used to find indices of identical elements rather than linear search.

template<typename T, typename SizeType, bool BinarySearch = false>
void set_intersect(
T *first,
SizeType &first_length,
const T *second,
unsigned intsecond_length)

Given ordered native arrays first and second, compute the intersection in-place and store it in first. The computed intersection is also ordered.

Template parameters
T

satisfies CopyAssignable and implements the operators == and <.

BinarySearch

if true, binary search is used to find indices of identical elements rather than linear search.

template<typename T, bool BinarySearch = false>
void set_intersect(
array< T > &first,
const T *second,
unsigned intsecond_length)

Given ordered array first and ordered native array second, compute the intersection in-place and store it in first. The computed intersection is also ordered.

Template parameters
T

satisfies CopyAssignable and implements the operators == and <.

BinarySearch

if true, binary search is used to find indices of identical elements rather than linear search.

template<typename T, bool BinarySearch = false>
void set_intersect(
array< T > &first,
const array< T > &second)

Given ordered arrays first and second, compute the intersection in-place and store it in first. The computed intersection is also ordered.

Template parameters
T

satisfies CopyAssignable and implements the operators == and <.

BinarySearch

if true, binary search is used to find indices of identical elements rather than linear search.

template<typename T, bool BinarySearch = false>
bool has_intersection(
const T *first,
unsigned intfirst_length,
const T *second,
unsigned intsecond_length)

Returns true if the intersection of first and second is non-empty, where first and second are ordered native arrays.

Template parameters
T

a generic type that implements the operators == and <.

BinarySearch

if true, binary search is used to find indices of identical elements rather than linear search.

template<typename T, bool BinarySearch = false>
bool has_intersection(
const array< T > &first,
const array< T > &second)

Returns true if the intersection of first and second is non-empty, where first and second are ordered arrays.

Template parameters
T

a generic type that implements the operators == and <.

BinarySearch

if true, binary search is used to find indices of identical elements rather than linear search.

template<typename T, bool BinarySearch = false>
bool is_subset(
const T *first,
unsigned intfirst_length,
const T *second,
unsigned intsecond_length)

Returns true if first is a subset of second, where first and second are ordered native arrays.

Template parameters
T

a generic type that implements the operators == and <.

BinarySearch

if true, binary search is used to find indices of identical elements rather than linear search.

template<typename T, typename EmitFunction, bool BinarySearch = false>
void set_subtract(
EmitFunctionemit,
const T *first,
unsigned intfirst_length,
const T *second,
unsigned intsecond_length)

Given ordered native arrays first and second, this function visits their elements sequentially, and for every element x that exists in first but not in second, emit(i) is called where first[i] == x. The visited elements are also ordered.

Template parameters
T

a generic type that implements the operators == and <.

BinarySearch

if true, binary search is used to find indices of identical elements rather than linear search.

template<typename T, typename SizeType, bool BinarySearch = false>
void set_subtract(
T *dst,
SizeType &dst_length,
const T *first,
unsigned intfirst_length,
const T *second,
unsigned intsecond_length)

Given ordered native arrays first and second, this function computes the set difference between first and second and stores the result in dst. This function assumes dst has sufficient capacity. The set difference is also ordered.

Template parameters
T

satisfies CopyAssignable and implements the operators == and <.

BinarySearch

if true, binary search is used to find indices of identical elements rather than linear search.

template<typename T, bool BinarySearch = false>
bool set_subtract(
array< T > &dst,
const T *first,
unsigned intfirst_length,
const T *second,
unsigned intsecond_length)

Given ordered native arrays first and second, this function computes the set difference between first and second and stores the result in dst. The set difference is also ordered.

Template parameters
T

satisfies CopyAssignable and implements the operators == and <.

BinarySearch

if true, binary search is used to find indices of identical elements rather than linear search.

template<typename T, bool BinarySearch = false>
bool set_subtract(
array< T > &dst,
const array< T > &first,
const array< T > &second)

Given ordered arrays first and second, this function computes the set difference between first and second and stores the result in dst. The set difference is also ordered.

Template parameters
T

satisfies CopyAssignable and implements the operators == and <.

BinarySearch

if true, binary search is used to find indices of identical elements rather than linear search.

template<typename T, typename SizeType, bool BinarySearch = false>
void set_subtract(
T *first,
SizeType &first_length,
const T *second,
unsigned intsecond_length)

Given ordered native arrays first and second, this function computes the set difference in-place between first and second and stores the result in first. The set difference is also ordered.

Template parameters
T

satisfies CopyAssignable and implements the operators == and <.

BinarySearch

if true, binary search is used to find indices of identical elements rather than linear search.

template<typename T, bool BinarySearch = false>
void set_subtract(
array< T > &first,
const array< T > &second)

Given ordered arrays first and second, this function computes the set difference in-place between first and second and stores the result in first. The set difference is also ordered.

Template parameters
T

satisfies CopyAssignable and implements the operators == and <.

BinarySearch

if true, binary search is used to find indices of identical elements rather than linear search.