8.8 Ассоциативный массив.

   


Назад  |  Вперёд

Из всех универсальных невстроенных типов самым полезным, по всей видимости, является ассоциативный массив. Его часто называют таблицей (map), а иногда словарем, и он хранит пары значений. Имея одно из значений, называемое ключом, можно получить доступ к другому, называемому просто значением. Ассоциативный массив можно представлять как массив, в котором индекс не обязан быть целым:

           template<class K, class V> class Map {
              // ...
           public:
              V& operator[](const K&); // найти V, соответствующее K
                                       // и вернуть ссылку на него
              // ...
           };

Здесь ключ типа K обозначает значение типа V. Предполагается, что ключи можно сравнивать с помощью операций == и <, так что массив можно хранить в упорядоченном виде. Отметим, что класс Map отличается от типа assoc из $$7.8 тем, что для него нужна операция "меньше чем", а не функция хэширования.

Приведем простую программу подсчета слов, в которой используются шаблон Map и тип String:

           #include <String.h>
           #include <iostream.h>
           #include "Map.h"

           int main()
           {
             Map<String,int> count;
             String word;

             while (cin >> word) count[word]++;

             for (Mapiter<String,int> p = count.first(); p; p++)
                 cout << p.value() << '\t' << p.key() << '\n';

             return 0;
           }

Мы используем тип String для того, чтобы не беспокоиться о выделении памяти и переполнении ее, о чем приходится помнить, используя тип char*. Итератор Mapiter нужен для выбора по порядку всех значений массива. Итерация в Mapiter задается как имитация работы с указателями. Если входной поток имеет вид

      It was new. It was singular. It was simple. It must succeed.

программа выдаст

           4         It
           1         must
           1         new.
           1         simple.
           1         singular.
           1         succeed.
           3         was.

Конечно, определить ассоциативный массив можно многими способами, а, имея определение Map и связанного с ним класса итератора, мы можем предложить много способов для их реализации. Здесь выбран тривиальный способ реализации. Используется линейный поиск, который не подходит для больших массивов. Естественно, рассчитанная на коммерческое применение реализация будет создаваться, исходя из требований быстрого поиска и компактности представления (см. упражнение 4 из $$8.9).

Мы используем список с двойной связью Link:

           template<class K, class V> class Map;
           template<class K, class V> class Mapiter;

           template<class K, class V> class Link {
             friend class Map<K,V>;
             friend class Mapiter<K,V>;
           private:
             const K key;
             V value;

             Link* pre;
             Link* suc;

             Link(const K& k, const V& v) : key(k), value(v) { }
             ~Link() { delete suc; } // рекурсивное удаление всех
                                     // объектов в списке
           };

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

Шаблон Map можно определить так:

           template<class K, class V> class Map {
              friend class Mapiter<K,V>;
              Link<K,V>* head;
              Link<K,V>* current;
              V def_val;
              K def_key;
              int sz;

              void find(const K&);
              void init() { sz = 0; head = 0; current = 0; }

           public:

              Map() { init(); }
              Map(const K& k, const V& d)
                 : def_key(k), def_val(d) { init(); }
              ~Map() { delete head; }  // рекурсивное удаление
                                       // всех объектов в списке
              Map(const Map&);
              Map& operator= (const Map&);

              V& operator[] (const K&);

              int size() const { return sz; }
              void clear() { delete head; init(); }
              void remove(const K& k);

                  // функции для итерации

              Mapiter<K,V> element(const K& k)
              {
                (void) operator[](k);  // сделать k текущим элементом
                return Mapiter<K,V>(this,current);
              }
              Mapiter<K,V> first();
              Mapiter<K,V> last();
           };

Элементы хранятся в упорядоченном списке с дойной связью. Для простоты, ничего не делается для ускорения поиска (см. упражнение 4 из $$8.9). Ключевой здесь является функция operator[]():

           template<class K, class V>
           V& Map<K,V>::operator[] (const K& k)
           {
             if (head == 0) {
                current = head = new Link<K,V>(k,def_val);
                current->pre = current->suc = 0;
                return current->value;
             }

             Link<K,V>* p = head;
             for (;;) {
               if (p->key == k) { // найдено
                    current = p;
                    return current->value;
               }

               if (k < p->key) { // вставить перед p (в начало)
                current = new Link<K,V>(k,def_val);
                current->pre = p->pre;
                current->suc = p;
                if (p == head)  // текущий элемент становится начальным
                   head = current;
                else
                   p->pre->suc = current;
                p->pre = current;
                return current->value;
               }

               Link<K,V>* s = p->suc;
               if (s == 0) {  // вставить после p (в конец)
                 current = new Link<K,V>(k,def_val);
                 current->pre = p;
                 current->suc = 0;
                 p->suc = current;
                 return current->value;
               }
               p = s;
             }
           }

