Lesson # 5. Using vector

Дата изменения: 28 октября 2020

Theory

Vectors

  • A template type is a special type that can take on different types when the type is initialized.
  • std::vector standard library class that provides the functionality of a dynamically growing array with a “templated” type.
  • std::vector uses a template type:

  • Example:

    #include <vector>   // Definition
    using namespace std;
    int main()
    {
    vector<int> mm(5);  // Initialization
    vector<int> a {1, 2, 3, 7};  // Initialization
    // Loop for to iterate and print values of vector
    for (int i=0; i < a.size(); i++)  // size() - Number of elements
       cout << a[i] << " ";
    // Another kind of for loop (foreach) to iterate and print values of vector
    for (auto x : a)
       cout << x << " ";
    for (int& x : a)
       x++;
    }
    To use vector #include directive need to be placed.
  • When initializing a “templated” type, the template type goes inside of < > at the end of the type name:
  • std::vector<char> v1;
    std::vector<int> v2;
    
  • pop_back function removes the last element
  • push_back function adds an element to the end:
  • Example 1:

    #include <iostream>
    #include <vector>
     
    int main()
    {
        // Create a vector containing integers
        std::vector<int> v = {7, 5, 16, 8};
     
        // Add two more integers to vector
        v.push_back(25);
        v.push_back(13);
     
        // print out the particular elements
        cout << v[0] << std::endl;
        cout << v[1] << std::endl;
        cout << v[2] << std::endl;
     
        // Iterate and print values of vector
        for(int n : v) {
            std::cout << n << '\n';
        }
    }

    Example 2:

    #include <vector>
    #include <iostream>
     
    int main() {
    vector<int> v;
    for (int i = 0; i < 100; i++) {
       v.push_back( i * i );
    }
     
    cout << v[12] << std::endl;
     
    return 0;
    }

Function template

  • A template variable is defined by declaring it before the beginning of a class or function:
  • template <typename T>
    int max(T a, T b) {
      if (a > b) { return a; }
         return b;
    }
    
  • Templated variables are checked at compile time, which allows for errors to be caught before running the program.
  • #include <iostream>
    using namespace std;
     
    template <typename T>
    T max(T a, T b) {
    	if (a > b) { return a; }
    	return b;
    }
    int main()
    {
    	cout << "max(3, 5): " << max(3, 5) << endl; // 5
    	cout << "max('a', 'd'): " << max('a', 'd') << endl; // d
    	cout << "max(\"Hello\", \"World\"): " << max("Hello", "World") << endl; // Hello
    	cout << "max(3, 5, 6): " << max(3, 5, 6) << endl; // error
     
    	system("pause");
    	return 0;
    }
  • A function template defines a family of functions.
  • A function template by itself is not a type, or a function, or any other entity. No code is generated from a source file that contains only template definitions. In order for any code to appear, a template must be instantiated: the template arguments must be determined so that the compiler can generate an actual function.
  • An explicit instantiation definition forces instantiation of the function or member function they refer to. It may appear in the program anywhere after the template definition, and for a given argument-list, is only allowed to appear once in the program, no diagnostic required.
  • template<typename T>
    void f(T s)
    {
        std::cout << s << '\n';
    }
     
    template void f<double>(double); // instantiates f<double>(double)
    template void f<>(char); // instantiates f<char>(char), template argument deduced
    template void f(int); // instantiates f<int>(int), template argument deduced
  • Implicit instantiation: When code refers to a function in context that requires the function definition to exist, and this particular function has not been explicitly instantiated, implicit instantiation occurs. The list of template arguments does not have to be supplied if it can be deduced from context.
  • #include <iostream>
     
    template<typename T>
    void f(T s)
    {
        std::cout << s << '\n';
    }
     
    int main()
    {
        f<double>(1); // instantiates and calls f<double>(double)
        f<>('a'); // instantiates and calls f<char>(char)
        f(7); // instantiates and calls f<int>(int)
        void (*ptr)(std::string) = f; // instantiates f<string>(string)
    }

    Note: omitting <> entirely allows overload resolution to examine both template and non-template overloads.

* resources: 1) https://en.cppreference.com/w/cpp/container/vector

Labs and tasks

To do all the tasks and labs of this lesson you must create three files:

  1. a header file (basicVectors.h) (functions definitions for all the tasks must be placed here);
  2. a basicVectors.cpp file (the implementations of the functions with comments for all the tasks must be placed here)
  3. a main.cpp must provide prompts for user, calling created functions and output results for all the tasks.
  4. Each function should be accompanied by a comment about what it is intended for, and a number of the task must be provided.
Lab:
The tasks of this lesson will be continuation of this lab.

