« Структуры данных и алгоритмы. Теория. Динамические структуры данных Структуры данных и алгоритмы. Теория. Деревья. Основные алгоритмы над деревьями »

Структуры данных и алгоритмы. Теория. Общие правила и рекомендации к разработке собственных контейнерных структур данных

January 6, 2007

Необходимым для любого программиста является знание и умение использовать разнообразные классы-коллекции - структуры данных, которые служат для хранения и управления другими объектами согласно определенной дисциплине обслуживания и представления. Практически каждая коммерческая библиотека для популярных языков программирования имеет собственный набор коллекций. Часто различные коллекции являются уже частью стандарта языка. Предполагается, что читатель имеет понятия о коллекциях из раздела STL стандартной библиотеки C++. В данном разделе рассматриваются индексируемые коллекции, итераторы коллекций, вводится понятие курсоров. Рассматриваются основные принципы создания модифицируемых в процессе просмотра коллекций.

При создании коллекций разработчики стремятся к тому, чтобы стандартизировать средства доступа и модификации различных коллекций. Часто с целью этого выполняется перегрузка набора операторов, в качестве примера далее приводится пример интерфейса класса множества (SET). 
  1. template <class T> class Set {
  2.  
  3.  protected:
  4.     // множество полей которые служат для хранения данных коллекции
  5.     // множество вспомогательных методов для реализации логики работы
  6.     // коллекции
  7.  
  8.  public:
  9.     // множество методов и операций, которые и составляют интерфейс данного класса
  10.     Set ();
  11.     Set (const Set<T> & ans);
  12.  
  13.     // создание множества на основании массива из N элементов
  14.     // находяющихся внутри массива “Elements”
  15.     Set (T * Elements, int n);
  16.  
  17.     // оператор объединения множеств
  18.     Set <T> operator + (const Set <T> & ans) const;
  19.  
  20.     // оператор разности множеств
  21.     Set <T> operator – (const Set <T> & ans) const;
  22.  
  23.     // оператор пересечения двух множеств
  24.     Set <T> operator * (const Set <T> & ans) const;
  25.  
  26.     // проверка принадлежности одного множества другому
  27.     bool operator > (const Set <T> & ans);
  28.  
  29.     // проверка принадлежности одного множества другому
  30.     bool operator < (const Set <T> & ans);
  31.  
  32.     // проверка принадлежности одного множества другому
  33.     bool operator >= (const Set <T> & ans);
  34.  
  35.     // проверка принадлежности одного множества другому
  36.     bool operator <= (const Set <T> & ans);
  37.  
  38.     // проверка равенства двух множеств
  39.     bool operator == (const Set <T> & ans);
  40.  
  41.     // проверка неравенства двух множеств
  42.     bool operator != (const Set <T> & ans);
  43.  
  44.     // оператор получения мощности – размерности множества
  45.     operator int ();
  46.  
  47.     friend Set <T> operator + (const T & ans , const Set<T> ansto);
  48. };
Обратите внимание на то, что интерфейс данного класса выполнен с использованием шаблонов – это демонстрирует общий характер для всех контейнеров – не важно, что хранить, ведь почти всегда операции над контейнером совершенно не зависят от того, какие именно данные там хранятся.

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

Пример кода класса, в котором выполняется перегрузка оператора “[]” приводится ниже. 
  1. #include <stdio.h>
  2.  
  3. template <class T>
  4. class SafeArray {
  5.  protected:
  6.    T * data;
  7.    int count;
  8.  public:
  9.    class EonInvalidIndex {
  10.      // некоторый набор полей 
  11.      // а также множество методов класса
  12.      // и все это для того чтобы предоставить 
  13.      // информацию о том что у нас “поломалось”
  14.    };
  15.  
  16.   SafeArray (int size): count (size) , data (new T[size]) {}
  17.  
  18.   ~SafeArray (){delete data;}
  19.  
  20.   T & operator [] (int idx){
  21.    if (idx < 0 || idx >= count)
  22.     throw EonInvalidIndex () ;
  23.    return data [idx];
  24.   }
  25. };
  26.  
  27.  
  28. // и пример использования
  29. void main (void){
  30.    SafeArray<char> sa  (10);
  31.    sa [0] = 'a';
  32.    try{
  33.      sa [10] = 'b';
  34.    }
  35.    catch (SafeArray<char>::EonInvalidIndex err){
  36.       printf ("we have some problems\n");
  37.    }
  38.    printf ("error was fixed");
  39. }
