20

As vector and deque both provides a function to push_back the element at the last.

where deque also provides a function push_front to insert the element at the beginning, which is bit costly in case of vector.

My question is when we can achieve the same functionality (push_back) of vector by using deque, then why vector is required?

herohuyongtao
  • 49,413
  • 29
  • 133
  • 174
rajenpandit
  • 1,265
  • 1
  • 15
  • 21

3 Answers3

23

One main difference between vectors and deques is that the latter allows efficient insertion at the front of the structure as well as the back.

Deques also do not guarantee that their elements are contiguous in memory so the at-style operator (indexing) may not be as efficient.

Note that the difference is unlikely to matter in practice for smaller collections but would generally become more important if, for example, the collection size increases or you're modifying it many times per second.

paxdiablo
  • 854,327
  • 234
  • 1,573
  • 1,953
  • 4
    [So does a `std::deque`](http://en.cppreference.com/w/cpp/container/deque/operator_at). – Joseph Mansfield Feb 27 '14 at 12:15
  • 1
    Efficient insertion depends. If there aren't too many elements, and they aren't too expensive to copy, inserting at the front can be cheaper in `std::vector` than in `std::deque`. – James Kanze Feb 27 '14 at 12:29
  • @James, if your structures contain only few elements, you may as well use an array and not bother with collections at all :-) I was thinking more along the lines of larger collections where it's more likely that a deque will be more efficient for front insertion. But you raise a good point so I'll add it. – paxdiablo Feb 27 '14 at 12:31
  • @paxdiablo The question is: when does a container become large enough to justify the difference. A very long time ago, I had a colleague who measured the time necessary to shift a million bytes, and it was surprisingly low (but cache memory and potential misses didn't come into play then). In the end, I don't have any real answer: for 10 `char`, use a C style array or `std::vector` (or `std::array` in C++11). For millions of elements which do a deep copy (with allocation, etc.), use `std::deque`. Somewhere in between is the break off line, but I have no idea where. – James Kanze Feb 27 '14 at 13:46
  • @paxdiablo Arrays are used when you know the exact number of elements at compile time. Other than in some borderline cases (such as trivial types), arrays cannot replace either vector or deque when the number of elements is determined at run time. – Nevin Feb 27 '14 at 15:30
  • Agreed, Nevin, though in reality, arrays are good if you know the _maximum_ rather than exact size. If you know the collection will never be larger than (eg) 10, arrays _may_ even be faster than a vector since you could access it directly rather than through class functions (or it may not, depending on the code generated). – paxdiablo Feb 27 '14 at 15:49
  • @paxdiablo I implemented a FIFO structure of 100 elements that is used to buffer some input sensor data. I implemented with deque by pushing back new incoming elements and popping the front when the size of 100 is reached. Do you think this is an acceptable architectural choice? Yes, I'm modyfing it many time per second. I wanted to know your opinion about which would be a better approach to realize a First In First Out structure that is used to buffer sensor data. Thank you in advance – Employee Aug 12 '19 at 01:52
  • @Lossofhumanidentity: your word "many" may not be the same as my word (italicised) *"many"* :-) If it's a true FIFO, you don't really need to worry about indexing so discount that. Then it's really just a matter of seeing how many inserts per second you can handle. Example, let's say you're sampling rate is 100Hz. All you really need is to dummy up data to pump in an item 100 times a second and see how your processing code handles it. If it never gets anywhere close to 100% capacity, it should be fine. – paxdiablo Aug 12 '19 at 04:11
  • 1
    Note that if you are keeping pointers to the elements, you must use vector as deque will be moved, rendering the pointers invalid. – Pierre Mar 29 '20 at 15:35
13

Performance, mainly. An std::deque has all of the functionality of std::vector, at least for normal use, but indexing and iterating over it will typically be somewhat slower; the same may hold for appending at the end, if you've used reserve. And of course, std::vector is the default container, using anything else will suggest to the reader that you have special requirements.

std::vector also guarantees contiguity, so it (and only it) can be used to interface legacy functions which require a T* or a T const*.

I might add that the one time I actually had a performance issue, and measured, std::vector was faster than std::deque, despite the fact that I was regularly removing elements from the front (using the container as a queue, pushing at the back, and popping at the front). I don't know if that generalizes, however; in my case, the queue was relatively short (never more than about 15 elements, and usually many less), and the contents were char, which is extremely cheap to copy. But in general, I'd use std::vector even if I needed to remove elements from the front, if only because of its better locality. I'd probably only consider std::deque if I expected thousands of elements, which were expensive to copy.

James Kanze
  • 150,581
  • 18
  • 184
  • 329
  • 1
    I implemented a FIFO structure of 100 elements that is used to buffer some input sensor data. I implemented with deque by pushing back new incoming elements and popping the front when the size of 100 is reached. Do you think this is an acceptable architectural choice? I wanted to know your opinion about which would be a better approach to realize a First In First Out structure that is used to buffer sensor data. Thank you in advance – Employee Aug 12 '19 at 01:56
  • 1
    @Employee it will function but is not as ideal for a FIFO as a vector. Since FIFO are ordered and sequential just as Vectors are, they are a better general pairing. However if you are going to change the order of items in the FIFO pipe *after* building the list, then deque may be appropriate. – That Realty Programmer Guy Apr 03 '23 at 17:01
5

std::deque is a double-ended queue. It provides efficient insertion and deletion of elements at the beginning also, not just at the end, as std::vector does. Vectors are guaranteed to store the elements in a contiguous storage, therefore you can access its elements by index/offset. std::deque does not offer this guarantee.

lrineau
  • 6,036
  • 3
  • 34
  • 47
Marius Bancila
  • 16,053
  • 9
  • 49
  • 91
  • 11
    You can also access elements of a `deque` using `[]` or `at()`. There's no difference in the interface at that level. – James Kanze Feb 27 '14 at 12:21