Компьютерные книги
Главное меню
Главная Поиск по сайту Добавить материал О нас Карта книг Карта сайта
Реклама
computersbooks.net -> Добавить материал -> Языки программирования -> Кубенский А.А. -> "Структуры и алгоритмы обработки данных. Объектно-ориентированный подход и реализация на C++" -> 102

Структуры и алгоритмы обработки данных. Объектно-ориентированный подход и реализация на C++ - Кубенский А.А.

Кубенский А.А. Структуры и алгоритмы обработки данных. Объектно-ориентированный подход и реализация на C++ — Спб.: БВХ-Петербург , 2004. — 464 c.
ISBN 5-94157-506-8
Скачать (прямая ссылка): strukturiialgoritmiobrabotkidannih2004.djvu
Предыдущая << 1 .. 96 97 98 99 100 101 < 102 > 103 104 105 106 107 108 .. 161 >> Следующая

'Листинг 5.2. Простая система распределения памяти :<для цифровой сортировки
//========^=====================:======================:==========:==
// Класс ListBuffer представляет буферный пул памяти для // организации в нем списков ключей (для цифровой сортировки). //==========================================================
template <class Кеу> class ListBuffer {
Elem<Key> * buffer; // Указатель на буфер
int size; // Размер буфера
int freePtr; // Указатель первого свободного элемента
// Представитель системы распределения памяти вне класса
static ListBuffer<Key> * singleton;
// Скрытый конструктор, резервирующий память // с помощью системного вызова calloc:
ListBuffer(int n) {
buffer = (Elem<Key>*)calloc(size = n, sizeof(Elem<Key>)); clear();
}
public :
// Методы доступа к статической переменной singleton представлены // статическими функциями - членами класса getinstance и setNewBuffer static ListBuffer<Key> * getinstance() { return singleton;
}
static void setNewBuffer(int n) {
// Вызов скрытого конструктора класса singleton = new ListBuffer<Key>(n);
}
294
Гпава 5
// Деструктор освобождает занятую память с помощью // системной функции free системы управления памятью:
^ListBuffer() { free(buffer); }
// Очистка памяти сводится к сбросу указателя //на первый свободный элемент буфера, void clear() { freePtr = 0;
}
// Операция выделения элемента свободной части буфера Е1еш<Кеу> * get() {
return & buffer[freePtr++];
}
};
template <class Key>
ListBuffer<Key> * ListBuffer<Key>::singleton = NULL;
Теперь описанная система распределения памяти под элементы типа Е1еш<кеу> может быть использована в описании этого класса для переопределения оператора new. В листинге 5.3 показано, как это можно сделать в нашем случае. На приложенном компакт-диске в папке "Chapters \5.i\DigitSort" вы можете найти полное описание всех приведенных выше классов вместе с новым определением функции digitSort, которая фактически осталась такой же, как и в разд. 2.2.
IЛистинг5,3, Определение эл^ .* 'Д'.\ \
| с переопределением оператора new ДДХОч'' г V ДЧуД
//=========================================================
// Класс Elem представляет элемент списка ключей,
// формируемого для выполнения цифровой сортировки. //===========================================================
template <class Кеу> struct Elem {
Key value; // Сам элемент
Elem<Key> * next; // Указатель следующего элемента в пуле памяти // Конструкторы:
Elem () { next = NULL; } //По умолчанию следующий элемент отсутствует Elem(const Elem<Key> & src) : value(src.value), next(src.next) {} Elem(const Key & val,_ Elem<Key> * n = NULL) : value(val), next(n) {}
Алгоритмы распределения памяти
295
// Оператор присваивания:
Е1еш<Кеу> & operator = (const Elem<Key> & src) { value = src.value; next = src.next; return *this;
}
// Запрос памяти
void * operator new(size_t sz) {
return ListBuffer<Key>::getinstance()->get();
}
};
В шаблоне Elem для объектов этого класса переопределен оператор new таким образом, что теперь вместо обращения к встроенной системе распределения памяти он обращается к функции get нашего класса ListBuffer. Заголовок этого оператора имеет стандартную, определенную правилами языка форму. Оператор возвращает значение типа void * (фактически возвращается указатель на новый объект класса Е1еш<кеу>), а аргументом оператора является целое число типа size t, обозначающее количество байтов, которое потребуется для размещения в памяти нового объекта. Поскольку наша система распределения памяти узкоспециализирована и может размещать только объекты класса Е1еш<кеу>, то в реализации оператора new значение этого аргумента не используется.
Мы показали, как в языке может быть реализована собственная система управления памятью, и показали, каким образом можно подменить стандартную систему управления памятью своей для размещения в ней объектов некоторого класса. В следующих разделах этой главы мы приведем несколько различных способов реализации систем управления памятью. Подобные системы используются не только для решения узкоспециализированных задач вроде цифровой сортировки, но применяются и в качестве стандартных систем при реализации ядра языка программирования, а также при реализации соответствующих подсистем операционных систем компьютеров.
5.2. Распределение памяти блоками постоянной длины
Рассмотрим сначала самый простой случай, когда все блоки памяти, выделяемые системой, имеют один и тот же размер. В этом случае система управления памятью может быть построена приблизительно так же, как это было сделано при реализации алгоритма цифровой сортировки элементов массива. В системе будет содержаться указатель freeArea, отмечающий начало свободного участка памяти, не занятого уже выделенными блоками памяти.
296
Гпава 5
Если в систему поступает запрос на выделение блока памяти (вызывается метод get), то система может просто выделить первый участок из свободной области памяти и передвинуть указатель свободной области памяти на новое место. Если участок памяти возвращается в систему (вызван метод release), то, вообще говоря, его не удастся просто присоединить к имеющейся свободной памяти, поскольку возвращаемый блок может и не примыкать к этой области памяти. Проще всего в освобождаемых участках памяти организовать список свободных блоков памяти. Тогда система при освобождении блока может просто присоединять этот блок к списку свободных блоков. В дальнейшем система может снова задействовать освобожденные блоки, выдавая их по запросу get.
Предыдущая << 1 .. 96 97 98 99 100 101 < 102 > 103 104 105 106 107 108 .. 161 >> Следующая
Книги
Web-программирован-
ие
Аппаратное обеспечение Графика Руководство по П.О. Самоучитель Теория программирования Фотошоп Языки программирования
Новые книги
Вирт Н. "Систематическое программирование " (Теория программирования)

Эком "Microsoft Excel 2000 шаг за шагом Русская версия самоучитель " (Самоучитель)

Поляков А.Ю. "Методы и алгоритмы компьютерной графики в примерах Vizual C++" (Графика)

Баяковский Ю.М. "Графическая библиотека Open GL " (Графика)

Валиков А. "Технология " (Языки программирования)
Авторские права © 2013 ComputersBooks. Все права защищены.