Guide to Competitive Programming

In C++, ordinary arrays are fixed-size structures, and it is not possible to change the size of an array after creating it. For example, the following code creates an array which contains n integer values:
int array[n];

A dynamic array is an array whose size can be changed during the execution of the program. The C++ standard library provides several dynamic arrays, most useful of them being the vector structure.

Vectors:

A vector is a dynamic array that allows us to efficiently add and remove elements at the end of the structure. For example, the following code creates an empty vector and adds three elements to it:

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

Then, the elements can be accessed like in an ordinary array:

cout << v[0] << “\n”; // 3
cout << v[1] << “\n”; // 2
cout << v[2] << “\n”; // 5

Another way to create a vector is to give a list of its elements:

vector<int> v = {2,4,2,5,1};

We can also give the number of elements and their initial values:

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. For example, the following code iterates through the vector and prints its elements:

for (int i = 0; i < v.size(); i++) {
cout << v[i] << “\n”;
}

A shorter way to iterate through a vector is as follows:

for (auto x : v) {
cout << x << “\n”;
}

The function back returns the last element of a vector, and the function pop_back removes the last element:

vector<int> v = {2,4,2,5,1};
cout << v.back() << “\n”; // 1
v.pop_back();
cout << v.back() << “\n”; // 5

Vectors are implemented so that the push_back and pop_back operations work in O(1) time on average. In practice, using a vector is almost as fast as using an ordinary array.

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, and the iterator end points to the position after the last element. For example, the situation can look as follows in a vector v that consists of eight elements:

[ 5, 2, 3, 1, 2, 5, 7, 1 ]
↑ ↑
v.begin() v.end()

Note the asymmetry in the iterators: begin() points to an element in the data structure, while end() points outside the data structure.

A range is a sequence of consecutive elements in a data structure. The usual way to specify a range is to give iterators to its first element and the position after its last element. In particular, the iterators begin() and end() define a range that contains all elements in a data structure.

The C++ standard library functions typically operate with ranges. For example, the following code first sorts a vector, then reverses the order of its elements, and finally shuffles its elements.

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, the following code prints the first element of a vector:

cout << *v.begin() << “\n”;

To give a more useful example, lower_bound gives an iterator to the first element in a sorted range whose value is at least x, and 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

Note that the above functions only work correctly when the given range is sorted. The functions use binary search and find the requested element in logarithmic time.

If there is no such element, the functions return an iterator to the element after the last element in the range.

The C++ standard library contains a large number of useful functions that are worth exploring. For example, 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 Structures:

A deque is a dynamic array that can be efficiently manipulated at both ends of the structure. Like a vector, a deque provides the functions push_back and pop_back, but it also provides the functions push_front and pop_front
which are not available in a vector. A deque can be used as follows:

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]

The operations of a deque also work in O(1) average time. However, 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.

C++ also provides two specialized data structures that are, by default, based on a deque. 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

Then, in a queue, elements are inserted at the end of the structure and removed from the front of the structure. Both the front and back of the function 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