Обратите внимание на то, что в качестве результата оператор “[]” возвращает ссылку на элемент. Если бы мы возвращали просто величину типа "T", а не "T &" то мы не смогли бы использовать результат вызова оператора, как в правой так и в левой части операции присвоения. 
  1. SafeArray <int> si(10);
  2. si[0] = 12; // левостороннее выражение
  3. int x = si [1]; // правостороннее выражение
Важно помнить, что не существует ограничений на тип выражения, которое будет использоваться в качестве индекса коллекции. Так для демонстрации приводится пример интерфейса хеша – ассоциативного массива. В отличии от обычного массива для доступа к элементам используется не целое число – порядковый номер, а значение ключа. Хеш – это словарь в нем один элемент служит для идентификации второго элемента. Далее приводится пример интерфейса хеша в котором хранятся строки и в качестве ключей также выступают строки string из стандартной библиотеки stl. 
  1. #include <stdio.h>
  2. #include <string>
  3.  
  4. using namespace std;
  5.  
  6. const MAX_HASH_SIZE = 100;
  7.  
  8. class Hash {
  9. protected:
  10.   string keys [MAX_HASH_SIZE];
  11.   string values [MAX_HASH_SIZE];
  12.   int hash_size;
  13. public:
  14.   Hash ();
  15.   Hash (const Hash & ans);
  16.  
  17.   Hash & operator = (const Hash & ans);
  18.  
  19.   string & operator [] (const string & idx);
  20. };
  21.  
  22. void main (void){
  23.   Hash h;
  24.   h ["apple"] = "яблоко";
  25.   h ["orange"] = "апельсинка";
  26. }
Задание: Вам необходимо написать реализацию методов приведенного выше интерфейса. После того как вы это сделаете, то исправьте следующий недостаток: в приведенном выше примере для хранения информации хеша используются два массива типа string с жестко заданным размером MAX_HASH_SIZE. Ваша задача – в качестве хранилища данных использовать динамический массив, размер которого будет задаваться как параметр конструктора хеша “Hash (int MaxSize)”. И наконец, после всего этого попробуйте перестроить хеш так чтобы в качестве как ключа так и значения мог использоваться произвольный тип данных. Подсказка – для этого используйте шаблоны.

С использованием оператора “[]” можно выполнить имитацию работы с многомерным массивом. К сожалению, вполне логичный, казалось бы, пример кода: 
  1. int & operator [] (int i , int j , int k);
Не работает. Правда существует простой и изящный способ обхода данного ограничения. Для этого необходимо создать вспомогательный класс или структуру Index. 
  1. struct Index {
  2.  int I , j , k;
  3. };
  4.  
  5. // ...
  6.  
  7. int & operator [] (const Index & idx);
  8.  
  9. // ...
  10.  
  11. // и наконец пример использования
  12. arr [Index (1 , 3 , 7)] = 23;

Умные указатели



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

Основные направления применения умных указателей:
  • Разименование значения NULL;
  • Отладка и трассировка;
  • Кэширование.

Однако перед тем как я более подробно рассмотрю эти применения, давайте для затравки попробуем решить одну из проблем всегда стоящих перед даже опытными программистами. Когда мы создаем некоторую переменную, то память для нее может быть выделена либо в стеке, либо в “куче”. Чтобы выделить место для стековой переменной нужно ее просто объявить в некотором блоке и по завершению этого блока выделенный фрагмент памяти будет автоматически освобожден. Итак, когда мы создаем объект, который размещается в памяти стека, то его деструктор неявно вызывается при выходе объекта из области видимости: 
  1. {
  2.   MyClass a;
  3.   a.someFunction ();
  4. }// именно тут происходит удаление объекта “a” и освобождение памяти.
А в данном примере, когда объект создается с помощью оператора “new” при завершении области действия, деструктор должен быть вызван явно через посредство оператора delete, если мы это не сделаем, то в памяти останется “потерянный фрагмент” (memory leaks – утечки памяти). 
  1. {
  2.   MyClass *a = new MyClass;
  3.   a->someFunction ();
  4.   delete a;// освобождение памяти необходимо выполнять явно.
  5. }
Получать адреса стековых объектов очень рискованно. Так если вы создадите функцию наподобие этой, и попытаетесь использовать возвращенную ссылку где-то дальше в вашей программе, то вы обратитесь к тому фрагменту памяти, где наверняка будет находиться нечто отличное от ожидаемого. 
  1. int * createArray (int delta){
  2.  int arr [10];
  3.  for (int I=0; I < 10; I++)
  4.     arr [i] = delta + I;
  5. }
  6.  
  7. // ...
  8. int *myarr = createArray (5);
  9. myarr [0] *= 2;
