3.2 KiB
3.2 KiB
Collections Overview
| Collection | Abstract Data Type | Data Structure | Details |
|---|---|---|---|
| BidiMap bidimap.h |
Bidirectional Map | Two Hashtables | A bijection between two sets of unique keys and unique values K <-> V using two hashtables |
| Deque deque.h |
Double-Ended Queue | Dynamic Circular Array | A circular array that allows push and pop on both ends (only) at constant time |
| HashMap hashmap.h |
Map | Hashtable | A unique set of keys associated with a value K -> V with constant time look up using a hashtable with open addressing and robin hood hashing |
| HashSet hashset.h |
Set | Hashtable | A unique set of values with constant time look up using a hashtable with open addressing and robin hood hashing |
| Heap heap.h |
Priority Queue | Dynamic Array | A binary heap as a dynamic array as an implicit data structure |
| IntervalHeap intervalheap.h |
Double-Ended Priority Queue | Custom Dynamic Array | A dynamic array of nodes, each hosting one value from the MinHeap and one from the MaxHeap |
| LinkedList linkedlist.h |
List | Doubly-Linked List | A default doubly-linked list |
| List list.h |
List | Dynamic Array | A dynamic array with push and pop anywhere on the array |
| MultiMap multimap.h |
Multimap | Custom Hashtable | A mapping of multiple keys with one node per key using a hashtable with separate chaining |
| Multiset multiset.h |
Multiset | Hashtable | A mapping of a value and its multiplicity using a hashtable with open addressing and robin hood hashing |
| Queue queue.h |
FIFO | Dynamic Circular Array | A queue using a circular array with enqueue at the back index and dequeue at the front index |
| SortedList sortedlist.h |
Sorted List | Sorted Dynamic Array | A lazily sorted dynamic array that is sorted only when necessary |
| Stack stack.h |
FILO | Dynamic Array | A stack with push and pop at the end of a dynamic array |
| TreeMap treemap.h |
Sorted Map | AVL Tree | A unique set of keys associated with a value K -> V using an AVL tree with log(n) look up and sorted iteration |
| TreeSet treeset.h |
Sorted Set | AVL Tree | A unique set of keys using an AVL tree with log(n) look up and sorted iteration |