Топ контрибуторов
loading
loading
Знаете ли Вы, что

В разделе "Статьи" можно найти обучающие статьи по информационным технологиям, а также узнать о новостях сервиса Quizful.

Лента обновлений
ссылка Oct 22 23:24
Комментарий от alexcei88:
В вопросе переменная s даже не выводиться, а выводитьс...
ссылка Oct 22 17:46
Комментарий от AlexFurm:
Это UB, так можно вызывать только статические функции ч...
ссылка Oct 22 17:43
Комментарий от AlexFurm:
Любые битовые операции с signed это UB
ссылка Oct 21 20:30
Комментарий от yoori:
Любой вариант скомпилируется если компилировать не в конеч...
ссылка Oct 21 16:53
Добавлен вопрос в тест QA (Quality Assurance)
Статистика

Тестов: 153, вопросов: 8596. Пройдено: 443367 / 2177507.

Пишем шаблон умного динамического массива

head tail Статья
категория
C++
дата19.09.2010
авторstosha
голосов5

Задача

Характерной деталью динамического массива является его размерность. Точнее, задание размерности во время выполнения. Предположим, мы хотим создать массив указателей. В этом случае перед нами стоит задача своевременно очистить память, еще до того, как массив прекратит существование. При этом желательно, чтобы это происходило автоматически. И еще хотелось бы работать с массивом в привычном для себя синтаксисе. Хорошо бы сделать это в виде шаблона, чтобы использовать его с указателями любых типов.

Предлагаю в качестве упражнения начинающему программисту С++ написать такой шаблон вместе со мной. Использовать для этого будем MS Visual Studio. Заодно получить знания и дополнительный опыт, столь необходимые перед прохождением собеседования.

Немного шишек

Прежде всего, почитаем, что об этом пишут в книгах. В качестве динамических массивов рекомендуют использовать контейнер STL vector (или в данном случае, вместо вектора можно использовать другой контейнер - deque). Вообще, по определению (1) "Вектором называется абстрактная модель, имитирующая динамический массив". Вначале объявляем переменную - массив:


#include <vector>
std::vector<int*>arr;
Вектор arr не содержит ни одного элемента. Далее, заполняем массив данными:

int* pi = new int(8); // выделить память для целой переменной и присвоить ей значение 8 
arr.push_back(pi); // поместить указатель в первый элемент массива
Теперь можно обратиться к элементу массива:

arr[0] = 100; // заменить значение "8" на "100".

В массиве, где хранятся указатели, чтобы обратиться к элементу массива, надо перед именем не забыть поставить значок разыменования (*). Почему мы использовали в качестве элемента указатель, а не само значение int? Для int или других базовых типов вероятно лучше хранить значение, а не указатель. Но чтобы поместить в контейнер объект пользовательского типа надо помнить, что контейнер в своей внутренней работе постоянно использует операцию копирования. Даже если хранимый объект поддерживает такую операцию (а он обязан ее поддерживать), это может потребовать значительных ресурсов PC.

Кроме того, чтобы освободить память, занятую массивом, надо "вручную" освободить память, занятую каждым элементом. Например, так:


for (std::vector<int*>::const_iterator it=arr.begin();it!=arr.end();++it)
{
  delete *it;
}

Если этого не сделать, произойдет утечка памяти (memory leak). Ведь контейнер не знает, какого типа информация хранится в его недрах, и поэтому не будет за нас этого делать. Не забывайте, что в нашем контейнере хранятся указатели на переменные, которые расположены в динамической памяти (так называется память, которую распределяет оператор new) . До того, когда контейнер перестанет существовать, необходимо эту память освободить. А перестанет он существовать после выхода из блока (или функции), в котором объявлен, или при выполнении оператора создания исключения trow или после завершения программы, или после принудительного вызова деструктора: arr.~vector<int*>(). Т.е., в тот момент, отследить который очень трудно. Поэтому желательно, чтобы освобождение памяти происходило автоматически. В этом нам поможет идиома RAII (Resource Acquisition Is Initialization). На этой идиоме основаны т.н. умные указатели. Новый стандарт C++0x предлагает использовать в качестве умного указателя unique_ptr, который позволяет хранить указатели на массивы, чего не мог делать auto_ptr (объявленный в новом стандарте устаревшим (obsolete)). В качестве примера мы напишем свой умный указатель для хранения указателей на массивы одного типа. Его основная задача - хранить указатели на массивы и в деструкторе их безопасно чистить. Итак,