To do: An integer N (N > 0) and an integer vector (array) of length N are given. Fill the vector with the first N positive odd numbers: 1, 3, 5,… N. Do not use the conditional statement. Create a oddVectorGenerator() function to do the task.

Note: To print the resulting vector, hereinafter, you must use the print_vector() function template. The function must be placed inside special header file printVect.h (you should add a new file to your application).

Copy the print_vector function code and paste it to the printVect.h file:

#ifndef PRINTVECT_H
#define PRINTVECT_H
 
#include <iostream>
#include <vector>
 
// note: function templates are always must be inside header files
 
// function template to output vector
template<typename T>
void print_vector(const std::vector<T>& v, char delim = ' ') {
	for (auto x : v)
		std::cout << x << delim;
	std::cout << std::endl;
}
 
/* #ifndef PRINT_VECT_H: */
#endif

Expected output:

lab 1
enter N - the number of vector elements
>> 25
1 3 5 7 9 11 13 15 17 19 21 23

✍ How to do:

  • Create a new console application with a name Lesson 5.
  • In the Source files folder of the Solution Explorer window, add new files: basicVectors.cpp and main.cpp. In the Header Files folder add a new header file: basicVectors.h.
  • Function templates are always placed in header files unlike regular functions. Add a new header file and name it printVect.h. Copy and paste the template function code into it.
  • Open your main.cpp file and include there all the header files that program will need:
  • #include <iostream>
    #include "basicVectors.h"
    #include "printVect.h"
    using namespace std;
    
    
  • Then, you must define an integer vector. You should do it inside the main.cpp file, right after all the included directives:
  • vector<int> v;
    
  • Output the comment to indicate that this is lab 1. Then, ask user to input a number of the vector elements. Set the entered value to the n variable:
  • cout << "lab 1"<< endl;
    cout << "enter N - the number of vector elements";
    int n;
    cin >> n;
    
  • Open your basicVectors.h header file. Include all necessary directives:
  • #pragma once
    #include <iostream>
    #include <vector>
    using namespace std;
    
  • We’re going to define our oddVectorGenerator() function, that must fill the vector with the first N positive odd numbers:
  • void oddVectorGenerator(vector<int>&, int);
    
    We’re going to pass vector parameter by reference (&), because we don’t need to locate a new memory space to store it.
  • Open basicVectors.cpp file to add an implementation of the created function. But first, add all the include directives to the file:
  • #include 
    #include <cassert>
    #include "printVect.h"
    #include "basicVectors.h"
    using namespace std;
    
  • After that, let’s create the oddVectorGenerator() function and all the code it must implement:
  • void oddVectorGenerator(vector<int> &v, int n)
    {
    	for (int i = 1; i < n; i += 2)
    	{
    		v.push_back(i);
    	}
    }
    
    push_back function adds an element to the end of the vector.
    Only odd numbers will be set to vector due to the for loop step=2.
  • Open your main.cpp file and call the function. To output the results call the print_vector() function too:
  • oddVectorGenerator(v, n);
    print_vector(v);
    system("pause");
    
  • Run the program. And proceed with Task 1.
Task 1:

To do: A vector is given (you can have the following element values: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10). Output its elements in reverse order. Create a function to do it.

Note 1: You must complete this task in the same application as Lab 1. Output the task number before the results of this task are printed.

cout << "task 1" << endl;

Note 2: To use the same variable v in this task you should clear the elements, and then, set new elements to it:

v.resize(0);
v = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };

Note 3: You can create a new vector with the reversed elements.

Expected output:

task 1
before task:
1 2 3 4 5 6 7 8 9 10
after task:
10 9 8 7 6 5 4 3 2 1
Task 2:

To do: An integer vector is given. Calculate the number of odd numbers in this vector, as well as the number of positive numbers in it.

Note 1: You must complete this task in the same application as Lab 1. Output the task number before the results of this task are printed.

Note 2: To use the same variable v in this task you should clear the elements, and then, set new elements to it:

v.resize(0);
v = { -1, 2, 3, 4, -5, 6, 7, 8, -9, 10 };

Note 3: To check if the negative number is odd you should use abs function.

Expected output:

task 2
vector:
-1 2 3 4 -5 6 7 8 -9 10
number of positive: 7 number of odd : 5
Task 3:

To do: An integer vector is given. Output the index of its first even element.

Note 1: You must complete this task in the same application as Lab 1. Output the task number before the results of this task are printed.

Note 2: To use the same variable v in this task you should clear the elements, and then, set new elements to it:

v.resize(0);
v = { -1, 2, 3, 4, -5, 6, 7, 8, -9, 10 };

Expected output:

task 3
vector:
-1 5 3 4 -5 6 7 8 -9 10
the first even element number is: 4
Task 4:

