Бьерн Страуструп (947334), страница 48
Текст из файла (страница 48)
int[] в short[].
Аналогичный пример:
class circle: public shape { /* ... */ };
Vector<circle*> v4;
Vector<shape*> v5;
Vector<circle*> v6;
Здесь v4 и v6 одного типа, а v5 имеет совершенно другой тип. Из того
факта, что существует неявное преобразование circle в shape и
circle* в shape*, не следует, что есть неявные преобразования
Vector<circle*> в Vector<shape*> или Vector<circle*>* в
Vector<shape*>* :
v5 = v6; // несоответствие типов
Дело в том, что в общем случае структура (представление) класса,
созданного по шаблону типа, такова, что для нее не предполагаются
отношения наследования. Так, созданный по шаблону класс может
содержать объект типа, заданного в шаблоне как параметр, а не просто
указатель на него. Кроме того, допущение подобных преобразований
приводит к нарушению контроля типов:
void f(Vector<circle>* pc)
{
Vector<shape>* ps = pc; // ошибка: несоответствие типов
(*ps)[2] = new square; // круглую ножку суем в квадратное
// отверстие (память выделена для
// square, а используется для circle
}
На примерах шаблонов Islist, Tlink, Slist, Splist, Islist_iter,
Slist_iter и SortableVector мы видели, что шаблоны типа дают
удобное средство для создания целых семейств классов. Без шаблонов
создание таких семейств только с помощью производных классов
может быть утомительным занятием, а значит, ведущим к ошибкам.
С другой стороны, если отказаться от производных классов и использовать
только шаблоны, то появляется множество копий функций-членов шаблонных
классов, множество копий описательной части шаблонных классов и во
множестве повторяются функции, использующие шаблоны типа.
8.7.1 Задание реализации с помощью параметров шаблона
В контейнерных классах часто приходится выделять память. Иногда
бывает необходимо (или просто удобно) дать пользователю возможность
выбирать из нескольких вариантов выделения памяти, а также позволить
ему задавать свой вариант. Это можно сделать несколькими способами.
Один из способов состоит в том, что определяется шаблон типа для
создания нового класса, в интерфейс которого входит описание
соответствующего контейнера и класса, производящего выделение памяти
по способу, описанному в $$6.7.2:
template<class T, class A> class Controlled_container
: public Container<T>, private A {
// ...
void some_function()
{
// ...
T* p = new(A::operator new(sizeof(T))) T;
// ...
}
// ...
};
Шаблон типа здесь необходим, поскольку мы создаем контейнерный класс.
Наследование от Container<T> нужно, чтобы класс Controlled_container
можно было использовать как контейнерный класс. Шаблон типа с
параметром A позволит нам использовать различные функции размещения:
class Shared : public Arena { /* ... */ };
class Fast_allocator { /* ... */ };
Controlled_container<Process_descriptor,Shared> ptbl;
Controlled_container<Node,Fast_allocator> tree;
Controlled_container<Personell_record,Persistent> payroll;
Это универсальный способ предоставлять производным классам
содержательную информацию о реализации. Его положительными качествами
являются систематичность и возможность использовать функции-подстановки.
Для этого способа характерны необычно длинные имена. Впрочем, как
обычно, typedef позволяет задать синонимы для слишком длинных имен
типов:
typedef
Controlled_container<Personell_record,Persistent> pp_record;
pp_record payroll;
Обычно шаблон типа для создания такого класса как pp_record используют
только в том случае, когда добавляемая информация по реализации
достаточно существенна, чтобы не вносить ее в производный класс ручным
программированием. Примером такого шаблона может быть общий
(возможно, для некоторых библиотек стандартный) шаблонный класс
Comparator ($$8.4.2), а также нетривиальные (возможно, стандартные
для некоторых библиотек) классы Allocator (классы для выделения памяти).
Отметим, что построение производных классов в таких примерах
идет по "основному проспекту", который определяет интерфейс с
пользователем (в нашем примере это Container). Но есть и "боковые
улицы", задающие детали реализации.
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;
}
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
