§ 9.4. Двумерные массивы. Контейнеры set и map. Двумерные массивы разных типов

Школьный курс python
Содержание

Что такое двумерный массив?

Двумерный массив структура данных, хранящая прямоугольную таблицу, которая называется матрицей. В математике матрица, имеющая m строк и n столбцов (m × n), представляется в следующем виде:

Матрица, в которой количество строк и столбцов одинаково, называется – квадратной. Традиционно, для обозначения индекса строки используют латинскую i, а индекс столбца обозначают латинской j. Элементы имеющие равные индексы (i == j) находятся на главной диагонали. Диагональ, проходящая через другие два угла, называется побочной.

В чем смысл такой организации данных? Матрицы используются в различных разделах математики. Одно из важных предназначений матриц – это описание векторного пространства, которое является предметом изучения линейной алгебры. Трансформация объекта (масштабирование, скос, вращение) и преобразование координат описывается с помощью матриц.
В большинстве случаев, как в математике, так и в программировании, с матрицей работают как с единым объектом. Однако, во многих языках, в том числе и в C++, структуры данных (или типа) “двумерный массив” не существует. Двумерные массивы создаются как массив массивов. Это означает, что элементами одномерного (линейного) массива являются линейные массивы равной фиксированной длины.

Двумерный С-массив и двумерные контейнеры

Двумерный C-массив

Рассмотрим в начале простой случай, когда элементами двумерного массива являются C-массивы. Создать двумерный C-массив (с инициализацией или без таковой) несложно. Определение двумерного массива отличается от определения линейного массива тем, что указываются не одна, а две размерности, каждая из которых заключена в отдельные []:

int arr[4][6];

Это определение означает, что объявлен целочисленный массив arr содержащий 4 элемента, каждый из которых содержит линейный массив размерностью 6 элементов. Принято считать, что первая размерность определяет строки, а вторая – столбцы. Таким образом, мы объявили двумерный массив состоящий из 4 строк и 6 столбцов.
Поскольку мы имеем дело с массивом массивов, то инициализация производится с помощью вложенных {} как показано в примере ниже:

const int n = 5;
const int m = 4;
int mas[n][m] {
	{1, 0, 1, 0},
	{1, 1, 0, 1},
	{0, 1, 1, 0},
	{1, 0, 1, 1},
	{0, 1, 0, 1}
};

Если требуется инициализировать двумерный массив нулевых элементов, то следует поступать так:

int mas[4][5] {{}, {}, {}, {}};

Если требуется быстро создать двумерный массив нулевых элементов произвольной размерности, то можно воспользоваться структурой вложенных циклов:

Программа 9.4.1
#include <iostream>
using namespace std;

int main() {
    int m, n;
    cout << "m = "; cin >> m;
    cout << "n = "; cin >> n;
    int arr[m][n];
    for (auto &i: arr)
        for (auto &j: i)
            j = 0;
    for (auto &i: arr) {
        for (auto &j: i)
            cout << j << ' ';
        cout << '\n';
    }
    return 0;
}

Вывод

m = 10
n = 10
0 0 0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 0 
Матричный вывод мы обсуждали ранее здесь. Если требуется работа с индексами, то диапазонный for следует заменить на обычный, по переменной

После создания двумерного массива, к его элементу можно получить доступ указав индексы по строке и столбцу. Например, arr[3][2] означает, что элемент, с которым производится операция, расположен в третьей строке и втором столбце. Таким образом, в отличие от одномерного массива, в двумерном массиве доступ к элементу получают с помощью двух размерностей: первая – по строкам, вторая – по столбцам.
Для организации ввода (или вывода) значений элементов двумерного C-массива (а также двумерных контейнеров) используется структура вложенных циклов (так, как показано в программе 9.4.1). Если используется обычный for, то во внешнем цикле (обычно с переменной i) осуществляется перебор строк, а во вложенном цикле (обычно с переменной j) осуществляется перебор элементов текущей строки (т. е. проход по столбцам матрицы). Процесс заполнения двумерного массива обычно автоматизирован, так как клавиатурный ввод матрицы в тестовых задачах довольно утомительный. Ниже в программе, матрица заполняется случайными числами.