Размещать в стеке большие объекты не возможно. Если вы познакомитесь в дальшейшем с VCL (библиотека визуальных компонент разработки для delphi, cbuilder) то там вы увидите что все классы, описывающие визуальные элементы управления (и не только) создаются только в “куче”. Если вы забудетесь и вызовете оператор delete для стекового объекта, то в лучшем случае ваша программа молча вылетит. В худшем случае вы познакомитесь с таким видом ошибок, как “фантомные”. Дело в том, что в большинстве реализаций оператора “new”, он перед блоком памяти, адрес которого возвращает, записывает служебную информацию (размер выделенного фрагмента памяти), а теперь представьте, что произойдет, если вы попытаетесь освободить память для стекового объекта, у которого непосредственно перед ним может находиться все что угодно.

Однако рекомендация: «создавайте ваши объекты только в “куче”», также не слишком хороша. Прежде всего идет потеря в скорости работы: после некотрого промежутка времени работы вашей программы память кучи будет уже достаточно фрагментирована, чтобы задача выделения блока стала уже не тривиальной. Компьютер должен потратить часть ресурсов чтобы решить откуда взять блок нужного размера. Однако самым главным недостаком будет необходимость явного контроля за освобождением памяти. Если мы забудем освободить память, то постепенно через несколько часов или дней работы нашей программы могут появиться совершенно неожиданные ошибки, когда стопроцентно надежные фрагменты кода уже будут отказываться работать, или же вы переусердствуете и попытаетесь освободить память два раза. В такой ситуации те программисты, которые пишут на языках с “автоматической сборкой мусора” (в таких языках оператора delete или его аналога просто нет, а среда исполнения сама освобождает некоторый фрагмент памяти, когда на объект находящийся в нем нет больше активных ссылок, раз нет ссылок, то нельзя к нему обратиться и следовательно объект можно уничтожить без боязни) находятся в более выигрышной позиции. Итак, автоматическое удаление это плюс стековых объектов, поэтому существует прием создания “оберток”. Создается класс обертки содержащий поле типа указателя не целевой объект. Для удобства работы выполняется перегрузка оператора селектора “->”. Далее приводится пример кода, в котором к ранее созданному в главе посвященной стеку классу “MySuperStack” добавлется обертка. 
  1. template <class T>
  2. class Wrapper {
  3. 	T * ptr;
  4. public:
  5. 	Wrapper (T * w) : ptr (w) {printf ("Wrapper was created");};
  6.  
  7. 	~Wrapper (){delete ptr;};
  8. 	T * operator -> () {return ptr;}
  9.  
  10. };
  11.  
  12. void main (void){
  13. 	Wrapper < MySuperStack <int> > wr ( new MySuperStack<int>(10 , 10));
  14.  
  15. 	wr->push (123);// именно благодаря перегруженному оператору “->”
  16. 	wr->pop ();// мы получаем возможность доступа к методам стека
  17. }// именно здесь по завершению  области действия wr вызывается его деструктор 
  18. и освобождается память выделеннная и под “MySuperStack”
Следует отметить, что иногда встречается реализация оператора преобразования к типу "T *" - "operator T * ()". Однако это не безопасно с точки зрения дизайна, так как появлется гипотетическая вероятность попытки удаления объекта дважды. С целью избежать подобной ситуации практикуют прием: закрывают конструктор класса “MySuperStack” делая его protected или private класс обертки объявляют дружественным к “MySuperStack”, который и отвечает за его создание. Таким образом нигде в нашей программе не будет доступа к объекту MySuperStack не через Wrapper. К сожалению, часто данный прием трудно реализуем.

Подведем итог: для того чтобы создавать объекты динамически и автоматизировать процесс вызова деструктора каждый раз, когда объект выходит из области видимости, то рекомендуется создать обертку целевого класса. Обертка создается в памяти стека функции, а, следовательно, будет удалена автоматически, в деструкторе обертки идет явное удаление динамического объекта с помощью “delete ptr;”. Для удобства использования перегружают оператор-селектор “->”.

Рассмотрим теперь прием с разыменованием значения NULL. Общая схема использования умного указателя выглядит так: 
  1. template <class T> class SmartPointer {
  2.  protected:
  3.     T * data;
  4. public:
  5.     SmartPointer    (T * t): data (t){}
  6.     ~ SmartPointer () {delete data;}
  7.     operator T * (){ 
  8.        return data;
  9.     }
  10. };
