Урок 5. Векторы и массивы в C++

Теория

Одномерные массивы в C++

Пример 1:

// Объявление массива из 5 целочисленных элементов 
int b[5];

Пример 2:

#include <iostream>
using namespace std;
int main()
{
 // Объявление и инициализация массива
 int a[] = {2, 3, 5, 7};
 cout << a[3] << endl; // output: 1
 // переприсваивание значения последнему элементу массива
 a[3] = 1;
 
 a[4] = 2; // возникнет ошибка
}

1. x (элемент массива) — только для чтения

int a[] = {3, 7, 9, 5, 7, 2, 7};
for (int x : a)     
    cout << x << " ";  // только вывод: 3 7 9 5 7 2 7

2. x (элемент массиваt) может изменяться

int a[] = {3, 7, 9, 5, 7, 2, 7};
for (int &x : a)  // x по ссылке
{ 
    x += 1;  
    cout << x << " ";  // вывод: 4 8 10 6 8 3 8
}

Пример 1:

// будут сгенерированы случайные числа в диапазоне от 1 до 10    
#include <iostream>
#include <ctime>
using namespace std;
 
int main()
{
// чтобы получать новые случайно сгенерированные числа каждый раз, когда мы запускаем программу:
	srand(time(0)); 
	int b[5];
	for (int &x : b)
	{
		x = 1 + rand() % 10;
		cout << x << " "; // пример вывода: 8 4 2 6 5
	}
	return 0;
}
}

Пример 2: мы можем сделать то же самое с классическим циклом for:

#include <iostream>
#include <ctime>
using namespace std;
 
int main()
{
// чтобы получать новые случайно сгенерированные числа каждый раз, когда мы запускаем программу:
	srand(time(0));
	int b[5];
	for (int i=0;i<5;i++)
	{
		b[i] = 1 + rand() % 10;
		cout << b[i] << " "; // пример вывода: 8 4 2 6 5
	}
	return 0;
}

Двумерные массивы

Пример:

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] << ' ';
		}
	}

Векторы

• Векторы относятся к шаблонному типу. Шаблонный тип — это особый тип, который может принимать различные типы при инициализации.
• std::vector — стандартная библиотека, которая обеспечивает функциональность динамического массива шаблонного типа.
• Основное отличие от массивов заключается в том, что векторы являются динамическими массивами. Это означает, что размер вектора не нужно задавать изначально, элементы могут добавляться динамически.
• std::vector использует шаблонный тип:


Пример:

#include <vector> // Определение using namespace std; int main() { vector<int> mm(5); // Инициализация // или он может быть пустым: vector<int> mm(); vector<int> a {1, 2, 3, 7}; // Инициализация // Цикл для итерации и печати значений вектора for (int i=0; i < a.size(); i++) // size() - Количество элементов cout << a[i] << " "; // 1, 2, 3, 7 // Другой вид цикла for (foreach) для итерации и печати значений вектора for (auto x : a) cout << x << " "; // 1, 2, 3, 7 for (int& x : a) x++; }

#include <vector> // Определение using namespace std; int main() { vector<int> mm(5); // Инициализация // или он может быть пустым: vector<int> mm(); vector<int> a {1, 2, 3, 7}; // Инициализация // Цикл для итерации и печати значений вектора for (int i=0; i < a.size(); i++) // size() - Количество элементов cout << a[i] << " "; // 1, 2, 3, 7 // Другой вид цикла for (foreach) для итерации и печати значений вектора for (auto x : a) cout << x << " "; // 1, 2, 3, 7 for (int& x : a) x++; }

Для использования вектора необходимо поместить директиву #include <vector> .
• При инициализации “шаблонного” типа сам тип помещается внутри < >:

std::vector<char> v1;
std::vector<int> v2;

• pop_back функция удаления последнего элемента
• push_back функция добавления элемента в конец

Пример 1:

#include <iostream> #include <vector>   int main() { // Создание вектора, содержащего целые числа std::vector<int> v = {7, 5, 16, 8};   // Добавление к вектору еще двух целых чисел v.push_back(25); v.push_back(13);   // печать конкретных элементов cout << v.at(0) << endl; // 7 // или: cout << v[1] << std::endl; // 5 cout << v[2] << std::endl;   // вставка в конкретное место, начиная с начала v.insert(v.begin() + 2, 5); // number 5 into third position   // проход по элементам и вывод значений вектора for(int n : v) { std::cout << n << '\n'; } }

#include <iostream> #include <vector> int main() { // Создание вектора, содержащего целые числа std::vector<int> v = {7, 5, 16, 8}; // Добавление к вектору еще двух целых чисел v.push_back(25); v.push_back(13); // печать конкретных элементов cout << v.at(0) << endl; // 7 // или: cout << v[1] << std::endl; // 5 cout << v[2] << std::endl; // вставка в конкретное место, начиная с начала v.insert(v.begin() + 2, 5); // number 5 into third position // проход по элементам и вывод значений вектора for(int n : v) { std::cout << n << '\n'; } }

Пример 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; }

