ПРОГРАММИРОВАНИЕ НА VISUAL C++

Выпуск No. 37 от 18 марта 2001 г.

Приветствую, уважаемые подписчики!

Сегодня нас ждет новая статья нашего постоянного автора Александра Шаргина, на этот раз посвященная стандартной библиотеке шаблонов C++.

/ / / / СТАТЬЯ / / / / / / / / / / / / / / / / / / / / / /

Введение в STL
Часть 1

Автор: Александр Шаргин
rudankort@mail.ru

Стандартная библиотека шаблонов (Standard Template Library, STL) входит в стандартную библиотеку языка C++. В неё включены реализации наиболее часто используемых контейнеров и алгоритмов, что избавляет программистов от рутинного переписывания их снова и снова. При разработке контейнеров и применяемых к ним алгоритмов (таких как удаление одинаковых элементов, сортировка, поиск и т. д.) часто приходится приносить в жертву либо универсальность, либо быстродействие. Однако разработчики STL поставили перед собой сверхзадачу - сделать библиотеку одновременно эффективной и универсальной. Надо признать, что им удалось достичь цели, хотя для этого и пришлось использовать наиболее продвинутые возможности языка C++, такие как шаблоны и перегрузка операторов.

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

Стандарт языка C++ не регламетнирует реализацию контейнеров и алгоритмов STL. Поэтому с каждым компилятором поставляется своя реализация этой библиотеки. В последующем изложении я буду опираться на реализацию, поставляемую фирмой Microsoft вместе с компилятором Visual C++ 6.0. Тем не менее, большая часть сказанного будет справедлива и для других реализаций STL.

Основные концепции STL

Краеугольными камнями STL являются понятия контейнера (container), алгоритма (algorithm) и итератора (iterator).

• Контейнер - это хранилище объектов (как встроенных, так и определённых пользователем типов). Простейшие виды контейнеров (статические и динамические массивы) встроены непосредственно в язык C++. Кроме того, стандартная библиотека включает в себя реализации таких контейнеров, как вектор (vector), список (list), очередь (deque), ассоциативный массив (map), множество (set), и некоторых других.

• Алгоритм - это функция для манипулирования объектами, содержащимися в контейнере. Типичные примеры алгоритмов - сортировка и поиск. В STL реализовано порядка 60 алгоритмов, которые можно применять к различным контейнерам, в том числе к массивам, встроенным в язык C++.

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

Рассмотрим эти концепции более подробно.

Итераторы

Итераторы используются для доступа к элементам контейнера так же, как указатели - для доступа к элементам обычного массива. Как мы знаем, в языке C++ над указателями можно выполнять следующий набор операций: разыменование, инкремент/декремент, сложение/вычитание и сравнение. Соответственно, любой итератор реализует все эти операции или некоторое их подмножество. Кроме того, некоторые итераторы позволяют работать с объектами в режиме "только чтение" или "только запись", тогда как другие предоставляют доступ и на чтение, и на запись. В зависимости от набора поддерживаемых операций различают 5 типов итераторов, которые приведены в следующей таблице.

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

Контейнеры

Как мы уже знаем, контейнер предназначен для хранения объектов. Хотя внутреннее устройство контейнеров очень сильно различается, каждый контейнер обязан предоставить строго определённый интерфейс, через который с ним будут взаимодействовать алгоритмы. Этот интерфейс обеспечивают итераторы. Каждый контейнер обязан иметь соответствующий ему итератор (и только итератор). Важно подчеркнуть, что никакие дополнительные функции-члены для взаимодействия алгоритмов и контейнеров не используются. Это сделано потому, что стандартные алгоритмы должны работать в том числе со встроенными контейнерами языка C++, у которых есть итераторы (указатели), но нет ничего, кроме них. Таким образом при написании собственного контейнера реализация итератора - необходимый минимум.

Каждый контейнер реализует определённый тип итераторов. При этом выбирается наиболее функциональный тип итератора, который может быть эффективно реализован для данного контейнера. "Эффективно" означает, что скорость выполнения операций над итератором не должна зависеть от количества элементов в контейнере. Например, для вектора реализуется итератор с произвольным доступом, а для списка - двунаправленный. Поскольку скорость выполнения операции [] для списка линейно зависит от его длины, итератор с произвольным доступом для списка не реализуется.

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

Кроме обычных итераторов в STL существуют обратные итераторы (reverse iterator). Обратный итератор отличается тем, что просматривает последовательность элементов в контейнере в обратном порядке. Другими словами, операции + и - у него меняются местами. Это позволяет применять алгоритмы как к прямой, так и к обратной последовательности элементов. Например, с помощью функции find можно искать элементы как "с начала", так и "с конца" контейнера.

Каждый класс контейнера, реализованный в STL, описывает набор типов, связанных с контейнером. При написании собственных контейнеров следует придерживаться этой же практики. Вот список наиболее важных типов:

• value_type - тип элемента
• size_type - тип для хранения числа элементов (обычно size_t)
• iterator - итератор для элементов контейнера
• key_type - тип ключа (в ассоциативном контейнере)

Помимо типов можно выделить набор функций, которые реализует почти каждый контейнер в STL. Они не требуются для взаимодействия с алгоритмами, но их реализация улучшает взаимозаменяемость контейнеров в прграмме. Если, к примеру, какой-то контейнер реализует набор характерных для списка функций, то его можно будет вставить в программу вместо списка, изменив в ней всего одну строчку. Список основных функций приведён в таблице.