А теперь мы попытаемся так реализовать код оператора селектора “->” чтобы при попытке доступа по NULL наша программа не завершалась бы аварийно, а продолжала бы хромать дальше. Например, так: 
  1. T * operator -> (){
  2.  if (! data){
  3.     perror (“error, dereferencing NULL, created new element”);
  4.     return (data = new T);
  5.  }
  6.  return data;
  7. }
Более изящным было бы, пожалуй, выбросить исключение, не забывайте, что если мы работаем с визуальным интерфейсом, то наши perror просто пропадут. 
  1. struct InvalidItemException {
  2.    // некоторый набор полей 
  3. };
  4.  
  5. T * operator -> (){
  6.  if (! data){
  7.     throw InvalidItemException ();
  8.  }
  9.  return data;
  10. }
Задание: создайте такую версию оператора “->”, которая бы при попытке доступа к несуществующему элементу записывала бы в файл-журнал время и имя метода. Предполагается что подобные файлы-журналы крайне удобны при отладке кода, особенно удаленной, когда разработчик физически не может выехать и наблюдать за ошибочным поведением программы у заказчика. Тогда заказчик по электронной почте просто посылает подобный файл журнала для анализа программистом.

Ведение статистики использования объекта. Это имеет большое значение при решении задач профилирования кода. Если вы в операторах “->” и “T *” выполните хотя бы подсчет количества обращений, то можно уже искать узкие места программы “bottle necks”, т.е. те фрагменты кода, которые вызыватся наиболее часто и занимают больше всего времени. Для оптимизации по скорости работы программы в дальнейшем можно “bottle neck” функции переписать.

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

Кэширование: в основе данной концепции лежит тот факт, что существуют объекты занимающие настолько большой объем памяти что одновременное нахождение хотя бы десятка из них в физической оперативной памяти не желательно. При этом, что очень важно, вероятность одновременного использования всех их крайне мала. Подобный прием, в ходе которого малоиспользуемые объекты сохраняются, например, на жесткий диск используется в современных операционных системах (виртуальная память, файлы подкачки, swap-файлы, страничный обмен). И только тогда, когда идет непосредственно обращение к объекту, которого нет в оперативной памяти его умный указатель выполняет его подзагрузку, так что для клиента создается иллюзия, что объект всегда был доступен.

Задание: необходимо разработать умный указатель, выполняющий вышеописанную дисциплину. В качество целевого объекта используйте объект BigArray (это будет уже знакомый нам класс динамического массива из предыдущих заданий, однако в потомок должен реализовать методы SaveToDisk, LoadFromDisk для сохранения и записи в файл-хранилище).

Блокировка совместного использования: умные указатели также служат для решения задачи запрета совместного использования неразделяемого ресурса несколькими потоками в многозадачном приложении. Общепринятой является механизм синхронизации: идея данного приема в том, что перед началом использования некоторого ресурса значение специального флага, назовем его “IsBusy” устанавливается в состояние “Заблокировано”, а после завершения работы с объектом наш флаг сбрасывается в состояние “Свободен”. Идея запрета доступа к объекту не через умный указатель и перегрузка оператора селектора позволяет создать единый способ обращения к функциональности класса только через посредника, который этот процесс и контролирует.

В библиотеке STL присутствует класс шаблона auto_ptr (аналогичный ранее рассмотренному Wrapper), существует достаточное количество коммерческих библиотек, в которых развиваются идеи умных указателей, однако, каждый программист должен попытаться создать их для себя сам, так как это способствует лучшему пониманию механизмов их работы.

Также следует отметить с некоторым заделом на будущее, что если вам придется писать код приложений с использованием технологий COM, то такие непонятные пока для вас вещи как “Iunknown”, “QueryInterface”, “ClassFactory” и т.д. произрастают из идеологии умных указателей.

Курсоры



