Matěj's Datastructures

This header only library is going to hold all the various data structures I will implement in the future, for now it contains just maps and persistent maps implemented using AVL trees.

To use this library just copy the include/datastructures directory into your project, no external compilation is needed, the data structures live in the datastructures namespace.

For the documentation see this page, or if its down, generate the docs using:

cmake --workflow --preset docs

The code can be found here.

Requirements

For using the library (Header-only)

• C++23 compatible compiler (GCC 13+, Clang 17+, or MSVC 2022)

For building tests & development (CMake Presets)

• CMake 3.20+
• Ninja (required by CMakePresets)
• Git (used by CMake FetchContent to automatically download Catch2)

For generating documentation (Optional)

• Doxygen 1.9+ (recommended 1.9.4+ for Doxygen Awesome theme)
• Graphviz (dot) for class and hierarchy diagrams
• Git (to download the doxygen-awesome-css theme via FetchContent)

Project Structure

• All public classes are in the namespace datastructures
• Internal implementation is in the namespace datastructures::detail
• Tests are in the tests directory and use catch2.
• The project uses CMake to handle compilation and testing.

Data Structures

The library so far defines:

• maps
• persistent maps

Ethereal Maps

This is an implementation of an associative container which maps values of one type to another. It has an O(log n) access and O(log n) insertion/deletion.

To map class is defined in the map.hpp header. It is mostly compatible with the map class from the standard template library, although lacks some features which didn't seem that important for me to implement, like .emplace() etc.

The map class also supports custom methods to compare keys. To use this feature, define a comparator class which has an overloaded operator()(key_type, key_type) method and pass it to the TKeyComp template parameter. If the comparator needs context, use the corresponding constructor to pass your instance to the class.

Similarly, custom allocators are also supported with the exact same logic. Use TAlloc to tell the map which allocator type to use and optionally pass the allocator instance to the constructor.

Example

#include <datastructures/map.hpp>
#include <string>
#include <iostream>

using namespace datastructures;

int main() {
    map<int, std::string> map;

    map.insert_or_assign(20, "twenty");
    map.insert_or_assign(10, "ten");
    map.insert_or_assign(30, "thirty");

    std::cout << map.find(10)->second << "\n"; // prints "ten"
    
    std::cout << map.find(99) == map.end(); // prints true

    return 0;
}

Time Complexity Table

Operation	Time complexity
find	O(log n)
contains	O(log n)
insert	O(log n)
insert_or_assign	O(log n)
erase(key)	O(log n)
operator[]	O(log n)
at	O(log n)
begin / end	O(log n)
size / empty	O(1)
clear	O(n)
iteration over all elements	O(n)

Persistent Maps

A map that has immutable updates, which means that you can search in all older versions.

When you access some element you have to specify in which version to search in.

Similarly, when you perform updates, you can choose which version the new one will be based on. This will create a version tree with each version based on some older one.

Path Copying

The persistence is implemented using the path copying method. That means that for every update operation every modified node and the path to them are copied.

Since the path lenght is atmost log n, the time complexity does not change, although each new version requires O(log n) new space instead of the O(1) new space as in the ethereal map.

Versions

Each version has an ID associated with it. The structure does not remember what change each version brought, if you need this behaviour, implement it separately.

Each update method returns a boolean value encoding whether the opeartion succeded, in such case a new version was created. They also return the newest version ID in that branch, that means the original version ID in the case the operation was not performed and the newly created version ID if the operation was carried out successfuly. The only exception is insert_or_assign which always creates a new version and the boolean value carries the information about the type of the update method that was used.

Version IDs are assigned sequentially starting from 0. For every version with ID n, all versions with IDs from 0 to n - 1 also exist. Therefore, version IDs form a continuous sequence without gaps, and the most recently created version always has the highest ID.

The initial empty-tree version is a special case and has the ID -1.

To get the preceeding version for some other version with ID i, call map.get_preceding_version(i). To get the last version ID created use map.get_current_version(). With these two functions and the fact above you can build the whole version tree if needed.

Invalid version handling

If an invalid version ID (does not exist) is passed to an access method, the function will behave the same way as if the the key did not exist.

If the invalid version ID is given to an update method, the newly created version is going to be based on the initial version with ID -1.

Examples

Basic usage

#include <datastructures/persistent_map.hpp>
#include <iostream>
#include <string>

using namespace datastructures;

int main() {
    persistent_map<int, std::string> map;

    auto [_, v0] = map.insert_or_assign(10, "ten", -1);
    auto [__, v1] = map.insert_or_assign(20, "twenty", v0);
    auto [erased, v2] = map.erase(10, v1);

    std::cout << *map.find(10, v0) << "\n"; // ten
    std::cout << *map.find(20, v1) << "\n"; // twenty

    // Older versions remain unchanged.
    std::cout << (map.find(10, v1) != nullptr) << "\n"; // true
    std::cout << (map.find(10, v2) == nullptr) << "\n"; // true
    std::cout << erased << "\n";                        // true
}

Traversing the version tree

#include <datastructures/persistent_map.hpp>
#include <iostream>

using namespace datastructures;

int main() {
    persistent_map<int, int> map;

    auto [_, v0] = map.insert_or_assign(10, 10, -1);
    auto [__, v1] = map.insert_or_assign(20, 20, v0);
    auto [___, v2] = map.insert_or_assign(30, 30, v0);

    for (auto version = 0; version <= map.get_current_version(); ++version) {
        std::cout << version << " <- "
                  << map.get_preceding_version(version) << "\n";
    }
}

This prints:

0 <- -1
1 <- 0
2 <- 0

which represents the version tree:

-1
 |
 0
/ \
1  2

Time & New Space Complexity Table

Operation	Time complexity	New Space
find	O(log n)	0
contains	O(log n)	0
insert	O(log n)	O(log n)
insert_or_assign	O(log n)	O(log n)
erase(key)	O(log n)	O(log n)
size / empty	O(1)	0
clear	O(n)	0

Licence

The project is licenced under GNU public licence.