Sane C++ Libraries
C++ Platform Abstraction Libraries
All Classes Namespaces Functions Variables Typedefs Enumerations Enumerator Friends Modules Pages
Containers

🟨 Generic containers (SC::Vector, SC::SmallVector, SC::Array etc.)

Containers is a library holding some commonly used generic data structures.

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:

Vector

A contiguous sequence of heap allocated elements.

Template Parameters
TType 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
TType of single element of the Array
NNumber 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
TType of single vector element
NNumber 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
KeyType of the key (must support == comparison)
ValueValue type associated with Key
ContainerContainer used for the 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
ValueThe contained value
ContainerThe 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
TType 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.

SC_TRY(not map.insert("ASD").isValid());
SC_TRY(map.resize(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

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