To do: An integer vector is given. Ouput the maximum of its local minima (a local minimum is an element that is less than any of its neighbors: e.g. ... 5 2 7 ... => number 2 is a local minimum, because 2 < 5 and 2 < 7).

Note 1: You must complete this task in the same application as Lab 1. Output the task number before the results of this task are printed.

Note 2: To initialize a variable that should store the current value of the maximum local minimum, it is convenient to use the INT_MIN constant from the standard header:

int max = std::numeric_limits<int>::min();

Expected output:

task 4
vector:
-1 5 3 4 -5 8 7 8 -9 10
the maximum of local minima is: 7
Task 5:

To do: An integer vector A of size N (> 0) is given. Fill it with powers of two from the 1 power to the N: 2, 4, 8, 16,….

Note 1: You must complete this task in the same application as Lab 1. Output the task number before the results of this task are printed.

Expected output:

task 5
Enter N number:
>>> 5
vector:
2  4  8  16  32
Task 6:

To do: an integer vector A of size N is given. It contains at least one even number. Find the first and last even number in the given vector. To do the task create getFirstAndLastEvenNumber() function.

Note 1: Use passing parameters by reference (&) to return two values from a function.

Note 2: Besides the getFirstAndLastEvenNumber() function you should create one more function of boolean type, to check if the number is even:

inline bool isEven(int n)
{
    //
}

Note 3: You must complete this task in the same application as Lab 1. Output the task number before the results of this task are printed.

Expected output:

task 6
Enter N number:
>>> 5
vector:
2  12  1  16  3
the first: 2, the last: 16
Task 7:

To do: Three integer vectors A, B and C of the same size N are given. You must fill in vector C with values according to the following rule: each of its elements is equal to the maximum of the elements of vectors A and B with the same index.

Note 1: You must complete this task in the same application as Lab 1. Output the task number before the results of this task are printed.

Note 2: To compare two values you should use the standard max function, for example:

int maximum = std::max(a, b);

Note 3: You should check if the sizes of the vectors are equal, use assert() function, for example:

 assert((a.size() == b.size()) && (c.size() == a.size()));

Note 4: You should create the following function signature:

void maxInVectors(std::vector<int> &a, std::vector<int> &b, std::vector<int> &c)
{
// body function
}

Expected output:

task 7
A vector:
0 1 2 3 4 42 6 7 8 422
B vector:
9 8 7 6 5 4 3 2 1 0
vector C:
9 8 7 6 5 42 6 7 8 422

Extra tasks

*ExTask 1:

To do: An integer vectors Ais given. You must create B vector of the same size and fill in the vector with all numbers from vector A that have the digit 2 in decimal notation.

Note 1: You must complete this task in the same application as Lab 1. Output the task number before the results of this task are printed.

Note 2: In the implementation of the function, use a function that checks whether a given integer has a given digit in its decimal notation. You should implement it yourself:

bool hasDigit (int n, int digit);

Note 3: You should check if the sizes of the vectors are equal, use assert() function.

Note 4: You should use push_back(value) method to add the new value to a vector. The method adds a new element to the end of the vector, for example:

b.push_back(x);

Expected output:

task 6
vector A:
0 1 2 3 4 42 6 7 8 422
vector B:
2 42 422
*ExTask 2:

To do: An integer vector is given. Output the length of the largest series of consecutive zeros.

Note 1: You must complete this task in the same application as Lab 1. Output the task number before the results of this task are printed.

Expected output:

task 7
vector:
0 1 0 0 0 42 6 7 8 422
maximum length of 0: 3
*ExTask 3:

To do: Remove all odd elements from the vector by shifting the remaining elements to its beginning.

Note 1: You should use the remove_if() standard method, which removes elements from the container that pass a specified test:

auto newEnd = std::remove_if(a.begin(), a.end(), [](int n)
	{
		return // some test;
	});

Note 2: To delete the elements from the vector you can use the erase() standard method.

Expected output:

task 8
before task:
0 1 2 3 4 42 6 7 8 422
after task:
0 2 4 42 6 8 422
*ExTask 4:

To do: A vector of size N and an integer K (0 ≤ K < N) are given. Remove the element with K index from the vector by shifting all the following elements one position to the left and decreasing the vector size by one.

Note 1: To check the index you can use the following construction:

if(index < 0 || index > size)
        throw "Incorrect index!";

Note 2: To delete the elements from the vector you can't use the erase() standard method.

Expected output:

task 9
enter the index to delete
>>> 2
before task:
1 2 3 4 5 6 7 8 
after task:
1 2 4 5 6 7 8

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *

*
*


Вставить формулу как
Блок
Строка
Дополнительные настройки
Цвет формулы
Цвет текста
#333333
Используйте LaTeX для набора формулы
Предпросмотр
\({}\)
Формула не набрана
Вставить