Dynamic Arrays

Ordinary arrays are fixed-size structures while a dynamic array is an array whose size can be changed during the execution of the program.

Vectors

A vector is a dynamic array that allows us to efficiently add and remove elements at the end of the structure.

vector<int> v;
v.push_back(3); // [3]
v.push_back(2); // [3,2]
v.push_back(5); // [3,2,5]

Ways to create a vector:

vector<int> v = {2,4,2,5,1};
vector<int> a(8); // size 8, initial value 0
vector<int> b(8,2); // size 8, initial value 2

• The function size returns the number of elements in the vector.
• The function back returns the last element of a vector.
• The function pop_back removes the last element.

Iterators and Ranges

An iterator is a variable that points to an element of a data structure.

• The iterator begin points to the first element of a data structure.
• The iterator end points to the position after the last element. Note the asymmetry in the iterators: begin() points to an element in the data structure, while end() points outside the data structure.

Sort, reverse, shuffle.

sort(v.begin(),v.end());
reverse(v.begin(),v.end());
random_shuffle(v.begin(),v.end());

The element to which an iterator points can be accessed using the * syntax. For example,

cout << *v.begin() << "\n";

• The syntax lower_bound gives an iterator to the first element in a sorted range whose value is at least x.
• The syntax upper_bound gives an iterator to the first element whose value is larger than x.

vector<int> v = {2,3,3,5,7,8,8,8};
auto a = lower_bound(v.begin(),v.end(),5);
auto b = upper_bound(v.begin(),v.end(),5);
cout << *a << " " << *b << "\n"; // 5 7
// the above functions only work correctly when the given range is sorted.

The following code creates a vector that contains the unique elements of the original vector in a sorted order:

sort(v.begin(),v.end());
v.erase(unique(v.begin(),v.end()),v.end());

Other Structure

A deque is a dynamic array that can be efficiently manipulated at both ends of the structure. It has operators that can be used to manipulate the front and the end of the data.

deque<int> d;
d.push_back(5); // [5]
d.push_back(2); // [5,2]
d.push_front(3); // [3,5,2]
d.pop_back(); // [3,5]
d.pop_front(); // [5]

Note that deques have larger constant factors than vectors, so deques should be used only if there is a need to manipulate both ends of the array. There are two specialized data structures under deques: stacks and queues.

A stack has the functions push and pop for inserting and removing elements at the end of the structure and the function top that retrieves the last element:

stack<int> s;
s.push(2); // [2]
s.push(5); // [2,5]
cout << s.top() << "\n"; // 5
s.pop(); // [2]
cout << s.top() << "\n"; // 2

In a queue, elements are inserted at the end of the structure and removed from the front of the structure. Both the functions front and back are provided for accessing the first and last element.

queue<int> q;
q.push(2); // [2]
q.push(5); // [2,5]
cout << q.front() << "\n"; // 2
q.pop(); // [5]
cout << q.back() << "\n"; // 5