Containers Tutorial

OULY provides high-performance containers with STL-compatible interfaces and support for custom allocators. This tutorial covers the available containers and their optimal usage patterns.

Container Overview

OULY includes several specialized containers:

  • small_vector - Stack-optimized vector for small collections

  • dynamic_array - High-performance resizable array

  • sparse_vector - Memory-efficient sparse storage

  • intrusive_list - Zero-allocation linked list

  • soavector - Structure of Arrays container

Each container is designed for specific use cases and performance characteristics.

Small Vector

The small_vector stores small collections on the stack, avoiding heap allocations:

#include <ouly/containers/small_vector.hpp>
#include <iostream>

int main() {
    // Small vector with stack storage for up to 8 elements
    ouly::small_vector<int, 8> numbers;

    // These additions use stack storage (no heap allocation)
    for (int i = 0; i < 8; ++i) {
        numbers.push_back(i);
    }

    std::cout << "Capacity: " << numbers.capacity() << "\n";  // 8
    std::cout << "Is on stack: " << !numbers.is_heap_allocated() << "\n";  // true

    // This triggers heap allocation
    numbers.push_back(8);
    std::cout << "After growth - on heap: " << numbers.is_heap_allocated() << "\n";  // true

    // STL-compatible interface
    for (const auto& num : numbers) {
        std::cout << num << " ";
    }
    std::cout << "\n";

    return 0;
}

Use Cases: * Function parameters/return values with typically small sizes * Collections with known small upper bounds * Avoiding heap allocations for performance-critical paths

Dynamic Array

The dynamic_array provides optimized growth strategies and custom allocator support:

#include <ouly/containers/dynamic_array.hpp>
#include <ouly/allocators/linear_arena_allocator.hpp>

int main() {
    // Using custom allocator
    ouly::linear_arena_allocator<> arena(1024 * 1024);

    ouly::dynamic_array<float> positions;
    positions.set_allocator(&arena);

    // Efficient bulk operations
    positions.resize(1000);
    positions.reserve(2000);  // Pre-allocate capacity

    // Fill with data
    for (size_t i = 0; i < positions.size(); ++i) {
        positions[i] = static_cast<float>(i) * 0.1f;
    }

    std::cout << "Array size: " << positions.size() << "\n";
    std::cout << "Array capacity: " << positions.capacity() << "\n";

    // Efficient range operations
    auto subrange = positions.subrange(100, 200);
    for (auto value : subrange) {
        std::cout << value << " ";
    }

    return 0;
}

Sparse Vector

The sparse_vector efficiently stores data for sparse indices:

#include <ouly/containers/sparse_vector.hpp>
#include <iostream>

struct Component {
    float x, y, z;
    Component(float x, float y, float z) : x(x), y(y), z(z) {}
};

int main() {
    ouly::sparse_vector<Component> components;

    // Insert at sparse indices
    components.emplace(10, 1.0f, 2.0f, 3.0f);
    components.emplace(100, 4.0f, 5.0f, 6.0f);
    components.emplace(1000, 7.0f, 8.0f, 9.0f);

    std::cout << "Size: " << components.size() << "\n";  // 3 elements
    std::cout << "Dense storage, sparse indices\n";

    // Check if indices exist
    if (components.contains(100)) {
        auto& comp = components[100];
        std::cout << "Component at 100: (" << comp.x << ", " << comp.y << ", " << comp.z << ")\n";
    }

    // Iterate over all elements (dense iteration)
    for (auto& [index, component] : components) {
        std::cout << "Index " << index << ": ("
                  << component.x << ", " << component.y << ", " << component.z << ")\n";
    }

    return 0;
}

Use Cases: * Entity-component systems with sparse entity IDs * Sparse matrices and mathematical computations * Cache-friendly storage for sparse data sets

Intrusive List

The intrusive_list provides zero-allocation linked list functionality:

#include <ouly/containers/intrusive_list.hpp>
#include <iostream>

struct Node : public ouly::intrusive_list_node<Node> {
    int value;
    Node(int v) : value(v) {}
};

