Sequential Containers

1. Array

Declaration: array<datatype, size> arrayName;

Initialization: array<int,5> marks = {87, 98, 70, 90, 100};

Size of an array is Fixed.

Arrays are already there in C++, then why is it added in STL? _- C-style arrays don’t know their own size. But Array Containers know their own size. _ So when passing an array to a function, we don’t need to pass it’s size unlike we do in C-type arrays. - C-style arrays worked and entirely accessed by pointers whereas Array Containers are not. Array Containers have more inbuilt functions than C-style arrays. So these are more efficient.

2. Vector

Vectors are dynamically sized arrays. Always prefer vectors over raw arrays

Container properties

1. Sequence: Elements in sequence containers are ordered in a strict linear sequence. Individual elements are accessed by their position in this sequence.
2. Dynamic array: Allows direct access to any element in the sequence, even through pointer arithmetics, and provides relatively fast addition/removal of elements at the end of the sequence.
3. Allocator-aware: The container uses an allocator object to dynamically handle its storage needs.

Declaration:

• To declare an empty int array:

Vector <int> a

• To declare a zero-initialized double “array” of size 50:

Vector <double> b(50)

• To declare an int “array” of size n, with element initialized to 10:

Vector <int> (n,10)

• Unlike arrays, vectors are aware of their size.

Vector <int> v1{1,4,2,8}

Cout << v1.size(); // 4

• When there is no capacity left, an additional memory of size 2 times the original capacity is allocated. The capacity is now doubled and the data is moved to the newly allocated memory. Push_back is used to append an element at the end in a vector.

How to traverse through a vector?

1. Using indices

2. Using iterator

3. Using ranged-based loop

Vector has it’s own public member functions to utilize it.

Time Complexity:

If we create a new double sized array whenever current array becomes full (or it is about to become full), and copy current elements to new double sized array, we get amortized time complexity as O(1). So a particular insert operation may be costly, but overall time complexity remains O(1). Since erasing an element requires moving other elements (to ensure random access), time complexity of erase is O(1)