文件列表:

include/
test/
LICENSE
Makefile

# DDS 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. ## Data-Structures: These are the data-structures currently implemented in the DDS library: ### Slice (extends: LinearContainer, RandomAccessContainer, SortableContainer) `Slice` 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) | 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 BucketContainer) 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 | ### SinglyLinkedList / DoublyLinkedList (extends: LinearContainer) Both these classes are pretty self explainatory. The SinglyLinkedList implements the `backward_foreach`,`backward_fold` and `backward_transform` method by navigating to the last element of the list and using the recursion call-stack to retrieve the elements in opposite order. Nonetheless it's better to use a DoublyLinkedList if you're planning to do a non negligible amount of reverse iterations. | 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) | 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 BucketContainer) 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 | ### Array (extends: RandomAccessContainer, SortableContainer) This is 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) | 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 BucketContainer) 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 |

近期下载者：

相关文件：

评论：[我要评论] [举报此文件]

收藏者：