Aleph-w 3.0
A C++ Library for Data Structures and Algorithms
Loading...
Searching...
No Matches
Aleph::DynArray_Set< T, Equal > Class Template Reference

Set-like container backed by a dynamic array. More...

#include <tpl_dynarray_set.H>

Inheritance diagram for Aleph::DynArray_Set< T, Equal >:
[legend]
Collaboration diagram for Aleph::DynArray_Set< T, Equal >:
[legend]

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.
 
Tinsert (const T &item)
 Insert item (duplicates are allowed).
 
Tinsert (T &&item)
 
Tsearch (const T &key) noexcept
 Search for the first element equal to key.
 
const Tsearch (const T &key) const noexcept
 
bool contains (const T &key) const noexcept
 Check whether key is present.
 
Tfind (const T &key)
 Find and return a reference to the first matching element.
 
const Tfind (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.
 
DynArrayoperator= (DynArray &&other) noexcept
 Move assignment.
 
Taccess (const size_t i) const noexcept
 Fast access without checking allocation and bound_min_clock checking.
 
Toperator() (const size_t i) const noexcept
 
bool exist (const size_t i) const
 Return true if the i-th entry is accessible.
 
Ttest (const size_t i) const noexcept
 Test if the i-th entry es writable,.
 
Ttouch (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)
 
Tappend ()
 Allocate a new entry to the end of array.
 
Tappend (const T &data)
 Copy data to the end of array, increase the dimension and return a modifiable reference to the copied data.
 
Tappend (T &&data)
 Move data to the end of array, increase the dimension and return a modifiable reference to the copied data.
 
Tinsert (const T &item)
 
Tinsert (T &&item)
 
void push (const T &data)
 
Tpush (T &&data)
 
void put (const T &data)
 
Tput (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.
 
DynArrayreverse ()
 Reverse the order of items in array.
 
T pop ()
 Remove the last item of array (as if this was a stack)
 
Ttop () const
 Return a modifiable reference to the last item of stack.
 
Tget_first () const
 Return a modifiable reference to the first item of array (as if this was a queue)
 
Tget_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< __Tmaps_if (Prop prop, Operation &op) const
 Conditional mapping of the elements of the container.
 
Aleph::DynList< __Tmaps_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.
 
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.
 
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
 

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

Detailed Description

template<typename T, class Equal = Aleph::equal_to<T>>
class Aleph::DynArray_Set< T, Equal >

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

  • Insertion is very fast (amortized append).
  • Search is linear.
  • Removal of an already found element is fast (swap-with-last).

This container allows duplicates for performance reasons.

Template Parameters
TElement type.
EqualEquality predicate used for linear search. It must model a boolean binary predicate.
See also
DynArray

Definition at line 71 of file tpl_dynarray_set.H.

Member Typedef Documentation

◆ Base

template<typename T , class Equal = Aleph::equal_to<T>>
using Aleph::DynArray_Set< T, Equal >::Base = DynArray<T>
private

Definition at line 73 of file tpl_dynarray_set.H.

◆ Item_Type

template<typename T , class Equal = Aleph::equal_to<T>>
using Aleph::DynArray_Set< T, Equal >::Item_Type = T

Definition at line 78 of file tpl_dynarray_set.H.

◆ Key_Type

template<typename T , class Equal = Aleph::equal_to<T>>
using Aleph::DynArray_Set< T, Equal >::Key_Type = T

Definition at line 79 of file tpl_dynarray_set.H.

Constructor & Destructor Documentation

◆ DynArray_Set() [1/3]

template<typename T , class Equal = Aleph::equal_to<T>>
Aleph::DynArray_Set< T, Equal >::DynArray_Set ( Equal  __eq)
inlineexplicit

Construct an empty set using a custom equality predicate.

Parameters
__eqEquality predicate used by linear search methods.

Definition at line 87 of file tpl_dynarray_set.H.

◆ DynArray_Set() [2/3]

template<typename T , class Equal = Aleph::equal_to<T>>
Aleph::DynArray_Set< T, Equal >::DynArray_Set ( Equal  __eq,
const size_t  dim 
)
inline

Construct a set with a given initial dimension using a custom equality predicate.

Parameters
__eqEquality predicate used by linear search methods.
dimInitial dimension.

Definition at line 98 of file tpl_dynarray_set.H.

◆ DynArray_Set() [3/3]

template<typename T , class Equal = Aleph::equal_to<T>>
Aleph::DynArray_Set< T, Equal >::DynArray_Set ( Equal  __eq,
size_t  _pow_dir,
size_t  _pow_seg,
size_t  _pow_block 
)
inline

Construct a set using custom DynArray layout parameters and a custom equality predicate.

Parameters
__eqEquality predicate used by linear search methods.
_pow_dirDirectory power-of-two.
_pow_segSegment power-of-two.
_pow_blockBlock power-of-two.

Definition at line 111 of file tpl_dynarray_set.H.

Member Function Documentation

◆ contains()

template<typename T , class Equal = Aleph::equal_to<T>>
bool Aleph::DynArray_Set< T, Equal >::contains ( const T key) const
inlinenoexcept

Check whether key is present.

Returns
true if at least one matching element exists.

Definition at line 165 of file tpl_dynarray_set.H.

References Aleph::DynArray_Set< T, Equal >::search().

Referenced by TEST(), TEST(), and TEST().

◆ count()

template<typename T , class Equal = Aleph::equal_to<T>>
size_t Aleph::DynArray_Set< T, Equal >::count ( const T key) const
inlinenoexcept

Count how many occurrences of key exist.

Returns
Number of occurrences.

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

Referenced by TEST(), TEST(), TEST(), and TEST().

◆ find() [1/2]

template<typename T , class Equal = Aleph::equal_to<T>>
Aleph::DynArray_Set< T, Equal >::find ( const T key)
inline

Find and return a reference to the first matching element.

Exceptions
std::domain_errorif 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().

◆ find() [2/2]

template<typename T , class Equal = Aleph::equal_to<T>>
const T & Aleph::DynArray_Set< T, Equal >::find ( const T key) const
inline

Definition at line 182 of file tpl_dynarray_set.H.

References Aleph::DynArray_Set< T, Equal >::find().

◆ get_equal()

template<typename T , class Equal = Aleph::equal_to<T>>
const Equal & Aleph::DynArray_Set< T, Equal >::get_equal ( ) const
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.

◆ insert() [1/2]

template<typename T , class Equal = Aleph::equal_to<T>>
Aleph::DynArray_Set< T, Equal >::insert ( const T item)
inline

Insert item (duplicates are allowed).

Returns
Pointer to the inserted element inside the container.
Exceptions
std::bad_allocif 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().

◆ insert() [2/2]

template<typename T , class Equal = Aleph::equal_to<T>>
T * Aleph::DynArray_Set< T, Equal >::insert ( T &&  item)
inline

Definition at line 138 of file tpl_dynarray_set.H.

References Aleph::DynArray< T >::append().

◆ remove_all()

template<typename T , class Equal = Aleph::equal_to<T>>
size_t Aleph::DynArray_Set< T, Equal >::remove_all ( const T key)
inline

Remove all occurrences of key.

Returns
The number of removed elements.

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

◆ remove_one()

template<typename T , class Equal = Aleph::equal_to<T>>
bool Aleph::DynArray_Set< T, Equal >::remove_one ( const T key)
inline

Remove a single occurrence of key.

If there are multiple occurrences, only one is removed.

Returns
true if an element was removed; false if not found.

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

◆ search() [1/2]

template<typename T , class Equal = Aleph::equal_to<T>>
const T * Aleph::DynArray_Set< T, Equal >::search ( const T key) const
inlinenoexcept

Definition at line 156 of file tpl_dynarray_set.H.

References Aleph::DynArray_Set< T, Equal >::search().

◆ search() [2/2]

template<typename T , class Equal = Aleph::equal_to<T>>
Aleph::DynArray_Set< T, Equal >::search ( const T key)
inlinenoexcept

Search for the first element equal to key.

Returns
Pointer to the stored element if found, nullptr otherwise.

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

◆ set_equal()

template<typename T , class Equal = Aleph::equal_to<T>>
void Aleph::DynArray_Set< T, Equal >::set_equal ( Equal  __eq)
inline

Replace the equality predicate used by this container.

Warning
Changing the predicate after inserting elements changes the semantics of subsequent search() / contains() operations.

Definition at line 125 of file tpl_dynarray_set.H.

References Aleph::DynArray_Set< T, Equal >::eq, and Aleph::maps().

Friends And Related Symbol Documentation

◆ eq()

template<typename T , class Equal = Aleph::equal_to<T>>
Aleph::eq
related

This is an overloaded member function, provided for convenience. It differs from the above function only in what argument(s) it accepts.

Member Data Documentation

◆ eq


The documentation for this class was generated from the following files: