C++. Контрольна робота. Додаток типу ConsoleApplication. Шаблонний клас CArray – масив даних довільного типу

Контрольна робота. Додаток типу ConsoleApplication. Шаблонний клас CArray – масив даних довільного типу

За даним прикладом можна навчитись розробляти власні шаблонні класи, в яких пам’ять виділяється динамічно.


Зміст


Умова задачі

Розробити шаблонний клас CArray — масив даних довільного типу T та тести, які демонструють роботу з цим класом. Пам’ять для масиву даних виділяється динамічно.

Повинні бути реалізовані наступні методи:

  • конструктор за замовчуванням;
  • конструктор копіювання;
  • деструктор;
  • метод push_back(T _value) який додає елемент _value в кінець масиву;
  • метод erase(int _index) який видаляє елемент з масиву за заданим індексом _index;
  • метод insert(int _index) який вставляє елемент в масив за заданим індексом _index;
  • метод size() який повертає розмір масиву;
  • метод clear() який очищає масив;
  • операторна функція operator[](), яка перевантажує оператор [] індексування елементів масиву і повертає значення елементу масиву за заданим індексом;
  • метод print(), який виводить масив.

Рішення повинно демонструвати роботу класу при допомозі наступних тестів:

  • 1. Робота з числами (int)
    • 1.1. Додавання в циклі 20 випадкових чисел в діапазоні від 0 до 100.
    • 1.2. Впорядкування отриманого набору чисел за зростанням.
    • 1.3. Видалення кожного другого елементу.
    • 1.4. Вставка 10 випадкових чисел в діапазоні від 0 до 100 на випадкові позиції.
    • 1.5. Очищення контейнеру.
  • 2. Робота з об’єктами (std::string)
    • 2.1. Додавання в циклі 15 випадково вибраних слів, що складаються з латинських букв нижнього регістру.
    • 2.2. Впорядкування отриманого набору слів за зростанням.
    • 2.3. Видалення кожного слова, що включає в себе будь-яку з букв a, b, c, d, e.
    • 2.4. Вставка трьох випадково вибраних слів на випадкові позиції.

 


Виконання

1. Текст програми

Реалізація програми типу Console Application, яка реалізує клас та тести з ним, має наступний вигляд.

// Задача про шаблонний клас
#include <iostream>
#include <new>
#include <vector>
#include <time.h>
using namespace std;

template <typename T>
class CArray
{
public:
  // конструктор за замовчуванням
  CArray()
  {
    count = 0;
  }

  // конструктор копіювання - обов'язковий, оскільки пам'ять для даних виділяється динамічно
  CArray(const CArray& _A)
  {
    try {
      // спроба виділити пам'ять для масиву типу T
      A = new T[_A.count];
      count = _A.count;
      for (int i = 0; i < count; i++)
        A[i] = _A.A[i];
    }
    catch (bad_alloc e)
    {
      count = 0;
      cout << "Error. Cannot allocate memory." << endl;
      cout << e.what() << endl;
    }
  }

  // оператор копіювання
  CArray& operator=(const CArray& _A)
  {
    // звільнити попередньо виділену пам'ять
    if (count > 0)
      delete[] A;

    // виділити пам'ять заново
    try {
      A = new T[_A.count];
      count = _A.count;

      for (int i = 0; i < count; i++)
        A[i] = _A.A[i];
    }
    catch (bad_alloc e)
    {
      count = 0;
      cout << "Error. Cannot allocate memory." << endl;
      cout << e.what() << endl;
    }
    return *this;
  }

  // деструктор
  ~CArray()
  {
    // звільнити попередньо виділену пам'ять
    if (count > 0)
      delete[] A;
  }

