Efficient Data Structures

Context

• Create data structures for controling the data layout (AoS vs SoA)
• These data structures should hide the underlying data layout.
• We want to change the underlying data layout without affecting the code using it.

Using Memory of an Existing Buffer

Problem: Given an existing buffer, we want to allocate our data structures within that buffer.

Solution: We use anallocator that takes a pointer to the buffer and its size in bytes.

#include <cstddef>
#include <stdexcept>

template <typename T>
class BufferAllocator {
public:
    using value_type = T;

    BufferAllocator(char* buffer, std::size_t size)
        : buffer_(buffer), size_(size), offset_(0) {}

    template <typename U>
    BufferAllocator(const BufferAllocator<U>& other) noexcept
        : buffer_(other.buffer_), size_(other.size_), offset_(other.offset_) {}

    T* allocate(std::size_t n) {
        std::size_t bytes = n * sizeof(T);
        if (offset_ + bytes > size_) throw std::bad_alloc();
        T* ptr = reinterpret_cast<T*>(buffer_ + offset_);
        offset_ += bytes;
        return ptr;
    }

    void deallocate(T* ptr, std::size_t n) noexcept {}

private:
    char* buffer_;
    std::size_t size_;
    std::size_t offset_;
};

#include <vector>
#include <iostream>

int main() {
    constexpr std::size_t bufferSize = 1024;
    char buffer[bufferSize];

    // vector of int
    BufferAllocator<int> allocator(buffer, bufferSize);
    std::vector<int, BufferAllocator<int>> v(allocator);
    for (int i = 0; i < 10; ++i) v.push_back(i);
    for (int value : v) std::cout << value << " ";  // 0, 1, 2, ...
    std::cout << std::endl;

    // vector of double
    BufferAllocator<double> new_allocator(buffer, bufferSize);
    std::vector<double, BufferAllocator<double>> w(new_allocator);
    for (int i = 0; i < 10; ++i) w.push_back(-1 * (double)i);
    for (double value : w) std::cout << value << " ";  // 0, -1, -2, ...
    std::cout << std::endl;

    // reading from the int vector now yields garbage
    for (int value : v) std::cout << value << " ";  // 2352344, 34553553, ...
    std::cout << std::endl;

    return 0;
}