Умные динамические массивы

Заходим в MS Visual Studio. Создадим новый консольный проект, назовем его DynArray. В DynArray.cpp вводим:


#include <iostream>
#include <conio.h>
#include "vld.h"
#include "DynArrTempl.h"
#include "DynArrDestructor.h"
#include "SomeClass.h"
#include "logger.h"

typedef DynArrTempl::CArrayElement<csomeclass> TDynArray;
typedef TDynArrDestructor<dynarrtempl::carrayelement<csomeclass> > TDynArrCleaner;

int main()
{
   {
      int N;
      std::cerr << "Enter size of array (must be > 2): ";
      std::cin >> N;
      if (N < 3)
      {
         return 0;
      }

      LOG::instance().trace("A: create", 0);
      TDynArray* A = new TDynArray[N];    // Конструирование массива А
      TDynArrCleaner destructor(A);
      _ASSERT(N == A->size());

      LOG::instance().trace("B: create", 0);
      TDynArray* B = new TDynArray[7];    // Конструирование массива В
      destructor.add(B);
      _ASSERT(7 == B->size());

      CSomeClass sum;
      int rsum(0);
      for (int i = 0; i < N; ++i)
      {
         CSomeClass p(i + 1);
         A[i] = p;            // Присваивание значения CSomeClass
         sum = sum + A[i];    // Суммирование CSomeClass
         rsum += i + 1;

         _ASSERT(p == A[i]);  // Сравнения 
         _ASSERT(A[i] == p);
      }
      _ASSERT(rsum == sum);

      A[0] = A[1];            // Присваивание элементов массива
      _ASSERT(A[0] == A[1]);

   }  // Деструктор массива А и Б

   return 0;
}
Вначале мы определили тип TDynArray. CArrayElement - шаблонный класс, который принимает в качестве параметра тип CSomeClass. Т.е., чтобы использовать динамический массив, надо разработать свой класс (в качестве примера тут будем использовать класс CSomeClass) таким образом, чтобы он обладал свойствами, которые использует шаблон. Кстати, в этом проявляется так называемый "статический полиморфизм". Удобно записать эту строку где-то в отдельном заголовочном файле. Если вдруг нам захочется проверить работоспособность нашего теста с другим классом, достаточно будет отредатировать только эту строчку: заменить CSomeClass на другой. Нового тут ничего нет. Например, всем хорошо известный тип string тоже имеет где-то такую же строчку, так как основан тоже на шаблоне, параметризованном типом char*. Приступим к шаблону CArrayElement. Добавим в проект заголовочный файл "DynArrTempl.h":

#include <vector>
#include <algorithm>
#include "logger.h"

namespace DynArrTempl
{
   //================================
   // Хранилище указателей на элементы массива Т-типа
   // Локальный класс
   template<class t>
   class CDynArray
   {
      std::vector<t*>array_ptrs;
   public:

      // Добавить указатель
      void add(T* pt)
      {
         array_ptrs.push_back(pt);
      }  

      // Удалить указатель
      void erase(T* pt)
      {
         array_ptrs.erase(std::find(array_ptrs.begin(), array_ptrs.end(), pt));
      }  

      size_t size() const
      {
         return array_ptrs.size();
      }  

   };

   //================================
   // Хранилище для ссылок на массивы указателей Т-типа.
   // Локальный статический класс.
   template<class t>
   class CDynArrPtr
   {
      CDynArrPtr(){}

// в приватной области объявим вектор arrays. Тут будут храниться             // указатели на массивы Т-типа.Обратите внимание, это всего лишь 
// объявление. Транслятор не выделяет память. Он просто не знает, 
// когда это надо делать. Ведь когда конструируется объект (выделяется 
// память под данные, статические данные уже должны существовать. Чтобы 
// подсказать транслятору, мы определим переменную arrays ниже в общей 
// области. статический вектор (один) будет создан для каждого типа Т свой.
   
      static std::vector<cdynarray<t>* >arrays;
      static int flag;

