Бьерн Страуструп. Язык программирования С++ Второе дополненное издание



Pdf көрінісі
бет165/256
Дата11.07.2022
өлшемі2,87 Mb.
#37591
1   ...   161   162   163   164   165   166   167   168   ...   256
Байланысты:
Бьерн Страуструп. Язык программирования С . М Бином, 2011

8.8 Ассоциативный массив 
Из всех универсальных невстроенных типов самым полезным, по всей видимости, является 
ассоциативный массив. Его часто называют таблицей (map), а иногда словарем, и он хранит пары 
значений. Имея одно из значений, называемое ключом, можно получить доступ к другому, называемому 
просто значением. Ассоциативный массив можно представлять как массив, в котором индекс не обязан 
быть целым: 
template class Map { 
// 
... 
public: 
V& 
operator[](const 
K&); 
// 
найти V, соответствующее K 


Бьерн Страуструп.
Язык программирования С++ 
 
226 
// и вернуть ссылку на него 
// 
... 
}; 
Здесь ключ типа K обозначает значение типа V. Предполагается, что ключи можно сравнивать с 
помощью операций == и <, так что массив можно хранить в упорядоченном виде. Отметим, что класс 
Map отличается от типа assoc из $$7.8 тем, что для него нужна операция "меньше чем", а не функция 
хэширования. 
Приведем простую программу подсчета слов, в которой используются шаблон Map и тип String: 
#include  
#include  
#include "Map.h" 
int main() 

Map 
count; 
String 
word; 
while (cin >> word) count[word]++; 
for (Mapiter 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 Map; 
template class Mapiter; 
template class Link { 
friend class Map
friend class Mapiter
private: 
const 

key; 

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


Бьерн Страуструп.
Язык программирования С++ 
 
227 
// объектов в списке 
}; 
Каждый объект Link содержит пару (ключ, значение). Классы описаны в Link как друзья, и это 
гарантирует, что объекты Link можно создавать, работать с ними и уничтожать только с помощью 
соответствующих классов итератора и Map. Обратите внимание на предварительные описания 
шаблонных классов Map и Mapiter. 
Шаблон Map можно определить так: 
template class Map { 
friend class Mapiter
Link
head; 
Link
current; 

def_val; 

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 element(const K& k) 

(void) operator[](k); // 
сделать k текущим элементом 
return 
Mapiter(this,current); 

Mapiter 
first(); 
Mapiter 
last(); 
}; 
Элементы хранятся в упорядоченном списке с дойной связью. Для простоты ничего не делается для 
ускорения поиска (см. упражнение 4 из $$8.9). Ключевой здесь является функция operator[](): 
template 
V& Map::operator[] (const K& k) 

if (head == 0) { 
current = head = new Link(k,def_val); 
current->pre = current->suc = 0; 
return 
current->value; 

Link* p = head; 
for (;;) { 
if (p->key == k) { // 
найдено 
current 

p; 
return 
current->value; 

if (k < p-
>key) { // вставить перед p (в начало) 
current 

new 
Link(k,def_val); 


Бьерн Страуструп.
Язык программирования С++ 
 
228 
current->pre 

p->pre; 
current->suc 

p; 
if (p == head) // текущий элемент становится начальным 
head 

current; 
else 
p->pre->suc 

current; 
p->pre 

current; 
return 
current->value; 

Link* s = p->suc; 
if (s == 0) { // вставить после p (в конец) 
current 

new 
Link(k,def_val); 
current->pre 

p; 
current->suc 

0; 
p->suc 

current; 
return 
current->value; 



s; 


Операция индексации возвращает ссылку на значение, которое соответствует заданному как параметр 
ключу. Если такое значение не найдено, возвращается новый элемент со стандартным значением. Это 
позволяет использовать операцию индексации в левой части присваивания. Стандартные значения для 
ключей и значений устанавливаются конструкторами Map. В операции индексации определяется 
значение current, используемое итераторами. 
Реализация остальных функций-членов оставлена в качестве упражнения: 
template 
void Map::remove(const K& k) 

// см. упражнение 2 из $$8.10 

template 
Map::Map(const Map& m) 

// копирование таблицы Map и всех ее элементов 

template 
Map& Map::operator=(const Map& m) 

// копирование таблицы Map и всех ее элементов 

Теперь нам осталось только определить итерацию. В классе Map есть функции-члены first(), last() и 
element(const K&), которые возвращают итератор, установленный соответственно на первый, последний 
или задаваемый ключом-параметром элемент. Сделать это можно, поскольку элементы хранятся в 
упорядоченном по ключам виде. Итератор Mapiter для Map определяется так: 
template class Mapiter { 
friend class Map
Map
m; 
Link
p; 
Mapiter(Map* mm, Link* pp) 
{ m = mm; p = pp; } 
public: 
Mapiter() { m = 0; p = 0; } 
Mapiter(Map
mm); 


Бьерн Страуструп.
Язык программирования С++ 
 
229 
operator void*() { return p; } 
const 
K& 
key(); 
V& 
value(); 
Mapiter& 
operator--(); 
// 
префиксная 
void 
operator--(int); 
// 
постфиксная 
Mapiter& 
operator++(); 
// 
префиксная 
void 
operator++(int); 
// 
постфиксная 
}; 
После позиционирования итератора функции key() и value() из Mapiter выдают ключ и значение того 
элемента, на который установлен итератор. 
template const K& Mapiter::key() 

if (p) return p->key; else return m->def_key; 

template V& Mapiter::value() 

if (p) return p->value; else return m->def_val; 

По аналогии с указателями определены операции ++ и -- для продвижения по элементам Map вперед и 
назад: 
Mapiter& Mapiter::operator--() //
префиксный декремент 

if (p) p = p->pre; 
return 
*this; 

void Mapiter::operator--(int) // 
постфиксный декремент 

if (p) p = p->pre; 

Mapiter& Mapiter::operator++() // 
префиксный инкремент 

if (p) p = p->suc; 
return 
*this; 

void Mapiter::operator++(int) // 
постфиксный инкремент 

if (p) p = p->suc; 

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

m == &mm; p = m->head; 

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



Бьерн Страуструп.
Язык программирования С++ 
 
230 
// 
... 
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 
void readlines(Map&key) 


word; 
while (cin >> word) { 
V val = 0; 
if (cin >> val) 
key[word] 
+=val; 
else 
return; 


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

Map 
tbl("nil",0); 
readlines(tbl); 
int total = 0; 
for (Mapiter p(tbl); p; ++p) { 
int val = p.value(); 
total +=val; 


Бьерн Страуструп.
Язык программирования С++ 
 
231 
cout << p.key() << '\t' << val << '\n'; 

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



Достарыңызбен бөлісу:
1   ...   161   162   163   164   165   166   167   168   ...   256




©emirsaba.org 2024
әкімшілігінің қараңыз

    Басты бет