Программа 9.4.2
#include <iostream>
#include <random>
#include <chrono>
using namespace std;
using namespace chrono;

int main() {
    const int n = 6;
    const int m = 5;
    int arr[n][m];
    int seed = system_clock::now().time_since_epoch().count();
    default_random_engine rnd(seed);
    uniform_int_distribution<int> uid(10, 99);
    for(int i = 0; i < n; i++)
        for(int j = 0; j < m; j++)
            arr[i][j] = uid(rnd);
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < m; j++) {
            cout << arr[i][j];
            cout.width(3); // Устанавливаем ширину вывода
        }
        cout << '\n';
    }
    return 0;
}

Возможный вывод

41 12 63 97 83  
12 25 74 97 81  
41 51 59 23 70  
27 76 62 84 21  
87 86 45 89 75  
69 16 59 95 67 
Двумерные контейнеры array и vector

Определение объекта array как двумерного массива состоящего из 7 строк и 5 столбцов производится следующим образом:

array<array<int, 5>, 7> arr;

Выражение array<int, 5> является описанием типа двумерного массива, содержащего 7 массивов array, в каждом из которых по 5 элементов. В программе для ввода и вывода элементов двумерного массива array помимо обычного for можно использовать диапазонный, который делает программу гораздо компактнее:

Программа 9.4.3
#include <iostream>
#include <array>
#include <random>
#include <chrono>
using namespace std;
using namespace chrono;

int main() {
    int seed = system_clock::now().time_since_epoch().count();
    default_random_engine rnd(seed);
    uniform_int_distribution<int> uid(10, 99);
    array<array<int, 5>, 7> arr;
    for (auto &r : arr)
        for (auto &j : r)
            j = uid(rnd);
    for (auto &r : arr) {
        for (auto &j : r) {
            cout << j;
            cout.width(3);
        }
        cout << "\n";
    }
    return 0;
}

Решим следующую задачу.
Задача 1. Дана матрица размера m × n. Для каждой строки матрицы найти сумму её элементов. Выведите номер строки в которой сумма максимальна, а также элементы этой строки. Для заполнения матрицы используйте генератор случайных чисел.
Решим эту задачу с помощью контейнера vector

Программа 9.4.4
#include <iostream>
#include <vector>
#include <random>
#include <chrono>
using namespace std;
using namespace chrono;

int main() {
    int seed = system_clock::now().time_since_epoch().count();
    default_random_engine rnd(seed);
    uniform_int_distribution<int> uid(10, 99);
    size_t m, n;
    cout << "m = "; cin >> m;
    cout << "n = "; cin >> n;
    // Опреление двумерного вектора векторов
    vector<vector<int>> arr;
    arr.reserve(m);
    // Заполняем двумерный вектор векторов
    for (size_t i = 0; i < m; i++) {
        for (size_t j = 0; j < n; j++) {
            // Заполняем элементами i-тый вектор
            arr[i].push_back(uid(rnd));
            // Выводим
            cout << arr[i][j] << " ";
        }
        cout << '\n';
    }
    // Решение задачи
    int Max = 0, k;
    for (size_t i = 0; i < arr.capacity(); i++) {
        int Sum = 0;
        for (size_t j = 0; j < arr[i].size(); j++)
            Sum += arr[i][j];
        if (Sum > Max) {
            Max = Sum;
            k = i;
        }
    }
    cout << "Максимальная сумма: " << Max
         << ",\nнаходится в строке: " << k
         << endl;
    return 0;
}

Возможный вывод

m = 7
n = 7
51 44 48 86 27 86 56 
32 47 94 76 28 27 41 
77 36 56 91 67 58 40 
63 49 87 92 91 55 88 
16 35 31 94 90 41 20 
23 16 19 98 84 78 96 
85 19 11 11 56 44 91 
Максимальная сумма: 525,
находится в строке: 3

Если не предполагается работать с индексом j (как в программе выше), то, в качестве вложенного цикла, можно использовать диапазонный for. Например, в программе 9.4.4 код можно оформить следующим образом:

