Vectors
 Vector is a sequential data structure that supports access to its elements by its indices
 A vector is also called an array list
 Vector elements can be accessed just like an array
 Unlike arrays, the size of vectors can be increased dynamically
Vector ADT operations
In all cases, the index parameter i is assumed to be in the range 0 ≤ i ≤ size()−1
at(i)
: Return the element of V with index i; an error condition occurs if i is out of range.
set(i,e)
: Replace the element at index i with e; an error condition occurs if i is out of range.
insert(i,e)
: Insert a new element e into V to have index i; an error condition occurs if i is out of range.
erase(i)
: Remove from V the element at index i; an error condition occurs if i is out of range.
Operation  Output  V 

insert(0,7)  (7)  
insert(0,4)  (4,7)  
at(1)  7  (4,7) 
insert(2,2)  (4,7,2)  
at(3)  “error”  (4,7,2) 
erase(1)  (4,2)  
insert(1,5)  (4,5,2)  
insert(1,3)  (4,3,5,2)  
insert(4,9)  (4,3,5,2,9)  
at(2)  5  (4,3,5,2,9) 
set(3,8)  (4,3,5,8,9) 
Array based vector implementation
Algorithm for array based vector implementation
1  Algorithm insert(i,e): 
This array replacement strategy is known as an extendable array.
Of course, in C++ (and most other programming languages) we cannot actually grow the array A; its capacity is fixed at some number N, as we have already observed. Instead, when an overflow occurs, that is, when n = N and function insert is called, we perform the following steps:
 Allocate a new array B of capacity N
 Copy A[i] to B[i], for
i=0,...,N1
 Deallocate A and reassign A to point to the new array B.
C++ Implementation of ArrayVector
Reason for Overloaded [] Operator
https://www.learncpp.com/cpptutorial/overloadingthesubscriptoperator/
Our class definition differs slightly from the operations given in our ADT. For example, we provide two means for accessing individual elements of the vector. The first involves overriding the C++ array index operator (“[ ]”), and the second is the at function.
The two functions behave the same, except that the at
function performs a range test before each access. (Note the similarity with the STL vector class given in Section 6.1.4.) If the index i is not in bounds, this function throws an exception.
Because both of these access operations return a reference
, there is no need to explicitly define a set function. Instead, we can simply use the assignment operator. For example, the ADT function v.set(i,5)
could be implemented either as v[i] = 5
or, more safely, as v.at(i) = 5
.
Constructor, ADTs, new reserve()
function, and housekeeping functions
The member data for class ArrayVector consists of the array storage A, the current number n of elements in the vector, and the current storage capacity.
The class ArrayVector also provides the ADT functions insert and remove. We discuss their implementations below.
We have added a new function, called
reserve
, that is not part of the ADT. This function allows the user to explicitly request that the array be expanded to a capacity of a size at least n. If the capacity is already larger than this, then the function does nothing.Even though we have not bothered to show them, the class also provides some of the standard housekeeping functions. These consist of a copy constructor, an assignment operator, and a destructor. Because this class allocates memory, their inclusion is essential for a complete and robust class implementation. We leave them as an exercise (R6.6). We should also add versions of the indexing operators that return constant references.
When the vector is constructed, we do not allocate any storage and simply set A to NULL. Note that the first attempt to add an element results in array storage being allocated.
1  typedef int Elem; 
STL Vector
A container is a data structure that stores a collection of objects.
Many of the data structures that we study later in this book, such as stacks, queues, and lists, are examples of STL containers.
The class vector is perhaps the most basic example of an STL container class.
The definition of class vector is given in the system include file named “vector.”
1 

 Members can be accessed using the index operator
[]
or using theat()
function. However, only theat()
function does range check.  Vectors can be dynamically resized.
 Vectors can efficiently append and remove elements at the end of an array.
 STL vector objects are automatically destroyed via its destructor for each of its elements. (With C++ arrays, it’s manual)
STL vectors have a number of useful functions that operate on the entire vector (not individual elements)
 Most of these use copy constructors (e.g., push_back())
1  vector(n): Construct a vector with space for n elements; if no argument is given, create an empty vector. 
Differences between ArrayVector and STL Vector
One difference is that the STL constructor allows for an arbitrary number of initial elements, whereas our ArrayVect constructor always starts with an empty vector.
The STL vector functions V.front() and V.back() are equivalent to our functions V[0] and V[n−1], respectively, where n is equal to V.size().
The STL vector functions V.push back(e) and V.pop back() are equivalent to our ArrayVect functions V.insert(n,e) and V.remove(n − 1), respectively