Sequences

C++ provides a family of types known as vector. A vector, which is more generally referred to as a dynamic array, is conceptually a sequence of values all of the same type.

Unlike a variable of some scalar or fundamental type that can only store a single value, a vector variable can store multiple values of the same type. Each value that is stored in a vector is known as an element of that vector. The type of all the elements is known as the element type.

A declaration of a kind of vector looks like the following:


vector<int> v;

This variable is named v and it's type is called "vector of int"; this particular vector has int as it's element type. Right after the point of declaration, no initializer was provided to v therefore this vector initially contains no elements.

During declaration or at any time after declaration, a list of values can be assigned to a vector:


v = { 4, -20, 7, 42, 0, -86, 55 };

The operand used for assigning to this vector is a possibly empty braced-enclosed list of values each of the same type: it is known as a braced-init-list or more generally as an initializer list. An initializer list can be used to initialize many kinds of objects that can store elements. When an initializer list is assigned to a vector, all of the values within that list will replace any existing content of that vector.

Each element of a vector can be accessed using the subscript operator ([]):


v[0] = 3;
cout << v[0] << ' ' << v[1] << v[2] << endl;

A particular vector element can be accessed through it's index, which is an integral value within the range of 0 to N where N is the number of elements in the vector. 0 is the index of the first element and N-1 is the index of the last element. When a vector element is accessed, one can either assign a new value to it or use it within some other expression.

A vector can expand and store additional elements, one way to do this is through an operation known as push_back:


v.push_back(123);

push_back is not just a function, it is a member function of all vector types, accessible through an existing vector object using the member-of operator (.). In the above code, a new element shall be created and inserted at the end of the vector named v and the value of that element shall be 123.

If one wanted to undo the last push_back operation on a vector, the member function pop_back can be called with zero arguments: it shall erase the last element of the vector.

Iteration

Many times, one wishes to iterate through all elements of a vector. The purpose of doing this might be to print each element, accumulate all the elements into a calculation, or to apply an operation on each element. The following code prints each element of our vector<int> v:


int i = 0;
while (i < v.size()) {
	cout << v[i] << ' ';
	++i;
}

The control structure shown above is known as a while-loop, it repeatedly executes it's supplied statement(s) while it's supplied condition evaluates to true. The variable i, initialized at 0, increments on each iteration where an element of the vector at index i gets printed until i reaches beyond the last index of the vector: that index being equal to the number of elements in v which can be queried with a call to the member function size.

This method of iterating through a vector is alternative to the more common use of the for-loop:


for (int i = 0; i < v.size(); ++i) {
	cout << v[i] << ' ';
}

The for-loop requires an initial statement, a condition, an iteration expression, and a statement or compound statement in this order. The initial statement executes exactly once, the condition get evaluated at the beginning of each iteration (terminating the for-loop if this condition evaluates to false), the iteration expression evaluates at the end of each iteration, and the main statement gets executed during each iteration (after the condition and before the iteration expression).

for-loops are usually used if one needs to "count" through a sequence and apply some operation during the progression of this sequence. If one does not need to know the index of the current element during an iteration through a vector, then one can use a range-based for-loop:


for (int e : v) cout << e << ' ';

This form of for-loop can be read as "for each int e in v, print e and a space". On each iteration, the variable e will be assigned a copy of the next element in v.

If one wants to modify each element in a vector, a reference can be used in the range-based for-loop instead:


for (int& e : v) e *= 2;

The code above will multiply and assign each element by 2.

Often times, it is desirable to extract all standard input and perhaps store it into a vector:


double n;
vector<double> v;
while (cin >> n) v.push_back(n);

This code can be roughly interpreted as "while a number was successfully scanned, append it to v". This code works because the variable cin has a special implicit conversion to bool which evaluates to false if the last input operation failed.

If standard input is from the keyboard, then the way the user signals the end of input is by pressing CTRL-D.

Algorithms

The following algorithms are useful for processing a vector of double:


double double_vector_max(const vector<double>& v)
{
	double max = v[0];
	for (double e : v) {
		if (e > max) max = e;
	}
	return max;
}

double double_vector_min(const vector<double>& v)
{
	double min = v[0];
	for (double e : v) {
		if (e < min) min = e;
	}
	return min;
}

double double_vector_sum(const vector<double>& v)
{
	double sum = 0;
	for (double e : v) sum += e;
	return sum;
}

double double_vector_product(const vector<double>& v)
{
	double prod = 1;
	for (double e : v) prod *= e;
	return prod;
}

double double_vector_mean(const vector<double>& v)
{
	double sum = double_vector_sum(v);
	return sum / v.size();
}

double double_vector_range(const vector<double>& v)
{
	return double_vector_max(v) - double_vector_min(v);
}

The following table demonstrates the use of some of the member functions available to all vectors; a vector of double named v is used as an example in this table:

Expression	Description
`v.front()`	Returns a reference to the first element of v
`v.back()`	Returns a reference to the last element of v
`v.empty()`	Returns `true` if v contains zero elements
`v.size()`	Returns the number of elements in v
`v.clear()`	Erases all elements from v
`v.push_back(x)`	Appends x to v
`v.pop_back()`	Erases the last element from v