Теллес М. - Borland C++ Builder. Библиотека программиста - 1998

Borland C++ Builder (+CD). Библиотека программиста 121

генерации стандартизованных заголовков в своих файлах, к примеру. Во втором файле у вас должен быть текст, например:

The author of this program:

$$Author$$ and it was written on $$Date$$

Тогда после запуска программы замены вывод будет выглядеть так:

The author of this program:

Matt Telles and it was written on Today.

Вот и все, что можно сказать о векторах (vector). Как почти все в STL, они очень просты в использовании и работа с ними интуитивно понятна. Вспомните о векторах, когда будете писать какие-нибудь классы или компоненты в CBuilder, которым будет нужен массив неопределенного (или впоследствии изменяемого) размера.

Работа со связными списками

Следующий важный компонент STL, который мы собираемся рассмотреть — класс list (список). Это тот самый всем знакомый односвязный список, который каждый из программистов или его брат, или сестра должны были написать для начального курса программирования. Основная идея списка в том, что у вас есть стартовая точка (обычно называемая головой, head, списка) и затем серия элементов в списке (называются вершинами, nodes, списка). Каждое элемент содержит указатель на следующий элемент, так что по списку можно легко перемещаться в одном направлении.

Версия класса list в STL довольно богата в своей реализации. Она предлагает возможность добавлять элементы в конец списка, в начало списка, и даже вставлять элементы в середину связанного списка. Если вы собираетесь создать структуру данных, которой требуется вставка элементов в середину уже существующих, то используйте list, а не vector. Вектора требуют, чтобы элементы хранились в одном блоке, каждый следующий сразу за предыдущим в памяти. В списке же элементы указывают друг на друга, а не содержатся в соседних адресах памяти. Так что вставка в список — несложная операция. Добавление в конец и начало списка являются тоже довольно быстрыми операциями.

В общем вам нужно знать, как добавлять элементы в список и как получить и обратно. Для того, чтобы положить что-нибудь в список, вы используете метод insert (вставить). Это то же метод, что мы видели в классе vector, и используете вы его точно так же. Например, для создания нового списка, содержащего целые числа, мы могли бы написать:

list<int, allocator<int> > intList;

Тип элементов в списке будет int (от англ. integer, целый). Аргумент allocator<int> в конструкторе списка добавляет классу list гибкости, позволяя ему выделять память под новые целые числа динамически. STL предоставляет класс allocator для создания новых элементов данного типа, но вы можете, если хотите, предоставлять свою собственную схему выделения памяти. Обычно же вы будете просто использовать шаблонную ссылку на класс allocator. Замечание о классах типа allocator: класс allocator требует, чтобы ваш объект мог быть создан вызовом конструктора без параметров. Это значит, что для класса Foo вам нужно иметь описание примерно в таком виде:

class Foo

Borland C++ Builder (+CD). Библиотека программиста 122

{

public: Foo(int x); Foo(void);

}

Если у вас не будет такого конструктора (void constructor, как они называются), то компилятор пожалуется на какие-то загадочные выражения в заголовочном файле класса list и ваше приложение не скомпилируется. Если такое происходит, добавьте конструктор без параметров. Кроме того, если ваш класс требует особой работы с копиями, то не забудьте написать конструктор для копий:

Foo(const Foo& aFoo);

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

В любом случае для добавления нового элемента в список вам нужно использовать метод insert:

intList.insert (intList.begin(), 12 );

Это выражение поместит значение 12 в начало списка, пропихав все остальные элементы списка на один назад в иерархии списка. Точно также, следующее выражение

intList.insert (intList.end(), 12 );

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

intlist.insert (intList.begin(), 11);

intlist.insert (intList.begin(), 12);

intlist.insert (intList.begin(), 13);

то получаете список, содержащий значения: 13, 12, 11 (именно в этом порядке). Вместе со всем этим, давайте посмотрим на некоторые доступные методы класса list, а также разберемся, что они делают. В табл. 5.3 перечислены самые важные методы класса list и приведено описание того, что каждый из них делает.

Таблица 5.3 Важные метода класса list

insert

Вставляет новый элемент в данную позицию в списке push_back

Обычно используемый метод, эквивалентный вставке в конец списка push_front

Обычно используемый метод, эквивалентный вставке в начало списка

Borland C++ Builder (+CD). Библиотека программиста 123

splice

Один из способов вставить один список (или его часть) в другой список swap

Обменивает данные между списками эффективным образом remove

Этот метод удаляет из списка все элементы, подходящие под заданное значение remove_if

Этот метод удаляет из списка все элементы c данным значением, подходящие под заданный

предикат erase

Этот метод удаляет данный элемент в списке unique

Эта вспомогательная операция удалит из списка все элементы, кроме одного для каждого

значения size

