Course topics 5, 6 and 7¶

Self-study (english videos and slides)¶

The topic for this week is the C++ Standard Template Library (STL)

The following links will take you to the video-lectures and the accompanying slides:

Standard Template Library (STL)¶

STL introduction

STL containers

STL container performance

STL iterators

STL: Iterator performance and iterator categories

slides for Standard Template Library (STL)

Note The STL container performance video uses a table entitled Choosing container based on performance. There are some mistakes in the version of this table presented in the video. However, a corrected version of this table is given in the file containing the slides.

Week05 - Glossary

Question 1

The STL can be divided into three parts. What are they?

generic algorithms, containers and interactions

iterators, contaminants and generic algorithms

containers, iterators and generic algorithms

containers, iterators and genetic algebras

Question 2

What information does the STL documentation contain regarding the runtime efficiency of most STL algorithms?

typically an upper bound and sometimes a lower bound

typically a lower bound and sometimes the average efficiency

typically a median value, but always a 95% confidence interval

typically an upper bound and sometimes the average efficiency

Question 3

For a C++ programmer it is important to know how to use the STL because

by using the STL, the programmer can fool other people into believing the programmer is an expert

the programmer can save considerable time by using the STL’s collection of algorithms whose asymptotic performances are known

when using STL containers or algorithms the programmer need not understand what code he/she is using or writing

Question 1

The two main types of STL containers are sequences and associative containers. What are the main features of sequence containers? (There may be more than 1 correct statement.)

the user can place the elements in any order he/she wants

the user must specify the position where an element is added or removed

the size of a sequence data structure is always fixed when it is created

it is impossible for a user to access two consecutive elements of a sequence

the sequence elements can be accessed using an index or using an iterator

Question 2

For an associative container,

the elements in the container are stored in the order of their search keys

the elements in the container are always stored in order

an element in the container can be found by using its search key

the container has a lock that can be opened with a search key after the container performs a ’memory dump’

Question 3

With regard to the appropriate choice of associative container, which of the following statements are correct? (There may be more than 1 correct statement.)

If one only has keys and all the keys are unique and ordering is not important, then one should use an unordered set container.

If one has keys that are associated with elements and each element has its own key and ordering is important, then one should use an ordered multimap container.

If one has keys that are associated with elements and several elements may have the same key and ordering is important, then one should use an ordered multiset container.

If one only has keys and some keys may be repeated and ordering is important, then one should use an ordered multiset container.

If one has keys that are associated with elements and each element has its own key and ordering is not important, then one should use a randomized recycling container.

Question 1

Let \(X\) be an STL container and \(Op1\) be some basic operation (example search for a value). It is possible that STL does not have a function that does \(Op1\) for \(X\). There are two reasons for this. One reason is that doing \(Op1\) for \(X\) is either impossible or it makes no sense. What is the other reason?

The designers of STL were not competent enough to invent working code for \(Op1\).

Peforming \(Op1\) for container \(X\) would always cause the program to terminate due to invalidation.

The only ways to do \(Op1\) for container \(X\) have poor efficiency and many users might assume that \(Op1\) can be done very efficiently.

Some commonly used C++ compilers were not capable of compiling the code for \(Op1\), so the STL designers decided to remove \(Op1\).

Question 2

For which of the following cases does STL provide a function having a constant runtime efficiency? (There may be more than 1 correct case.)

Searching for a key or value from a list container.

Adding an element to an ordered map.

Obtaining the smallest element in an ordered map.

Obtaining the element associated with the smallest key in an ordered map.

Obtaining the element at a certain position in an array.

Question 3

When trying to write code that runs efficiently, a programmer should choose containers so that

operations that are never computed are computed as inefficiently as possible

all operations are computed as efficiently as possible

the amount of data that needs to be stored is as small as possible

operations that are computed frequently are computed as efficiently as possible

Question 1

Regarding iterators in STL, which of the following statements are true? (More than one statement may be true.)

They have no use in STL.

They can be used to indicate a range of elements in a collection.

An iterator is like a bookmark between two consecutive elements.

They are a third kind of container.

Question 2

Suppose \(i1\) and \(i2\) are iterators for some sequence container. If \(i2 < i1\) is true, which of the following is correct?

The element to which \(i1\) points is larger than the element to which \(i2\) points.

Iterator \(i1\) points to a position that is closer to the beginning of the container than the position to which \(i2\) points.

Iterator \(i1\) points to a position that is closer to the end of the container than the position to which \(i2\) points.

The range of positions between \(i2\) and \(i1\) is empty.

Question 1

Suppose \(i1\) and \(i2\) are iterators from two different categories. Which of the following is correct?

For the same operation, \(i1\) and \(i2\) may have different runtime performances.

There exist no common operations that both \(i1\) and \(i2\) can do.

There exists at least one operation that only one of the iterators can do.

For one of the iterators the \(++\) operation will fail.

Question 2

Regarding iterator categories, which of the following statement are true? (More than one may be true.)

Only the forward-list container supports bidirectional iterators.

All categories of iterators allow the \(--\) (minus-minus) operation.

No associative container supports random-access iterators.

All sequence containers support random-access iterators.

A bidirectional iterator does not allow jumping an arbitrary number of elements forward or backward whereas a random-access iterator does.

Question 1

What is a central question, related to this course, whose answer can be found in this week’s videos?

Question 2

Of the following topics, which do you think deserves further discussion/explanation during the weekly consultation session?

STL sequences

STL associative containers

iterators

Question 3

Were there any parts of the video lectures that were particularly difficult? Particularly interesting? Something about which you wish to learn more?

Extra links on the topic:

The cppreference site: Containers
Wikipedia’s pages on the Standard Template Library
A long list of examples using STL

Week05 - Glossary

Viikko05 - Sanasto

Submit weekly exercises¶

Questions to be submitted this week

Week 6 of the course¶

Self-study¶

The topics for this week are the following: (i) STL algorithms (ii) Lambda functions and (iii) Tuning STL algorithms and containers

The following links will take you to the video-lectures and the accompanying slides:

STL algorithms

STL algorithm - examples

Lambda functions

Lambda functions and capturing variables

Tuning STL algorithms and containers

Ordinary slides from all lectures

STL algorithms - examples: c++ code

STL algorithms¶

Question 1

Suppose one has some STL container in variable \(A\) and one wishes to input \(A\) into an STL algorithm \(X\). What parameter (or parameters) would one input to \(X\) to indicate that one wishes \(X\) to use the entire container \(A\)?

One need input simply the variable \(A\).

One must input the actual values of the first and last elements of \(A\).

An iterator to the beginning of \(A\) and an iterator to the end of \(A\).

One must input the variable \(A\) along with the container type (for example vector, list, map).

Question 2

For what reasons is it better to use algorithms from the STL library to compute some task rather than writing your own algorithms for computing the task? (There may be more than 1 correct reason.)

Using STL algorithms makes code more readable and understandable.

An STL algorithm always has better runtime efficiency than corresponding code that you write yourself.

In an STL algorithm special cases and potetial error situations are handled.

When using an STL algorithm, you do not have to know or understand what you are computing.

STL algorithms - examples¶

Question 1

Suppose begin and end are two iterators associated with vector v. Suppose the location to the right of begin is \(i\) and the location to the right of end is \(j\). What is the significance of the difference end - begin?

The difference is a new iterator where end is shifted \(i\) locations to the left.

The difference is the numerical value of \(j-i\).

The difference is the numerical value of \(j-i + 1\).

The difference is the numerical value of \(i-j + 1\)..

Question 2

Which of the following is true about the STL algorithsm?

They are building blocks which one can use in forming one’s own algorithm to compute one’s own task.

There is an STL algorithm available which will solve any computational task one will ever encounter.

They are useless because the tasks they handle are too simple.

Lambda functions¶

Question 1

Suppose in C++ one has a vector std::vector<int> v{6, 3, 4, 9, 2, 7, 1, 11};. Which of the following will result in *it having a value of 2?

auto it = std::find_if(begin(v), end(v), [](auto x){ return x % 2 = 0; });

auto it = std::find_if(begin(v), end(v), [](auto x){ return x % 2 != 0; });

auto it = std::find_if(begin(v), end(v)+3, [](auto x){ return x % 2 != 0; });

auto it = std::find_if(begin(v)+3, end(v), [](auto x){ return x % 3 != 0; });

Question 2

Regarding lambda functions, which of the following statements are true? (More than 1 may be true.)

A lambda function can be given as a parameter to an STL algorithm.

A lambda function can always be written without using arithmetic operations.

A lambda function can only return boolean values (true/false).

A lambda function is an anonymous function.

Question 3

Suppose in C++ one has a vector std::vector<int> v{-19, 21, -4, 6};. What will be the value of *it when the following is executed?:: auto it = std::find_if(begin(v), end(v), [](int i){ return (i%2 != 0 && i >0); });

-19

-4

Lambda functions and variable captures¶

Question 1

When we say a lambda function captures a variable we mean

that it will be impossible for any other function, other than the lambda function, to use a variable having the same name as the captured variable

that the lambda function deletes a local variable from the calling function

that the lambda function makes a copy of a variable or a reference that it uses inside itself

that when the lambda function uses a local variable, the variable name must begin with the prefix capt!, which is an abbreviation for captured

Question 2

Suppose in C++ one has a vector v of integers and d is some nonzero integer. What will be the value of a when the following is executed?:: int a = std::count_if(v.begin(), v.end(), [d](int i){return (i % d != 0 && i*d > 0 );});

The number of nonzero elements in v that are greater than d.

Zero always.

The number of elements in v that are divisble by d or have the same sign as d.

The number of elements in v that are not divisble by d and have the same sign as d.

Tuning STL algorithms and containers¶

Question 1

Which of the following statements, regarding tuning of STL algorithms, is true? (More than one statement may be true.)

By using tuning, we can expand the use of existing STL algorithms.

When an STL algorithm is tuned, the number of parameters input to the algorithm always increases.

To tune an STL algorithm we must actually rewrite the STL algorithm code to meet our requirements.

When tuning an STL algorithm we rename the STL algorithm to clarify its use in our code.

When tuning an STL algorithm we often add a named function or a lambda function to an STL algorithm call.

Question 2

The STL contains algorithms named count_if, find_if and remove_if. Which of the following properties do all these algorithms have?

They all require precisely two input parameters, which are both iterators.

One of the parameters they require is either a lambda function or a pointer to a named function.

All of the them return one iterator.

The iterators used as input parameters cannot be associated with a vector container.

Question 1

What is a central question, related to this course, whose answer can be found in this week’s videos?

Question 2

Of the following topics, which do you think deserves further discussion/explanation during the weekly consultation session?

STL algorithms

Examples using STL algorithms

Lambda functions

Lambda functions and variable captures

Tuning STL algorithms and containers

Question 3

Were there any parts of the video lectures that were particularly difficult? Particularly interesting? Something about which you wish to learn more?

Extra links on the topic:

STL algorithms from cppreference.com

Week06 - Glossary

Homework to be returned for the weekly exercises¶

Questions to be submitted this week