   public:
      // Открыть запись элементов Т-типа в новый массив
      static void clear_flag()
      {
         flag = 0;
      }

      // Вызывается только из конструктора элемента массива при инициализации по new[]
      static CDynArray<t>* get_array()
      {
         if (0 == flag)
         {
            flag = 1;
            // Создать новый массив указателей Т-типа
            CDynArray<t>* new_array = new CDynArray<t>;
            arrays.push_back(new_array);
         }
         return arrays[arrays.size() - 1];
      }
   };

   //================================
   // Элемент динамического массива Т-типа
   // Открытый класс. Из этих элементов формируются динамические массивы указателей Т-типа
   template<class t>
   class CArrayElement
   {
      // Хранилище элементов
      CDynArray<t>* dynArrPtr;

      // Элемент массива
      T* elementPtr;
   public:

      // Конструктор вызывается автоматически по new[]
      CArrayElement()
      {
         dynArrPtr = CDynArrPtr<t>::get_array();
         // Создать новый элемент массива. Конструировать по умолчанию.
         elementPtr = new T; 
         // Добавить новый элемент в массив
         dynArrPtr->add(elementPtr);

         LOG::instance().trace("=CArrayElement: constr", 0);

      }

      // Деструктор вызывается автоматически по delete[]
      ~CArrayElement()
      {
         // Удалить элемент из массива
         dynArrPtr->erase(elementPtr);
         // Очистить память элемента массива
         delete elementPtr;

         if (dynArrPtr->size() == 0)
         {
            // Если элементов в массиве нет, но очистить память от указателя на массив
            delete dynArrPtr;
         }

         LOG::instance().trace("=CArrayElement: destr", 0);

      }

      // Закрыть массив. Был сконструирован последний элемент массива по new[]
      void close()
      {
         CDynArrPtr<t>::clear_flag();
      }

      size_t size() const
      {
         return dynArrPtr->size();
      }

      // Оператор присваивания элементов массива.
      // Копируется содержимое
      // Т-тип должен поддерживать оператор присваивания.
      CArrayElement<t> &operator=(const CArrayElement<t> &item)
      {
         *elementPtr = *item.data();
         return *this;
      }

      // Оператор присваивания элементу массива нового значения Т-типа
      // Т-тип должен поддерживать оператор присваивания.
      CArrayElement<t> &operator=(const T &t)
      {
         *elementPtr = t;
         return *this;
      }

      // Проверка на равенство элемента массива значению Т-типа
      // Т-тип должен поддерживать оператор проверки на равенство
      bool operator==(const T &t)
      {
         return (*elementPtr == t);
      }

      // Явное преобразование типа
      operator T()
      {
         return *elementPtr;
      };

      T *data() const
      {
         return elementPtr;
      }

      // Вывод в поток элемента массива.
      // Т-тип должен поддерживать вывод в поток
      friend std::ostream &operator<<(std::ostream &stream, const CArrayElement<t> &pt)
      {
         stream << *pt.element;
         return stream;
      }

   };

   // Инициализация статических переменных
   template<class t>std::vector<cdynarray<t>* > CDynArrPtr<t>::arrays;
   template<class t>int CDynArrPtr<t>::flag;

}
В массиве мы будем хранить указатели на объекты класса, который сейчас напишем. Класс будет обладать минимумом, который легко нарастить, добавив свою функциональность. Есть методы, которые класс должен поддерживать, чтобы быть совместимым с шаблоном CArrayElement. Естественно, речь не идет об неких обязательных элементах. Мы только хотим, чтобы наш массив обладал такими свойствами, чтобы пользоваться им было удобно. Чтобы синтаксис был естественным для работы с массивами. Хотелось бы, чтобы элементы массива можно было присваивать один другому, чтобы их можно было сравнивать и складывать. Вот пример такого класса: Вначале объявления:

#include <iostream>
#include "logger.h"

class CSomeClass
{
   int simply_i;
public:
   CSomeClass();

   ~CSomeClass();

   // Исключить неявное преобразование из целого типа.
   // Конструктор вызывать только явно с параметром целого типа
   explicit CSomeClass(int i);

   // Явное преобразование типа в целое
   operator int() const;