int main() {
    ouly::intrusive_list<Node> list;

    // Create nodes (can be allocated anywhere)
    Node node1(10);
    Node node2(20);
    Node node3(30);

    // Insert into list (no heap allocation)
    list.push_back(node1);
    list.push_back(node2);
    list.push_front(node3);

    std::cout << "List contents: ";
    for (const auto& node : list) {
        std::cout << node.value << " ";
    }
    std::cout << "\n";

    // Remove specific node
    list.remove(node2);

    std::cout << "After removal: ";
    for (const auto& node : list) {
        std::cout << node.value << " ";
    }
    std::cout << "\n";

    return 0;
}

Use Cases: * Memory pools where allocation is managed separately * Real-time systems requiring predictable performance * Embedded systems with strict memory constraints

Structure of Arrays (SoA)

The soavector stores aggregate types in Structure of Arrays format for better cache utilization and SIMD optimization:

#include <ouly/containers/soavector.hpp>
#include <iostream>

// Define aggregate structure
struct Particle {
    float x, y, z;    // position
    float vx, vy, vz; // velocity
    int life;         // lifetime
    float mass;       // mass
};

int main() {
    // soavector automatically expands Particle into separate arrays
    ouly::soavector<Particle> particles;

    // Add particles - constructor arguments match struct members
    for (int i = 0; i < 100; ++i) {
        particles.emplace_back(
            static_cast<float>(i),      // x
            static_cast<float>(i * 2),  // y
            0.0f,                       // z
            1.0f, 0.0f, 0.0f,          // velocity
            100,                        // life
            1.0f                        // mass
        );
    }

    // Access individual arrays for vectorization
    auto& x_positions = particles.get<0>();  // Array of x coordinates
    auto& y_positions = particles.get<1>();  // Array of y coordinates
    auto& z_positions = particles.get<2>();  // Array of z coordinates
    auto& x_velocities = particles.get<3>(); // Array of x velocities
    auto& lifetimes = particles.get<6>();    // Array of lifetimes

    // SIMD-friendly operations on individual arrays
    for (size_t i = 0; i < particles.size(); ++i) {
        x_positions[i] += x_velocities[i];
        y_positions[i] += particles.get<4>()[i]; // y velocity
        z_positions[i] += particles.get<5>()[i]; // z velocity
        lifetimes[i] -= 1;
    }

    // Individual element access (reconstructs the aggregate)
    auto particle = particles[0];
    std::cout << "Particle 0: x=" << particle.x
              << " y=" << particle.y
              << " life=" << particle.life << "\n";

    // Iterate over all particles (less efficient than array access)
    for (const auto& p : particles) {
        if (p.life <= 0) {
            // Handle dead particle
        }
    }

    return 0;
}

Use Cases: * Game engines (particles, entities, physics) * Scientific computing with large datasets * Any application requiring SIMD optimizations

Container Algorithms

OULY containers work with STL algorithms and provide additional utilities:

#include <ouly/containers/dynamic_array.hpp>
#include <algorithm>
#include <numeric>

int main() {
    ouly::dynamic_array<int> numbers = {5, 2, 8, 1, 9, 3};

    // STL algorithms work seamlessly
    std::sort(numbers.begin(), numbers.end());

    auto sum = std::accumulate(numbers.begin(), numbers.end(), 0);
    std::cout << "Sum: " << sum << "\n";

    // Find element
    auto it = std::find(numbers.begin(), numbers.end(), 8);
    if (it != numbers.end()) {
        std::cout << "Found 8 at position: " << std::distance(numbers.begin(), it) << "\n";
    }

    // Custom algorithms
    numbers.for_each([](int& x) { x *= 2; });

    return 0;
}

Custom Allocators

All OULY containers support custom allocators:

#include <ouly/containers/dynamic_array.hpp>
#include <ouly/allocators/pool_allocator.hpp>

