This library provides various generic data structures implemented in modern object-oriented C++20. The library is tested with the gtest unit-test
framework, and the execution of the tests themselves is monitored with valgrind and fsanitize to ensure the absence of memory leaks.
These are the data-structures currently implemented in the DDS library:
Slice<T> is implemented as a circular buffer that dynamically resizes itself when needed.
It supports random access syntax with square brackets and is indexed starting from 0 up to size()-1.
Objects of type T are constructed on demand and are destroyed as soon as possible using std::construct_at and
std::destroy_at. So even on allocation objects are not constructed immediately, but their construction is
delayed until the user performs an insertion.
| Method | Time-Complexity | Description |
|---|---|---|
| size | O(1) | returns the number of elements stored in the slice |
| count | O(N) | return the number of occurrences of a given element |
| redundant | O(N^2) | returns true if the slice contains duplicates, false otherwise |
| contains | O(N) | returns true if the slice contains a given target element, false otherwise |
| append | O(1) | add an element in the last position, resizing the internal storage if needed |
| prepend | O(1) | add an element in the first position, resizing the internal storage if needed |
| popback | O(1) | removes the last element from the slice |
| popfront | O(1) | removes the first element from the slice |
| [ index ] | O(1) | returns a T& or a const T& to the element at the given position |
| foreach | O(N) | applies a lambda function to every element of the slice |
| forward_foreach | O(N) | applies a lambda function to every element of the slice from first to last |
| backward_foreach | O(N) | applies a lambda function to every element of the slice from last to first |
| fold | O(N) | performs a "fold" operations, often also called "reduce" |
| forward_fold | O(N) | performs a fold from first to last |
| backward_fold | O(N) | performs a fold from last to first |
| transform | O(N) | returns a new Container (LinearContainer or SetContainer) containing the output of a given transformation function, applied to every element of the slice |
| forward_transform | O(N) | a trasform that operates from first to last |
| backward_transform | O(N) | a transform that operates from last to first |
| sort | O(N log N) | sorts the elements of the slice |
| quicksort | O(N log N) | sorts the elements of the slice using the quick-sort algorithm |
| mergesort | O(N log N) | sorts the elements of the slice using the merge-sort algorithm |
| insertionsort | O(N^2) | sorts the elements of the slice using the insertion-sort algorithm |
| selectionsort | O(N^2) | sorts the elements of the slice using the selection-sort algorithm |
This class is a classic doubly-linked-list implementation. It extends LinearContainer<T> but it's not a RandomAccessContainer<T>. The
only way to read and write an element of the list is by using the MutableTraversableContainer<T> API.
| Method | Time-Complexity | Description |
|---|---|---|
| size | O(1) | returns the number of elements stored in the list |
| count | O(N) | return the number of occurrences of a given element |
| redundant | O(N^2) | returns true if the list contains duplicates, false otherwise |
| contains | O(N) | returns true if the list contains a given target element, false otherwise |
| append | O(1) | add an element in the last position, resizing the internal storage if needed |
| prepend | O(1) | add an element in the first position, resizing the internal storage if needed |
| popback | O(1) | removes the last element from the list |
| popfront | O(1) | removes the first element from the list |
| foreach | O(N) | applies a lambda function to every element of the list |
| forward_foreach | O(N) | applies a lambda function to every element of the list from first to last |
| backward_foreach | O(N) | applies a lambda function to every element of the list from last to first |
| fold | O(N) | performs a "fold" operations, often also called "reduce" |
| forward_fold | O(N) | performs a fold from first to last |
| backward_fold | O(N) | performs a fold from last to first |
| transform | O(N) | returns a new Container (LinearContainer or SetContainer) containing the output of a given transformation function, applied to every element of the list |
| forward_transform | O(N) | a trasform that operates from first to last |
| backward_transform | O(N) | a transform that operates from last to first |
Just a wrapper on an ordinary C-Style statically allocated array. It offers a consistent API with the rest of the library.
It needs two template parameters, a type, and a compiletime-known size_t value rappresenting the size.
| Method | Time-Complexity | Description |
|---|---|---|
| size | O(1) | returns the number of elements stored in the array |
| count | O(N) | return the number of occurrences of a given element |
| redundant | O(N^2) | returns true if the array contains duplicates, false otherwise |
| contains | O(N) | returns true if the array contains a given target element, false otherwise |
| [ index ] | O(1) | returns a T& or a const T& to the element at the given position |
| foreach | O(N) | applies a lambda function to every element of the array |
| forward_foreach | O(N) | applies a lambda function to every element of the array from first to last |
| backward_foreach | O(N) | applies a lambda function to every element of the array from last to first |
| fold | O(N) | performs a "fold" operations, often also called "reduce" |
| forward_fold | O(N) | performs a fold from first to last |
| backward_fold | O(N) | performs a fold from last to first |
| transform | O(N) | returns a new Container (LinearContainer or SetContainer) containing the output of a given transformation function, applied to every element of the array |
| forward_transform | O(N) | a trasform that operates from first to last |
| backward_transform | O(N) | a transform that operates from last to first |
| sort | O(N log N) | sorts the elements of the array |
| quicksort | O(N log N) | sorts the elements of the array using the quick-sort algorithm |
| mergesort | O(N log N) | sorts the elements of the array using the merge-sort algorithm |
| insertionsort | O(N^2) | sorts the elements of the array using the insertion-sort algorithm |
| selectionsort | O(N^2) | sorts the elements of the array using the selection-sort algorithm |
A Tree<T> is an AVL balanced binary-search-tree. It works on non-comparable-types as long as a policy gets specified in the constructor. It guarantees logarithmic time complexity
insertions and removals. They can be traversed with foreach and alike methods according to the ordering policy specified at construction.
| Method | Time-Complexity | Description |
|---|---|---|
| size | O(1) | returns the number of elements stored in the tree |
| count | O(log N) | return the number of occurrences of a given element (either 0 or 1 since it stores no duplicates) |
| redundant | O(1) | always returns false since it stores no duplicates |
| contains | O(log N) | returns true if the tree contains a given target element, false otherwise |
| insert | O(log N) | attempts to insert the value provided as first argument, if already present false is returned, on success it returns true |
| remove | O(log N) | attempts to remove the value provided as first argument, if not found false is returned, on success it returns true |
| insert_all | O(M log N) | takes a traversable container of M objects of type T and attempts to insert them, returns true if every one of them got inserted, false otherwise |
| insert_some | O(M log N) | takes a traversable container of M objects of type T and attempts to insert them, returns true if at least one of them got inserted, false otherwise |
| remove_all | O(M log N) | takes a traversable container of M objects of type T and attempts to remove them, returns true if every one of them got removed, false otherwise |
| remove_some | O(M log N) | takes a traversable container of M objects of type T and attempts to remove them, returns true if at least one of them got removed, false otherwise |
| foreach | O(N) | applies a lambda function to every element of the list |
| forward_foreach | O(N) | applies a lambda function to every element of the list from min to max |
| backward_foreach | O(N) | applies a lambda function to every element of the list from max to min |
| fold | O(N) | performs a "fold" operations, often also called "reduce" |
| forward_fold | O(N) | performs a fold from min to max |
| backward_fold | O(N) | performs a fold from max to min |
| transform | O(N) | returns a new Container (LinearContainer or SetContainer) containing the output of a given transformation function, applied to every element of the list |
| forward_transform | O(N) | a trasform that operates from min to max |
| backward_transform | O(N) | a transform that operates from max to min |