Using vector type, dynamic arrays

Back

Go ahead

Содержание:

Theory
Labs and tasks
- 1-d and 2-d Arrays
- Vectors
Extra tasks

Theory

Single-dimensional arrays

The size of an array is fixed.

Array elements are zero-indexed.

The array does not store its size.

sample 1:

// Declaring an array of 5 int elements 
int b[5];

sample 2:

#include <iostream>
using namespace std;
int main()
{
 // Declaring and initialization an array of  
 int a[] = {2, 3, 5, 7};
 cout << a[3] << endl; // output: 1
 // reassigning a value to a last element of an array
 a[3] = 1;
 
 a[4] = 2; // the error will occur
}

Using foreach loop:

x (array element) is read-only

int a[] = {3, 7, 9, 5, 7, 2, 7};
for (int x : a)     
    cout << x << " ";  // output only: 3 7 9 5 7 2 7

x (array element) can be read and written

int a[] = {3, 7, 9, 5, 7, 2, 7};
for (int &x : a)  // x by reference
{ 
    x += 1;  
    cout << x << " ";  // output: 4 8 10 6 8 3 8
}

Using an automatic random number generator with scaling:

sample 1:

// random numbers will be generated in the range from 1 to 10    
#include <iostream>
#include <ctime>
using namespace std;
 
int main()
{
// to have new randomly generated numbers each time we run the program:
	srand(time(0)); 
	int b[5];
	for (int &x : b)
	{
		x = 1 + rand() % 10;
		cout << x << " "; // example of output: 8 4 2 6 5
	}
	return 0;
}
}

sample 2: we can do the same with classic for loop:

#include <iostream>
#include <ctime>
using namespace std;
 
int main()
{
// to have new randomly generated numbers each time we run the program:
	srand(time(0));
	int b[5];
	for (int i=0;i<5;i++)
	{
		b[i] = 1 + rand() % 10;
		cout << b[i] << " "; // example of output: 8 4 2 6 5
	}
	return 0;
}

Formula for the bounds of generating numbers:

min + (rand() % ((max — min) + 1))

Two-dimensional arrays

Example:

int numbMatrix[2][3] = { {1,2,3},{4,5,6} };
 
	for (int i =0; i < 2; i++){
		for (int j = 0; j < 3; j++) {
			cout << numbMatrix[i][j] << ' ';
		}
	}

Vectors

Vectors are template type. 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.
The main difference from arrays is that vectors are dynamic arrays. This means that the vector size does not need to be set initially, elements can be added dynamically.
std::vector uses a template type:

Example:

#include <vector>   // Definition
using namespace std;
int main()
{
vector<int> mm(5);  // Initialization
// or it can be empty: vector<int> mm(); 
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] << " "; // 1, 2, 3, 7
// Another kind of for loop (foreach) to iterate and print values of vector
for (auto x : a)
   cout << x << " "; // 1, 2, 3, 7
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.at(0) << endl; // 7
    // or:
    cout << v[1] << std::endl; // 5
    cout << v[2] << std::endl;
 
    // insertion into exact position starting from the very beginning
    v.insert(v.begin() + 2, 5); // number 5 into third position
 
    // 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.

Labs and tasks

All the tasks that you did not have time to complete in class automatically become your homework. The homework must be completed before the next lesson.

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

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

1-d and 2-d Arrays

Task 0: 1-d Arrays

To do:
A single-dimensional array of 10 elements is given. The elements of this array is randomly generated in the interval [5;15]. Output the number of even and odd elements of the array.

Expected output:

Array:
5 10 19 16 6 7 8 11 9 11 
number of evens = 4, number of odds = 6

[Solution and Project name: Lesson_4, files: Task0header.h, Task0imp.cpp, Task0main.cpp]

Task 00: 2-d Arrays

To do:
A two-dimensional array 2-by-3 is given. The elements of this array is randomly generated in the interval [1;10]. Create a function to print the maximum value of the array.

Expected output:

Array:
2 8 5
1 10 5
max = 10

[Solution and Project name: Lesson_4, files: Task00header.h, Task00imp.cpp, Task00main.cpp]

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 an 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.

Vectors

Task 1:

To do: A vector is given (you can have the following elements 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. Or you can complete it using another multi-file application with a print() fuctction inside.

cout << "task 1" << endl;

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

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 values.

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

[Solution and Project name: Lesson_5
or you can have individual files: L5Task1header.h, L5Task1imp.cpp, L5Task1main.cpp]

Task 2:

To do: An integer vector is given. Calculate the quantity of odd elements within this vector, as well as the quantity of positive elements within it.

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

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

Note 3: It is better to use abs function, because negative element can be met within the array.

Expected output:

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

[Solution and Project name: Lesson_5
or you can have individual files: L5Task2header.h, L5Task2imp.cpp, L5Task2main.cpp]

Task 3:

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

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

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

[Solution and Project name: Lesson_5
or you can have individual files: L5Task3header.h, L5Task3imp.cpp, L5Task3main.cpp]

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 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

[Solution and Project name: Lesson_5
you can have individual files: L5Task4header.h, L5Task4imp.cpp, L5Task4main.cpp]

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:

A = 2¹, 2², 2³, 2⁴,… 2^N

Expected output:

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

[Solution and Project name: Lesson_5
you can have individual files: L5Task5header.h, L5Task5imp.cpp, L5Task5main.cpp]

Task 6:

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

Note 1: Use 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. Or you can complete it using another multi-file application with a print() fuctction inside.

Expected output:

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

[Solution and Project name: Lesson_5
you can have individual files: L5Task6header.h, L5Task6imp.cpp, L5Task6main.cpp]

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 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

[Solution and Project name: Lesson_5
you can have individual files: L5Task7header.h, L5Task7imp.cpp, L5Task7main.cpp]

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 A vector that have the digit 2 in decimal notation.

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

[Solution and Project name: Lesson_5
you can have individual files: L5ExTask1header.h, L5ExTask1imp.cpp, L5ExTask1main.cpp]

*ExTask 2:

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

Expected output:

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

[Solution and Project name: Lesson_5
you can have individual files: L5ExTask2header.h, L5ExTask2imp.cpp, L5ExTask2main.cpp]

*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

[Solution and Project name: Lesson_5
you can have individual files: L5ExTask3header.h, L5ExTask3imp.cpp, L5ExTask3main.cpp]

*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

[Solution and Project name: Lesson_5
you can have individual files: L5ExTask4header.h, L5ExTask4imp.cpp, L5ExTask4main.cpp]

Back

Go ahead