Course topic 6 exercises

Iterators

All 6 questions concern iterators. In questions 1, 2 and 3 you should select the code that will compute given the task. Unless otherwise specified, the iterator type is std::vector<int>::iterator.

Question 1

We want to move iterator it forward by 5 positions.

it + 5;

for ( int i = 0; i <= 5 ; i++ ) { it++; }

it += 5;

Question 2

We want an iterator that points to the last item. (In the bookmark analogy, the bookmark would be between the two last books.)

it = vec.end(); --it;

std::prev(vec.back());

vec.end();

Question 3

We want to compute the size of the vector.

for ( auto it = vec.begin(); it < vec.end() ; vec.end()-- ) {size++;}

vec.end() - vec.begin();

*vec.begin();

Question 4

What does the following code print?

  vector<int> ints = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
  auto iter = ints.begin();
  auto another = iter + 5;
  iter +=3;
  if ( iter < another ){
      cout << *iter;
  } else {
      cout << *another;
  }

3

5

8

Question 5

What does the following code print?

  vector<int> ints = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
  auto iter = ints.begin();
  auto another = ints.insert(iter, 11);
  iter = ints.begin() + 5;
  if ( iter < another ){
      cout << *iter;
  } else {
      cout << *(another + 2);
  }

2

11

1

Question 6

What does the following code print?

  vector<int> ints = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
  auto iter = ints.begin();
  iter = iter * 3;
  cout << *iter;

3

9

Nothing, as it doesn’t compile.

STL containers

In each problem, a list of requirements are a given for a data structure. For each problem, select which C++ STL data structure has the best overall runtime efficiency for the given requirements. More information about STL data structures can be found from the lecture slides and in the cppreference website

Please note that there are three submissions, but the questions will be randomized for each round.

Question 1

1. Elements are added to the end of the data structure, and they are read & removed in reverse order, hence the last element added is the first that will be read and removed.

array

vector

forward_list

list

set

unordered_set

stack

queue

deque

map

unordered_map

Question 2

2. Elements are added to the data structure, and they are read & removed in the same order, hence the first added element is the first that will be read and removed.

array

vector

forward_list

list

set

unordered_set

stack

queue

deque

map

unordered_map

Question 3

3. Elements are often added to the data structure. Often it is necessary to go through all the elements in the order in which they were added. Occasionally it is necessary to go through all the elements in increasing order, after which the largest element is removed.

array

vector

forward_list

list

set

unordered_set

stack

queue

deque

map

unordered_map

Question 4

4. Elements are often added to the data structure. Often there is a need to go through all the elements in increasing order, after which the smallest element is removed.

array

vector

forward_list

list

set

unordered_set

stack

queue

deque

map

unordered_map

Question 5

5. Elements are often added to the end of the data structure. Seldomly an element is added in the middle in some designated location. Often there is a need to get the i ^th element (where i varies).

array

vector

forward_list

list

set

unordered_set

stack

queue

deque

map

unordered_map

Question 6

6. It is often necessary to add an element to the data structure to the left or the right of an element that has just been found. Elements are removed from the end of the data structure.

array

vector

forward_list

list

set

unordered_set

stack

queue

deque

map

unordered_map

Question 7

7. Elements are often added to the data structure. Often it is necessary to find out, if an element of given value is in the data structure, and then remove the element, if it is found.

array

vector

forward_list

list

set

unordered_set

stack

queue

deque

map

unordered_map

Question 8

8. Elements are often added to the data structure. Often it is necessary to find out, if an element of given value is in the data structure, and then remove the element, if it is found. Less often it is necessary to go through all the elements in increasing order.

array

vector

forward_list

list

set

unordered_set

stack

queue

deque

map

unordered_map

Question 9

9. N items are inserted into a container.

   What would be the asymptotic efficiency of the whole insertion, if the container was a list?

O(1)

O(log N)

O(N)

O(N log N)

Question 10

10. Consider again the previous question. What would be the asymptotic efficiency if the container was a set?

O(1)

O(log N)

O(N)

O(N log N)

Question 11

11. A container has N items in arbitrary order. A check is made to see if a certain value is in the container.

    What would be the average efficiency of computing the check, if the container is vector?

O(1)

O(log N)

O(N)

O(N log N)

Question 12

12. Consider again the previous question. What would be the average efficiency if the container was an unordered_set?

Θ(1)

Θ(log N)

Θ(N)

Θ(N log N)

Estimating asymptotic efficiency

A+ presents the exercise submission form here.

Practise iteration

Iteration

Iteration - short instructions

Update your course repository by pulling latest changes from course-upstream to your repository with the following command: git pull course-upstream main

Inside your repository you should see a directory wk03_stl/iteration with the following contents:

wk03_stl/iteration
          ├── iteration.pro
          ├── iteration1.hh
          ├── iteration2.hh
          ├── iteration3.hh
          ├── iteration4.hh
          ├── iteration1.cc (edit the function in here)
          ├── iteration2.cc (edit the function in here)
          ├── iteration3.cc (edit the function in here)
          ├── iteration4.cc (edit the function in here)
          ├── main.cc
          └── CLI11.hh
    

Grader will only copy your iteration*.cc files. Please do not add any includes to the files.

Your task is to implement four different functions which all take an STL list container as an argument. Then the list is iterated through using STL iterators and depending on the function either all or some of the list items are printed.

All functions must print the list items on the same line separated by only one empty space " " and then at the end of the line one new line. (std::endl) It is OK to print one space after the last list item. Preceding and trailing whitespace characters will be ignored.

The grader will compare the output of your functions to the output of the model solution and therefore it is important that you do not print anything else but the list items.

Functions to implement

#	Function name	File	Expected output for the list: {5, 6, 9, 13, 17, 21, 23, 29}
1	void printAllItems(const list<int>& lst)	iteration1.cc	5 6 9 13 17 21 23 29
2	void printEverySecond(const list<int>& lst)	iteration2.cc	5 9 17 23
3	void printHalf(const list<int>& lst)	iteration3.cc	5 6 9 13
4	void printReverse(const list<int>& lst)	iteration4.cc	29 23 21 17 13 9 6 5

Testing your functions

Inside the wk03_stl/iteration directory you can open the qt project file iteration.pro In order to run the program with parameters, you need to either run it in terminal or change the command line parameters from Qt Creator.

Changing the command line parameters in Qt Creator

After opening the project, from the left ribbon menu in Qt Creator, select projects (wrench icon). From the opened menu, on the left part under the Build & Run section select run. You may now find the setting for Command line arguments, you can paste the arguments there.

Running the program

Running tests is simple and the iteration program will print usage instructions if you run it with --help as the only command line argument.

Submitting Your Project to Plussa

A+ presents the exercise submission form here.

Posting submission...