for (size_t i = 0; i < arr.capacity(); i++) {
    int Sum = 0;
    for (auto r: arr[i])
        Sum += r;
    if (Sum > Max) {
        Max = Sum;
        k = i;
    }
}
Это код можно еще сократить, если воспользоваться функцией accumulate() (заголовок numeric), которая суммирует элементы диапазонов. Тогда код цикла суммирования (стрр. 31-33) можно заменить на эту инструкцию:

int Sum = accumulate(arr[i].begin(), arr[i].end(), 0);

Нужно сказать, что “оформление” матрицы в виде массива-массивов не является чем-то обязательным, а предназначено лишь для наглядного представления и удобной работы (это не относится к двумерным массивам, обсуждаемым ниже). Вместо двумерного массива можно использовать одномерный массив. Для этого, число строк и столбцов сохраняется в виде констант (например, row и col). Тогда программу, аналогичную программе 9.4.2, можно составить следующим образом:

Программа 9.4.5
#include <iostream>
#include <array>
#include <random>
#include <chrono>
using namespace std;
using namespace chrono;

int main() {
    int seed = system_clock::now().time_since_epoch().count();
    default_random_engine rnd(seed);
    uniform_int_distribution<int> uid(10, 99);
    const int row = 7;
    const int col = 5;
    array<int, col * row> arr;
    for (int i = 0; i < row * col; i++)
        arr[i] = uid(rnd);
    for (int i = 0; i < row * col; i++) {
        cout << arr[i];
        cout.width(3);
        if ((i+1) % row == 0)
            cout << "\n";
    }
    cout << endl;
    return 0;
}

Ассоциативные контейнеры set (множество) и map (словарь)

set

Ассоциативный контейнер set (множество, набор) является реализацией математического объекта “множество”. Множество, в отличие от последовательных контейнеров, имеет принципиально иную организацию хранения данных в виде, так называемого, сбалансированного бинарного дерева, что обеспечивает очень быстрый поиск элементов в этом контейнере.
set хранит уникальные объекты – ключи. Ключ – это объект любого типа, в том числе абстрактного (для которого определена соответствующая функция сравнения). Значение ключа является константным, т. е. изменять его нельзя (но можно удалить или вставить новый ключ). При добавлении элемента в контейнер он автоматически занимает необходимую позицию в упорядоченной совокупности других элементов. Иными словами, происходит автоматическая сортировка контейнера. set является динамическим массивом.
Поскольку множества не являются последовательными контейнерами, операция [] не поддерживается. Доступ к элементам осуществляется только с помощью итераторов или диапазонного цикла for.

Объясняется это тем, что работа диапазонного цикла for также основана на итераторах. Кстати, об итераторах! При вставке или удалении элементов множества итераторы, указывающие на элементы этого множества, остаются рабочими.

Для начала работы с классом set необходимо включить одноименный заголовок следующей директивой:

#include <set>

Объекты класса set можно получить с помощью следующих конструкторов:

Пустой массив
set<type> ar; 
Копированием или перемещением другого контейнера
set<type> ar(other);
Итераторами в интервале [first, last)
set<type> ar(first, last);
Списком инициализации
set<type> ar(std::initializer_list init); 

Помимо типа ключа, шаблонный параметр может включать также необязательную функцию сравнения. Если такая функция отсутствует, то она задана неявно функцией less<> (операция <).
Если инициализация производится явно, то шаблонный параметр можно опустить. Также можно опустить шаблонный параметр, если инициализация производится итераторами другого set:

set s1 {1, 2, 3, 4, 5};
set s2(s1.begin(), s1.end());

Для set определен деструктор. Он уничтожает объект класса set:

ar.~set();

Для класса set определены методы-модификаторы перечисленные в таблице 1.

Таблица 1. Методы-модификаторы контейнера set
Метод Описание
clear удаляет содержимое контейнера
insert вставляет элменты или узлы
emplace создает элементы на месте
emplace_hint тоже, но с подсказкой
erase удаляет элементы
swap меняет местами содержимое контейнеров
extract извлекает узлы из контейнера
merge производит слияние с узлами другого контейнера

