Split a vector into 2 subranges without reallocating memory

Question

Let's say I have a container (vector) cont and an iterator split pointing somewhere in the container.

I want to obtain two subranges [cont.begin(), split) and [split, cont.end()) using the memory of the initial container - or maybe the initial container will shrink to the first subrange and the remaining memory will be stolen by the second.

If I was working with manually allocated arrays, I'd have someting like :

double *cont; // the 'container' - memory was allocated for this
int sz;       // the size of the container
int cap;      // the capacity of the container

Then (since I'm manually doing the bookeeping) I could introduce a new 'container'

double *slice = cont + split; // in this context split is an index and not an iterator
int slice_sz  = sz - split;
int slice_cap = capacity - split;

So then the 'container' would be updated as

sz -= split;
cap = split;

Is this doable with STL ? Can I use the existing chunk of memory and have two containers with updated members (size, capacity etc ... I suppose the hack of passing .data has no meaning)

PS

I'm aware the standard solution would be to work with iterator ranges, but I have a context where I need to work with complete containers, so [begin, split) and [split, end) is not any good.

Answer 1

If you use a specific allocator, you may share the memory. Something like the following may help:

template <typename T>
struct buffer_allocator
{
    using size_type = std::size_t;
    using difference_type = std::ptrdiff_t;
    using pointer = T*;
    using const_pointer = const T*;
    using reference = T&;
    using const_reference = const T&;
    using value_type = T;

    buffer_allocator(T* buffer, std::size_t max_size) :
        buffer(buffer), max_size(max_size)
    {}

    template<typename... Args>
    void construct(T* p, Args&&... args)
    { /*::new((void *)p) T(std::forward<Args>(args)...);*/ }

    void destroy(T* p) { /*p->~T();*/ }

    T* allocate(std::size_t n)
    {
        if (max_size != n) { throw std::bad_alloc{}; }
        return buffer;
    }

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

    std::size_t get_max_size() const { return max_size; }

private:
    T* buffer;
    std::size_t max_size;
};

And use it that way: (https://ideone.com/MaDYPZ)

std::vector<int> v{0, 1, 2, 3, 4};
buffer_allocator<int> b1(v.data(), 3);
buffer_allocator<int> b2(v.data() + 3, v.size() - 3);
std::vector<int, buffer_allocator<int>> v1(b1.get_max_size(), b1);
std::vector<int, buffer_allocator<int>> v2(b2.get_max_size(), b2);

Answer 2

You can't have two "containers", but you can have two iterator ranges.

vector<double> v;
vector<double>::iterator split = v.begin() + offset;

do_something(v.begin(), split);
do_something(split, v.end());

So the question becomes, what sort of operations do you want to perform on your two ranges?

Answer 3

As you already mention slices, you could have a look at std::valarray and see if that fits your requirements better.

std::valarray v(n);
auto first = v.slice(0, split, 1);
auto second = v.slice(split, v.size() - split, 1);

This gives you two slices referencing the original valarray.

Answer 4

Is it possible for you to use std::list instead of std::vector? The list container has a splice function that can be used to move elements between lists: http://www.cplusplus.com/reference/list/list/splice/

This is mostly possible because list is usually implemented as a linked list.