How to efficiently cut vector's head?


#1

There is truncate method on vec. It cuts vector’s tail, and this operation doesn’t need to copy content of vector, hence, this is probably an efficient operation.

But how can you cut vector’s head? Or, can you make a new vector that has vec[k…] elements only, totally forgetting original vector?

Risking to go in a misleading direction, should things like into_vec be used, or code like that be used? If so, how pointer is to change, and how to let system know that memory infront of the pointer can be reclaimed.


#2

Does it have to be a Vec? The standard library VecDeque data structure supports an efficient pop_front() which cuts the head element.


#3

The most efficient method is probably vec.drain(..k), which removes the first k items from the vector, shifting the remainder over. There is no way of performing this operation without copying the remainder of the items in the vector.


#4

It looks like Drain::drop always uses memmove rather than memcpy, possibly leaving some performance on the table. It would seem there are cases where the drained and remaining regions don’t overlap, maybe even the most common drain usecase? I couldn’t find any discussion around this, so maybe it’s a non-issue (or I’m missing something).

But as @dtolnay mentioned, if this is a common need then a Vec probably isn’t the right container to begin with.


#5

I could imagine memmove’s implementation checking for non-overlapping buffers and calling to memcpy, but I don’t know if it actually does that.


#6

Thank you for pointing VecDeque, didn’t know about its existence.
But in my particular case, I needed a slice &x[0…n], with n > cut_index, and VecDeque can only provide disjoint chunks.

In the end, I changed layout of internal calls, removing a need for slice that spans the cut, overcoming this need entirely.

Yet, the lesson I am having here is that

  • pointer in vector has an allocated chunk associated with it, and it cannot be changed in size (std::mem?), and can only be forgotten or deallocated.
  • this limited range of actions is due to what machine gives us.
    Is this correct?

#7

I think it is more precisely due to what the OS and libc gives us. I cannot think of a reason why realloc() could not resize a chunk of memory forward, extra allocator complexity aside.