Решим задачу с множеством.
Задача 2. Даны две строки S1 и S2. Получить множество слов, которые встречаются только в S1 или в S2 (но не в обоих одновременно), с учетом регистра символов (т. е. 'ad' и 'Ad' - разные слова).
Прежде чем решать данную задачу, несколько слов скажем как обычно поступают в работе с данным контейнером. Выше было замечено, что set производит автоматическую сортировку. Это означает, что при вставке очередного элемента, множество трансформируется (т. е. дерево перестраивается). Из этого следует, что не следует производить слишком частое удаление или вставку элементов в контейнере set. Множество создается инициализацией уже имеющимся массивом данных (например, array или vector).
В этой задаче мы немного "забежим вперед" и познакомимся со строкой как динамическим массивом. Для решения данной задачи мы создадим функцию, которая не только вернет массив слов, но и очистит слова от знаков пунктуации. Существует несколько вариантов получения из строки массива слов (или, что равно, разбиения строки на слова). Наиболее "элегантный" способ основан на использовании потоков. Этот способ будет нами рассмотрен во время знакомства со строками, через пару уроков.

Программа 9.4.6
#include <iostream>
#include <vector>
#include <set>
using namespace std;

// Функция возвращает ссылку на массив слов
vector<string> &word_to_ar (vector<string>&, string &);

int main() {
    // Массивы слов
    vector<string> words1, words2;
    // Строки
    string str1, str2;
    // Получаем строки
    cout << "str1 => "; getline(cin, str1);
    cout << "str2 => "; getline(cin, str2);
    // Получаем массивы слов
    words1 = word_to_ar(words1, str1);
    words2 = word_to_ar(words2, str2);
    // Получаем множества слов
    // дубликатов не будет
    set<string> set1 (words1.begin(), words1.end());
    set<string> set2 (words2.begin(), words2.end());
    // Решение задачи
    // Элементы находятся либо в set1, либо в set2,
    // но не в обоих одновременно
    set<string> res;
    for (auto r : set1)
        if (set2.find(r) == set2.end())
            res.emplace(r);
    for (auto r : set2)
        if (set1.find(r) == set1.end())
            res.emplace(r);
    // Выводим итоговый массив
    cout << "res  => ";
    for (auto r : res)
        cout << r << " ";
    cout << endl;
    return 0;
}

vector<string> &word_to_ar(vector<string> &vec, string &s) {
    // В word будем формировать слово
    string word = "";
    for (size_t i = 0; i < s.size(); i++) {
        // Если символ != пробелу
        if (s[i] != ' ') {
            // и это не символ пунктуации,
            if (!ispunct(s[i]))
                // то собираем слово посимвольно
                word += s[i];
            // Проверяем: не последний ли это символ?
            if (i + 1 == s.size())
                // Если да, то добавляем в массив последнее слово
                vec.push_back(word);
        } else { // если это пробел,
            // то отправляем слово в массив слов
            vec.push_back(word);
            // и сбрасываем накопитель символов
            word = "";
        }
    }
    return vec;
}

Ввод/вывод

str1 => A posse ad esse non valet consequential.
str2 => Ab esse ad posse valet consequentia.
res  => A Ab consequentia consequential non
A posse ad esse non valet consequential — (лат.) По возможному ещё не следует заключать о действительном. Ab esse ad posse valet consequentia — (лат.) По действительному заключению о возможном.

Еще раз напомним, что главным преимуществом set является быстрый поиск ключа в массиве. Для поиска элементов в set используются несколько методов. В нашей задаче мы применили метод find(), который возвращает итератор указывающий на позицию элемента. Однако, в данной задаче, нам нужен не сам элемен, а факт его нахождения в массиве. Для этого мы осуществляем сравнение итератора возвращаемого find() с итератором конца массива - end(). Если они окажутся равными, то такого элемента в массиве нет.
Остальные методы для поиска в set см. в таблице 2.

Таблица 2. Методы поиска в контейнере set
Метод Описание
count возвращает количество элементов, соответствующих определенному ключу
find возвращает итератор, который указывает на эквивалентный ключ или end(), если такого ключа нет
contains проверяет, содержит ли контейнер элемент с определенным ключом (true, если такой элемент есть)
equal_range возвращает пару (тип pair) иераторов определяющих диапазон: первый ссылается на первый элемент, который не меньше, чем key, а второй - на первый элемент, который большее, чем key
lower_bound возвращает итератор на первый элемент, который не меньше заданного ключа
upper_bound возвращает итератор на первый элемент, который больше, чем данный ключ
map

