Containers in c++

SEQUENTIAL CONTAINER

Vector (Dynamic Array - Contiguous memory): 
O(1): Vectors provide fast (constant time) element insertion and deletion at the end of the vector and Acess.
O(n): Slow (linear time) insertion and deletion anywhere else.

Insertion and deletion are slow because the operation must move all the elements “down” or “up” by one to make room for the new element or to fill the space left by the deleted element. Like arrays, vectors provide fast (constant time) access to any of their elements.

List (Doubly Linked List - Not Contiguous memory):


O(n): Lists provide slow (linear time) element lookup and access,
O(1): (constant time) insertion and deletion of elements once the relevant position has been found

Deque (Doubly Ended Queue - Not Contiguous memory):

O(1): (constant time) element access. Like a list, it provides fast (amortized constant time) insertion and deletion at both ends of the sequence.

O(1): (linear time) insertion and deletion in the middle of the sequence.


                                      ADAPTER CONTAINER(They are interfaces built on top of one of the three standard sequential containers)

Queue (FIFO Queue):
The name queue comes directly from the definition of the English word queue, which means a line of people or objects. The queue container provides standard first in, first out (or FIFO) semantics. A queue is a container in which you insert elements at one end and take them out at the other end.

O(1): Both insertion and removal of elements are quick (constant time).

PRIORITY Queue (FIFO Queue):
Priority Queue A priority queue provides queue functionality in which each element has a priority. Elements are removed from the queue in priority order. In the case of priority ties, the FIFO semantics hold so that the first element inserted is the first removed. Priority queue insertion and deletion are generally slower than simple queue insertion and deletion because the elements must be reordered to support the priority order.

Stack(FILO STACK):
Stack The STL stack provides standard first-in, last-out (or FILO) semantics. Like a queue, elements are inserted and removed from the container. However, in a stack, the most recent element inserted is the first one removed. The name stack derives from a visualization of this structure as a stack of objects in which only the top object is visible. When you add an object to the stack, you hide all the objects underneath it.
O(1): Both insertion and removal of elements are quick (constant time).

associative containers

SET(binary tree)

set stores the elements in an ordered fashion so that it can provide reasonably fast lookup, insertion, and deletion.

 O(logn): The set provides logarithmic insertion, deletion, and lookup, which are faster insertion and deletion than a vector provides, and faster lookup than a list provides. However, insertion and deletion are slower than a list, and lookup is slower than a vector.

Note that a set does not allow duplication of elements. That is, each element in the set must be unique. If you want to store duplicate elements, you must use a multiset.

MultiSet:

A multiset is simply a set that allows duplication of elements.


Map and Multimap
The elements are sorted according to the keys. In all other respects, it is identical to a set. You should use a map when you want to associate keys and values.

A multimap has the same relation to a map as a multiset does to a set. Specifically, a multimap is a map that allows duplicate keys.

The set and map containers are called associative containers because they associate keys and values. This term is confusing when applied to sets, because in sets the keys are themselves the values. Because these containers sort their elements, they are called sorted associative containers.