Skip to content

VecDeque missing operations for "front" handling. #92547

Open

Description

@Firstyear

From the docs of VecDeque:

"""
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

Activity

  1. hellow554 commented on Jan 4, 2022

    @hellow554
    Contributor

    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.

  2. Firstyear commented on Jan 4, 2022

    @Firstyear
    ContributorAuthor

    No it doesn't. If I have

    fn something(&mut self) {
        self.queue.split_off(4)
    }
    

    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:

    fn something(&mut self) {
        let rhs = self.queue.split_off(4);
        std::mem::swap(&mut rhs, self.queue);
    }
    
  3. sfackler commented on Jan 4, 2022

    @sfackler
    Member
    fn something(&mut self) {
        self.queue = self.queue.split_off(4);
    }
  4. Firstyear commented on Jan 4, 2022

    @Firstyear
    ContributorAuthor

    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.

  5. the8472 commented on Jan 5, 2022

    @the8472
    Member

    Improving the documentation might be sufficient.

  6. Firstyear commented on Jan 5, 2022

    @Firstyear
    ContributorAuthor

    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.

  7. Spielerr commented on Jan 5, 2022

    @Spielerr

    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.

  8. yshui commented on Mar 2, 2022

    @yshui
    Contributor

    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

  9. EdenSegal commented on May 18, 2022

    @EdenSegal

    I also think that truncate_front is needed.

  10. urben1680 commented on Sep 28, 2022

    @urben1680

    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.

  11. esemeniuc commented on Nov 30, 2023

    @esemeniuc

    Would love to see this added as well!

  12. JulianKnodt commented on Jan 23, 2024

    @JulianKnodt
    Contributor

    (sorry for piggybacking off this post)
    I was also looking for an equivalent of extend_from_slice or extend for the beginning (see here)

    I can add it if it would be acceptable.

  13. appcypher commented on Mar 25, 2024

    @appcypher

    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.

  14. dachan-harmonicinc commented on May 23, 2024

    @dachan-harmonicinc

    Please add it. I really need truncate_front

  15. vkrivopalov commented on May 7, 2025

    @vkrivopalov
    Contributor

    VecDeque::truncate_front() has been added with #140668

  16. antonilol commented on Nov 10, 2025

    @antonilol
    Contributor

    Linking a tracking issue I opened recently: #146975

    extend_front has been implemented in #146861

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Metadata

Metadata

Assignees

No one assigned

    Labels

    C-feature-requestCategory: A feature request, i.e: not implemented / a PR.

    Type

    No type

    Projects

    No projects

      Milestone

      No milestone

      Relationships

      None yet

      Development

      No branches or pull requests

      Issue actions