Алгоритмы

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

Каждый алгоритм использует итераторы определённого типа. Например, алгоритм простого поиска (find) просматривает элементы подряд, пока нужный не будет найден. Для такой процедуры вполне достаточно итератора ввода. С другой стороны, алгоритм более быстрого двоичного поиска (binary_search) должен иметь возможность переходить к любому элементу последовательности, и поэтому требует итератора с произвольным доступом. Вполне естественно, что вместо менее функционального итератора можно передать алгоритму более функциональный, но не наоборот.

Все стандартные алгоритмы описаны в файле algorithm, в пространстве имён std.

Вспомогательные компоненты STL

Помимо уже рассмотренных элементов в STL есть ряд второстепенных понятий, с которыми следует познакомиться.

Аллокаторы

Аллокатор (allocator) - это объект, отвечающий за распределение памяти для элементов контейнера. С каждым стандартным контейнером связывается аллокатор (его тип передаётся как один из параметров шаблона). Если какому-то алгоритму требуется распределять память для элементов, он обязан делать это через аллокатор. В этом случае можно быть уверенным, что распределённые объекты будут уничтожены правильно.

В состав STL входит стандартный класс allocator (описан в файле xmemory). Именно его по умолчанию используют все контейнеры, реализованные в STL. Однако никто не мешает вам реализовать собственный. Необходимость в этом возникает очень редко, но иногда это можно сделать из соображений эффективности или в отладочных целях.

Объекты-функции

Многие алгоритмы получают в качестве параметра различные функции. Эти функции используются для сравнения элементов, их преобразования и т. д. Рассмотрим следующий шаблон функции.

template<class T,
class CmpFn> T &max(T &x1, T &x2, CmpFn cmp)
{
    return cmp(x1, x2) ? x1 : x2;
}

Что такое CmpFn? Естественнее всего предположить, что это указатель на функцию. Однако вызов функции по указателю - операция довольно долгая. В нашем примере вызов займёт больше времени, чем выполнение всех остальных инструкций в функции max. Проблема в том, что при таком подходе к передаче функции её не удаётся объявить как встроенную (inline).

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

Таким образом, объекты-функции используются в целях оптимизации

Предикаты

Термин "предикат" довольно часто фигурирует в книгах по STL. В действительности предикат - это просто функция (в частности объект-функция), которая возвращает bool. Различают унарные и бинарные предикаты. Унарные получают один параметр, бинарные - два.

Предикаты широко используются в STL. Унарные предикаты используются для задания подмножества элементов контейнера, удовлетворяющих некоторому условию. Например, функция count_if считает количество элементов последовательности, для которых заданный унарный предикат возвращает true. Бинарные предикаты чаще всего используются для сравнения двух элементов.

Адаптеры

Адаптер (adapter) - это класс, который не реализует собственную функциональность, а вместо этого предоставляет альтернативный интерфейс к функциональности другого класса.

В STL адаптеры применяются для самых различных классов (контейнеров, объектов-функций и т. д.). Наиболее типичный пример адаптера - стек. Стек может использовать в качестве нижележащего класса различные контейнеры (очередь, вектор, список), обеспечивая для них стандартный стековый интерфейс (функции push/pop).

/ / / / ОБРАТНАЯ СВЯЗЬ / / / / / / / / / / / / / /

Александру Шаргину от читателя пришло интересное письмо. Он решил, что его было бы полезно прочитать всем.

В N36 рассылки "Программирование на Visual C++" я прочитал ваш пример убивания чужого окна, использующий DLL. Однако, мне показалось, что пример не полный, поскольку может возникнуть ситуация, когда сразу несолько процессов вызовут функцию DLL KillWndNow. В этом случае может сложиться ситуация, когда сначала первый процесс запишет в shared-переменную hWndToKill хэндл убиваемого окна, затем второй процесс запишет тужа же, но уже другой хэндл, потом первый запустит механизм убивания, но в результате убьется окно, на которое уже успел указать второй процесс.

Более корректно было бы поместить весь код функции KillWndNow в критическую секцию. Но, поскольку критические секции могут использоваться только в рамках одного процесса, для синхронизации здесь уместно использоваться мютекс.

Еще один нюанс. В функции KillWndNow где-нибудь после строчки
WaitForSingleObject(hEvent, INFINITE);
нужно вставить оператор hWndToKill=NULL, иначе при любой загрузке DLL (например, другим процессом, который вызвал KillWndNow) в функции DllMain будет исполняться ветка кода, пытающаяся убивать окно, хотя фактически запрос на такую операцию не поступал.

И, наконец, последнее. Все это будет работать только в том случае, если эта DLL еще не была загружена процессом, окно которого мы хотим убить. А если была? Придется использовать какой-то другой механизм, или все-таки можно как-нибудь усовершенствовать существующий? Самое плохое даже не то, что чужое окно не будет убиваться, а то, что функция KillWndNow подвиснет на вызове WaitForSingleObject, поскольку это событие никогда не реализуется. А если еще и добавить мютекс, как я описал выше, то повиснут и все последующие вызовы этой функции, но уже на ожидании освобождения мютекса. - Dmitry Batsuro

/ / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / /

Остальных рубрик сегодня не будет. За неделю мне не пришло НИ ОДНОГО ответа на вопрос, так что я решил его оставить на следующую неделю.

До встречи!

Алекс Jenter   jenter@mail.ru
Красноярск, 2001.