   // Класс должен поддерживать оператор присваивания объекта своего класса,
   // чтобы содержимое элементов динамического массива м.б. присваивать между собой
   CSomeClass& operator=(const CSomeClass &);

   // Присваивание элементам динамического массива целых значений
   CSomeClass& operator=(const int i);

   // Суммирование элементов динамического массива
   CSomeClass& CSomeClass::operator+(const CSomeClass &o);

   // Сравнивание элементов динамического массива
   bool operator==(const CSomeClass &);

   // Вывод в поток элементов динамического массива
   friend std::ostream &operator<<(std::ostream &, const CSomeClass &);

};
Вот определения:

#include "SomeClass.h"

CSomeClass::CSomeClass():simply_i(0)
{
}

CSomeClass::CSomeClass(int i):simply_i(i)
{
   std::stringstream text;
   text << "==CSomeClass: constr for " << simply_i;
   LOG::instance().trace(text.str().c_str(), 0);
}

CSomeClass::~CSomeClass()
{
   std::stringstream text;
   text << "==CSomeClass: destr for " << simply_i;
   LOG::instance().trace(text.str().c_str(), 0);
}

CSomeClass::operator int() const
{
   return simply_i;
}

CSomeClass& CSomeClass::operator=(const CSomeClass &o)
{
   simply_i = o.simply_i;
   return *this;
}

CSomeClass& CSomeClass::operator=(const int i)
{
   simply_i = i;
   return *this;
}

CSomeClass& CSomeClass::operator+(const CSomeClass &o)
{
   simply_i = simply_i + o.simply_i;
   return *this;
}

bool CSomeClass::operator==(const CSomeClass &o)
{
   return simply_i == o.simply_i;
}

std::ostream &operator<<(std::ostream &stream, const CSomeClass &o)
{
   std::cout << o.simply_i;
   return stream;
}
Чтобы обеспечить идиому RAII, предлагаю такой класс:

#include <vector>
#include "logger.h"

//================================
template<class t>
class TDynArrDestructor
{
   // Хранилище указателей на массивы Т-типа
   static std::vector<t*>lstDynArrays;
public:

   TDynArrDestructor(T* Array)
   {
      add(Array);
   }

   // Сохраним очередной указатель на массив Т-типа
   void add(T* Array)
   {
      if (lstDynArrays.end() == std::find(lstDynArrays.begin(), lstDynArrays.end(), Array))
      {
         lstDynArrays.push_back(Array);
      }
      Array->close();
   }

   // Согласно идиоме RAII вызывается автоматически
   // Освобождает память, занятую динамическими массивами
   ~TDynArrDestructor()
   {
      T* arr = new T[0];
      delete[] arr;
      std::vector<t*>::const_iterator it;
      for(it= lstDynArrays.begin(); it != lstDynArrays.end(); ++it)
      {
         arr = *it;

         LOG::instance().trace("-----Started destructor array-----", 0);

         delete[] arr;  // Вызывается деструктор для каждого элемента массива

         LOG::instance().trace("-----Finished destructor array-----", 0);

      }
      lstDynArrays.clear();
   }

}; 

// инициализация статического массива
template<typename t>std::vector<t*> TDynArrDestructor<t>::lstDynArrays;

Итак, схема использования такая.
Предположим, типом хранимых элементов массива будут CSomeClass (тип "Т"). Создаем динамический массив с элементами класса CArrayElement типа Т. Каждый элемент в конструкторе выделяет память для объекта типа Т и записывает указатель во внутренний буфер (dynArrPtr). Этот внутренний буфер (указатель на который хранится в каждом элементе массива) и является массивом, который мы должны потом почистить. Указатель на массив (внутренний буфер) хранится в статическом буфере класса (TDynArrCleaner), ссылка на объект которого помещается в локальный стек как автоматическая переменная (destructor). Далее, при раскрутке стека автоматически вызывается деструктор, где и происходит очистка содержимого массивов.

Скачать все файлы проекта можно здесь.

Литература.

  1. Джосьютис Н. С++. Стандартная библиотека. 2004.

Если Вам понравилась статья, проголосуйте за нее

Голосов: 5  loading...
ByteMaster   valyala   sava_vodka   bit27   serj