tags:

views:

184

answers:

4

hi,

Can some one please tell me what is the difference between vector vs dequeue. I know the implementation of vector in C++ but not dequeue. Also interfaces of map and set seem similar to me. What is the difference between the two and when to use one.

+2  A: 

set: holds unique values. Put 'a' in twice, the set has one 'a'. map: maps keys to values, e.g. 'name' => 'fred', 'age' => 40. You can look up 'name' and you'll get 'fred' out.

dequeue, like a vector but you can only add/remove at the ends. No inserts into the middle. http://en.wikipedia.org/wiki/Deque

Graham Perks
I'd say "deque, like a vector but you can add/remove at BOTH ends (rather than just the back)".
Drew Hall
The standard library deque supports insertions in the middle, with the same linear complexity provided for by the standard vector. Other implementations might not since its not central to the core "double ended queue" idea.
Dennis Zickefoose
But a deque is *not* like a vector in that consecutive elements are *not* guaranteed to be contiguous in memory. If you push enough elements onto one end of a deque that it runs out of its internal storage, it will allocate a new block of storage and tack it on to one end or the other. If you push enough elements onto the end of a vector that it runs out of capacity, the vector has to allocate a new block big enough to hold everything, copy everything over to it, and release the old storage. Much slower than a deque, and the block size just gets bigger and bigger.
Mike DeSimone
Graham Perks
+1  A: 

A map is what is often refered to as an associative array, usually implemented using a binary tree (for example). A deque is a double-ended queue, a certain incarnation of a linked list.

That is not to say that the actual implementations of the container library uses these concepts - the containr library will just give you some guarantees about how you can access the container and at what (amortized) cost.

I suggest you take a look at a reference that will go into detail about what those guarantees are. Scott Meyers book "Effective STL: 50 Specific Ways to Improve Your Use of the Standard Template Library" should talk a bit about those, if I remember correctly. Apart from that, the C++ standard is obviously a good choice.

What I really want to say is: containers really are described by their properties, not by the underlying implementation.

Jim Brissom
+5  A: 

vector: A dynamic-array class. The internal memory allocation makes sure that it always creates an array. Useful when the size of the data is known and is known to not change too often. It is also good when you want to have random-access to elements.
deque: A double-ended queue that can act as a stack or queue. Good for when you are not sure about the number of elements and when accessing data-element are always in a serial manner. They are fast when elements are added/removed from front and end but not when they're added/removed to/from the middle.
list: A double-linked list that can be used to create a 'list' of data. The advantage of a list is that elements can be inserted or deleted from any part of the list without affecting an iterator that is pointing to a list memeber (and is still a member of the list after deletion). Useful when you know that elements will be deleted very often from any part of the list.
map: A dictionary that maps a 'key' to a 'value'. Useful for applications like 'arrays' whose index are not an integer. Basically can be used to create a map-list of name to an element, like a map that stores name-to-widget relationship.
set: A list of 'unique' data values. For e.g. if you insert 1, 2, 2, 1, 3, the list will only have the elements 1, 2, 3. Note that the elements in this list are always ordered. Internally, they're usually implemented as binary search trees (like map).

Vite Falcon
+1 : You might mention that a `set` is really a `map` with the value being the key. You might also mention `multimap` and `multiset` for completeless.
John Dibling
@John: Thanks for mentioning to add that detail about set. I've added that part. I'm ignoring multimap and multiset because the OP was more into vectors, deque, map and set. I put in list to make sure he knows about it incase that was what he wants. Also, I have no experience in using multiset.
Vite Falcon
@John: A set is not necessarily a map. A set only needs storage for the key and a map has to allocate storage for the key and value. So you might say that a set is really a map without values.
Zan Lynx
+1  A: 

See here for full details:

http://stackoverflow.com/questions/181693/what-are-the-complexity-guarantees-of-the-standard-containers

vector Vs deque

A deque is the same as a vector but with the following addition:

  • It is a "front insertion sequence"

This means that deque is the same as a vector but provides the following additional gurantees:

  • push_front() O(1)
  • pop_front() O(1)

set Vs map

A map is a "Pair Associative Container" while set is a "Simple Associative Container"

This means they are exactly the same. The difference is that map holds pairs of items (Key/Value) rather than just a value.

Martin York
`deque` also relocates elements in fewer situations than `vector` does, which might be important not because of time complexity, but because you have references to them.
Steve Jessop