C++ deque vs vector and C++ map vs Set

Question

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

Answer 1

std::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.
std::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.
std::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 member (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.
std::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.
std::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).

Answer 2

See here for full details:

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.

Answer 3

std::vector

Your default sequential containers should be a std::vector. Generally, std::vector will provide you with the right balance of performance and speed. The std::vector container is similar to a C-style array that can grow or shrink during runtime. The underlying buffer is stored contiguously and is guaranteed to be compatible with C-style arrays.

Consider using a std::vector if:

You need your data to be stored contiguously in memory Especially useful for C-style API compatibility You do not know the size at compile time You need efficient random access to your elements (O(1)) You will be adding and removing elements from the end You want to iterate over the elements in any order Avoid using a std::vector if:

You will frequently add or remove elements to the front or middle of the sequence The size of your buffer is constant and known in advance (prefer std::array) Be aware of the specialization of std::vector: Since C++98, std::vector has been specialized such that each element only occupies one bit. When accessing individual boolean elements, the operators return a copy of a bool that is constructed with the value of that bit.

std::array

The std::array container is the most like a built-in array, but offering extra features such as bounds checking and automatic memory management. Unlike std::vector, the size of std::array is fixed and cannot change during runtime.

Consider using a std::array if:

You need your data to be stored contiguously in memory Especially useful for C-style API compatibility The size of your array is known in advance You need efficient random access to your elements (O(1)) You want to iterate over the elements in any order Avoid using a std::array if:

You need to insert or remove elements You don’t know the size of your array at compile time You need to be able to resize your array dynamically std::deque The std::deque container gets its name from a shortening of “double ended queue”. The std::deque container is most efficient when appending items to the front or back of a queue. Unlike std::vector, std::deque does not provide a mechanism to reserve a buffer. The underlying buffer is also not guaranteed to be compatible with C-style array APIs.

Consider using std::deque if:

You need to insert new elements at both the front and back of a sequence (e.g. in a scheduler) You need efficient random access to your elements (O(1)) You want the internal buffer to automatically shrink when elements are removed You want to iterate over the elements in any order Avoid using std::deque if:

You need to maintain compatibility with C-style APIs You need to reserve memory ahead of time You need to frequently insert or remove elements from the middle of the sequence Calling insert in the middle of a std::deque invalidates all iterators and references to its elements

std::list

The std::list and std::forward_list containers implement linked list data structures. Where std::list provides a doubly-linked list, the std::forward_list only contains a pointer to the next object. Unlike the other sequential containers, the list types do not provide efficient random access to elements. Each element must be traversed in order.

Consider using std::list if:

You need to store many items but the number is unknown You need to insert or remove new elements from any position in the sequence You do not need efficient access to random elements You want the ability to move elements or sets of elements within the container or between different containers You want to implement a node-wise memory allocation scheme Avoid using std::list if:

You need to maintain compatibility with C-style APIs You need efficient access to random elements Your system utilizes a cache (prefer std::vector for reduced cache misses) The size of your data is known in advance and can be managed by a std::vector

Answer 4

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

edit: my dequeue description is lacking, see comments below for corrections

Answer 5

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.