array.h
[view source]

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)
SizeTypeindex_of (const Key & element, const T * data, const SizeType & length, const SizeType & start = 0)
unsigned intlast_index_of (const Key & element, const T * data, const SizeType & length)
structarray
boolarray_init (array< T > & m, size_t 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)
boolis_sorted (const T * items, size_t length, const Sorter & sorter)
boolis_sorted (const array< T > & items, const Sorter & sorter)
structdefault_sorter
structpointer_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)
[view source]
#define RESIZE_FACTOR 2

The multiplicative factor by which array capacity is changed.

struct is_resizeable
[view source]

template<typename T>

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

[view source]
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.
SizeType

a type that satisfies is_integral.

T

the generic type of the elements in data.

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.

[view source]
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.

[view source]
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.

[view source]
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.

[view source]
template<typename Key, typename T, typename SizeType>
SizeType index_of(
const Key &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 >= start such that element == data[i].
Key

a generic type for which operator == is defined for arguments of type Key and T.

T

a generic type for which operator == is defined for arguments of type Key and T.

Returns

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

length if the element was not found.

[view source]
template<typename Key, typename T, typename SizeType>
unsigned int last_index_of(
const Key &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].
Key

a generic type for which operator == is defined for arguments of type Key and T.

T

a generic type for which operator == is defined for arguments of type Key and T.

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
[view source]

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 [] (size_t index)
const T &operator [] (size_t index) const
voidclear ()
voidremove (size_t index)
boolensure_capacity (size_t new_length)
boolappend (const T * elements, size_t size)
boolcontains (const Key & element) const
unsigned intindex_of (const Key & element) const
unsigned intindex_of (const Key & element, SizeType start) 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)
[view source]
T * array::data

The underlying native array of elements.

[view source]
size_t array::length

The length of the array.

[view source]
size_t array::capacity

The capacity of array::data.

[view source]
array::array(
size_tinitial_capacity)

Constructs an array with zero size and the given initial_capacity.

[view source]
T & array::operator [] (
size_tindex)

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

[view source]
const T & array::operator [] (
size_tindex) const

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

[view source]
void array::clear()

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

[view source]
void array::remove(
size_tindex)

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.

[view source]
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.

[view source]
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.
T

is TriviallyCopyable.

[view source]
template<typename Key>
bool array::contains(
const Key &element) const
Calls array::index_of to determine whether element exists in this array.
Key

a generic type for which operator == is defined for arguments of type Key and T.

[view source]
template<typename Key>
unsigned int array::index_of(
const Key &element) const
Performs a linear search of the array to find the smallest index i such that element == array::data[i].
Key

a generic type for which operator == is defined for arguments of type Key and T.

Returns

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

array::length if the element was not found.

[view source]
template<typename Key, typename SizeType>
unsigned int array::index_of(
const Key &element,
SizeTypestart) const
Performs a linear search through the array to find the smallest index i >= start such that element == array::data[i].
Key

a generic type for which operator == is defined for arguments of type Key and T.

Returns

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

length if the element was not found.

[view source]
T & array::first()

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

[view source]
const T & array::first()

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

[view source]
T & array::last()

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

[view source]
const T & array::last()

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

[view source]
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.
T

is CopyAssignable.

[view source]
T array::pop()

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

[view source]
T * array::begin()

Returns an iterator to the beginning of the array.

[view source]
T * array::end()

Returns an iterator to the end of the array.

[view source]
const T * array::begin()

Returns a const iterator to the beginning of the array.

[view source]
const T * array::end()

Returns a const iterator to the end of the array.

[view source]
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.

[view source]
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.

[view source]
template<typename T>
bool array_init(
array< T > &m,
size_tinitial_capacity)

Initializes the array m with the given initial_capacity.

[view source]
template<typename T>
size_t size(
const array< T > &m)

Returns array::length of m.

[view source]
template<typename T>
void swap(
array< T > &a,
array< T > &b)

Swaps the underlying buffers of the given arrays.

[view source]
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].

[view source]
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].

[view source]
template<typename T>
void insertion_sort(
T *keys,
unsigned intlength)
Performs insertion sort on the given native array keys with given length.
T

is CopyAssignable, CopyConstructible, and LessThanComparable.

[view source]
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.
T

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

[view source]
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.
K

is CopyAssignable, CopyConstructible, and LessThanComparable.

V

is CopyAssignable, CopyConstructible.

[view source]
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.
K

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