Операция индексации возвращает ссылку на значение, которое соответствует заданному как параметр ключу. Если такое значение не найдено, возвращается новый элемент со стандартным значением. Это позволяет использовать операцию индексации в левой части присваивания. Стандартные значения для ключей и значений устанавливаются конструкторами Map. В операции индексации определяется значение current, используемое итераторами.

Реализация остальных функций-членов оставлена в качестве упражнения:

           template<class K, class V>
           void  Map<K,V>::remove(const K& k)
           {
              // см. упражнение 2 из $$8.10
           }

           template<class K, class V>
           Map<K,V>::Map(const Map<K,V>& m)
           {
              // копирование таблицы Map и всех ее элементов
           }

           template<class K, class V>
           Map& Map<K,V>::operator=(const Map<K,V>& m)
           {
              // копирование таблицы Map и всех ее элементов
           }

Теперь нам осталось только определить итерацию. В классе Map есть функции-члены first(), last() и element(const K&), которые возвращают итератор, установленный соответственно на первый, последний или задаваемый ключом-параметром элемент. Сделать это можно, поскольку элементы хранятся в упорядоченном по ключам виде.

Итератор Mapiter для Map определяется так:

           template<class K, class V> class Mapiter {
             friend class Map<K,V>;

             Map<K,V>* m;
             Link<K,V>* p;

             Mapiter(Map<K,V>* mm, Link<K,V>* pp)
                 { m = mm; p = pp; }
           public:
             Mapiter() { m = 0; p = 0; }
             Mapiter(Map<K,V>& mm);

             operator void*() { return p; }

             const K& key();
             V& value();

             Mapiter& operator--();  // префиксная
             void operator--(int);   // постфиксная
             Mapiter& operator++();  // префиксная
             void operator++(int);   // постфиксная
           };

После позиционирования итератора функции key() и value() из Mapiter выдают ключ и значение того элемента, на который установлен итератор.

           template<class K, class V> const K& Mapiter<K,V>::key()
           {
             if (p) return p->key; else return m->def_key;
           }

           template<class K, class V> V& Mapiter<K,V>::value()
           {
             if (p) return p->value; else return m->def_val;
           }

По аналогии с указателями определены операции ++ и -- для продвижения по элементам Map вперед и назад:

           Mapiter<K,V>& Mapiter<K,V>::operator--() //префиксный декремент
           {
             if (p) p = p->pre;
             return *this;
           }

           void Mapiter<K,V>::operator--(int)  // постфиксный декремент
           {
             if (p) p = p->pre;
           }

           Mapiter<K,V>& Mapiter<K,V>::operator++() // префиксный инкремент
           {
             if (p) p = p->suc;
             return *this;
           }

           void Mapiter<K,V>::operator++(int)   // постфиксный инкремент
           {
             if (p) p = p->suc;
           }

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

Объект Mapiter можно инициализировать так, чтобы он был установлен на начало Map:

           template<class K, class V> Mapiter<K,V>::Mapiter(Map<K,V>& mm)
           {
               m == &mm; p = m->head;
           }

Операция преобразования operator void*() возвращает нуль, если итератор не установлен на элемент Map, и ненулевое значение иначе. Значит можно проверять итератор iter, например, так:

           void f(Mapiter<const char*, Shape*>& iter)
           {
             // ...
             if (iter) {
              // установлен на элемент таблицы
             }
             else {
              // не установлен на элемент таблицы
             }

             // ...
           }

Аналогичный прием используется для контроля потоковых операций ввода-вывода в $$10.3.2.

Если итератор не установлен на элемент таблицы, его функции key() и value() возвращают ссылки на стандартные объекты.

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

           hammer       2
           nail         100
           saw          3
           saw          4
           hammer       7
           nail         1000
           nail         250

Нужно отсортировать список так, чтобы значения, соответствующие одному предмету, складывались, и напечатать получившийся список вместе с итоговым значением:

           hammer        9
           nail          1350
           saw           7
           -------------------
           total         1366

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

           template<class K, class V>
           void readlines(Map<K,V>&key)
           {
             K word;
             while (cin >> word) {
               V val  = 0;
               if (cin >> val)
                  key[word] +=val;
               else
                  return;
             }
           }

Теперь можно написать простую программу, вызывающую функцию readlines() и печатающую получившуюся таблицу:

           main()
           {
             Map<String,int> tbl("nil",0);
             readlines(tbl);

             int total = 0;
             for (Mapiter<String,int> p(tbl); p; ++p) {
                 int val = p.value();
                 total +=val;
                 cout << p.key() << '\t' << val << '\n';
             }

             cout << "--------------------\n";
             cout << "total\t" << total << '\n';
           }

Назад  |  Вперёд


OtDiatlovaOU
К началу книги

Оформление и дизайн книги OtDiatlovaOU.
Вся книга, архив.

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

Rambler's Top100
Hosted by uCoz