mardi 30 juin 2015

is the overloaded operator of a std::deque slower than that of a vector

From here I read that for a std::deque the time complexity of retrieving a value using the operator [] is constant. From here I read that time complexity of using the same operator for a std::vector is constant. However in this question Why would I prefer using vector to deque one of the answers with a significant upvote count states that

std::deque doesn't have guaranteed continuous memory - and it's often somewhat slower for indexed access. A deque is typically implemented as a "list of vector".

My question is if its true that retrieval of an index location in a vector is faster than a deque (although both are constant). IS the reason for this is that a double lookup is required for a deque as opposed to a single lookup ?

Aucun commentaire:

Enregistrer un commentaire