Hi!
can you please tell me why people use vector while deque do the same with much more features :(
→ Pay attention
Before contest
Rayan Programming Contest 2024 - Selection (Codeforces Round 989, Div. 1 + Div. 2)
4 days
Register now »
Rayan Programming Contest 2024 - Selection (Codeforces Round 989, Div. 1 + Div. 2)
4 days
Register now »
*has extra registration
→ Top rated
| # | User | Rating |
|---|---|---|
| 1 | tourist | 3993 |
| 2 | jiangly | 3743 |
| 3 | orzdevinwang | 3707 |
| 4 | Radewoosh | 3627 |
| 5 | jqdai0815 | 3620 |
| 6 | Benq | 3564 |
| 7 | Kevin114514 | 3443 |
| 8 | ksun48 | 3434 |
| 9 | Rewinding | 3397 |
| 10 | Um_nik | 3396 |
→ Top contributors
| # | User | Contrib. |
|---|---|---|
| 1 | cry | 167 |
| 2 | Um_nik | 163 |
| 3 | maomao90 | 162 |
| 3 | atcoder_official | 162 |
| 5 | adamant | 159 |
| 6 | -is-this-fft- | 158 |
| 7 | awoo | 155 |
| 8 | TheScrasse | 154 |
| 9 | Dominater069 | 153 |
| 10 | nor | 152 |
→ Find user
→ Recent actions
Codeforces (c) Copyright 2010-2024 Mike Mirzayanov
The only programming contests Web 2.0 platform
Server time: Nov/27/2024 02:41:28 (k1).
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