  // додати елемент в кінець масиву
  void push_back(T value)
  {
    T* A2; // додатковий покажчик на масив
    // спроба виділити пам'ять
    try {
      A2 = new T[count + 1];
      count++; // якщо пам'ять виділена, то збільшити на 1 кількість елементів в масиві

      // скопіювати масив A в масив A2
      for (int i = 0; i < count - 1; i++)
        A2[i] = A[i];

      // додати елемент value
      A2[count - 1] = value;

      // звільнити пам'ять, виділену під масив A
      if ((count - 1) > 0)
        delete[] A;

      // перенаправити покажчик A на масив A2
      A = A2;
    }
    catch (bad_alloc e)
    {
      cout << "Error. Cannot allocate memory." << endl;
      cout << e.what() << endl;
    }
  }

  // метод, що виводить масив A - потрібен для тестування
  void print()
  {
    cout << "Array A: " << endl;

    if (!count)
    {
      cout << "Array is empty." << endl;
      return;
    }

    for (int i = 0; i < count; i++)
      cout << A[i] << " ";
    cout << endl;
  }

  // додати елемент в масив за заданим індексом
  void insert(int _index, const T& _value)
  {
    // перевірка на коректність індексу
    if (!CheckIndex(_index))
    {
      cout << "Error. Bad index. ";
      return;
    }

    T* A2;
    A2 = Alloc(count + 1); // спроба виділити пам'ять
    if (A2 == nullptr)
    {
      cout << "Error. Method insert(). Cannot allocate memory." << endl;
      return;
    }

    // копіювання A в A2 до позиції _index
    for (int i = 0; i < _index; i++)
      A2[i] = A[i];

    // вставка в позиції _index
    A2[_index] = _value;

    // копіювання A в A2 після позиції _index
    for (int i = _index + 1; i < count + 1; i++)
      A2[i] = A[i - 1];

    // звільнити пам'ять, попередньо виділену для масиву A
    if (count > 1)
      delete[] A;

    count++; // збільшити к-сть елементів масиву на 1

    // перенаправлення покажчика A на масив A2
    A = A2;
  }

  // метод erase() - видаляє елемент з масиву за заданим індексом _index
  void erase(int _index)
  {
    // перевірка, чи коректний індекс
    if (!CheckIndex(_index))
    {
      cout << "Bad index." << endl;
      return;
    }

    // цикл видалення з масиву елементу в позиції _index
    for (int i = _index; i < count - 1; i++)
      A[i] = A[i + 1];
    count--; // зменшити кількість елементів масиву на 1

    // перерозподілити пам'ять
    T* A2 = Alloc(count); // виділити пам'ять заново

    // скопіювати A в A2
    for (int i = 0; i < count; i++)
      A2[i] = A[i];

    // звільнити пам'ять, виділену під масив A
    if (count > 0)
      delete[] A;

    // перенаправити покажчик A на A2
    A = A2;
  }

  // метод, який повертає розмір масиву
  int size()
  {
    return count;
  }

  // метод, який очищає масив
  void clear()
  {
    if (count > 0)
    {
      delete[] A;
      count = 0;
    }
  }

  // операторна функція operator[], яка перевантажує оператор індексування масиву
  T& operator[](int _index)
  {
    if (CheckIndex(_index))
      return A[_index];
    else
    {
      T value = 0;
      cout << "Bad index." << endl;
      return value;
    }
  }

protected:
  T* A; // масив даних
  int count; //кількість елементів масиву

  // внутрішній метод, що перевіряє, чи значення індексу в допустимих межах
  // повертає true, якщо індекс _index коректний
  bool CheckIndex(int _index)
  {
    if ((_index < 0) || (_index >= count))
      return false;
    return true;
  }

  // метод, що виділяє пам'ять для масиву типу T,
  // метод повертає покажчик на виділений масив
  T* Alloc(int _count)
  {
    T* A2 = nullptr;
    try {
      A2 = new T[_count];
    }
    catch (bad_alloc e)
    {
      cout << e.what() << endl;
      return nullptr;
    }
    return A2; // повернути покажчик на виділений фрагмент
  }
};

// Тести для демонстрації роботи класу
// 1.1. Додавання в циклі 20 випадкових чисел в діапазоні від 0 до 100
void Test_1_1(CArray<int>& A)
{
  int i, number;
  cout << "Test 1.1. Form the array with 20 random numbers." << endl;

  srand(time(NULL));
  for (i = 0;i < 20;i++)
  {
    // сформувати випадкове число від 0 до 100
    number = rand() % 100;

    // додати число в кінець масиву
    A.push_back(number);
  }
}

