Sane C++ Libraries: Containers (original) (raw)

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

SaneCppContainers.h is a library holding some commonly used templated data structures.

While all libraries are designed to let you use your favorite externally provided string / vector classes, there is also an choice of basic containers (mainly Vector<T> incarnations), with support for inline buffer and custom scoped allocators provided by Memory library.

Note

See Tests/InteropSTL/*.cpp for an example of externally provided Container classes.

Dependencies

• Dependencies: Memory
• All dependencies: Foundation, Memory

Features

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

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.

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 is {}", myVector.isEmpty() ? "empty" : "not empty");

Array

A contiguous sequence of elements kept inside its inline storage.

Template Parameters

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).

SC_TRY(myVector.push_back(1));

SC_TRY(myVector.push_back(2));

SC_TRY(myVector.push_back(3));

(void)myVector.push_back(4);

SC_TRY(myVector.pop_back());

SC_TRY(myVector.pop_front());

SC_TRY(myVector.pop_front());

(void)myVector.pop_front();

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

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& myVector) -> bool

{

SC_TRY(myVector.push_back(1));

SC_TRY(myVector.push_back(2));

SC_TRY(myVector.push_back(3));

return true;

};

SC_TRY(pushThreeIntegers(mySmallVector));

SC_TRY(mySmallVector.push_back(4));

SC_TRY(mySmallVector.pop_back());

VectorMap

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

Template Parameters

VectorSet

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

Template Parameters

for (auto& item : setOfStrings)

{

}

ArenaMap

A sparse vector keeping objects at a stable memory location.

Template Parameters

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());

keys[0] = map.insert("ASD");

SC_TRY(not map.resize(4));

keys[1] = map.insert("DSA");

keys[2] = map.insert("BDA");

SC_TRY(not map.insert("123").isValid());

SC_TRY(map.get(keys[0])->view() == "ASD");

SC_TRY(map.get(keys[1])->view() == "DSA");

SC_TRY(map.get(keys[2])->view() == "BDA");

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

Statistics