int main() {
    // Pool allocator for fixed-size allocations
    ouly::pool_allocator<> pool(1024, 100);  // 100 blocks of 1KB each

    // Container using custom allocator
    ouly::dynamic_array<char> buffer;
    buffer.set_allocator(&pool);

    // All allocations will use the pool
    buffer.resize(1024);
    buffer.resize(2048);  // Will allocate second block

    std::cout << "Pool utilization: " << pool.used_blocks() << "/" << pool.total_blocks() << "\n";

    return 0;
}

You can also use OULY containers with STL allocator adaptors:

#include <ouly/allocators/std_allocator_wrapper.hpp>
#include <vector>

int main() {
    ouly::linear_arena_allocator<> arena(1024);

    // Use OULY allocator with STL containers
    using AllocType = ouly::std_allocator_wrapper<int, decltype(arena)>;
    std::vector<int, AllocType> vec(AllocType(arena));

    vec.push_back(1);
    vec.push_back(2);
    vec.push_back(3);

    return 0;
}

Container Configuration

OULY containers can be customized using configuration templates in the ouly::cfg namespace:

Blackboard Configuration

The blackboard container supports custom hash map implementations:

#include <ouly/containers/blackboard.hpp>
#include <unordered_map>

// Using custom hash map type
using CustomConfig = ouly::config<
    ouly::cfg::map<std::unordered_map>
>;

ouly::blackboard<CustomConfig> board;

Available Container Configuration Options:

  • ouly::cfg::map<T> - Specify custom hash map implementation for blackboard

  • ouly::cfg::name_map<T> - Custom key-to-offset mapping for blackboard

  • ouly::cfg::name_val_map<T> - Complete custom blackboard hash map

  • ouly::cfg::pool_size<N> - Set pool size for internal allocations

  • ouly::cfg::index_pool_size<N> - Pool size for index management

  • ouly::cfg::use_sparse - Enable sparse storage strategy

  • ouly::cfg::use_direct_mapping - Enable direct mapping strategy

  • ouly::cfg::custom_vector<T> - Use custom vector implementation

Common Configuration Examples:

// Sparse container with custom pool size
using SparseConfig = ouly::config<
    ouly::cfg::use_sparse,
    ouly::cfg::pool_size<8192>
>;

// Direct mapping with large index pool
using FastConfig = ouly::config<
    ouly::cfg::use_direct_mapping,
    ouly::cfg::index_pool_size<16384>
>;

// Custom vector backend
using VectorConfig = ouly::config<
    ouly::cfg::custom_vector<std::vector<int>>
>;

Performance Considerations

Container Selection

  1. small_vector - Best for collections typically < N elements

  2. dynamic_array - General-purpose high-performance array

  3. sparse_vector - When indices are sparse but iteration should be dense

  4. intrusive_list - When you need stable references and zero allocation

  5. soavector - When you need SIMD optimization and cache efficiency

Performance Comparison: AoS vs SoA

// Array of Structures (AoS) - poor cache utilization for partial access
struct Particle { float x, y, z; int life; };
std::vector<Particle> aos_particles;

// Structure of Arrays (SoA) - better cache utilization and SIMD-friendly
struct Particle { float x, y, z; int life; };
ouly::soavector<Particle> soa_particles;  // Automatically splits into separate arrays

// When you only need to update positions:
// AoS loads entire Particle structs (16 bytes each)
// SoA loads only position arrays (4 bytes each)

Growth Strategies

ouly::dynamic_array<int> numbers;

// Pre-allocate if final size is known
numbers.reserve(1000);

// Use bulk operations when possible
numbers.resize(1000);  // Better than 1000 push_back calls

Best Practices

  1. Choose the Right Container

    • Analyze access patterns (random vs sequential)

    • Consider element lifetime and stability requirements

    • Profile different containers for your use case

  2. Memory Management

    • Use custom allocators for better control

    • Pre-allocate capacity when size is predictable

    • Consider memory alignment for SIMD operations

  3. Performance Optimization

    • Use SoA layout for vectorizable operations

    • Prefer intrusive containers in memory-constrained environments

    • Batch operations when possible

  4. API Design

    • Containers are designed to work with range-based for loops

    • STL algorithms work seamlessly

    • Custom iterators provide additional safety and features

Next Steps