// 1.2. Впорядкування набору чисел за зростанням
void Test_1_2(CArray<int>& A)
{
  int i, j;
  int t;

  cout << "Test 1.2. Sorting the array." << endl;

  // сортування методом вставки
  for (i=0;i<A.size()-1;i++)
    for (j=i; j>=0; j--)
      if (A[j] > A[j + 1])
      {
        t = A[j];
        A[j] = A[j + 1];
        A[j + 1] = t;
      }
}

// 1.3. Видалення кожного другого елементу
void Test_1_3(CArray<int>& A)
{
  CArray<int> B; // новий масив

  cout << "Test 1.3. Deleting every secont item." << endl;
  B.clear();
  for (int i = 0; i < A.size();i++)
  {
    if (i % 2 == 1)
      B.push_back(A[i]);
  }
  A = B;
}

// 1.4. Вставка 10 випадкових чисел в діапазоні від 0 до 100 на випадкові позиції
void Test_1_4(CArray<int>& A)
{
  int i;
  int number, pos;
  int t;

  cout << "Test 1.4. Inserting 10 random numbers to random positions" << endl;

  // прив'язатись до поточного часу при генеруванні випадкових чисел
  srand(time(NULL));

  t = 0; // змінна, що визначає кількість доданих чисел
  for (i = 0; i < 10; i++)
  {
    number = rand() % 100; // випадкове число
    pos = rand() % (10 + t); // випадкова позиція (0..10+t)
    A.insert(pos, number);
    t++; // кількість доданих чисел
  }
}

// 1.5. Очистка контейнера
void Test_1_5(CArray<int>& A)
{
  cout << "Test 1.5. Clear the array." << endl;
  A.clear();
}

// Демонстрація роботи класу з числами int
void DemoInt()
{
  CArray<int> A; // масив, який повинен бути протестований

  // Тест 1.1
  Test_1_1(A);
  A.print(); // вивести масив на екран

  // Тест 1.2
  Test_1_2(A);
  A.print();

  // Тест 1.3
  Test_1_3(A);
  A.print();

  // Тест 1.4
  Test_1_4(A);
  A.print();

  // Тест 1.5
  Test_1_5(A);
  A.print();
}

// 2. Робота з об'єктами (std::string)
// 2.1. Додавання в циклі 15 випадково вибраних слів, що складаються з латинських букв у нижньому регістрі
void Test_2_1(CArray<string>& A)
{
  int i, j;
  int len; // довжина слова
  string word;
  char symbol;

  cout << "Test 2.1. Adding 15 new words." << endl;
  srand(time(NULL));

  // цикл формування слів
  for (i = 0; i < 15; i++)
  {
    len = rand() % 6 + 1; // випадкова довжина слова від 1 до 6

    // сформувати випадкове слово
    word = "";
    for (j = 0;j < len;j++)
    {
      // отримати випадковий символ
      symbol = 'a' + rand() % ((int)'z' - (int)'a' + 1);
      word += symbol; // додати символ до слова
    }

    A.push_back(word); // додати випадкове слово до масиву
  }
}

// 2.2. Впорядкування набору слів за зростанням
void Test_2_2(CArray<string>& A)
{
  int i, j;
  string t;

  cout << "Test 2.2. Sorting words." << endl;

  // сортування методом вставки
  for (i = 0;i < A.size() - 1;i++)
  {
    for (j=i; j>=0; j--)
      if (A[j] > A[j + 1])
      {
        t = A[j];
        A[j] = A[j + 1];
        A[j + 1] = t;
      }
  }
}

