|
Aleph-w 3.0
A C++ Library for Data Structures and Algorithms
|
Set-like container backed by a dynamic array. More...
#include <tpl_dynarray_set.H>
Public Types | |
| using | Item_Type = T |
| using | Key_Type = T |
Public Types inherited from Aleph::DynArray< T > | |
| using | Item_Type = T |
| using | Key_Type = T |
| The type of element stored in the array. | |
Public Types inherited from StlAlephIterator< DynArray< T > > | |
| using | iterator = StlIterator< DynArray< T > > |
| using | const_iterator = StlConstIterator< DynArray< T > > |
Public Member Functions | |
| DynArray_Set (Equal __eq) | |
| Construct an empty set using a custom equality predicate. | |
| DynArray_Set (Equal __eq, const size_t dim) | |
| Construct a set with a given initial dimension using a custom equality predicate. | |
| DynArray_Set (Equal __eq, size_t _pow_dir, size_t _pow_seg, size_t _pow_block) | |
| Construct a set using custom DynArray layout parameters and a custom equality predicate. | |
| const Equal & | get_equal () const noexcept |
| Return the equality predicate used by this container. | |
| void | set_equal (Equal __eq) |
| Replace the equality predicate used by this container. | |
| T * | insert (const T &item) |
Insert item (duplicates are allowed). | |
| T * | insert (T &&item) |
| T * | search (const T &key) noexcept |
Search for the first element equal to key. | |
| const T * | search (const T &key) const noexcept |
| bool | contains (const T &key) const noexcept |
Check whether key is present. | |
| T & | find (const T &key) |
| Find and return a reference to the first matching element. | |
| const T & | find (const T &key) const |
| size_t | count (const T &key) const noexcept |
Count how many occurrences of key exist. | |
| bool | remove_one (const T &key) |
Remove a single occurrence of key. | |
| size_t | remove_all (const T &key) |
Remove all occurrences of key. | |
Public Member Functions inherited from Aleph::DynArray< T > | |
| size_t | get_dir_size () const noexcept |
| Return the directory size. | |
| size_t | get_seg_size () const noexcept |
| Return the segment size. | |
| size_t | get_block_size () const noexcept |
| Return the block size. | |
| size_t | size () const noexcept |
| Return the current dimension of array. | |
| size_t | max_size () const noexcept |
| Return the maximum allowed dimension (or the maximum number of elements that could have the array treated as a container). | |
| size_t | get_num_blocks () const noexcept |
| Return the number of blocks consumed by the array. | |
| void | set_default_initial_value (const T &value) noexcept |
| Set the default value. | |
| void | set_default_initial_value (T &&value=T()) |
| DynArray (const size_t _pow_dir, const size_t _pow_seg, const size_t _pow_block) | |
| Construct a dynamic array given directory, segment and block sizes. | |
| DynArray (const size_t dim=0) | |
| Default constructor. | |
| template<template< typename > class List> | |
| DynArray (const List< T > &l) | |
| template<class It > | |
| DynArray (It b, It e) | |
| DynArray (std::initializer_list< T > l) | |
| ~DynArray () | |
| void | copy_array (const DynArray< T > &src_array) |
Copy the items of src_array to this | |
| DynArray (const DynArray< T > &array) | |
| Copy constructor. | |
| DynArray< T > & | operator= (const DynArray< T > &array) |
| Copy assignment. | |
| void | swap (DynArray< T > &array) noexcept |
Swap in constant time array with this | |
| DynArray (DynArray &&other) noexcept | |
| Move constructor. | |
| DynArray & | operator= (DynArray &&other) noexcept |
| Move assignment. | |
| T & | access (const size_t i) const noexcept |
| Fast access without checking allocation and bound_min_clock checking. | |
| T & | operator() (const size_t i) const noexcept |
| bool | exist (const size_t i) const |
Return true if the i-th entry is accessible. | |
| T * | test (const size_t i) const noexcept |
| Test if the i-th entry es writable,. | |
| T & | touch (const size_t i) |
| Touch the entry i. | |
| void | reserve (const size_t l, const size_t r) |
| Allocate a range of entries. | |
| void | reserve (const size_t dim) |
| Assure that the range between 0 and dim is allocated. | |
| void | cut_ne (const size_t new_dim=0) |
| void | cut (const size_t new_dim=0) |
| Cut the array to a new dimension; that is, it reduces the dimension of array and frees the remaining memory. | |
| void | adjust (const size_t dim) |
| Set a new dimension. | |
| void | empty () noexcept |
| Empty the array. | |
| Proxy | operator[] (const size_t i) const |
| Proxy | operator[] (const size_t i) |
| T & | append () |
| Allocate a new entry to the end of array. | |
| T & | append (const T &data) |
Copy data to the end of array, increase the dimension and return a modifiable reference to the copied data. | |
| T & | append (T &&data) |
Move data to the end of array, increase the dimension and return a modifiable reference to the copied data. | |
| T & | insert (const T &item) |
| T & | insert (T &&item) |
| void | push (const T &data) |
| T & | push (T &&data) |
| void | put (const T &data) |
| T & | put (T &&data) |
| void | remove (T &item) |
| Given a valid reference to an item in the array, it removes it and decrease the dimension. | |
| void | erase (T &item) |
| bool | is_empty () const noexcept |
Return true if the array is empty. | |
| DynArray & | reverse () |
| Reverse the order of items in array. | |
| T | pop () |
| Remove the last item of array (as if this was a stack) | |
| T & | top () const |
| Return a modifiable reference to the last item of stack. | |
| T & | get_first () const |
| Return a modifiable reference to the first item of array (as if this was a queue) | |
| T & | get_last () const |
| Return a modifiable reference to the last item of array (as if this was a queue) | |
| Iterator | get_it () |
| Iterator | get_it () const |
| Iterator | get_it (const size_t pos) |
| Iterator | get_it (const size_t pos) const |
| template<class Operation > | |
| bool | traverse (Operation &operation) const |
| Traverse all the array and execute a conditioned operation must have the signature: | |
| template<class Operation > | |
| bool | traverse (Operation &operation) |
| template<class Operation > | |
| bool | traverse (Operation &&operation) const |
| template<class Operation > | |
| bool | traverse (Operation &&operation) |
Public Member Functions inherited from LocateFunctions< DynArray< T >, T > | |
| auto | get_it () const |
| Return a properly initialized iterator positioned at the first item on the container. | |
| auto | get_it (const size_t pos) const |
Return a properly initialized iterator positioned at the pos item on the container. | |
| auto | get_itor () const |
Alias of get_it(). | |
| T & | nth_ne (const size_t n) noexcept |
| Return the n‑th element without bounds checking. | |
| const T & | nth_ne (const size_t n) const noexcept |
Const overload of nth_ne(size_t). | |
| T & | nth (const size_t n) |
| Return the n-th item of container. | |
| const T & | nth (const size_t n) const |
Const overload of nth(size_t). | |
| T * | find_ptr (Operation &operation) noexcept(operation_is_noexcept< Operation >()) |
| Find a pointer to an item in the container according to a searching criteria. | |
| const T * | find_ptr (Operation &operation) const noexcept(operation_is_noexcept< Operation >()) |
Const overload of find_ptr(Operation&). | |
| const T * | find_ptr (Operation &&operation) const noexcept(operation_is_noexcept< Operation >()) |
Overload of find_ptr(Operation&) const that accepts rvalues. | |
| T * | find_ptr (Operation &&operation) noexcept(operation_is_noexcept< Operation >()) |
Overload of find_ptr(Operation&) that accepts rvalues. | |
| size_t | find_index (Operation &operation) const noexcept(operation_is_noexcept< Operation >()) |
| Find the position of an item in the container according to a searching criteria. | |
| size_t | find_index (Operation &&operation) const noexcept(operation_is_noexcept< Operation >()) |
Overload of find_index(Operation&) that accepts rvalues. | |
| std::tuple< bool, T > | find_item (Operation &operation) noexcept(operation_is_noexcept< Operation >()) |
| Safe sequential searching of an item matching a criteria. | |
| std::tuple< bool, T > | find_item (Operation &operation) const noexcept(operation_is_noexcept< Operation >()) |
| std::tuple< bool, T > | find_item (Operation &&operation) noexcept(operation_is_noexcept< Operation >()) |
| std::tuple< bool, T > | find_item (Operation &&operation) const noexcept(operation_is_noexcept< Operation >()) |
Public Member Functions inherited from FunctionalMethods< DynArray< T >, T > | |
| void | emplace (Args &&... args) |
| Appends a new element into the container by constructing it in-place with the given args. | |
| void | emplace_end (Args &&... args) |
| void | emplace_ins (Args &&... args) |
| Insert a new element into the container by constructing it in-place with the given args. | |
| size_t | ninsert (Args ... args) |
| Insert n variadic items. | |
| size_t | nappend (Args ... args) |
| Append n variadic items. | |
| void | for_each (Operation &operation) |
| Traverse all the container and performs an operation on each element. | |
| void | for_each (Operation &operation) const |
Const overload of for_each(Operation&). | |
| void | for_each (Operation &&operation) const |
Overload of for_each(Operation&) const that accepts rvalues. | |
| void | for_each (Operation &&operation) |
Overload of for_each(Operation&) that accepts rvalues. | |
| void | each (Operation &operation) |
Alias of for_each(Operation&). | |
| void | each (Operation &operation) const |
Const alias of for_each(Operation&). | |
| void | each (Operation &&operation) const |
Const alias of for_each(Operation&) that accepts rvalues. | |
| void | each (Operation &&operation) |
Alias of for_each(Operation&) that accepts rvalues. | |
| void | each (size_t pos, const size_t slice, Operation &operation) const |
Traverse the container starting at pos taking one item every slice, performing a mutable operation on each visited element. | |
| void | each (const size_t pos, const size_t slice, Operation &&operation) const |
| void | mutable_for_each (Operation &operation) |
| void | mutable_for_each (Operation &&operation) |
| bool | all (Operation &operation) const |
| Check if all the elements of container satisfy a condition. | |
| bool | all (Operation &&operation) const |
Overload of all(Operation&) that accepts rvalues. | |
| bool | exists (Operation &op) const |
| Test for existence in the container of an element satisfying a criteria. | |
| bool | exists (Operation &&op) const |
Overload of exists(Operation&) that accepts rvalues. | |
| Aleph::DynList< __T > | maps (Operation &op) const |
| Map the elements of the container. | |
| Aleph::DynList< __T > | maps (Operation &&op) const |
Overload of maps(Operation&) that accepts rvalues. | |
| Aleph::DynList< __T > | maps_if (Prop prop, Operation &op) const |
| Conditional mapping of the elements of the container. | |
| Aleph::DynList< __T > | maps_if (Prop prop, Operation &&op) const |
Overload of maps_if(Prop, Operation&) that accepts rvalues. | |
| Aleph::DynList< T > | to_dynlist () const |
| Convert container to DynList. | |
| std::vector< T > | to_vector () const |
| Convert container to std::vector. | |
| __T | foldl (const __T &init, Op &op) const |
| Fold the elements of the container to a specific result. | |
| __T | foldl (const __T &init, Op &&op=Op()) const |
Overload of foldl(const __T&, Op&) that accepts rvalues. | |
| __T | fold_left (const __T &init, Op &op) const |
| Alias for foldl with the same accumulator type. | |
| __T | fold_left (const __T &init, Op &&op=Op()) const |
Overload of fold_left(const __T&, Op&) that accepts rvalues. | |
| T | fold (const T &init, Operation &operation) const |
| Simplified version of foldl() where the folded type is the same type of elements stored in the container. | |
| T | fold (const T &init, Operation &&operation) const |
Overload of fold(const T&, Operation&) that accepts rvalues. | |
| Aleph::DynList< T > | filter (Operation &operation) const |
| Filter the elements of a container according to a matching criteria. | |
| Aleph::DynList< T > | filter (Operation &&operation) const |
Overload of filter(Operation&) that accepts rvalues. | |
| Aleph::DynList< const T * > | ptr_filter (Operation &operation) const |
| Filter the elements of a container according to a matching criteria and return a pointer to the matched items in the container. | |
| Aleph::DynList< const T * > | ptr_filter (Operation &&operation) const |
Overload of ptr_filter(Operation&) that accepts rvalues. | |
| Aleph::DynList< std::tuple< T, size_t > > | pfilter (Operation &operation) const |
| Filter the elements of a container according to a matching criteria and determine its positions respect to the traversal of container. | |
| Aleph::DynList< std::tuple< T, size_t > > | pfilter (Operation &&operation) const |
Overload of pfilter(Operation&) that accepts rvalues. | |
| std::pair< Aleph::DynList< T >, Aleph::DynList< T > > | partition (Operation &op) const |
| Exclusive partition of container according to a filter criteria. | |
| std::pair< Aleph::DynList< T >, Aleph::DynList< T > > | partition (Operation &&op) const |
Overload of partition(Operation&) that accepts rvalues. | |
| std::pair< Aleph::DynList< T >, Aleph::DynList< T > > | partition (size_t n) const |
| Exclusive partition of container in the nth item. | |
| std::pair< Aleph::DynList< T >, Aleph::DynList< T > > | split_half () const |
| Split the container into two halves by alternating elements. | |
| std::tuple< Aleph::DynList< T >, Aleph::DynList< T > > | tpartition (Operation &op) const |
| Exclusive partition of container according to a filter criteria. | |
| std::tuple< Aleph::DynList< T >, Aleph::DynList< T > > | tpartition (Operation &&op) const |
Overload of tpartition(Operation&) that accepts rvalues. | |
| size_t | length () const noexcept |
| Count the number of elements of a container. | |
| Aleph::DynList< T > | rev () const |
| Return a list with the elements of container in reverse order respect to its traversal order. | |
| Aleph::DynList< T > | take (const size_t n) const |
| Return a list with the first n elements seen in the container during its traversal. | |
| Aleph::DynList< T > | take (size_t i, const size_t j, const size_t step=1) const |
| Return a list with elements seen in the container between i and j position respect to its traversal. | |
| Aleph::DynList< T > | drop (const size_t n) const |
| Drop the first n elements seen in the container during its traversal. | |
| void | mutable_drop (const size_t n) |
| Drop the first n elements seen from container. | |
Public Member Functions inherited from GenericItems< Container, T > | |
| Aleph::DynList< T > | items () const |
| Return a list of all the elements of a container sorted by traversal order. | |
| Aleph::DynList< T > | keys () const |
Public Member Functions inherited from EqualToMethod< DynArray< T > > | |
| bool | equal_to (const DynArray< T > &r) const noexcept |
Test if elements of this are exactly contained in another container. | |
| bool | operator== (const DynArray< T > &r) const noexcept |
| bool | operator!= (const DynArray< T > &r) const noexcept |
| Negation of equal_to() | |
Public Member Functions inherited from StlAlephIterator< DynArray< T > > | |
| iterator | begin () noexcept |
| Return an STL-compatible iterator to the first element. | |
| const_iterator | begin () const noexcept |
| Return a const iterator to the first element. | |
| iterator | end () noexcept |
| Return an STL-compatible end iterator. | |
| const_iterator | end () const noexcept |
| Return a const end iterator. | |
| const_iterator | cbegin () const noexcept |
| Return a const iterator to the first element. | |
| const_iterator | cend () const noexcept |
| Return a const end iterator. | |
Private Types | |
| using | Base = DynArray< T > |
Private Attributes | |
| Equal | eq |
Related Symbols | |
(Note that these are not member symbols.) | |
| eq | |
Related Symbols inherited from FunctionalMethods< DynArray< T >, T > | |
| each | |
| each | |
| each | |
Additional Inherited Members | |
Static Public Member Functions inherited from Aleph::DynArray< T > | |
| static void | compute_sizes (const size_t n, size_t &d, size_t &s, size_t &b) noexcept |
Given a dimension n, it proposes values for the directory, segment and block sizes. | |
| static std::tuple< size_t, size_t, size_t > | compute_sizes (const size_t n) noexcept |
Given a dimension n, it proposes values for the directory, segment and block sizes. | |
Static Public Attributes inherited from Aleph::DynArray< T > | |
| static const size_t | Default_Pow_Dir = 6 |
| The type of element stored in the array. | |
| static const size_t | Default_Pow_Seg = 8 |
| Default two power for directory size. | |
| static const size_t | Default_Pow_Block = 12 |
| Default two power for segment size. | |
| static const unsigned long long | Max_Dim_Allowed |
| Maximum dimension allowed. | |
Set-like container backed by a dynamic array.
DynArray_Set<T, Equal> is a lightweight set-like container that stores its elements in a DynArray<T>.
This container allows duplicates for performance reasons.
| T | Element type. |
| Equal | Equality predicate used for linear search. It must model a boolean binary predicate. |
Definition at line 71 of file tpl_dynarray_set.H.
|
private |
Definition at line 73 of file tpl_dynarray_set.H.
| using Aleph::DynArray_Set< T, Equal >::Item_Type = T |
Definition at line 78 of file tpl_dynarray_set.H.
| using Aleph::DynArray_Set< T, Equal >::Key_Type = T |
Definition at line 79 of file tpl_dynarray_set.H.
|
inlineexplicit |
Construct an empty set using a custom equality predicate.
| __eq | Equality predicate used by linear search methods. |
Definition at line 87 of file tpl_dynarray_set.H.
|
inline |
Construct a set with a given initial dimension using a custom equality predicate.
| __eq | Equality predicate used by linear search methods. |
| dim | Initial dimension. |
Definition at line 98 of file tpl_dynarray_set.H.
|
inline |
Construct a set using custom DynArray layout parameters and a custom equality predicate.
| __eq | Equality predicate used by linear search methods. |
| _pow_dir | Directory power-of-two. |
| _pow_seg | Segment power-of-two. |
| _pow_block | Block power-of-two. |
Definition at line 111 of file tpl_dynarray_set.H.
|
inlinenoexcept |
Check whether key is present.
Definition at line 165 of file tpl_dynarray_set.H.
References Aleph::DynArray_Set< T, Equal >::search().
|
inlinenoexcept |
Count how many occurrences of key exist.
Definition at line 191 of file tpl_dynarray_set.H.
References Aleph::DynArray< T >::access(), Aleph::DynArray_Set< T, Equal >::eq, and Aleph::DynArray< T >::size().
|
inline |
Find and return a reference to the first matching element.
| std::domain_error | if key is not found. |
This is an overloaded member function, provided for convenience. It differs from the above function only in what argument(s) it accepts.
Definition at line 174 of file tpl_dynarray_set.H.
References ah_domain_error_if, and Aleph::DynArray_Set< T, Equal >::search().
Referenced by Aleph::DynArray_Set< T, Equal >::find(), and TEST().
Definition at line 182 of file tpl_dynarray_set.H.
References Aleph::DynArray_Set< T, Equal >::find().
|
inlinenoexcept |
Return the equality predicate used by this container.
Definition at line 118 of file tpl_dynarray_set.H.
References Aleph::DynArray_Set< T, Equal >::eq.
|
inline |
Insert item (duplicates are allowed).
| std::bad_alloc | if memory allocation fails. |
This is an overloaded member function, provided for convenience. It differs from the above function only in what argument(s) it accepts.
Definition at line 132 of file tpl_dynarray_set.H.
References Aleph::DynArray< T >::append().
Referenced by TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), and TEST().
|
inline |
Definition at line 138 of file tpl_dynarray_set.H.
References Aleph::DynArray< T >::append().
|
inline |
Remove all occurrences of key.
Definition at line 219 of file tpl_dynarray_set.H.
References Aleph::DynArray< T >::access(), Aleph::DynArray_Set< T, Equal >::eq, Aleph::maps(), Aleph::DynArray< T >::remove(), and Aleph::DynArray< T >::size().
Referenced by TEST().
|
inline |
Remove a single occurrence of key.
If there are multiple occurrences, only one is removed.
Definition at line 206 of file tpl_dynarray_set.H.
References Aleph::DynArray< T >::remove(), and Aleph::DynArray_Set< T, Equal >::search().
Referenced by TEST().
Definition at line 156 of file tpl_dynarray_set.H.
References Aleph::DynArray_Set< T, Equal >::search().
|
inlinenoexcept |
Search for the first element equal to key.
This is an overloaded member function, provided for convenience. It differs from the above function only in what argument(s) it accepts.
Definition at line 147 of file tpl_dynarray_set.H.
References Aleph::DynArray< T >::access(), Aleph::DynArray_Set< T, Equal >::eq, and Aleph::DynArray< T >::size().
Referenced by Aleph::DynArray_Set< T, Equal >::contains(), Aleph::DynArray_Set< T, Equal >::find(), Aleph::DynArray_Set< T, Equal >::remove_one(), Aleph::DynArray_Set< T, Equal >::search(), TEST(), TEST(), and TEST().
|
inline |
Replace the equality predicate used by this container.
search() / contains() operations. Definition at line 125 of file tpl_dynarray_set.H.
References Aleph::DynArray_Set< T, Equal >::eq, and Aleph::maps().
This is an overloaded member function, provided for convenience. It differs from the above function only in what argument(s) it accepts.
|
private |