#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; }

Шаблонные функции

• Переменная шаблона определяется путем ее объявления перед началом класса или функции:

template <typename T>
int max(T a, T b) {
  if (a > b) { return a; }
     return b;
}

• Переменные шаблона проверяются во время компиляции, что позволяет отлавливать ошибки перед запуском программы.

#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; }

#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; }

• Шаблонные функции определяют семейство функций.
• Шаблонная функция сама по себе не является типом, или функцией, или какой-либо другой сущностью. Никакой код не генерируется из исходного файла, содержащего только определения шаблонов. Для того чтобы появился какой-либо код, должен быть создан экземпляр шаблона: аргументы шаблона должны быть определены таким образом, чтобы компилятор мог сгенерировать фактическую функцию.
• Явное определение экземпляра принудительно создает экземпляр функции или функции-члена, на которые они ссылаются. Оно может появиться в программе в любом месте после определения шаблона, и для данного списка аргументов разрешается использовать в программе только один раз.

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

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

• Неявное создание экземпляра: Когда код ссылается на функцию в контексте, который требует существования определения функции, и эта конкретная функция не была создана явно, происходит неявное создание экземпляра. Список аргументов шаблона не обязательно указывать, если он может быть выведен из контекста.

#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) }

#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) }

Замечание: не использование <>полностью разрешает перегрузку для проверки как шаблонных, так и нешаблонных перегрузок.

Лабораторные работы

Для выполнения всех заданий и лабораторных работ урока вы должны создать три файла:

1. заголовочный файл (basic Vectors.h) (определения функций для всех заданий должны быть размещены здесь);
2. файл basicVectors.cpp (здесь должны быть размещены реализации функций с комментариями ко всем задачам)
3. main.cpp должен предоставлять пользовательский ввод, вызывать созданные функции и выводить результаты для всех задач.
4. Каждая функция должна сопровождаться комментарием о том, для чего она предназначена, и должен быть указан номер задания.

Одномерные и двумерные массивы

Массив:
5 10 19 16 6 7 8 11 9 11 
кол-во четных = 4, кол-во нечетных = 6

Массив:
2 8 5
1 10 5
максимальный элемент = 10

Векторы

#ifndef PRINTVECT_H
#define PRINTVECT_H
 
#include <iostream>
#include <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

lab 1
введите N - число элементов вектора
>> 25
1 3 5 7 9 11 13 15 17 19 21 23

✍ Алгоритм:

cout << "task 1" << endl;

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

task 1
до:
1 2 3 4 5 6 7 8 9 10
после:
10 9 8 7 6 5 4 3 2 1

задание 2
вектор:
-1 2 3 4 -5 6 7 8 -9 10
положительных: 7, нечетных: 5

задание 3
вектор:
-1 5 3 4 -5 6 7 8 -9 10
первый четный элемент массива: 4

задание 4
вектор:
-1 5 3 4 -5 8 7 8 -9 10
наибольший локальный минимум: 7

A = 21, 22, 23, 24,… 2N

задание 5
введите N:
>>> 5
вектор:
2  4  8  16  32

inline bool isEven(int n)
{
    // ...
}

задание 6
введите N:
>>> 5
вектор:
2  12  1  16  3
первый: 2, последний: 16

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

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

void maxInVectors(std::vector<int> &a, std::vector<int> &b, std::vector<int> &c)
{
// тело функции
}

задание 7
вектор A:
0 1 2 3 4 42 6 7 8 422
вектор B:
9 8 7 6 5 4 3 2 1 0
вектор C:
9 8 7 6 5 42 6 7 8 422

Extra tasks

bool hasDigit (int n, int digit);

b.push_back(x);

задание доп.1
вектор A:
0 1 2 3 4 42 6 7 8 422
вектор B:
2 42 422

задание доп.2
вектор:
0 1 0 0 0 42 6 7 8 422
максимальная длина нулей: 3

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

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

if(index < 0 || index > size)
        throw "Неверный индекс!";

Задание 9
введите индекс для удаления
>>> 2
до:
1 2 3 4 5 6 7 8 
после:
1 2 4 5 6 7 8

A,    A + D,    A + 2·D,    A + 3·D,    … 

Примерный вывод:

A2,    A4,    A6,    …,    A1,    A3,    A5,    … 

Примерный вывод:

Примерный вывод:

Примерный вывод:

Примерный вывод:

Массив:
5 3 4 2 1 6 3 2
После сортировки:
2 3 4 5 6 3 2 1

Массив:
1 4 7 3 9 2 4 5 2
После сортировки:
1 2 2 3 4 4 5 7 9
Введите число X:
2
Число 2 найдено.
Количество сравнений: 2

Массив:
1 4 7 3 9 2 4 5 2
После сортировки:
1 2 2 3 4 4 5 12 19
Введите число X:
12
Число 12 найдено. 
Пример:
Массив:
1 4 7 3 9 2 4 5 2
После сортировки:
1 2 2 3 4 4 5 12 19
Введите число X:
11
Число 11 не найдено. Ближайшее число 12.