Igate Interview Question
Technical ArchitectsCountry: India
Interview Type: In-Person
@eugene: Correct, i dont know the "exact" internal implementation of deque but i see it is a class with number of dynamically allocated memory chunks and information about how these chunks are linked. Having said that, I believe the information I shared does answer the 3 questions asked.
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 are very similar to a plain array that grows by reallocating all of its elements in a unique block when its capacity is exhausted, the elements of a deques can be divided in several chunks of storage, with the class keeping all this information and providing a uniform access to the elements. Therefore, deques are a little more complex internally, but this generally allows them to grow more efficiently than the vectors with their capacity managed automatically, specially in large sequences, because massive reallocations are avoided.
- romilshah29 July 25, 2012So deques can be preferred over vector when the estimated size of data is not clearly known and much reallocation is expected.
When an element is inserted into a deque there is a check for available space for the new entry. If no space is available a chunk of memory is allocated and linking information is added to deque class.