Table of Contents
Приложение А: Стандартная библиотека шаблонов C++
Стандартная Библиотека Шаблонов (STL) - широко используемая библиотека C++ от Silicon Graphics (www.sgi.com). В данном Приложении представлен краткий обзор ключевых частей, которые используются всюду в программе Greenstone. Для ознаклмления с более полным описанием ознакомьтесь с официальным справочным описанием STL, доступным в режиме on-line на сайте www.sgi.com, или с одним из многих STL-учебников, например Josuttis (1999).
Как предполагает слово "шаблон", STL - не только библиотека объектных модулей plug-and-use (подключай-и-используй). Вместе с механизмом шаблонов в C++, обеспечивается форум для программистов, чтобы разрабатывать их собственные объекты, которые используют алгоритмические возможности, реализованные в пределах STL. В результате добавляется дополнительный уровень сложности, но это стоит того.
Помочь понять прграмму Greenstone вам помогут подборки, представленные в этом руководстве, которые мы снабдили нескольким примерам обучающего уровня по использованию STL.
Списки (Lists)
<imgcaption figure_programming_a_list_of_integers|%!– id:1214 –%Программирование списка целых чисел %!– withLineNumber –%></imgcaption>
#include <iostream.h>
#define nil 0
struct intlist {
int val;
struct intlist* next;
};
int total_int_list(intlist* head)
{
int total = 0;
intlist* curr = head;
while (curr!=nil)
{
total += curr->val;
curr = curr->next;
}
return total;
}
void main()
{
intlist node1 = { 5, nil };
intlist node2 = { 4, nil };
node2.next = &node1;
int total = total_int_list(&node2);
cout << " List items total to: " << total << endl;
}
Сначала мы изучим две программы, которые реализуют целочисленный список. Превоначально используйте основные типы C++ (путь "по проторенной дорожке"), далее используйте STL. Рисунок <imgref figure_programming_a_list_of_integers> показывает выполнение исходной программы, которое не использует STL. Строки 5-8 определяют основную структуру данных, которую мы собираемся использовать: поле val сохраняет целочисленное значение, a next указывает на следующий элемент в списке - классическое воплощение списка связей.
Чтобы продемонстрировать использование структуры данных, основная программа (строки 23-32), устанавливает целочисленный список с элементами [5, 4]. Тогда вызывается функция total_int_list (определенная в строках 10-21), которая в качестве ее единственного параметра берет указатель на вершину списка и суммирует значения в нем. Возвращенный ответ (в нашем примере 9) выводится на экран.
Основная работа достигается строками 12-18. Сначала производится небольшая инициализация: локальная переменная total установливает nil и сигг, чтобы указать на начало списка. Тогда цикл с условием добавляет текущий целочисленный элемент в список для общего выполнения (total += curr. >val;) перед переходом к следующему элементу (curr = curr. >next;). Цикл с условием заканчивается, когда curr становится равным nil, показывая, что элементов для обработки больше не осталось.
<imgcaption figure_programming_a_list_of_integers_using_stl|%!– id:1218 –%Программирование списка целых чисел с использованием STL ></imgcaption>
#include <iostream.h>
#include <list>
int total_int_list(list<int>* head)
{
int total = 0;
list<int>::iterator curr = head->begin();
while (curr!=head->end())
{
total += *curr;
curr++;
}
return total;
}
void main()
{
list<int> vals;
vals.push_back(5);
vals.push_back(4);
int total = total_int_list(&vals);
cout << " List items total to: " << total << endl;
}
Рисунок <imgref figure_programming_a_list_of_integers_using_stl> показывает эквивалентную программу, созданную с использованием STL. Больше нет необходимости определять подходящую структуру данных в программе; все, что является необходимым - это ffinclude <list> указание в строке 2, которое включает версию шаблона для списка, определенного в STL. Объект называют "класс-контейнер", потому что, когда мы объявляем переменную этого типа, мы также определяем тип, в котором мы хотим ее сохранить. В строке 19 целочисленный список реализован с использованием оператора list<int> vals;. Элементы можно добавить к объекту, используя функцию-член push_back(), как это сделано в строках 20-21.
Основная работа выполнена строками 6-12. Есть все еще две инициализации и цикл с условием, но отличающийся от представленного в предыдущем случае. Новый синтаксис имеет немного общего со старым. Ключевым моментом этого нового способа обработки является переменная типа iterator (строка 7). В STL много классов включают типы iterator, чтобы обеспечить однородный способ работы через последовательность контейнерных объектов. Первый элемент возвращен с begin(), и только один - последний элемент с end(). Перемещение к следующему элементу достигнуто операцией приращения ++, которая перегружена классом iterator, чтобы осуществить эту задачу, и к значению, сохраненному там, обращаются через разыменование (*сигг на строке 10), который также является перегруженным.
STL-реализация этой программы немного меньше, чем обычная программа (25 строк против 31). Это достижение наиболее важно для больших проектов, потому что объект list STL более мощный, чем иллюстрируемый нами пример. Возьмем к примеру, двойной связанный список, который поддерживает несколько форм вставки и удаления - кое-что, что требовало бы дополнительных усилий по программированию дополений к основной целочисленной версии списка.
Обратите внимание, что параметр для total_int_list на рисунке <imgref figure_programming_a_list_of_integers_using_stl> был реализован как указатель, соответствовавший указателю, используемому в total_int_list на рисунке <imgref figure_programming_a_list_of_integers>. В STL зачастую более естественно (и более желательно) использовать ссылки, а не указатели. Тогда параметр становится list<int>& head, и его функции-члены вызываются синтаксисом head, begin 0; и так далее.
Maps
При реализации системы цифровой библиотки, полезно иметь возможность сохранения элементов в массиве, индексированном текстовыми строками, а не числовыми индексами. В Greenstone, например, это очень упрощает сохранение макрофайлов, как только они считались, и различных файлов конфигурации. Тип данных, который поддерживает такой доступ, называют associative array (ассоциативным массивом), и он часто встраивается в современные языки высокого уровня. Он также известен под именем hash array (особенно в Perl), так как хеширование - нормальная методика, по обыкновению реализующая текстовый индекс.
<imgcaption figure_using_associative_arrays_in_stl|%!– id:1225 –%Использование ассоциативных массивов в STL %!– withLineNumber –%></imgcaption>
#include <iostream.h>
#include <map>
int total_int_table(map<char*, int>& table)
{
int total = 0;
map<char*, int>::iterator curr = table.begin();
while (curr!=table.end())
{
total += (curr->second);
curr++;
}
return total;
}
int main()
{
map<char*, int> table;
table["Alice"] = 31;
table["Peter"] = 24;
table["Mary"] = 47;
int total = total_int_table(table);
cout << " Age total: " << total << endl;
}
В STL ассоциативные массивы достигаются использованием объекта тар. Рисунок <imgref figure_using_associative_arrays_in_stl> показывает придуманный пример, в котором возраст трех человек (Алиса, Питер и Мэри) хранится в ассоциативном массиве под их собственными именами (строки 19-22). Проблема состоит в том, чтобы записать функцию, которая вычисляет полный возраст людей, не зная, сколько их имеется или каковы их имена. Конечно, это могло бы быть решено с использованием стандартных числовых массивов целых чисел. Данный пример был придуман, чтобы продемонстрировать, что особенности тар производят подобие обработки с объектом list совместно с iterator.
Подобно list, map относится к классу-контейнеру. Однако, при объявлении переменной этого типа мы должны определить две1) вещи: индексный тип, и тип элемента. Как вы могли заметить в строке 19, мы получаем ассоциативный массив, который сохраняет целые числа, используя char* (который является строкой, объявленной в C++) как индексный тип, сопровождаемый int в качестве типа элемента.
Есть несколько способов сохранить элементы в ассоциативном массиве. В данном примере в строках 20-22 перегруженный массив описывается, используя [], чтобы инициализировать таблицу с возрастами этих трех человек. Подобно total_int_table, который исполняет основное вычисление в программе, на рисунке <imgref figure_programming_a_list_of_integers> используется total_int_list Фактически, они почти идентичны, и это не никакое совпадение. STL трудно использовать наследование так, чтобы различные объекты все еще использовали те же самые фундаментальные операции. Это особенно точно в отношении итераторов. Небольшие различия между двумя функциями состоят в том, что итератор теперь получен из map<char*, int> и доступ к его элементам происходит совместно с curr .>second(), потому что разыменование переменной (*сигг) определено, чтобы возвратить объект типаршг. Он создает запись и индексного имени (first), и значения элемента (second), но мы хотим иметь только последнее. Кроме этого, программа остается тойже самой. Единственное остающееся отличие - это изменение единственного аргумента функции с указателя на ссылку - является незначительным.
Два других типа STL, широко используемые в программе Greenstone - это vector и set. Первый облегчает поддержание динамических массивов, а последний поддерживает математические операции установки типа объединения, пересечения и различия.