Чтобы понять концепцию курсоров и того, как их использовать при работе с коллекциями, необходимо рассмотреть конкретный пример. Классическим примером являются разреженные массивы. Разраженный массив относится к числу основных структур данных. Он представляет собой матрицу, у которой большинство ячеек в любой момент времени остаются пустыми. Какими бы большими и быстрыми компьютерами мы не обладали, но для хранения матрицы размером 1000*1000*1000 вам потребуется слишком много ресурсов и хотелось бы мне посмотреть на вас когда вы будете убеждать заказчика, что ваша программа не может работать пока он не докупит еще пару гигабайт памяти и все лишь потому, что вы не удосужились поработать над оптимизацией. Когда вы на C++ или ином языке высокого уровня декларируете массив, то память выделяется для него всего сразу. При этом 99% захваченных вами ресурсов не будут использоваться и, увы, не будут доступны также и для других приложений. Все методы работы с разреженными массива имеют общую черту – память выделяется для него не сразу, а именно по мере необходимости. В качестве простейшего пример использования разреженных массивов можно привести приложения вроде ms excel или иной электронной таблицы, ведь вы не думаете, что программа хранит информацию обо всех ее ячейках (даже не заполненных), ведь в excel количество ячеек порядка 256 * 65536 = 16 777 216. если вы будете работать в сфере математического или физического моделирования, экономики, то вам придется использовать разреженные массивы.

В качестве небольшого исследования я далее привожу пример кода реализации разреженного массива навеянный решением, предложенным в книге Г.Шилдт, “Теория и практика C++” (с небольшими модификациями, разумеется). Попробуйте в нем разобраться и ответить на следующий вопрос: когда создаются новые элементы и хорош ли такой подход, а если нет то почему: 
  1. #include <stdio.h>
  2.  
  3. /* структура служащая для адресации элементов в массиве,
  4. количество полей: i, j – количество размерностей нашего разреженного массива, 
  5. в данном случае у нас обычная прямоугольная двумерная матрица.
  6. */
  7. struct Index {
  8. protected:
  9.   int i , j;
  10. public:
  11.   Index (int ii , int jj) : i(ii) , j (jj) {}
  12.   Index () : i(-1) , j (-1) {}
  13.  
  14.   bool operator == (const Index & idx) {
  15.      return i == idx.i && j == idx.j;
  16.   }
  17. };
  18.  
  19. struct Item {
  20.   Index index;
  21.   int Data;
  22.   Item * next;
  23. public:
  24.   Item (int DData , Index idx) : index (idx) , Data (DData), next (NULL){}
  25.   void SetIndex (const Index &idx)  { index = idx;}
  26.   Index GetIndex (void) {return index;}
  27.   Item () :  Data (-1), next (NULL) {}
  28.  
  29.   int GetData () {return Data;}
  30.   int & GetRefData () {return Data;}
  31.   void SetData (int DData) {Data = DData;}
  32. };
  33.  
  34.  
  35. class SparseArray {
  36. protected:
  37.    Item * first;
  38.  
  39. public:
  40.    SparseArray (void) : first (NULL) {}
  41.    ~SparseArray (){
  42.       while (first){
  43.          Item * tmp = first;
  44.          first = first->next;
  45.          delete tmp;
  46.       }
  47.    };
  48.  
  49.    int & operator [] (const Index & idx ){
  50.       Item * tmp =  first;
  51.       while (tmp){
  52.          if (tmp->GetIndex() == idx) break;
  53.          tmp = tmp->next;
  54.       }
  55.  
  56.       if (tmp) return tmp->GetRefData ();
  57.  
  58.       Item * nelt = new Item();
  59.       nelt->next = first;
  60.       first = nelt;
  61.       first->SetIndex (idx);
  62.       first->SetData (0);
  63.       return first->GetRefData (); 
  64.   }
  65.  
  66. }; //end of class
  67.  
  68. // и пример использования
  69. void main (void){
  70.    SparseArray sp ;
  71.  
  72.    sp [Index (1 , 1)] = 2;
  73.    sp [Index (1 , 3)] = 3;
  74.    sp [Index (1 , 5)] = 4;
  75.  
  76.    printf ("sp [Index (1 , 5)] = %d\n" , sp [Index (1 , 5)]);
  77.    printf ("sp [Index (1 , 2)] = %d\n" , sp [Index (1 , 2)]); 
  78. }
