You signed in with another tab or window. Reload to refresh your session.You signed out in another tab or window. Reload to refresh your session.You switched accounts on another tab or window. Reload to refresh your session.Dismiss alert
{{ message }}
Repository navigation
VecDeque missing operations for "front" handling. #92547
"""
A double-ended queue implemented with a growable ring buffer.
The “default” usage of this type as a queue is to use push_back to add to the queue, and pop_front to remove from the queue. extend and append push onto the back in this manner, and iterating over VecDeque goes front to back.
"""
From this, we can assume the default way to use VecDeque when visualised is:
front [ a, b, c, d, e ] back
# push_back(f)
front [ a, b, c, d, e, f ] back
VecDeque has a number of operations to reduce the size of the content in the VecDeque such as truncate or split_off, but these assume you want to truncate or split from the back.
front [ a, b, c, d, e, f ] back
# truncate(4)
front [ a, b, c, d ] back
front [ a, b, c, d, e, f ] back
# split_off(4)
front [ a, b, c, d ] back -> front [ e, f ] back
However, what is missing is equivalents for operating on the front of the VecDeque
front [ a, b, c, d, e, f ] back
# truncate_front(4)
front [ c, d, e, f ] back
This created confusion for me wanting to use VecDeque as an ordered ringbuffer since VecDeque will iterate front to back, and recommends you push_back, but trying to maintain a fixed capacity requires you to either manually pop_front to len, OR you need to actually store your VecDeque in reverse, and rely on iter().rev() allowing you to use truncate.
Since VecDeque intends to be "double ended" it would be useful and convenient to have a number of the methods given front variants. My non-exhaustive list is:
truncate
split_off
Reacted by EFanZh, urben1680, Serge Matveenko, Carl Walsh, Dominic C., Dixon Sean Low Yan Feng, Kent Ross, Matthew Borkowski, Skyler Ross, Dana Sorensen and 1 more
Maybe I don't understand you right, but split_off does exactly what you want. It gives you two independent deques. You can choose yourself what to keep and what to throw away (if you want to).
As an alternative you could also use drain and drop the result.
What happens is that self.queue has it's right hand side (the back) removed similar to truncate. The only way to emulate this with "split off" to remove from the front (left) is:
Given rust's pride in docs and accessibility, I think that methods for front operations should exist, so that others don't have to play a puzzle-solving game to achieve this behaviour.
Actually, it's not @the8472. If you look at the source to vecdeque you will see that truncate operates differently to split_off, meaning that it's not sufficient to suggest it as a replacement to truncate. For split_off, retaining the right side, then sure, a documentation improvement would be sufficient. I still think truncate_front is needed.
Yup, I agree with @Firstyear , achieving truncate at front of a deque using split_off or drop/drain workarounds is not ideal. A method such as truncate_front is very similar to the existing implementation of truncate, by altering the front and rear pointers, which would be the most optimized.
There are additional methods of deque which can be extended to respect the inherent property of a deque, that is to support operations both on front and back.
Maybe I don't understand you right, but split_off does exactly what you want. It gives you two independent deques. You can choose yourself what to keep and what to throw away (if you want to).
As an alternative you could also use drain and drop the result.
split_off allocates, and using drain would be O(n), neither are replacement of truncate_front
I want to add that I would also use such functions, truncate_front and split_off_front, the latter if I want to split off the other end.
The workaround in this comment is not ideal as the capacity of self.queue is reduced to it's length while the split off part does not necessarily need a capacity as large as it did as a whole.
Just adding my voice here in support for corresponding "front" operations.
For me in particular, I need the extend_front method and it is weird that it doesn't exist because some other operations do.
I would also like to contribute towards its addition.
Activity
hellow554 commentedon Jan 4, 2022
Maybe I don't understand you right, but
split_offdoes exactly what you want. It gives you two independent deques. You can choose yourself what to keep and what to throw away (if you want to).As an alternative you could also use
drainand drop the result.Firstyear commentedon Jan 4, 2022
No it doesn't. If I have
What happens is that self.queue has it's right hand side (the back) removed similar to truncate. The only way to emulate this with "split off" to remove from the front (left) is:
sfackler commentedon Jan 4, 2022
Firstyear commentedon Jan 4, 2022
Given rust's pride in docs and accessibility, I think that methods for front operations should exist, so that others don't have to play a puzzle-solving game to achieve this behaviour.
the8472 commentedon Jan 5, 2022
Improving the documentation might be sufficient.
Firstyear commentedon Jan 5, 2022
Actually, it's not @the8472. If you look at the source to vecdeque you will see that truncate operates differently to split_off, meaning that it's not sufficient to suggest it as a replacement to truncate. For split_off, retaining the right side, then sure, a documentation improvement would be sufficient. I still think truncate_front is needed.
Spielerr commentedon Jan 5, 2022
Yup, I agree with @Firstyear , achieving truncate at front of a deque using split_off or drop/drain workarounds is not ideal. A method such as truncate_front is very similar to the existing implementation of truncate, by altering the front and rear pointers, which would be the most optimized.
There are additional methods of deque which can be extended to respect the inherent property of a deque, that is to support operations both on front and back.
yshui commentedon Mar 2, 2022
split_offallocates, and usingdrainwould beO(n), neither are replacement oftruncate_frontEdenSegal commentedon May 18, 2022
I also think that truncate_front is needed.
urben1680 commentedon Sep 28, 2022
I want to add that I would also use such functions,
truncate_frontandsplit_off_front, the latter if I want to split off the other end.The workaround in this comment is not ideal as the capacity of
self.queueis reduced to it's length while the split off part does not necessarily need a capacity as large as it did as a whole.esemeniuc commentedon Nov 30, 2023
Would love to see this added as well!
JulianKnodt commentedon Jan 23, 2024
(sorry for piggybacking off this post)
I was also looking for an equivalent of
extend_from_sliceorextendfor the beginning (see here)I can add it if it would be acceptable.
appcypher commentedon Mar 25, 2024
Just adding my voice here in support for corresponding "front" operations.
For me in particular, I need the
extend_frontmethod and it is weird that it doesn't exist because some other operations do.I would also like to contribute towards its addition.
dachan-harmonicinc commentedon May 23, 2024
Please add it. I really need truncate_front
vkrivopalov commentedon May 7, 2025
VecDeque::truncate_front()has been added with #140668antonilol commentedon Nov 10, 2025
Linking a tracking issue I opened recently: #146975
extend_front has been implemented in #146861