maybesomeone's blog

Deque
By maybesomeone, history, 2 years ago, In English

is vector better than deque ?. can someone tell what are some things that makes vector better than deque

  • Vote: I like it
  • +11
  • Vote: I do not like it

Comments Comments (5)
| Write comment?
»
2 years ago, # |
← Rev. 3   Vote: I like it +3 Vote: I do not like it

You can push_back() [basically adding elements on the last] on both deque and vector. Deque can pop_front()/push_front() which is basically removing/adding the first element. You can also do this in vector but it will take O(n) to shift the entire vector but deque will take O(1). But you can always have an integer/pointer variable that points to the start of the vector, so when you need to remove an element from the front, just increase the value of the pointer/variable by 1 (adding to the front will still take O(n) and you cant avoid that). Vector also has added benefits of being able to sort elements easily. So Vector is better in my opinion but there are some cases where deque is needed (mainly because using vector in place of deque in this way will mean that size of the vector is equal to or greater than the deque as you aren't actually deleting the element from the vector, and also in cases where you need to add elements in the front). Hope this helps brother!

→ Reply
  • »
    »
    2 years ago, # ^ |
      Vote: I like it +6 Vote: I do not like it

    i know this and we can also sort deque. my main question is what makes vector better than deque. or is both of them same in terms of time complexity and memory usage

    → Reply
    • »
      »
      »
      2 years ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      Oh, I didn't know you can sort deques. In terms of functionality I think deque is faster but it doesn't have built in sorting-upperbounds-lowerbounds-find functions (you have to make them yourself).

      → Reply
»
2 years ago, # |
  Vote: I like it +3 Vote: I do not like it

You should read this. This blog has detailed discussion on C++ deque and C++ vector

→ Reply
»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Deque is very similar to vector in terms of time complexity. The most obvious difference is that deque allows for O(1) push_front/pop_front.

However one noticable difference is that push_back on a vector can invalidate pointers to elements in the vector, but push_back onto a deque will not. This is because vector needs to do reallocation to increase its capacity. On the other hand deque is stored in fixed sized blocks in memory, so it does not need to reallocate.

→ Reply