// 2.3. Видалення кожного слова, що включає в себе будь-яку з букв a,b,c,d,e
void Test_2_3(CArray<string>& A)
{
  // додаткові змінні
  int i, j;
  string word;
  CArray<string> B;
  bool f_delete;

  cout << "Test 2.3. Deleting words wit characters a..z " << endl;

  // цикл утворення нового масиву B, який не містить слів
  for (i = 0; i < A.size(); i++)
  {
    word = A[i];
    f_delete = false;
    for (j=0; j<word.length(); j++)
      if (('a' <= word[j]) && (word[j] <= 'e')) // якщо символ в межах 'a'..'e'
    {
      f_delete = true; // то можна видаляти
      break;
    }

    // додати слово в масив B, яке не містить 'a'..'e'
    if (!f_delete)
      B.push_back(word);
  }
  A = B; // скопіювати масив B в A
}

// 2.4. Вставка 3-х нових випадкових слів на випадкові позиції
void Test_2_4(CArray<string>& A)
{
  int i, j;
  int len; // випадкова довжина випадкового слова
  string word; // випадкове слово
  char symbol; // випадковий символ
  int position; // випадкова позиція (0, 1, ...)
  int t; // кількість доданих слів

  cout << "Test 2.4. Inserting 3 new random words to random positions" << endl;

  // прив'язатись до таймера при формуванні випадкових слів
  srand(time(NULL));

  // Цикл додавання випадкових слів
  for (i = 0, t = 0; i < 3; i++, t++)
  {
    // взяти випадкову позицію
    position = rand() % (A.size() + t);

    // взяти випадкову довжину слова 1..6
    len = rand() % 6 + 1;

    // генерування випадкового слова
    word = "";

    for (j = 0; j < len; j++)
    {
      // сформувати випадковий символ
      symbol = 'a' + rand() % ((int)'z' - (int)'a' + 1);
      word += symbol; // додати символ до слова
    }

    // вставити випадкове слово word у випадкову позицію position
    A.insert(position, word);
  }
}

// Метод, що демонструє роботу з об'єктами std::string
void DemoString()
{
  CArray<string> A; // оголосити масив слів для тестування

  Test_2_1(A);
  A.print();

  Test_2_2(A);
  A.print();

  Test_2_3(A);
  A.print();

  Test_2_4(A);
  A.print();
}

int main()
{
  DemoInt();
  DemoString();
}

 

2. Результат роботи програми
Test 1.1. Form the array with 20 random numbers.
Array A:
40 55 83 90 71 0 38 98 15 49 44 69 74 82 84 90 88 14 93 10
Test 1.2. Sorting the array.
Array A:
0 10 14 15 38 40 44 49 55 69 71 74 82 83 84 88 90 90 93 98
Test 1.3. Deleting every secont item.
Array A:
10 15 40 49 69 74 83 88 90 98
Test 1.4. Inserting 10 random numbers to random positions
Array A:
10 15 38 93 84 40 83 71 49 69 40 88 74 74 83 15 88 90 44 98
Test 1.5. Clear the array.
Array A:
Array is empty.
Test 2.1. Adding 15 new words.
Array A:
txkhs crt paqkm shcni wgagcv ye jlww rayr qtjc usd bprcx s yvd pwxb jobx
Test 2.2. Sorting words.
Array A:
bprcx crt jlww jobx paqkm pwxb qtjc rayr s shcni txkhs usd wgagcv ye yvd
Test 2.3. Deleting words wit characters a..z
Array A:
jlww s txkhs
Test 2.4. Inserting 3 new random words to random positions
Array A:
jlww acrtk xk s qkm txkhs

 

3. Пояснення до роботи програми
3.1. Виклик функцій для тестування роботи класу

З функції main() викликаються функції DemoInt() та DemoString(). Кожна з функцій викликає відповідний тест.

Функція DemoInt() викликає тести для типу int. Кожен тест оформлений у вигляді окремої функції: Test_1_1(), Test_1_2(), Test_1_3(), Test_1_4(), Test_1_5(). Кожна з тестувальних функцій отримує вхідним параметром посилання на масив типу int

CArray<int>& A

Оскільки, передача масиву відбувається за посиланням, то є можливість змінювати вхідний масив у функції.



