Features

Class	Description
SC::Vector	A contiguous sequence of heap allocated elements.
SC::Array	A contiguous sequence of elements kept inside its inline storage.
SC::SmallVector	A Vector that can hold up to `N` elements inline and `> N` on heap.
SC::VectorMap	A map holding VectorMapItem key-value pairs in an unsorted Vector.
SC::VectorSet	A set built on an unsorted Vector, ensuring no item duplication.
SC::ArenaMap	A sparse vector keeping objects at a stable memory location.

Status

🟨 MVP
All classes defined in the library should be reasonably stable and safe to use.

Description

Generic data structures are a fundamental building blocks for almost every application.
These are some of commonly used ones for common tasks, and the library will grow adding what's needed.

SC::Vector is the king of all generic containers for this library, being in many case the main backend storage for other containers.

SC::Array mimics all methods of SC::Vector but it's guaranteed never to allocate on heap.
All methods are designed to fail with a [[nodiscard]] return value when the container is full.

SC::SmallVector is the middle ground between SC::Array and SC::Vector.
It's a vector with inline storage for N elements, deriving from SC::Vector and it's designed to be passed everywhere a reference to SC::Vector is needed. This allows the caller to get rid of temporary heap allocations if an estimate of the space required is already known or if it's possible providing a reasonable default.
If this estimation is wrong, heap allocation will happen.

Blog

Some relevant blog posts are:

February 2025 Update

Vector

A contiguous sequence of heap allocated elements.

Template Parameters

T	Type of single vector element

All methods of SC::Vector that can fail, return a [[nodiscard]] bool (example SC::Vector::push_back).
Assignment and Copy / move construct operators will just assert as they can't return a failure code.
memcpy is used to optimize copies when T is a memcpy-able object.

Note: Use SC::SmallVector everywhere a SC::Vector reference is needed if the upper bound size of required elements is known to get rid of unnecessary heap allocations.

    Vector<int> myVector;
    SC_TRY(myVector.reserve(10));
    SC_TRY(myVector.push_back(1));
    console.print("[0]={}", myVector[0]);
    SC_TRY(myVector.push_back(2));
    SC_TRY(myVector.pop_back());
    SC_TRY(myVector.pop_front());
    console.print("Vector<int> is {}", myVector.isEmpty() ? "empty" : "not empty");

Array

A contiguous sequence of elements kept inside its inline storage.

Template Parameters

T	Type of single element of the Array
N	Number of elements contained inside this Array inline storage

SC::Array is like a SC::Vector but it will only allow up to N elements in the array, using inline storage, without resorting to heap allocation.
Trying to push or insert more than N elements will fail.
Only up to SC::Array::size elements are valid (and N - size() are initialized).

    Array<int, 3> myVector;
    SC_TRY(myVector.push_back(1));
    SC_TRY(myVector.push_back(2));
    SC_TRY(myVector.push_back(3));
    (void)myVector.push_back(4); // <-- This will fail
    SC_TRY(myVector.pop_back());
    SC_TRY(myVector.pop_front());
    SC_TRY(myVector.pop_front());
    (void)myVector.pop_front(); // <-- This will fail
    console.print("Array<int, 3> is {}", myVector.isEmpty() ? "empty" : "not empty");

SmallVector

A Vector that can hold up to N elements inline and > N on heap.

Template Parameters

T	Type of single vector element
N	Number of elements kept inline to avoid heap allocation

SC::SmallVector is like SC::Vector but it will do heap allocation once more than N elements are needed.
When the size() becomes less than N the container will switch back using memory coming from inline storage.

Note: SC::SmallVector derives from SC::Vector and it can be passed everywhere a reference to SC::Vector is needed. It can be used to get rid of unnecessary allocations where the upper bound of required elements is known or it can be predicted.

    auto pushThreeIntegers = [](Vector<int>& myVector) -> bool
    {
        SC_TRY(myVector.push_back(1));
        SC_TRY(myVector.push_back(2));
        SC_TRY(myVector.push_back(3));
        return true;
    };
    //...
 
    SmallVector<int, 3> mySmallVector;
    SC_TRY(pushThreeIntegers(mySmallVector)); // <-- No heap allocation will happen
 
    // ... later on
 
    SC_TRY(mySmallVector.push_back(4)); // <-- Vector is now moved to heap
 
    // ... later on
 
    SC_TRY(mySmallVector.pop_back()); // <-- Vector is moved back to SmallVector inline storage

