Alternatives to Vector in C++

In this article, we have explored the alternatives of Vector in C++ such as:

• array
• Deque
• Linked List
• map
• multiset

What is Vector ?

Vector is a dynamic array which resizes itself when insertion and deletion operations perform.Insertions are preformed at the end and in deletion when element gets deleted every element move next to the position i-1.

Array

An array is a collection of items stored at contiguous memory locations. The idea is to store multiple items of the same data-type together.Following are the benfits over the Vector are

• Array are non-resizable,sometimes this is desirable.
• Arrays don't require parsing extra STL headers.
• Arrays are faster,arrays can be initialized statically (while vectors are always initialized dynamically, at run time).
• Whether to use array or vector: It depends the constraints of the problem. Let’s consider a simple graph implementation.

If the constraints are small and the graph is dense:
2-d array: PRO: O(1) access of elements CON: Extra space

If the constraints are high and graph is sparse:
array of vector: PRO: Efficient space CON:O(n) access of elements
where n is the max number of neighbors of a particular node.

Deque

A deque, also known as a double-ended queue, is an ordered collection of items similar to the queue. It has two ends, a front and a rear, and the items remain positioned in the collection. What makes a deque different is the unrestrictive nature of inserting and deleting items. New items can be added at either the front or the rear. Likewise, existing items can be removed from either end.

In which respective deque is better than Vector ?

A deque offers constant-time insert() and erase() operations at the front of the container, whereas a vector does not -- hence the note in the Standard about using a deque if you need to insert or erase at both ends of the sequence.

Deque has its biggest advantages are:

• A vector can only add items to the end efficiently, any attempt to insert an item in the middle of the vector or at the beginning can be and often is very inefficient. A deque can insert items at both the beginning and then end in constant time, O(1), which is very good. Insertions in the middle are still inefficient, but if such functionality is needed a list should be used. A deque's method for inserting at the front is push_front(), the insert() method can also be used, but push_front is more clear.
• Just like insertions, erasures at the front of a vector are inefficient, but a deque offers constant time erasure from the front as well.

Linked List

Input:[2,3,1,4,5]

| 2 | 3 | 1 | 4 | 5 |

Let's suppose if we have to delete the 1 from the vector then element 4 moves from it's current positon to the i-1 and similarily 5 also.

| 2 | 3 | | 4 | 5 |

Fill the gap by copying/moving across:

| 2 | 3 | 4 | 4 | 5 |

| 2 | 3 | 4 | 5 | 5 |

Resize the Container:

| 2 | 3 | 4 | 5 |

So the time complexity will be O(n) which is not efficent.

Linked List is much better than vector for inserting/removing in the beginning or in the middle, it's not good for inserting/removing in a random position because of the need for linear search. And linear search is much faster with vectors because of better cache efficiency.

Map

If you need to store an array of objects ,vector is generally the way to go. If you need storage of keys and values, then that's what Map has been invented for. The question of which one is better Map or vector is way too complex,simply it depends upon the need of question.

In Map, contents are not necessarily stored contiguously in memory (in fact, the complexity requirements mean it's almost always a tree structure filled with pointers to discontiguous data).
The map holds its elements in a tree structure and just has to adjust some pointers to rebalance the tree.

Multiset

Advanatges:
In Multiset,the key feature is fast (O(log N)) lookup "equivalent" (according to the comparer) elements, plus implicit sorting according to the comparer (with O(log N) cost in insertion)).(this plus the usual set features, such as O(1) removal (after O(log N) search) and references that are never invalidated).

Disadvantages:

• The multiset is slower to insert objects than the vector, but they are held sorted. The multiset is likely to take up more memory than the vector as it has to hold pointers to an internal tree structure. This may not always be the case as the vector may have some empty space.

• If you collect the data all at once without needing to access it in order, it is probably simpler to push it onto the vector and then sort. So how dynamic is the data to be stored is the real criterion.

Choose the right Conatiner:

• Use vector as your default sequential container, especially as an alternative to built-in arrays.
• If you add or remove elements frequently at both the front and back of a container, use Deque.
• List efficent way for insertion and deletion in the conatiner(constant time). Do not use List if you need random access to objects because linear search is slow in comparison to vector.
• Map an assciative container,they espically designed to be efficient accessing elements by their key.
  Each element is composed of key and map value.
• Set the elements in a set are always sorted from lower to higher following a specific strict weak ordering criterion set on container construction.
  Unique element values: no two elements in the set can compare equal to each other. For a similar associative container allowing for multiple equivalent elements, see multiset.
  The element value is the key itself. For a similar associative container where elements are accessed using a key, but map to a value different than this key, see map.
• Queue A queue, or FIFO, is characterized by having elements inserted into one end and removed from the other end.For example: a queue of people at a theater's box office.
  The queue adaptor container is implemented in one of two ways: either as a deque or as a list.
• Stack is an ideal choice when you need to a LIFO data structure.For example, think about people entering the back seat of a car that has only one door: the last person to enter is the first to exit.The four basic operations that a stack supports are push(), pop(),top(), and empty().