Возвращает количество элементов в списке empty

Указывает, есть ли (FALSE) или нет (TRUE) элементов в списке resize

Заставляет список иметь заданное количество элементов front

Возвращает первый элемент в списке back

Возвращает последний элемент в списке sort

Сортирует список в возрастающем порядке. Может использоваться с функцией сравнения

элементов или использовать порядок сортировки по умолчанию find

Возвращает позицию первого элемента, удовлетворяющего заданному критерию reverse

Это метод изменит порядок в списке на противоположный, делая первый элемент последним, а последний — первым и аналогично переставляя все остальные элементы

for_each

Этот метод применит заданную функцию ко всем элементам списка

Предыдущие функции могут быть использованы в любом списке. Они предоставляют мощный набор операций, который позволяет вам делать практически все, что вам может понадобиться сделать с любым данным списком. Давайте посмотрим на полный пример того, как использовать списки. Создайте еще одно консольное приложение в CBuidler и добавьте этот код в файл project.cpp:

#include <stdio.h> #include <string.h> #include <stdlib.h> #include <list> #include <string> using namespace std; int main(void)

{

list<string, allocator<string> > listStrings; listStrings.insert (listStrings.end(), "Первый" ); listStrings.insert (listStrings.end(), "Второй" ); listStrings.insert (listStrings.end(), "Третий" );

Borland C++ Builder (+CD). Библиотека программиста 124

listStrings.insert (listStrings.end(), "Четвертый" ); listStrings.insert (listStrings.end(), "Пятый" ); listStrings.insert (listStrings.end(), "Шестой" );

list<string, allocator<string> >::iterator list_iterator; list_iterator = listStrings.begin();

while (list_iterator != listStrings.end() )

{

printf("Строка = <%s>\n", (*list_iterator).c_str()); // advance (list_iterator, 1);

list_iterator++;

}

return 0;

}

Этот простой пример показывает несколько важных особенностей в использовании списка. Во- первых, вы могли заметить, что сразу за включением заголовочных файлов находится строка:

using namespace std;

Эта строка важна при компиляции приложений с STL в CBuilder. В системе CBuilder компания Borland решила все третьесторонние (third-party) библиотеки (такие, как STL) завернуть в «обложку» namespace (именованной области видимости). Это для вас хорошо, так как означает, что библиотеки, которые вы используете в своих приложениях, не будут конфликтовать с другими библиотеками, для которых у вас может не быть исходного кода.

Namespace — это просто более высокий уровень области видимости ( scope). Например, в следующей простой программе есть три элемента, названные foo:

class MyFoo

{

int foo; // 1 public: MyFoo();

}

int foo; // 2

int main()

{

int foo = 2; // 3

}

int func()

{

foo = 3;

}

MyFoo::MyFoo()

{

foo = 4;

}

Borland C++ Builder (+CD). Библиотека программиста 125

