Vectors

Vectors

Just like arrays, vectors use contiguous storage locations for their elements, which means that their elements can also be accessed using offsets on regular pointers to its elements, and just as efficiently as in arrays. But unlike arrays, their size can change dynamically, with their storage being handled automatically by the container.

Usage 

• Store any type of data 
• Insert in amortized O(1)
• Remove in O(1) 
• Access in O(1)
• Size not known at compile time

Note

• Since vectors are more suitable to situations instead of arrays they are extensively used in all applications. 
• Vectors in java implements List interface and are synchronized.
• Vectors in C++ are sequence container. 

Vector Implementation

• The following implementation let's us create a vector with any int size.
• Default constructor creates a vector of size 2. 
• The container provides options to access and iterator to traverse the vector. 
• The container also provides push_back to add elements at the end of current last element. 
• The container also provide direct access to front and back elements 
• On Push back of the last element the container resizes to twice the capacity. It allocates new memory then copies original content swap unique pointers and reset the raw pointers. The local unique pointer variable goes out of scope and hence deletes the previous allocated memory. 
• The container also shrinks when the usage drops below half the current capacity.
• Since the vector internally allocates C array the memory allocated is contiguous.

Learning 

• C++ Vectors also have emplace_back function which leverages rvalue references to forward parameters to the container instead of creating temporaries like push_back. Read here
• Vector<bool> is a specialized version of vector and is not recommended to be used in Google Style guide. Read here
• std::swap is specialized for unique_ptr Read here. 
• std::vector also have overloaded operators  like equality and comparison. Read here
• One important question to answer is what's the complexity of inserting in a vector. 

Insert Complexity

• Now vectors have 2 main insert operations an inexpensive one and an expensive one. 
• If we always consider the worst case scenario as in terms of Big O, the expensive operation have order O(n) complexity and since we insert n5 elements the overall worst case analysis shows that complexity will be O (n^2). 
• However this is not true as the number of expensive operations does cannot occur on every insert. 
• Since the number of inexpensive operation increases and are often more than the number of expensive operation , we need to analyze this differently. 
• Amortized analysis is complexity analysis over a range of operations rather a single operation. 
• In this scenario, an amortized analysis means than while inserting n elements what is the overall cost of single insert operation. 
• Now if we see, there are two operations one inexpensive i.e O(1) when we  do not expand the vector, the other is expensive one where we allocate new memory and the copy the original elements to new memory taking O(2 ^ k) operations, where k is an intermediate value < n. 
• For reason that expand only happens on 2^k + 1 elements, 
• Therefore total number of operations = num of inexpensive operations * cost of light operations + num of expensive operations * cost of expensive operations. 
• Number of expensive operations = (2 + 4 + 8 + 16 ... + 2 ^ l) where l is the largest integer such that 2^l + 1 < n. 
• if we look at it the other way say n is the final size of the vector, therefore this expensive operations will occur n/2 + n /4 + n/ 8 + n/16 + ... + 1 which is almost equal to twice 2n. here
• Therefore the total operations will be somewhere n + 2n = 3n. 
• Dividing this by total number of inserts gives us a constant 3 .
• Therefore the amortized complexity  of inserting in a vector is O(1) .