Ассоциативный контейнер map (карта, словарь) реализован похожим образом, что и множества. Главное отличие словаря от множества заключается в том, что массив map - это упорядоченный ассоциативный массив пар элементов, состоящих из ключей и соответствующих им значений. В словарях типы ключей и значений могут быть как одним из фундаментальных типов, так и абстрактным типом. Если тип ключа - это абстрактный тип, то для него должна быть определена функция сравнения, определяющая направление сортировки. Ключ имеет константное значение, изменять значение ключа нельзя. Значение второго элемента пары (значение ключа) изменять можно.
Для начала работы с классами map (или multimap) необходимо подключить заголовок map следующей директивой:

#include <map>

Шаблонные параметры типа map включают: тип ключа и тип значения ключа (Key и T), а также функцию сравнения (comp). Если такая функция отсутствует, то она задана неявно функцией less<> (операция <).
Объекты класса map можно получить с помощью следующих конструкторов:

Пустой массив
map<Key, T> ar;
Копированием или перемещением другого словаря
map<Key, T> ar(other);
Итераторами в интервале [first, last)
map<Key, T> ar(first, last);
Списком инициализации
map<Key, T> ar(std::initializer_list init);
При инициализации списком, каждая пара должна заключаться в отдельные фигурные скобки:

map<string, int> ar {{"a1", 10}, {"www", 17}, {"j8", 100}};

Деструктор класса map уничтожает объект:

ar.~map();

Методы словарей общие с методами множеств, поэтому мы не будем здесь их повторять. Для доступа к элементам в словарях можно использовать операцию []. Но, в отличие от последовательных контейнеров, в квадратных скобках не индекс, а значение ключа! Использовать данную операцию нужно с осторожностью по следующей причине. Если ar[key] не существует, то в массив будет добавлен новый элемент с ключом key. В противном случае, возвращается ссылка на элемент.

Операцию "индексирования" можно использовать только с двумя типами ассоциативных классов контейнеров map и unordered_map.

Причины, по которым добавлены эти методы разработчиками языка очевидны, код становится очень лаконичным и красивым.
Решим задачу в которой используется словарь.
Задача 3. Дан массив средних показаний выпадения осадков по месяцами года в определенной местности. Определить наиболее дождливый месяц, наиболее засушливый месяц, среднее значение мм осадков за год, в какой сезон выпадает наибольшее количество осадков и какой сезон является наиболее засушливым.

Программа 9.4.7
#include <iostream>
#include <map>
#include <algorithm>

using namespace std;

int main() {
    map<int, string> M = {
        {1, "январь"  }, {2, "февраль"}, {3, "март"},
        {4, "апрель"  }, {5, "май"    }, {6, "июнь"},
        {7, "июль"    }, {8, "август" }, {9, "сентябрь"},
        {10, "октябрь"}, {11, "ноябрь"}, {12, "декабрь"}};
    map<int, int> D;
    int Sum {};
    for (int i = 1; i <= 12; i++) {
        int val;
        cin >> val;
        D.emplace(i, val);
        Sum += val;
    }
    const auto [min, max] = minmax_element(D.begin(), D.end(),
                            [](auto &p1, auto &p2) {
                                return p1.second < p2.second;
                            });
    cout << "Наиболее засушливый месяц => "
         << M[min->first] << endl;
    cout << "Наиболее дождливый месяц => "
         << M[max->first]
         << "\nСред. значение за год => "
         << double(Sum) / 12;
    cout << "\nСамый засушливый сезон => ";
    map<int, string> S {
        {D[12] + D[1]  + D[2],  "зима" },
        {D[3]  + D[4]  + D[5],  "весна"},
        {D[6]  + D[7]  + D[8],  "лето" },
        {D[9]  + D[10] + D[11], "осень"}
    };
    cout << minmax_element(S.begin(), S.end()).first->second
         << "\nСамый дождливый сезон => "
         << minmax_element(S.begin(), S.end()).second->second
         << endl;
    return 0;
}

Ввод/вывод

