Skip to content

Suboptimal translation for std::deque #610

Open

Description

@lucic71

We translate std::deque as Vec. This results in suboptimal operations, e.g. std::deque::pop_front is O(1) in C++ and Vec::remove(0) is O(N).

Translate std::deque as VecDeque.

Activity

  1. lucic71 commented on Nov 18, 2026

    @lucic71
    ContributorAuthor
    Operation C++ std::deque Vec (master) VecDeque
    push_back / emplace_back O(1) amortized O(1); O(n) on growth amortized O(1); O(n) on growth
    push_front / emplace_front O(1) O(n) (insert(0, x) shifts everything) amortized O(1); O(n) on growth
    pop_back O(1) O(1) O(1)
    pop_front O(1) O(n) (remove(0) shifts everything) O(1)
    d[i], at, front, back O(1) O(1) O(1)
    iterator ++, --, + n O(1) O(1) O(1)
    insert(pos, x) / erase(pos) in the middle O(min(i, n - i)) O(n - i) (shifts the tail only) O(min(i, n - i))
    size, empty O(1) O(1) O(1)
    clear, copy O(n) O(n) O(n)

    Besides that, both Vec and VecDeque break references after operations that modify the container at the ends. std::deque allocates blocks of memory, not individual elements, so references stay valid.

    I don't think VecDeque can be a good translation because it does not satisfy all complexity requirements and doesn't satisfy the reference validation rules.

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

    No labels
    No labels

    Type

    No type

    Projects

    No projects

      Milestone

      No milestone

      Relationships

      None yet

      Development

      No branches or pull requests

      Issue actions