Функція DemoString() викликає тести для класу std::string. Клас string реалізований у просторі імен std і призначений для роботи з рядками символів типу char*. Клас містить ряд методів для роботи з рядками символів. Кожен тест для типу string оформлений у вигляді окремої функції: Test_2_1(), Test_2_2(), Test_2_3(), Test_2_4(). Як і у випадку з типом int, кожна з функцій отримує вхідним параметром посилання на масив типу string

CArray<string>& A

У кожній тестувальній функції змінюєься вхідний масив (передача масиву за посиланням).

 

3.2. Для чого в класі реалізовано конструктор копіювання та оператор копіювання

У класі CArray оголошується динамічний масив A узагальненого типу T. Фактично, оголошується покажчик A на тип T

T* A; // масив даних

В залежності від ситуації, для масиву A пам’ять виділяється динамічно з допомогою оператора new. Якщо в класі пам’ять виділяється динамічно, то цей клас обов’язково повинен мати реалізацію конструктора копіювання та оператора копіювання щоб уникнути недоліків побітового копіювання. Більш детально про необхідність оголошення в класі конструктора копіювання та оператора копіювання описується в темі:

 

3.3. Особливості виділення пам’яті в операторі new

У класі в різних функціях відбувається виділення пам’яті з допомогою оператора new. Існує ризик, що пам’ять може не виділитись. У цьому випадку, система генерує виключення (exception). Для того, щоб виконання програми не припинялось а виводилось відповідне повідомлення, виклик оператора new взято в блок try…catch як показано нижче

...
try {
  // спроба виділити пам'ять для масиву типу T
  A = new T[_A.count];

  count = _A.count;
  for (int i = 0; i < count; i++)
    A[i] = _A.A[i];
}
catch (bad_alloc e)
{
  count = 0;
  cout << "Error. Cannot allocate memory." << endl;
  cout << e.what() << endl;
}
...

Як видно з коду, виключення типу bad_alloc перехоплюється в блоці catch. bad_alloc – це є клас, що описує виключну ситуацію у випадку, якщо пам’ять оператором new не виділилась. Клас bad_alloc успадкований з класу exception і є частиною ієрархії класів, що описують виключення у C++.

 

3.4. Звільнення пам’яті в класі оператором delete[]

Оскільки, пам’ять для масиву A виділяється як для масиву (а не одиночного елементу)

A = new T[count]

то звільняти її потрібно оператором

delete[] A;

Якби пам’ять виділялась як для одиночного елементу, то замість delete[] потрібно було використати delete.

 

3.5. Додаткові внутрішні функції класу

У класі, в розділі private реалізовано наступні додаткові внутрішні функції

  • CheckIndex() – перевіряє, чи значення індексу масиву A є в допустимих межах;
  • Alloc() – повертає покажчик на виділену ділянку пам’яті заданого розміру _count, який є вхідним параметром.

Ці функції викликаються декілька разів у різних методах класу.

 

3.6. Особливості генерування випадкових чисел. Функції srand(), time(), rand()

Для того, щоб згенерувати випадкове число, у програмі використовуються наступні функції:

  • srand() – встановлює стартове число для функції rand(). На основі цього числа буде формуватись послідовність випадкових чисел функцією rand();
  • rand() – повертає цілочисельне випадкове число (генерує випадкове число);
  • time() – функція з бібліотеки time.h.

Функція time() з параметром NULL

time(NULL)

повертає кількість мілісекунд, які пройшли з 1 січня 1970 року. Ця функція необхідна для того, щоб сформувати стартове число для генератора випадкових чисел. Кількість мілісекунд завжди буде різною, оскільки запуск програми залежить від користувача і неможна передбачити момент запуску.

Функція time() вкладена як параметр у функції srand()

srand(time(NULL));

Функція srand() встановлює стартове число, яке буде використовуватись як основа генерування послідовності випадкових чисел функцією rand().

Отже, поєднання функцій srand(), time(), rand() дозволяє при кожному виклику генерувати різні послідовності чисел.

 


Зв’язані теми