А вот пример результата вывода программы при запуске: 
sp [Index (1 , 5)] = 4
sp [Index (1 , 2)] = 0
Что же я буду предполагать, что вы потратили часть своего времени и разобрались в данном коде. А теперь я сформулирую недостаток решения. Как вы думаете что произойдет если я хочу просто пройтись в цикле по всем элементам нашего массива размером 1000000*1000000 и хочу просто подсчитать количество элементов которые имеют значения. Пожалуй, правильным ответом будет: аварийное завершение нашей программы с сообщением windows “нехватка виртуальной памяти”, а может ничего и не увидите – машина просто молча уйдет на перезагрузку, в общем, нам необходимо отслеживать и различать две различные ситуации обращения с помощью оператора “[]” для того чтобы просматривать значение элемента и для того чтобы его модифицировать. В ситуации, когда идет обращение с целью использования несуществующего элемента (в этой ситуации не нужно выделять память для этого элемента) необходимо каким-либо образом сигнализировать об ошибке: например, выбросить исключение или вернуть ссылку на “несуществующий” элемент – например, можно условиться что значение 0, или -1 означает нет данных. В случае если мы храним в контейнере адреса объектов, то можно возвращать значение NULL.

А с использованием курсоров решение подобной задачи становится гораздо легче.

Нам нужно чтобы оператор “[]” возвращал нечто обладающее двумя свойствами:
  1. это должно обладать способностью преобразования к типу элемента хранимого в разреженном массиве;
  2. оно может быть использовано в левой части операции присвоения для изменения соответствующей ячейки.

  1. #include <stdio.h>
  2.  
  3. class DataType{
  4.   // данный класс представляет собой имитацию
  5.   // класса хранящего некоторый набор данных
  6. };
  7.  
  8. struct Index {
  9. protected:
  10.    int i , j;
  11. public:
  12.    Index (int ii , int jj) : i(ii) , j (jj) {}
  13.    Index () : i(-1) , j (-1) {}
  14.  
  15.    bool operator == (const Index & idx) {
  16.       return i == idx.i && j == idx.j;
  17.    }
  18. };
  19.  
  20. struct Item {
  21.    Index index;
  22.    DataType * Data;
  23.    Item * next;
  24. public:
  25.    Item (DataType * DData , Index idx) : index (idx) , Data (DData), next (NULL){}
  26.    void SetIndex (const Index &idx)  { index = idx;}
  27.    Index GetIndex (void) { return index;}
  28.    Item () :  Data (NULL), next (NULL) {}
  29.  
  30.    DataType * GetData () { return Data;}
  31.    DataType * & GetRefData () { return Data;}
  32.    void SetData (DataType * DData) {Data = DData;}
  33. };
  34.  
  35. class SparseArray2 {
  36. protected:
  37.    Item * first;
  38.    friend class SparseCursor;
  39. public:
  40.    SparseArray2 () : first (NULL) {}
  41.    SparseCursor operator [] (Index idx);
  42. };
  43.  
  44.  
  45. class SparseCursor {
  46. /*
  47.  класс курсора – обратите внимание что он находится в дружеских отношениях
  48.  с классом разреженного массива равно как и наоборот, дело в том, что подобные классы 
  49.  тесно связаны с внутренним устройством друг друга
  50. */
  51.    friend class SparseArray2;
  52.    SparseArray2 & refParentContainer;
  53.    Index index;
  54.    Item * item;
  55. public:
  56.    SparseCursor (Index idx , Item * it , SparseArray2 & parentContainer)
  57.    : refParentContainer (parentContainer)  , item (it) , index (idx){}
  58.  
  59.    SparseCursor & operator = (DataType * DData){
  60.       if (item){
  61.          item->SetData (DData);
  62.          return *this;
  63.       }
  64.       Item * nelt = new Item;
  65.       nelt->index = index;
  66.       nelt->SetData (DData);
  67.       nelt->next = refParentContainer.first;
  68.       refParentContainer.first = nelt;
  69.       return *this;
  70.    }
  71. };
  72.  
  73. SparseCursor SparseArray2::operator [] (Index idx){
  74.   Item * tmp = first;
  75.   while (tmp){
  76.      if (tmp->index == idx) return SparseCursor (idx , tmp , *this);
  77.      tmp = tmp->next; 
  78.   }
  79.   return SparseCursor (idx , NULL , *this);
  80. }
  81.  
  82. // и пример использования
  83. void main (void){
  84.    SparseArray2 spa2 ;
  85.  
  86.    // мы добавляем новый элемент в наш резреженный массив
  87.    spa2 [Index(12 , 23)] = new DataType;
  88.  
  89.    // обращаемся к уже существующему и меняем его информационную часть
  90.    (spa2 [Index(12 , 23)] = new DataType) = new DataType;
  91. }