В зависимости от того, где в программе вы находитесь, имя foo означает что-то совершенно разное. Внутри функции main имя foo означает локальную переменную foo. Вне функции main, внутри другой функции func имя foo означает переменную foo на уровне файла (помеченную комментарием // 2). И наконец, в методе класса переменная — член класса (member variable) foo берет верх, которая помечена комментарием // 1 и обращение к ней идет в методе класса MyFoo (в конструкторе).

Namespace очень похожа на обычную область видимости, но она позволяет заключать в себя только выделенные части программы. В случае STL компания Borland решила поместить функции в область namespace std. Для доступа к членам этой области std вы используете стандартный оператор видимости «::» (scoping operator). Например, для использования класса list, определенного в namespace std, мы могли бы написать:

std::list< int, std::allocator<int> > intList;

Фактически, этот код будет компилироваться, запускаться и отлично работать в среде CBuilder. Иначе, если вы не любите использовать оператор видимости std:: всюду, где вы ссылаетесь на один из классов STL, то вы можете использовать другой метод, который говорит компилятору, что вы непосредственно обращаетесь к вещам в области namespace std. Это делается выражением using namespace <name>, которое говорит компилятору смотреть все неопознанные лексемы в области namespace <name>. Проблема с таким подходом в том, что убирается возможность держать посторонние библиотеки раздельно. Если бы у меня была другая область namespace, которая содержала бы класс list и я хотел бы использовать их обоих, то мне все-таки пришлось бы полностью задавать имена классов из второй области namespace. Короче говоря, области видимости namespace — хорошая идея, которая тем не менее может привести к некоторой работе со стороны программиста.

Итератор

Вторая важная часть этого примера программы — использование класса iterator (итератор). В

строчках кода

list<string, allocator<string> >::iterator list_iterator;

list_iterator = listStrings.begin();

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

list<string, allocator<string> >::

iterator forward_list_iterator; list<string, allocator<string> >::

iterator backward_list_iterator; forward_list_iterator = listStrings.begin(); backward_list_iterator = listStrings.end();

Для работы с итераторами вы можете использовать операторы ++ и —- для движения вперед и назад. Итераторы двигаются последовательно, так что нет прямого пути для движения из точки A в точку C, если на пути лежит точка B. Итераторы важны, так как они предоставляют способ манипулировать данными в списке (или другой структуре данных) без непосредственной работы

Borland C++ Builder (+CD). Библиотека программиста 126

со структурой данных. Поэтому вы можете использовать итератор всюду, где хотите, даже не зная в действительности каким образом реализована внутренняя структура данных. Итераторы могут быть разных типов. Одни двигаются только вперед, другие только назад. Некоторые могут быть использованы только для чтения, в то время как другие — для изменения данных, с которыми они работают. В любом случае, однако, оператор ++ будет проходить по данным, двигаясь от первого элемента к последнему. Оператор —-будет двигаться назад по структуре данных, от последнего элемента к первому. Когда итератор «указывает» на текущий элемент данных, как в предыдущем примере с forward_list_iterator, то вы можете получить внутренний тип данных (в данном случае строка), используя оператор «*». Например:

forward_list_iterator = listStrings.begin();

string s = (*forward_list_iterator);

Если предположить, что в списке были элементы, то строка s будет иметь такое же значение, что и первая строка в списке. Так как оператор * возвращает сам объект, то вы можете напрямую работать с элементом списка, манипулируя объектом iterator:

(*iterator).c_str()

Если итератор указывает на элемент-строку в списке, то этот код возвратит указатель на символ (char *), который представляет строку в данной позиции списка. Так что в нашем предыдущем примере итератор проходит по всем элементам списка, передавая символьный указатель, представляющий элемент, в функцию printf, которая затем печатает значение в стандартный вывод. Результат вывода этой программы должен быть таков:

Первый

Второй

Третий

Четвертый

Пятый

Шестой

Для проверки этой теории скомпилируйте программу, выбрав Build|Make в среде CBuilder. Откройте окно команд MS-DOS и запустите программу, набрав project1. Вы должны увидеть вывод, появляющийся в окне, и он должен выглядеть точно также, как мы только что показали в листинге.

Вот более-менее все, что можно сказать о списках и итераторах списков. Когда вам нужен список в вашем приложении, просто добавьте его в класс и вперед. Списки, наверное, лучше всего подходят для приложений, содержащих переменное количество данных, которые в основном

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

Работа с таблицами

Следующая вещь, с которой мы познакомимся в процессе разговора о STL — таблицы (или карты, maps). <Следующее высказывание построено на том, что по-английски этот класс STL называется map, то есть карта. В переводе же этот термин переводчик счел нужным заменить на таблицу. — Прим. пер.> Карты — это классно. Они говорят вам, как добраться из Нью-Йорка в Колорадо самым коротким путем, а также где эта замечательная дорога уходит с хайвея. Они не дадут вам потеряться и помогут попасть туда, куда вы едете.

Borland C++ Builder (+CD). Библиотека программиста 127

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

В табл. 5.4 приведены важные методы класса map (таблица) в STL.

Таблица 5.4 Важные методы класса map

empty

Указывает, есть ли (FALSE) или нет (TRUE) элементы в таблице count

Возвращает количество элементов, находящихся в данный момент в таблице insert

Добавляет новый элемент в таблицу erase

Удаляет существующий элемент из таблицы find

Выполняет поиск по данному ключу в таблице operator[]

Находит элемент в таблице, соответствующий ключевому значению lower_bound

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

ключевому значению max_size

Возвращает максимальный возможный размер таблицы (обычно это максимальный объем памяти, свободной для выделения)

rbegin

Возвращает последний элемент в таблице (начиная с конца) rend

Возвращает первый элемент в таблице (начиная с конца) size

Возвращает выделенный размер таблицы, обычно это количество элементов в таблице swap

Меняет данные между двумя таблицами upper_bound

Возвращает последний элемент, подходящий под данное ключевое значение operator=

Присваивает одной таблице другую, копируя все данные из первой таблицы во вторую operator<<

Потоковый оператор, который позволяет выводить элемент таблицы в выходной поток begin

Возвращает первый элемент в таблице end

Возвращает последний элемент в таблице key_comp

Сравнивает два элемента, используя функцию сравнения таблицы for_each

Производит заданное действие над всеми элементами в таблице

Вот пример применения этого класса:

Borland C++ Builder (+CD). Библиотека программиста 128

#include <stdio.h> #include <stdlib.h> #include <string.h> #include <string> #include <map>

int main(void)

{

map<string, string, less<string>, allocator<string> > stringMap;

stringMap["Kirk"] = "William Shatner"; stringMap["McCoy"] = "DeForest Kelley"; stringMap["Spock"] = "Leonard Nimoy"; stringMap["Scotty"] = "James Doohan"; stringMap["Sulu"] = "George Takei"; stringMap["Uhura"] = "Nichelle Nichols";

printf("Введите персонажа: "); char szBuffer[20]; gets(szBuffer);

if (stringMap[szBuffer].length() )

printf("На самом деле это: %s\n", stringMap[szBuffer].c_str()); else

printf("Я не знаю такого персонажа!\n"); return 0;

}

В этом примере мы инициализируем объект map, используя строку как ключевое значение. Ключевое значение в этом примере — фамилия (а в случае персонажа Spock, еще и имя) персонажа в оригинальных сериях Star Trek (а вдруг вы их не узнали?), а значение, присваиваемое каждому ключу — имя актера, который играл этого персонажа в фильме. Потом мы запрашиваем у пользователя имя персонажа и печатаем имя актера. Если имя персонажа не найдено, то возращенная строка будет пустой. Мы рассматриваем это как условие ошибки и говорим пользователю, что такого персонажа не найдено.

Этот пример показывает несколько интересных аспектов объекта map. Во-первых, вы действительно относитесь к map как к массиву, с потенциально нецелыми индексами. В этом случае мы используем строку как индекс. Вторая вещь, которая быстро становится ясной, состоит в том, что вы можете иметь только один элемент на каждое ключевое значение в таблице, иначе вы не смогли бы определить, какой из элементов относится к данному индексу массива. Представьте себе использование массива целых и получение двух ответов на выражение array[0].

Таблицы содержат упорядоченные пары данных. Упорядочивая их, мы можем выстроить их по алфавиту, например для печати. Кроме того, мы можем относиться к таблице как к словарю, получая определения «слов».

Зачем нужны таблицы?

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

Borland C++ Builder (+CD). Библиотека программиста 129

значениями — заменяющими строками. Так как таблицы упорядочены, то поиск в таблице заданного ключа работает очень быстро. Это делает таблицы замечательным выбором для простых структур, в которых требуется быстрый поиск данных. Макропроцессоры, словари, календари (расписания) событий могут выиграть от структуры и скорости таблиц.

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

Всемогущее множество

Следующий класс, который мы собираемся исследовать в нашем обзоре STL — класс set (множество). Этот класс представляет собой реализацию математического понятия множества. Множество содержит одиночные элементы данного вида; в нем не может быть двух и более элементов с одинаковыми значениями. Для использования этого класса вам нужно подключить в проект заголовочный файл <set>:

#include <set>

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

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

Давайте посмотрим на методы, имеющиеся в классе set, а затем поговорим об их использовании. В табл. 5.5 приведены основные методы класса set в STL.

Таблица 5.5 Важные методы класса set begin

Возвращает начальную позицию множества (первый элемент) end

Возвращает последнюю позицию множества (последний элемент) count

Возвращает количество элементов в множестве, подходящих под заданный критерий empty

Указывает, есть (TRUE) или нет (FALSE) элементов в множестве insert

Borland C++ Builder (+CD). Библиотека программиста 130

Добавить элемент в множество, если это возможно. Если такой элемент уже есть, то новый

добавлен не будет erase

Удаляет элемент из множества, если он там есть. Если такого элемента нет, то с множеством

ничего не происходит size

Возвращает количество элементов в множестве find

Возвращает первый же элемент, подходящий под заданный критерий или пустой элемент (NULL),

если такого элемента нет lower_bound

Для обычных множеств то же, что и find. Для мультимножеств возвращает первое вхождение,

подходящее под заданный критерий upper_bound

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

rbegin

Возвращает последний элемент rend

Возвращает первый элемент includes

Проверяет, не является ли множество подмножеством другого set_union

Возвращает объединение двух множеств set_intersection

Возвращает пересечение двух множеств set_difference

Возвращает разность двух множеств (элементы одного множества, не присутствующие в другом) accumulate

Урезает множество до одного значения count_if

Возвращает количество элементов, удовлетворяющих заданному условию swap

Обменивает элементы (сразу все) между множествами operator=

Копирует элементы из одного множества в другое (делает точную копию)

Вот пример использования множества. В данном примере мы получаем от пользователя значения (строки) и пытаемся добавить их в множество. Если значение не добавляется, мы выводим сообщение об ошибке и продолжаем работу. Процесс повторяется, пока пользователь не введет специальное значение (DONE), которое означает, что ввод данных завершен. Тогда мы выводим список значений, которые были добавлены в множество. Для создания этой программы выберите в CBuilder новый проект консольного приложения и введите следующий код в исходный файл

(project1.cpp):

#include <stdio.h> #include <string.h> #include <stdlib.h> #include <set> #include <string>

int main(void)

{