90
77
64
61
60
79
54
55
53
54
73
94
Наиболее засушливый месяц => сентябрь
Наиболее дождливый месяц => декабрь
Сред. значение за год => 67.8333
Самый засушливый сезон => осень
Самый дождливый сезон => зима
Вводились данные для г. Ейска

Программа не настолько, на самом деле, сложна, на сколько может показаться. Но в ней есть вещи о которых мы еще не упоминали. Первый сложный фрагмент:

const auto [min, max] = 
    minmax_element(D.begin(), D.end(),
                   [](auto &p1, auto &p2) {
                       return p1.second < p2.second;
                 });

Очевидно, что здесь производится распаковка пары. Пару возвращает функция библиотеки algorithm - minmax_element(). Первый элемент пары - это минимальное значение диапазона, второй элемент - максимальное значение. Функция имеет три аргумента: два обязательных (это итераторы исследуемого диапазона; в нашем случае, вся длина массива) и третий, необязательный (но в нашей программе он присутствует) аргумент, - это функция сравнения (далее - компаратор). Поскольку пара - это сложный объект, состоящий из двух объектов, то необходимо "подсказать" функции какой конкретно элемент пары должен участвовать в операции сравнения. Существует несколько способов это сделать, но мы выбрали наиболее простой - использование лямбла-функции (далее - просто лямбда). Лямбда - это анонимная функция, которая объявляется в месте её использования, при этом она не получает идентификатора. Если лямбда не имеет ссылок, то повторно использовать такую функцию нельзя. Лямбда имеет все атрибуты обычной функции плюс дополнительная секция - "список захвата", заключаемая в квадратные скобки (в нашем случае она не используется). В качестве параметров функция принимает два объекта для сравнения - это элементы map (которые являются парой). Копаратор возвращает логическое значение - результат сравнения двух объектов. Для нас важно указать не на сам факт сравнения, а на то, что конкретно сравнивается от пары. А сравниваются - значения ключей (второй компонент пары). Функция minmax_element реализована так, что не имеет значения какую конкретно операцию сравнения вы выберите (">" или "<"), результат это не изменит. Если не использовать компаратор, то будут сравниваться ключи.
Следующее сложное место программы:

M[min->first]

До этого момента, при распаковке пары, мы использовали операцию "точка" с помощью которой мы получали значения для первого (first) и второго (second) компонента пары по ссылке. Но, как было упомянуто ранее, итератор (с помощью которого мы получаем доступ к элементам map) является, по существу, указателем. Указатель - это разновидность переменной (для итераторов - это абстрактный тип), которая хранит адрес памяти. В этом случае, доступ к компонетам пары мы получаем с помощью операции стрелка (->). Тема указателей выходит за рамки нашего курса. Здесь мы можем лишь сказать следующее: стрелка является, по существу, операцией разыменования (суть её, напомню, в том, что мы получаем некоторое значение по адресу памяти, где это значение сохранено). Запомните: если пара обычная переменная, то компоненты пары мы получаем с помощью операции ".", а если это итератор (или указатель), то компоненты пары мы получаем с помощью операции "->". Например:

// Обычная переменная
pair var {a, b};
auto one = var.first;   // a - первый
auto two = var.second;  // b - второй
// Итератор
auto it = ar.begin();    // ar объект map
auto one = it -> first;  // первый компонент
auto two = it -> second; // второй компонент

Что касается операции min->first, то в ней мы получаем значение ключа для словаря M.

В программе выше, min и max - это пары в которых второй компонент имеет минимальное и максимальное значение, соответственно.

Для добавления элементов в массив (set или map) мы использовали метод epmlace(). Например, в программе 9.4.5:

ar.emplace(key, val);

Разумеется, это не единственная возможность, но в этом случае пара создается автоматически и код выглядит наиболее компактно. Другим вариантом добавления элементов является метод insert:

ar.insert(make_pair(key, val));

Для этого метода пару необходимо создавать. Если используются константы:

ar.emplace(20, "Sidorova");
ar.insert({20, "Sidorova"});

то для insert пару необходимо заключать в фигурные скобки.

Двумерные массивы разных типов