VectorMap

A map holding VectorMapItem key-value pairs in an unsorted Vector.

Template Parameters

Key	Type of the key (must support `==` comparison)
Value	Value type associated with Key
Container	Container used for the Map

    VectorMap<String, int> map;
    SC_TRY(map.insertIfNotExists({"A", 2})); // Allocates a String
    SC_TRY(map.insertIfNotExists({"B", 3})); // Allocates a String
    const int* value;
    SC_TRY(map.contains("A", value) && *value == 2); // <-- "A" is a StringView, avoiding allocation
    SC_TRY(map.contains("B", value) && *value == 3); // <-- "B" is a StringView, avoiding allocation
    SC_TRY(not map.contains("C"));                   // <-- "C" is a StringView, avoiding allocation

VectorSet

A set built on an unsorted Vector, ensuring no item duplication.

Template Parameters

Value	The contained value
Container	The underlying container used

    VectorSet<String> setOfStrings;
    SC_TEST_EXPECT(setOfStrings.insert("123"));
    SC_TEST_EXPECT(setOfStrings.insert("123"));
    SC_TEST_EXPECT(setOfStrings.contains("123"));
    SC_TEST_EXPECT(setOfStrings.insert("456"));
    SC_TEST_EXPECT(setOfStrings.contains("123"));
    SC_TEST_EXPECT(setOfStrings.contains("456"));
    SC_TEST_EXPECT(setOfStrings.size() == 2);
    SC_TEST_EXPECT(setOfStrings.remove("123"));
    SC_TEST_EXPECT(setOfStrings.size() == 1);
    SC_TEST_EXPECT(setOfStrings.contains("456"));
    SC_TEST_EXPECT(not setOfStrings.contains("123"));
 
    for (auto& item : setOfStrings)
    {
        SC_TEST_EXPECT(item == "456");
    }

ArenaMap

A sparse vector keeping objects at a stable memory location.

Template Parameters

T	Type of items kept in this Arena

SC::ArenaMap is a container used to keep objects memory location stable.
Internally it hold sparse objects inside of a SC::Vector and for this reason it can only be SC::ArenaMap::resize-d when it's empty.
Objects can be inserted up to the SC::ArenaMap::size and insertion returns handle keys allowing to retrieve the inserted object in constant time.

    ArenaMap<String> map;
    SC_TRY(not map.insert("ASD").isValid());
    SC_TRY(map.resize(3));
    ArenaMap<String>::Key keys[3];
    keys[0] = map.insert("ASD");
    SC_TRY(map.size() == 1);
    SC_TRY(not map.resize(4)); // cannot resize unless is empty
    keys[1] = map.insert("DSA");
    keys[2] = map.insert("BDA");
    SC_TRY(map.size() == 3);
    SC_TRY(not map.insert("123").isValid()); // Arena is full
 
    SC_TRY(map.get(keys[0])->view() == "ASD"); // Get first element
    SC_TRY(map.get(keys[1])->view() == "DSA"); // Get second element
    SC_TRY(map.get(keys[2])->view() == "BDA"); // Get third element

Details

SC::Segment is the class representing a variable and contiguous slice of bytes or objects backing both SC::Vector, SC::SmallVector, SC::Array, SC::Buffer and SC::SmallBuffer.
Memory layout of a segment is a SC::SegmentHeader holding size and capacity of the segment followed by the actual elements.
SC::SegmentHeader is aligned to uint64_t.

Roadmap

🟩 Usable Features:

Add option to let user disable heap allocations in SC::SmallVector
Explicit control on Segment / Vector allocators
HashMap<T>
Map<K, V>

🟦 Complete Features:

More specific data structures

💡 Unplanned Features:

None

Table of Contents

Features

Status

Description

Blog

Vector

Array

SmallVector

VectorMap

VectorSet

ArenaMap

Details

Roadmap