Идея в том, что в независимости от того идет ли в операторе “[]” обращение к существующему или несуществующему элементу возвращается курсор SparseCursor. Возвращенный объект знает, в какой ситуации его вернули (существует ли соответствующий элемент в коллекции или его нет, по тому равно ли значение item NULL или нет, если значение NULL, то значит, элемента не существует и, внимание, в операторе присвоения, курсор создает экземпляр нового элемента и помещает его внутрь нашего массива). Если обращение к коллекции идет для использования элемента (например, для того чтобы вызвать некоторый метод класса DataType), а не для того чтобы изменить значение элемента в определенной позиции, то перегруженный оператор присвоения не вызывается и память для него не выделяется. Теперь осталось решить, что делать в ситуации когда элемент хотят использовать. Для этого нам необходимо перегрузить оператор “->”, внутри этого оператора если соответствующего информационного компонента нет в массиве, то может быть выброшено исключение или возвращена ссылка на специальный элемент заглушку. К ранее приведенному описанию класса SparseCursor мы добавим следующие два оператора. 
  1. DataType * operator -> (){
  2.     if (item) return item->GetData();
  3.     throw EInvalidItemException ();
  4. }
  5. operator DataType * (){
  6.     return item?item->GetData ():NULL;
  7. }
Также нам потребуется создать класс, который будет служить для сигнализации о том что идет попытка использования несуществующего элемента: 
  1. struct EInvalidItemException{
  2.    // данный класс хранит набор информации о том
  3.    // почему произошло исключение из-за
  4.    // обращения к несуществующему элементу
  5. };
И в качестве демонстрации, если мы запустим следующий код: 
  1. void main (void){
  2.    SparseArray2 spa2 ;
  3.  
  4.    // мы добавляем новый элемент в наш резреженный массив
  5.    spa2 [Index(12 , 23)] = new DataType;
  6.  
  7.    // обращаемся к уже существующему и меняем его информационную часть
  8.    (spa2 [Index(12 , 23)] = new DataType) = new DataType;
  9.  
  10.    printf ("is null? %c" , spa2 [Index(12 , 24)]?'N':'Y');
  11. }
То получим следующий результат: 
is null? Y.

Итераторы



Мы создаем коллекцию и можем работать, обращаться к каждому из элементов коллекции. Что же давайте, сделаем перебор всех элементов созданного нами разреженного массива. Если вы хотите воспользоваться циклом наподобие: 
  1. for (int i=0; I < 10000; i++)
  2.   for (int j=0; j < 10000; j++)
  3.     printf ("elt at position (%d, %d) = %d" , i , j , array[index (I , j)]);
В такой ситуации, похоже, что нам придется запастись изрядным терпением. Далее одним из ключевых принципов ООП, способствующих разработке повторно-используемого кода, является скрытие от клиента внутренних особенностей устройства класса, нашей коллекции, мы должны предоставить клиенту несложный интерфейс для доступа и перебора каждого из элементов – подобные объеты служащие для унифицированного перебора элементов содержащихся внутри некоторого контейнера и называются итераторами.

Типичные операции, выполняемые над списками, массивами и иными контейнерами (т.е. классами которые служат для хранения и обслуживания согласно определенной дисциплине FIFO, LIFO или какой-то иной дисциплине, множества элементов) – это операции просмотра этих элементов по порядку и выполнения некоторой операции, например поиска максимального элемента или изменения значений согласно некоторой зависимости (далее приводится пример прохода по всем элементам списка и обычного массива): 
  1. for (int I=0; I< N; I++)
  2. printf ("element # %d = %d\n", I , Arr[I]);
  3. // печать всех элементов некоторого массива
 
  1. Pointer * P = MyList->getFist ();
  2. while (P != NULL){
  3. P->someFunction ();
  4. P = P->next();
  5. }
В данном случае для всех элементов заданного списка MyList вызывается некоторый метод someFunction.
Во всех этих примерах есть общность: всякий контейнер должен иметь метод для получения ссылки (номера, или иной указующей информации) на первый элемент, также метода получения следующего элемента за текущим и определения того, что мы дошли до конца данного контейнера.

Итератором называют абстрактное представление процесса просмотра коллекции элементов по порядку. Итератор включает последовательность S, текущую позицию в данной последовательности, а также способ перехода к следующей позиции и превращения ее в текущую. В простейшем виде всякий итератор должен поддерживать два следующих метода:
  • hasNext () – проверка того есть ли еще не пройденные элементы в итераторе;
  • next () – перемещения к следующему элементу с возвращением текущего.

Важно: итератор содержит обобщенную схему для доступа ко всем элементам контейнера, не зависящую от особенностей его реализации.

