07 - Containers

Basics

Introduction

In C++, a container is a data structure that groups a number of items (values) of the same type [Collection (abstract data type) - Wikipedia].

To use a collection it is necessary to include appropriate header file:

#include <collection_name>

Take note that above example requires valid collection name to work. Some of the available collections in C++ standard library:

• std::vector (#include <vector>),
• std::list (#include <list>),
• std::stack (LIFO),
• std::queue (FIFO),
• std::set,
• std::map.

🔨 🔥 Assignment 🔥 🔨

Using information from the lectures try to explain the LIFO and FIFO abbreviations.

Creating containers

To create an empty container (declare a container variable) use the following syntax:

container_type<stored_type> container_name;

where:

• container_type is the type of container used (e.g.: vector, list, etc.)
• stored_type is the type of elements that will be stored in the container
• container_name is the name of the container.

To ease the usage of containers, the set of common methods was implemented. Some available ones:

• size() - returns the number of elements in the collection,
• empty() - returns bool (true or false) value indicating whether the container is empty or not (if its size is equal to 0),
• emplace_back(new_element) - adds a new element to the end of the collection,
• clear() - removes all elements from the container.

Iterating containers

In order to iterate thought elements of the container a for loop can be used. In case of containers we are operating on the pointers to elements:

for(auto it=container.begin(); it != container.end(); it++)
{
    std::cout << *it << std::endl;
    // in order to get a value, use a '*'
}

To iterate over containers, C++11 range-based for loop can be used. This approach is based on iterators but hides their direct use. Sample for loop to print all elements:

std::cout << "Container: " << std::endl;
for (auto value : container) {
    std::cout << value << ", ";
}

In above case each access element is a copy of element in a container, modifying it will not affect the original container. In order to change the values inside the loop use a reference. Here is an example of incrementing all values in the container by 2:

for (auto &value : container) {
    value += 2;
}

Vector

Vector container represents an array that can change its size. It can be used in the same way as normal array but offers some additional functionality.

In addition to general container methods vector adds:

• operator[n] - gets n-th element of the container.

Examples of vector initialisation:

// different ways to create vectors
std::vector<int> v1;                // empty vector
std::vector<int> v2(5, -1);         // five elements with value -1
std::vector<int> v3(v1);            // a copy of first vector
std::vector<int> v4{ 0, -12, 53 };  // new vector with three values - 0, -12, 53

🔨 🔥 Assignment 🔥 🔨

1. Copy the above code to your program.
2. Write a set of for auto loops printing all the values in all the created vectors.

To add elements to a vector emplace_back or push_back method can be used:

std::vector<int> v5;
std::cout << v5.size() << std::endl;
v5.emplace_back(1);
std::cout << v5.size() << std::endl;

🔨 🔥 Assignment 🔥 🔨

1. Create an std::vector of int.
2. Write a while loop to ask the user for multiple integer values. Read the values from the user until the user enters 0. Each time add the element to the vector. HINT Use emplace_back() method to add elements to the vector.
3. Calculate the sum of all vector elements using a for auto loop.

Attention: there are some time-consuming operations that should be avoided when using vectors:

• adding elements at the beginning or in the middle (insert method),
• removing elements at the beginning or in the middle (erase method).

List

Attention: List is almost always much slower than std::vector and should only be used when really needed.

List container stores its elements in noncontiguous memory locations. It lacks the random access ([]) operator but allows efficient insertion and removal of elements in any location.

In addition to general container methods list adds:

• emplace_front(element) - inserts a new element at the beginning of the list,
• front() - gets the first element in the list,
• pop_front() - removes the first element in the list,
• back() - gets the last element in the list,
• pop_back() - removes the last element in the list,
• insert(position, element) - inserts a new element at the position (of type iterator),
• erase(position) - removes the element at the position (of type iterator) from the list and returns the iterator to next element.

Try the code below and add fragment for printing all of the created lists:

// different ways to create lists
std::list<int> l1;                // empty list
std::list<int> l2(5, -1);         // five elements with value -1
std::list<int> l3(l1);            // a copy of first list
std::list<int> l4{ 5, 6, 7, 8 };  // list with four values

🔨 🔥 Assignment 🔥 🔨

1. Create an empty list and add three elements (of values: 1, 2, 3) at the end (using emplace_back).
2. Print the list.
3. Add three elements (of values: 4, 5, 6) at the beginning (using emplace_front).
4. Print the list once again.
5. Add an element between any two elements in a list (of value: 7) using insert method.
6. Print the list.

Attention: there are some time-consuming operations that should be avoided when using list:

• random access to elements (need to iterate to desired element),
• iterating over the list often.

Passing containers to functions

To avoid copying the container when passing it to a function it should be passed by reference. Example for a vector container:

void do_something_with_vector(std::vector<int> &vec) {
    // do something with vector
}

🔨 🔥 Assignment 🔥 🔨

1. Ask the user to provide a number of values to be randomized.
2. Create an empty vector and fill it with as many random values as the user has stated, range 7-19.
3. Create 2 functions: for finding maximal and minimal values in vector.
4. Print the minimal and maximal value.

Time measurement

To measure time we have to add appropriate library:

#include <chrono>

Then we can use the code below to measure time:

auto start = std::chrono::steady_clock::now();
//
//  INSER TIMED CODE HERE
//
auto end = std::chrono::steady_clock::now();

auto diff = end - start; // calculate time difference, and display in miliseconds
cout << std::chrono::duration <double, std::milli>(diff).count() << " ms" << endl;

Final assignments 🔥 🔨

1. Using provided example of time measurement, test the execution time of the following operations:

• insert 100 000 elements at the end of vector (emplace_back),
• insert 100 000 elements at the end of list (emplace_back),
• insert 100 000 elements at the beginning of vector (using insert(vec.begin(), value)),
• insert 100 000 elements at the beginning of list (emplace_front).

Results for Intel Core i5-2540M:

2. Fill the vector with floating-point values that are randomly sampled from -5.0 to 5.0 in the main function. Write a function that computes and returns an average of elements stored in the vector. Use std::accumulate function: https://en.cppreference.com/w/cpp/algorithm/accumulate. Vector should be passed by const reference so it is not possible to modify its values inside a function.

3. Create a vector with 10 integer values. Then write a function that returns the number of elements that divide by 5 without a remainder. Use count_if: https://en.cppreference.com/w/cpp/algorithm/count.

Homework 💥 🏠

1. Create a vector of values from 1 to 10. Remove all prime numbers stored in that vector.

2. Write any sorting algorithm and verify how much time is needed if the number of elements is equal to 100, 1000, 10000 and 10000. Does the time grow linearly with the number of elements? Run your code in the Release mode (!).

Authors: Michał Fularz, Rafał Kabaciński, Piotr Kaczmarek, Michał Nowicki, Mikołaj Wasielica, Jan Wietrzykowski, Dominik Pieczyński, Tomasz Mańkowski