V

satisfies is_moveable.

[view source]
template<typename T>
void insertion_sort(
array< T > &keys)
Performs insertion sort on the given array keys.
T

is CopyAssignable, CopyConstructible, and LessThanComparable.

[view source]
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.
T

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

[view source]
template<typename K, typename V>
void insertion_sort(
array< K > &keys,
array< V > &values)
Performs insertion sort on the given arrays keys and values.
K

is CopyAssignable, CopyConstructible, and LessThanComparable.

V

is CopyAssignable, CopyConstructible.

[view source]
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.
K

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

V

satisfies is_moveable.

[view source]
template<typename T>
void reverse(
T *array,
unsigned intlength)
Reverses the order of the elements in the given native array with given length.
T

satisfies is_swappable.

[view source]
template<typename T>
void reverse(
array< T > &array)
Reverses the order of the elements in the given array.
T

satisfies is_swappable.

[view source]
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.
T

is CopyConstructible, LessThanComparable, and is_swappable.

[view source]
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.
T

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

[view source]
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.
K

is CopyConstructible, LessThanComparable, and is_swappable.

V

satisfies is_swappable.

[view source]
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.
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.

[view source]
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.
T

is CopyConstructible, LessThanComparable, and is_swappable.

[view source]
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.
T

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

[view source]
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.
K

is CopyConstructible, LessThanComparable, and is_swappable.

V

satisfies is_swappable.

[view source]
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.
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.

[view source]
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.
T

is CopyAssignable, CopyConstructible LessThanComparable, and is_swappable.

[view source]
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.
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.

[view source]
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.
K

is CopyAssignable, CopyConstructible LessThanComparable, and is_swappable.

V

satisfies is_swappable and is_moveable.

[view source]
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.
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.

[view source]
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.
T

is CopyAssignable, CopyConstructible LessThanComparable, and is_swappable.

[view source]
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.
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.

[view source]
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.
K

is CopyAssignable, CopyConstructible LessThanComparable, and is_swappable.

V

satisfies is_swappable and is_moveable.

[view source]
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.
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.

[view source]
template<typename T, typename Sorter>
bool is_sorted(
const T *items,
size_tlength,
const Sorter &sorter)
Returns true if and only if the given native array items with the given length is sorted in non-decreasing order.
T

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

[view source]
template<typename T, typename Sorter>
bool is_sorted(
const array< T > &items,
const Sorter &sorter)
Returns true if and only if the given array items is sorted in non-decreasing order.
T

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

struct default_sorter
[view source]

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 <.

struct pointer_sorter
[view source]

The pointer_sorter compares items using the < operator on the dereferenced arguments.

[view source]
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.
T

is CopyAssignable.

[view source]
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.
T

is CopyAssignable.

[view source]
template<typename T>
void shuffle(
T *array,
unsigned intlength)
Performs a Knuth shuffle on the given native array with given length.
T

satisfies is_swappable.

[view source]
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.
T

satisfies is_swappable.

[view source]
template<typename T>
void shuffle(
array< T > &items)
Performs a Knuth shuffle on the given array.
T

satisfies is_swappable.

[view source]
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.

[view source]
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.

[view source]
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.

[view source]
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
[view source]

template<typename K, typename V>

A simple pair data structure.

Public members
Kkey
Vvalue
[view source]
K pair::key

The key object in the field.

[view source]
V pair::value

The value object in the field.

[view source]
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.
T

satisfies is_moveable.

[view source]
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.
T

satisfies is_moveable.

[view source]
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.

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.

[view source]
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.
T

satisfies CopyAssignable and implements the operators == and <.

RemoveDuplicates

if true, this function ignores duplicate elements.

[view source]
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.
T

satisfies CopyAssignable and implements the operators == and <.

RemoveDuplicates

if true, this function ignore duplicate elements.

[view source]
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.
T

satisfies CopyAssignable and implements the operators == and <.

RemoveDuplicates

if true, this function ignore duplicate elements.

[view source]
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.
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].

[view source]
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.
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.

[view source]
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.
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.

[view source]
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.
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.

[view source]
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.
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.

[view source]
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.
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.

[view source]
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.
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.

[view source]
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.
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.

[view source]
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.
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.

[view source]
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.
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.

[view source]
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.
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.

[view source]
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.
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.

[view source]
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.
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.

[view source]
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.
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.

[view source]
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.
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.

[view source]
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.
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.

[view source]
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.
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.