Считается, что если некоторый АТД поддерживает концепцию итератора, то он содержит метод “elements” – или иной который создает и подготавливает для работы итератор. Можно отдельно выделять итераторы, которые обладают способностью перемещения в обоих направлениях, методы для модификации элементов контейнера, обладают способностью выбирать направление перемещения от последнего к первому или наоборот, итераторы, которые не позволяет модификации элементов, по которым выполняется проход. Особый интерес представляют итераторы которые выполняют замыкание: суть данного процесса в том что при создании экземпляра итератора мы становимся очень чуствительными к попытками изменить наш контейнер во время его прохода. При создании многопоточных приложений особенно часто бывает ситуация, когда два параллельно работают два программных потока: один из которых просматривает контейнер, а второй в этот же момент времени пытается добавить или удалить элемент. В итого получается что первый поток по нескольку раз просмотрел один и тот же элемент, или пропустил что-то. Решением может быть создание внутренней копии коллекции (принадлежащей конкретному итератору) соответствующей ей на момент вызова метода “elements”, так даже если другой поток пытался модифицировать контейнер, то первый поток не заметит этого и будет работать с первоначальным состоянием контейнера.

Возвращаясь к нашему примеру с разреженным массивом. Класс итератора для него можно реализовать согласно следующему примеру: 
  1. class SparseArray2;
  2.  
  3. class Iterator {
  4. protected:
  5.    Item * cur;
  6.    SparseArray2 & refSparse;
  7. public:
  8.    Iterator (SparseArray2 & loc_refSparse);
  9.    void rewind (void);
  10.    bool hasNext (void);
  11.    DataType * next (void);
  12. };
  13.  
  14.  
  15. class SparseArray2 {
  16. protected:
  17.   Item * first;
  18.   friend class SparseCursor;
  19.   friend class Iterator;  
  20. public:
  21.   SparseArray2 () : first (NULL) {}
  22.   SparseCursor operator [] (Index idx);
  23.  
  24.   Iterator elements (void){
  25.    return Iterator (*this);
  26.   }
  27. };
  28.  
  29. Iterator::Iterator (SparseArray2 & loc_refSparse) : 
  30.     refSparse (loc_refSparse) ,
  31.     cur (loc_refSparse.first) 
  32. {}
  33.  
  34. void Iterator::rewind (void){
  35.    cur = refSparse.first;
  36. }
  37.  
  38. DataType * Iterator::next (void){
  39.    DataType * tmp = cur->GetData ();
  40.    cur = cur->next;
  41.    return tmp;
  42. }
  43.  
  44. bool Iterator::hasNext (void) {
  45.    return cur != NULL;
  46. }
И пример использования данного итератора: 
  1. Iterator I = spa2.elements ();
  2. while (I.hasNext() ){
  3.     DataType * info = I.next ();
  4.     printf ("Data %x\n"  , info);
  5. }

Задание



1) Давайте рассмотрим снова наш пример хеша, необходимо добавить к нему поддержку просмотра элементов с помощью итераторов.

Необходимо создать два итератора:
  • первый итератор должен служить для просмотра списка ключей хеша;
  • второй итератор должен перебирать пары значений (ключ, значение).

2) В детской игре «Горячая картошка» группа из N детей садится в круг, после чего участники по кругу передают друг другу предмет, называемый “картошкой” (Допустим, по часовой стрелке). Дети передают картошку до тех пор, пока ведущий не зазвонит в колокольчик, после чего ребенок, у которого в руках осталась картошка, выбывает из игры, а остальные дети замыкают круг. Данный процесс повторяется до тех пор, пока не останется один ребенок, который объявляется победителем. Используя АТД список необходимо реализовать эффективную реализацию данной игры. Пусть ведущий звонит в колокольчик после того как картошку передали M раз.

3) Развейте дальше пример хеша и добавьте к нему еще один метод “const_elements”, который должен возвращать ссылку на итератор с внутренней копией коллекции.

4) Напишите псевдокод реализации алгоритма пузырьковой сортировки, использующей только два стека и максимально пять дополнительных переменных для сортировки набора чисел изначально хранящихся в одном из стеков. Конечным результатом будет являться один из стеков, в котором элементы расположены таким образом, чтобы последовательность операций извлечения элементов (pop) выстроила элементы в нужном порядке.

Categories: Структуры данных и алгоритмы

« Структуры данных и алгоритмы. Теория. Динамические структуры данных Структуры данных и алгоритмы. Теория. Деревья. Основные алгоритмы над деревьями »