Двумерными могут быть не только array и vector, но и другие абстрактные типы. При этом контейнер одного типа может содержать, в качестве элементов, контейнер другого типа. В программе выше, в качестве элементов массива vector, выступали объекты класса string (это символьные динамические массивы). Элементами статического массива array могут быть динамические массивы (такие как vector или list) и наоборот. Кроме того, если массивы-элементы - это динамические структуры, то они могут иметь переменную длину (т. е. матрицами такие массивы уже назвать нельзя). Двумерные массивы разных типов (с учетом их методов) по сложности уже близки к пользовательским комбинированным типам, таким, как записи (в Pascal), структуры (в C/C++) или классы (C/C++/python). Эти типы мы будем рассматривать в старших классах.
Рассмотрим пример задачи с "комбинированным" двумерным масивом.
Задача 4. В колледже N учащихся проходят курсовую подготовку по 4 предметам: A, B, C и D. Каждый курсант имеет уникальный номер (id). Нумерация начинается с 0. По окончании обучения они сдают выпускные экзамены по этим предметам. Результаты экзамена оцениваются по 10-бальной шкале. Диплом с отличием получает только тот выпускник курсов, который показал общий результат не менее 80% от максимальной суммы баллов по всем предметам. Программа "Экзаменатор" фиксирует результаты учащихся. По окончании экзамена, программе подан запрос на выборку данных: необходимо вывести данные тех учащихся, которые получили красный диплом, их id, средний и максимальный балл в порядке возрастания идентификаторов. В последней строке программа выводит общие средние баллы по всем предметам.

Программа 9.4.8
#include <iostream>
#include <iomanip>
#include <vector>
#include <map>
using namespace std;

// Функция получения суммы значений словаря
int sum_value(map<string, int> &val) {
    int s {};
    for (auto &r : val) {
        s += r.second;
    }
    return s;
}

// Функция определения max значения словаря
int max_value(map<string, int> &val) {
    int Max {-1};
    for (auto &r : val) {
        if (r.second > Max)
            Max = r.second;
    }
    return Max;
}

int main() {
    size_t N;
    cout << "N = "; cin >> N;
    // Массив курсантов
    vector<map<string, int>> P;
    P.reserve(N);
    for (size_t i = 0; i < N; i++) {
        cout << i + 1 << endl;
        // Записываем результаты каждого курсанта
        map<string, int> D = {{"A", 0}, {"B", 0}, {"C", 0}, {"D", 0}};
        cout << "A = "; cin >> D["A"];
        cout << "B = "; cin >> D["B"];
        cout << "C = "; cin >> D["C"];
        cout << "D = "; cin >> D["D"];
        // Добавляем словарь в массив
        P.push_back(D);
    }
    // Обработка запроса
    // Открываем протокол результатов экзамена
    int a {}, b {}, c {}, d {}, j {1};
    for (auto &r: P) {
        // Сумма баллов по предметам
        a += r["A"];
        b += r["B"];
        c += r["C"];
        d += r["D"];
        // Проверяем кандидата
        if (sum_value(r) >= 32 &&
                r["A"] >= 5 &&
                r["B"] >= 5 &&
                r["C"] >= 5 &&
                r["D"] >= 5)
            cout << "id = " << j << " "
                 << fixed << setprecision(2)
                 << sum_value(r) / 4. << " "
                 << max_value(r) << endl;
        ++j;
    }
    cout << "Ср. " << fixed << setprecision(2)
         << "A = " << float(a) / N << ", "
         << "B = " << float(b) / N << ", "
         << "C = " << float(c) / N << ", "
         << "D = " << float(d) / N << endl;
    return 0;
}

Ввод/вывод

N = 3
1
A = 5
B = 9
C = 8
D = 7
2
A = 10
B = 8
C = 6
D = 9
3
A = 8
B = 8
C = 9
D = 7
id = 2 8.25 10
id = 3 8.00 9
Ср. A = 7.67, B = 8.33, C = 7.67, D = 7.67

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

Приложение

Примеры решения задач
Вопросы
Темы сообщений
Задания А
Задания Б
Задания С
Ссылки
1 Звезда2 Звезды3 Звезды4 Звезды5 Звезд (1 оценок, среднее: 5,00 из 5)
Загрузка...

Если вы нашли ошибку, пожалуйста, выделите фрагмент текста и нажмите Ctrl+Enter.


Обсуждение закрыто.