Deque VS Vector - Codeforces

11 years ago, # |

-19

Really? I didn't know you can find/change the value of an arbitrary element of a deque in O(1)...

→ Reply

11 years ago, # ^ |

← Rev. 3 →

+16

take a look at here:http://www.cplusplus.com/reference/deque/deque/operator[]/
Says Complexity is constant.

→ Reply

11 years ago, # ^ |

-29

Lolwut. Its' not really a queue anymore...

→ Reply

11 years ago, # ^ |

Its not a queue.
It's deque. :D

→ Reply

11 years ago, # ^ |

-35

Which is a portmanteau of "double ended queue". See the word "queue" in there?

→ Reply

11 years ago, # ^ |

+25

That was just kidding.
In fact in c++ standard the name "deque" is used just bcz of efficient push and pop from both ends.

→ Reply

11 years ago, # ^ |

-19

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...

→ Reply

11 years ago, # ^ |

+17

bcz data is not stored in a continuous structure and it makes deque impossible to use for C libraries.

→ Reply

Rubanenko

11 years ago, # ^ |

I think it's implemented using vector, isn't it?

→ Reply

11 years ago, # ^ |

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.

→ Reply

11 years ago, # ^ |

No.
deque uses paging technic, which dose not keeps data continuously. but vector uses array. and in array data is stored continuously.

→ Reply

11 years ago, # ^ |

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.

→ Reply

11 years ago, # ^ |

deque is implemented as a vector of vectors.

→ Reply

11 years ago, # ^ |

For example. Also possible.

→ Reply

11 years ago, # ^ |

then we don't use vector anymore...?

→ Reply

11 years ago, # ^ |

deque is faster for growing size.
but vector is faster in other features.

→ Reply

11 years ago, # ^ |

sry, I don't understand what features do you mean.

→ Reply

11 years ago, # ^ |

for example accessing an element of vector is faster than accessing an element of deque.

→ Reply

11 years ago, # ^ |

I thought they are both O(1), isn't it?

→ Reply

11 years ago, # ^ |

but they have a constant difference.

→ Reply

11 years ago, # ^ |

Do you know exactly how much vector is faster? for example ~4 times...

→ Reply

11 years ago, # ^ |

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.

→ Reply

kien_coi_1997

11 years ago, # ^ |

-16

most recursive comments ever

→ Reply