C++ Programming

Chapter 14: Data Structures

Vector

#include <vector>

The central data structure of the C++ standard library is the vector. It is a lot like an array, but the number of items may change after declaration.

The following code creates a vector with three elements:

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

The vector provides the push_back and pop_back functions to add a new element vector's end and delete its last item, respectively. These functions allow you to resize the vector after declaration.

For example, the following code creates the vector v, which is initially empty. Then the code adds three elements to it. After executing the code, the content of the vector is {1,2,3}.

vector<int> v;
v.push_back(1);
v.push_back(2);
v.push_back(3);

Vector processing

The size function tells you how many items the vector currently has in it. Elements of a vector can be processed in the same way as in an array using the [] syntax. For example, the following code prints all the elements of a vector:

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

The code can be implemented more concisely as follows. Here, the x variable goes through each element in the vector one by one.

for (int x : v) {
    cout << x << "\n";
}

Iterators

An iterator points somewhere inside a data structure. A vector iterator's begin() points to its first element and the iterator's end() indicates after the last item. These iterators define the semi-open space that contains all vector elements.

For example, the following code creates an iterator that points to the first element of the vector:

vector<int>::iterator it = v.begin();

Because the iterator's type is vector<int>::iterator is long, but in this situation it is more convenient to use the keyword auto, which automatically deduces the type:

auto it = v.begin();

An iterator can be handled in much the same way as a pointer. For example, we get to the value of the iterator * operator. The following code prints the first element of the vector:

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

The following code prints all the elements of the vector in turn using an iterator:

auto it = v.begin();
while (it != v.end()) {
    cout << *it << "\n";
    it++;
}

Sorting

#include <algorithm>

We can sort vector elements with the function sort which is given as parameters the beginning and end of the interval to be sort. When we give iterators begin() and end(), the whole vector is sorted:

vector<int> v = {4,2,5,1};
sort(v.begin(),v.end());
// v is now {1,2,4,5}

We can also provide reverse iterators rbegin() and rend() to rearrange the items:

vector<int> v = {4,2,5,1};
sort(v.rbegin(),v.rend());
// v is now {5,4,2,1}

Arrays vs. vectors

In many cases, a vector is more comfortable to use than an array. The number of its elements can be changed, and it has many convenient functions, which are not built in with arrays.

Unlike arrays, vectors behave the same way as common variables, that is, they can be copied and compared normally. For example, the following code works:

vector<int> a = {1,2,3};
vector<int> b = {4,5,6};
b = a;
if (a == b) cout << "ok\n";

If the function parameter is a vector, its contents are copied and you can find out the size by using the size function.

void testi(vector<int> v) {
    for (int i = 0; i < v.size(); i++) {
        cout << v[i] << "\n";
    }
}

The vector is actually implemented internally by an array. The array is just hidden inside the vector, and the vector offers an outwardly more convenient way to use the array.

Working with pairs

A pair is a data structure, which contains exactly two elements. For example, the following code creates a pair x, both elements of which are integers.

pair<int,int> x = {1,2};
cout << x.first << " " << x.second << "\n"; // 1 2

The following code gives a sample of how we can combine parts of the standard library:

vector<pair<int,int>> v;
v.push_back({2,3});
v.push_back({1,5});
v.push_back({2,1});
sort(v.begin(),v.end());
// v is now {{1,5},{2,1},{2,3}}

The code creates a vector with each element being a pair. The code then adds pairs to the vector and arranges them. Pairs are automatically ranked first according to the first element and secondly the second element.

Other data structures

The C++ standard library contains many other data structures, like the following:

A set maintains a collection of items and provides powerful functions to add, delete, and search items.
A map contains a set of key-value pairs. You can think of a map as a generalization of an array, where indexes don't have to be integers.
A deque is a dynamic table, which can be resized from beginning to end.

These data structures provide building blocks for implementing powerful algorithms.

Tie koodariksi