A collection of data structures in C++:
This is a collection of data structures in C++.
The iterators that are used in tfds-classes behave differently than usual iterators, which is why you can't use range-based for loops (That's because these iterators allow both forward and backward iteration with the same syntax).
Dynamic array that can reallocate with an appropriate size when accessed out of bounds. The reallocation size is the smallest multiple of the current size that can fit the new index (in most cases 2 * old index). Automatic reallocation can be turned off in the constructor.
Obviously this is dangerous and should not be used in any kind of production code. But I thought it could be useful for testing something or setting up a quick prototype, as the array can pretty much be treated like pseudo-code.
Default constructor with type std::string, initial capacity 10 and automatic reallocation turned on:
tf::array<std::string> array;A custom initial capacity (in this case 100) and the reallocation behaviour can be set in the constructor:
tf::array<std::string> array(100, false);Runtime: O(1) / O(n) on reallocation
Exceptions: Throws a tf::exception if a buffer overflow or bad_alloc occurs (If automatic reallocation turned off: throws a tf::exception if the index is out of bounds).
Inserts the value "hello" at index 1:
array.insert(1, "hello");Runtime: O(1)
Exceptions: throws a tf::exception if index out of bounds.
Returns a constant reference to the value at index 1:
std::string value = array.get(1);Runtime: O(1) / O(n) on reallocation
Exceptions: Throws a tf::exception if a buffer overflow or bad_alloc occurs (If automatic reallocation turned off: throws a tf::exception if the index is out of bounds).
Returns a reference to the value at index 1:
array[1] = "hello";
std::string value = array[1];Setting a value "out of bounds":
array[25] = "new";Runtime: O(n)
Sets every entry to the value "hello":
array.set_all("hello");Runtime: O(n)
Exceptions: throws a tf::exception if new_capacity is zero or if it is too big and causes a bad_alloc.
Reallocates the array with the new capacity 20:
array.reallocate(20);The content of the array gets copied into the new buffer. If new_capacity is smaller than the old capacity, only the elements up to that point get copied, the rest gets deleted.
Runtime: O(1)
Returns the current current size of the internal buffer:
size_t array_capacity = array.capacity();Runtime: O(1)
Returns true if the array automatically reallocates when accessed out of bounds.
bool array_is_reallocating = array.auto_reallocating();A dynamic array similar to std::vector.
Unlike tf::array, the tf::vector does not automatically reallocate when accessed out of bounds. Instead, accessing out of bounds always throws an exception and new data is inserted to the back of the buffer with add(...), doubling the buffer size when the capacity is reached.
Default constructor with type std::string and initial capacity 10:
tf::vector<std::string> vector;The initial capacity can be set in the constructor:
tf::vector<std::string> vector(100);Runtime: O(1) / O(n) on reallocation
Exceptions: Throws a tf::exception if a buffer overflow or bad_alloc occurs.
Adds the value "hello" to the vector:
vector.add("hello");Runtime: O(1)
Exceptions: Throws a tf::exception if the index is larger or equal to the size.
Returns a constant reference to the element at index 1:
std::string value = vector.get(1);Runtime: O(1)
Exceptions: Throws a tf::exception if the index is larger or equal to the size.
Returns a reference to the element at index 1:
std::string value = vector[1];
vector[1] = "world";Runtime: O(n)
Sets every element to the value "hello":
vector.set_all("hello");Runtime: O(n)
Exceptions: Throws a tf::exception if the index is larger or equal to the size.
Removes and returns the element at index 1:
std::string value = vector.remove(1);Runtime: O(n)
Returns true if the value "hello" is in the vector:
bool contains_value = vector.contains("hello");Runtime: O(n)
Exceptions: throws a tf::exception if new_capacity is zero or if it is too big and causes a bad_alloc.
Reallocates the vector with the new capacity 20:
vector.reallocate(20);The content of the vector gets copied into the new buffer. If new_capacity is smaller than the old capacity, only the elements up to that point get copied, the rest gets deleted.
Runtime: O(1)
Clear the vector:
vector.clear();In reality, clear() just resets the internal index, which means that no actual memory is deallocated and the vector is not reverted to its original capacity. Following calls to add(...) will overwrite the data in the buffer.
Runtime: O(1)
Returns the number of elements in the vector:
size_t num_elements = vector.size();Runtime: O(1)
Returns the current size of the internal buffer:
size_t vector_capacity = vector.capacity();Runtime: O(1)
Returns true if the size of the vector is zero:
bool vector_empty = vector.empty();A doubly linked list.
Allows iteration both forwards and backwards.
Constructor with type std::string:
tf::linked_list<std::string> list;Iterate over the list front to back and print the values:
for (auto it = list.begin(); it.has_value(); ++it) {
std::cout << *it << std::endl;
}Iterate backwards and print the values:
for (auto it = list.end(); it.has_value(); --it) {
std::cout << it.value() << std::endl;
}The value of the iterator can be accessed with either *it or the method it.value() (both methods are identical and interchangeable).
The methods it.next_value() and it.prev_value() return pointers to the following or previous value if they exist, otherwise nullptr.
Runtime: O(1)
Adds the value "hello" to the end of the list:
list.add_back("hello");Runtime: O(1)
Adds the value "hello" to the start of the list:
list.add_front("hello");Runtime: O(n)
Exceptions: Throws a tf::exception if the existing value does not exist.
Adds the value "world" right after the value "hello":
list.add_after("world", "hello");Runtime: O(n)
Exceptions: Throws a tf::exception if the existing value does not exist.
Adds the value "hi" in front of the value "hello":
list.add_before("hi", "hello");Runtime: O(other.n)
Adds all values from list2 to the back of list.
list.add_back_all(list2);list2 is traversed front to back. Both lists have to share the same template type.
Runtime: O(1)
Exceptions: Throws a tf::exception if the list is empty.
Returns a reference to the last value in the list:
std::string last_value = list.back();
list.back() = "back";Runtime: O(1)
Exceptions: Throws a tf::exception if the list is empty.
Returns a reference to the first value in the list:
std::string first_value = list.front();
list.front() = "front";Runtime: O(1)
Exceptions: Throws a tf::exception if the list is empty.
Removes and returns the last value from the list:
std::string last_value = list.pop_back();Runtime: O(1)
Exceptions: Throws a tf::exception if the list is empty.
Removes and returns the first value from the list:
std::string first_value = list.pop_front();Runtime: O(n)
Exceptions: Throws a tf::exception if the value does not exist.
Removes the value "hello" from the list:
list.remove("hello");Runtime: O(n)
Returns true if the value "hello" is found in the list:
bool contains_value = list.contains("hello");Runtime: O(n)
Deallocates all stored values:
list.clear();Runtime: O(1)
Returns the number of elements in the list:
size_t num_elements = list.length();Runtime: O(1)
Returns true if the list has no elements:
bool list_empty = list.empty();An unordered map (Separate Chaining Hash Map).
Any type with non-changing memory can be used as the key, as the hash is built from the memory block of the key. Strings can be used as keys as well (C++ strings and C strings with the same text will produce the same hash).
The default table size is 100 (table size = number of buckets, bucket = linked list of entries). The table size is fixed and can only be modified on construction. For the best performance, the table size should be roughly the maximum number of elements. The performance of O(1) can only be ensured if the table is big enough.
Default constructor with std::string keys and int values and table size 100:
tf::hash_table<std::string, int> table;You can set a custom table size and turn off checking for duplicate keys in the constructor:
tf::hash_table<std::string, int> table(10, false);In this case, the hash table will not check the existing entries for duplicate keys when inserting to improve performance. This flag is mainly supposed to speed up insertion time if you KNOW that there can never be identical keys. If there are duplicate keys inside the table, functions like get(...) and remove(...) will only find one of the inserted pairs.
Iterate over every entry in the hash table and print the values:
for (auto it = table.begin(); it.has_value(); ++it) {
std::cout << *it << std::endl;
}Backward iteration is not supported, since the order of the entries is random and does not matter.
The value of the iterator can be accessed with either *it or the method it.value() (both methods are identical and interchangeable). The key of the iterator can be accessed with the method it.key().
Runtime: average case: O(1) / worst case: O(n)
Exceptions: Checks duplicate keys: throws a tf::exception if the key already exists.
Inserts the value 1 with key "hello" into the hash table:
table.insert("hello", 1);Runtime: average case: O(1) / worst case: O(n)
Exceptions: Throws a tf::exception if the key does not exist.
Returns a constant reference to the value with key "hello":
std::string value = table.get("hello");Runtime: average case: O(1) / worst case: O(n)
Exceptions: Throws a tf::exception if the key does not exist.
Returns a reference to the value with key "hello":
std::string value = table["hello"];
table["hello"] = 2;Runtime: average case: O(1) / worst case: O(n)
Exceptions: Throws a tf::exception if the key does not exist.
Removes the entry with key "hello" and returns the value:
std::string value = table.remove("hello");Runtime: average case: O(1) / worst case: O(n)
Returns true if an entry with key "hello" is found in the hash table:
bool contains_value = table.contains("hello");Runtime: O(n)
Deallocates all stored values:
table.clear();Runtime: O(1)
Returns the number of entries in the hash table:
size_t num_entries = table.size();Runtime: O(1)
Returns the number of buckets in the hash table:
size_t num_buckets = table.table_size();Runtime: O(1)
Returns true if the hash table has no entries:
bool table_empty = table.empty();Runtime: O(1)
Returns true if the hash table looks for duplicate keys when inserting:
bool table_checking_duplicate_keys = table.checks_duplicate_keys();An ordered map (iterative AVL Tree).
The entries are sorted by the key. If duplicate keys are allowed, entries with the same key are not ordered in any particular order.
The keys have to be comparable with either operator==, operator< and operator> or compare functions in the tf-namespace like in tf_compare_functions.hpp.
Constructor with int keys and std::string values:
tf::search_tree<int, std::string> tree;Additionally, you can allow duplicate keys with:
tf::search_tree<int, std::string> tree(true);Iterate over every entry in the search tree in ascending order and print the values:
for (auto it = tree.begin(); it.has_value(); ++it) {
std::cout << *it << std::endl;
}Iterate in descending order:
for (auto it = tree.end(); it.has_value(); --it) {
std::cout << it.value() << std::endl;
}The value of the iterator can be accessed with either *it or the method it.value() (both methods are identical and interchangeable). The key of the iterator can be accessed with the method it.key().
Runtime: O(log(n))
Exceptions: Duplicate keys not allowed: throws a tf::exception if the key already exists.
Inserts the value "hello" with key 1 into the search tree:
tree.insert(1, "hello");Runtime: O(log(n))
Exceptions: Throws a tf::exception if the key does not exist.
Returns a constant reference to one value with key 1:
std::string value = tree.get(1);Runtime: O(log(n))
Exceptions: Throws a tf::exception if the key does not exist.
Returns a reference to one value with key 1:
std::string value = tree[1];
tree[1] = "world";Runtime: O(log(n))
Exceptions: Throws a tf::exception if the tree is empty.
Returns a reference to one value with the smallest key:
std::string min_value = tree.min();Runtime: O(log(n))
Exceptions: Throws a tf::exception if the tree is empty.
Returns a reference to one value with the largest key:
std::string max_value = tree.max();Runtime: O(log(n))
Exceptions: Throws a tf::exception if the tree is empty.
Removes and returns one value with the smallest key:
std::string min_value = tree.pop_min();Runtime: O(log(n))
Exceptions: Throws a tf::exception if the search tree is empty.
Removes and returns one value with the biggest key:
std::string max_value = tree.pop_max();Runtime: O(log(n))
Exceptions: Throws a tf::exception if the key does not exist.
Removes and returns one entry with key 1:
std::string value = tree.remove(1);Runtime: O(log(n))
Exceptions: Throws a tf::exception if the key does not exist.
Removes all entries with key 1 and returns one of them:
std::string value = tree.remove_all(1);Runtime: O(log(n))
Exceptions: Throws a tf::exception if the key-value pair does not exist.
Removes the entry with key 1 and value "hello" and returns "hello" again:
std::string same_value = tree.remove_value(1, "hello");Runtime: O(log(n))
Returns true if the tree contains an entry with key 1:
bool key_present = tree.contains(1);Runtime: O(log(n))
Returns true if the tree contains an entry with key 1 and value "one":
bool key_value_present = tree.contains(1, "one");Runtime: O(n)
Deallocates all entries:
tree.clear();Runtime: O(1)
Returns the number of entries in the search tree:
size_t num_entries = tree.size();Runtime: O(1)
Returns the height of the search tree.
size_t tree_height = tree.height();Runtime: O(log(n))
Returns true if the search tree has no entries:
bool tree_empty = tree.empty();Runtime: O(1)
Returns true if the search tree allows multiple entries with the same key:
bool is_multi_search_tree = tree.allows_duplicate_keys();This is just a wrapper for tf::vector which only provides the functionality of a stack.
The high performance comes at the cost of a memory overhead, as the vector always reallocates with twice its previous size. If sparse memory is required, use a Linked List.
Default constructor with type std::string and initial capacity 10:
tf::stack<std::string> stack;A custom initial capacity, in this case 100, can be set in the constructor:
tf::stack<std::string> stack(100);Runtime: O(1) / O(n) on reallocation
Exceptions: Throws a tf::exception if a buffer overflow or bad_alloc occurs.
Puts the value "hello" on the stack:
stack.put("hello");Runtime: O(1)
Exceptions: Throws a tf::exception if the stack is empty.
Returns a reference to the top value of the stack:
std::string top_value = stack.peek();
stack.peek() = "world";Runtime: O(1)
Exceptions: Throws a tf::exception if the stack is empty.
Removes and returns the top value from the stack:
std::string top_value = stack.pop();Runtime: O(1)
Removes all elements from the stack:
stack.clear();In reality, clear() just resets the internal top index, which means that no actual memory is deallocated and the stack is not reverted to its original capacity.
Runtime: O(1)
Returns the number of elements on the stack:
size_t num_elements = stack.size();Runtime: O(1)
Returns true if the stack is empty:
bool stack_empty = stack.empty();This is just a wrapper for the Linked List which provides only the functionality of a FIFO queue.
Constructor with type std::string:
tf::fifo_queue<std::string> fifo_queue;Runtime: O(1)
Adds the value "hello" to the FIFO queue:
fifo_queue.add("hello");Runtime: O(1)
Exceptions: Throws a tf::exception if the FIFO queue is empty.
Returns the next value in the FIFO queue:
std::string next_value = fifo_queue.next();Runtime: O(n)
Returns true if the FIFO queue contains the value "hello":
bool contains_value = fifo_queue.contains("hello");Runtime: O(n)
Deallocates all elements:
fifo_queue.clear();Runtime: O(1)
Returns the number of elements in the FIFO queue:
size_t num_elements = fifo_queue.length();Runtime: O(1)
Returns true if the FIFO queue has no elements:
bool queue_empty = fifo_queue.empty();This is just a wrapper for the Search Tree which provides only the functionality of a priority queue.
Constructor with int keys and std::string values:
tf::prio_queue<int, std::string> prio_queue;Additionally, you can allow duplicate keys in the constructor:
tf::prio_queue<int, std::string> queue(true);Runtime: O(log(n))
Exceptions: Duplicate keys not allowed (default behaviour): throws a tf::exception if the key already exists.
Adds the value "hello" with the key 1 to the priority queue:
prio_queue.insert(1, "hello");Runtime: O(log(n))
Exceptions: Throws a tf::exception if the priority queue is empty.
Removes and returns one value with the smallest key:
std::string min_value = prio_queue.next_min();Runtime: O(log(n))
Exceptions: Throws a tf::exception if the priority queue is empty.
Removes and returns one value with the biggest key:
std::string max_value = prio_queue.next_max();Runtime: O(log(n))
Returns true if the priority queue contains a value with key 3:
bool contains_value = prio_queue.contains(3);Runtime: O(n)
Deallocates all entries:
prio_queue.clear();Runtime: O(1)
Returns the number of elements in the priority queue.
size_t num_entries = prio_queue.length();Runtime: O(1)
Returns true if the priority queue has no entries.
bool queue_empty = prio_queue.empty();