Hi!
can you please tell me why people use vector while deque do the same with much more features :(
→ Pay attention
→ Top rated
| # | User | Rating |
|---|---|---|
| 1 | tourist | 3690 |
| 2 | jiangly | 3647 |
| 3 | Benq | 3581 |
| 4 | orzdevinwang | 3570 |
| 5 | Geothermal | 3569 |
| 5 | cnnfls_csy | 3569 |
| 7 | Radewoosh | 3509 |
| 8 | ecnerwala | 3486 |
| 9 | jqdai0815 | 3474 |
| 10 | gyh20 | 3447 |
→ Top contributors
| # | User | Contrib. |
|---|---|---|
| 1 | maomao90 | 174 |
| 2 | awoo | 165 |
| 3 | adamant | 161 |
| 4 | TheScrasse | 160 |
| 5 | nor | 158 |
| 6 | maroonrk | 156 |
| 7 | -is-this-fft- | 152 |
| 8 | orz | 146 |
| 9 | SecondThread | 145 |
| 9 | pajenegod | 145 |
→ Find user
→ Recent actions
Codeforces (c) Copyright 2010-2024 Mike Mirzayanov
The only programming contests Web 2.0 platform
Server time: May/06/2024 07:16:58 (l2).
Desktop version, switch to mobile version.
Supported by
Really? I didn't know you can find/change the value of an arbitrary element of a deque in O(1)...
take a look at here:http://www.cplusplus.com/reference/deque/deque/operator[]/
Says Complexity is constant.
Lolwut. Its' not really a queue anymore...
Its not a queue.
It's deque. :D
Which is a portmanteau of "double ended queue". See the word "queue" in there?
That was just kidding.
In fact in c++ standard the name "deque" is used just bcz of efficient push and pop from both ends.
Dunno, I don't find nitpicking over words very funny...
Good question, then: why is vector still in use at all? It might have other benefits like being faster or more memory saving, but not on a scale that would matter for most problems...
bcz data is not stored in a continuous structure and it makes deque impossible to use for C libraries.
I think it's implemented using vector, isn't it?
Yeah, it is. But since the element indexing changes, you can't just take the [] operator from vector directly... and since it's just supposed to have the deque functionality, I didn't think element access would be implemented.
It's not like it's hard to write my own deque over a vector.
No.
deque uses paging technic, which dose not keeps data continuously. but vector uses array. and in array data is stored continuously.
The STL deque does. I could just take a 2 vectors and connect them by their starting ends, plus take 1 variable that indicates the true positions of front and back of the resulting deque.
deque is implemented as a vector of vectors.
For example. Also possible.
then we don't use vector anymore...?
deque is faster for growing size.
but vector is faster in other features.
sry, I don't understand what features do you mean.
for example accessing an element of vector is faster than accessing an element of deque.
I thought they are both O(1), isn't it?
but they have a constant difference.
Do you know exactly how much vector is faster? for example ~4 times...
according to this link:http://www.gotw.ca/gotw/054.htm
in builtin types around 2 or 3 times faster. and in complex types around 1.5 faster.
most recursive comments ever
Yes! really :D, I'm wondering too
Both vectors and deques provide a very similar interface and can be used for similar purposes, but internally both work in quite different ways: While vectors use a single array that needs to be occasionally reallocated for growth, the elements of a deque can be scattered in different chunks of storage
from cplusplus.com
Therefore the indexing operator[]() could take more time because you need to determine the certain chunk of memory at first and then the position of an element in this chunk.
And second point — it might be very confusing for the reader of the code to see a deque where he expected one of more standard array types.
Finally someone on codeforces who pays attention for readability :D