Шилдт c++_базовый_курс издание 3. Герберт Шилдт С базовый курс
 Скачать 9.37 Mb.
|
|
Глава 21: Введение в стандартную библиотеку шаблонов Материал этой главы составляет то, что многие считают самым важным добавлением в C++ за последние годы. Речь идет о стандартной библиотеке шаблонов (Standard Template Library — STL). Именно включение библиотеки STL в C++ было основным событием, которое обсуждалось в период стандартизации C++. Библиотека STL предоставляет шаблонные классы и функции общего назначения, которые реализуют многие популярные и часто используемые алгоритмы и структуры данных. Например, она включает поддержку векторов, списков, очередей и стеков, а также определяет различные функции, обеспечивающие к ним доступ. Поскольку библиотека STL состоит из шаблонных классов, алгоритмы и структуры данных могут быть применены к данным практически любого типа. Библиотека STL — это набор шаблонных классов и функций общего назначения. Библиотека STL— это результат разработки программного обеспечения, который вобрал в себя одни из самых сложных средств языка C++. Чтобы понимать содержимое библиотеки STL и уметь им пользоваться, необходимо освоить весь материал, изложенный в предыдущих главах. Особенно хорошо нужно ориентироваться в шаблонах. Откровенно говоря, шаблонный синтаксис, который описывает STL, может поначалу испугать, хотя он выглядит сложнее, чем есть на самом деле. Несмотря на то что материал этой главы не труднее остального в этой книге, не следует огорчаться, если что-то на первый взгляд вам покажется непонятным. Немного терпения при рассмотрении примеров — и вскоре вы поймете, что за непривычным синтаксисом скрывается строгая простота STL. STL — довольно большая библиотека, и все ее средства невозможно изложить в одной главе. Полное описание библиотеки STL со всеми ее нюансами и методами программирования заняло бы целую книгу. Цель представленного здесь обзора — познакомить вас с основными операциями, принципами проектирования и основами STL- программирования. Освоив материал этой главы, вы сможете легко изучить остальную часть библиотеки STL самостоятельно. В этой главе также описан еще один важный класс C++ — класс string. Он предназначен для определения строкового типа данных, который позволяет обрабатывать символьные строки во многом подобно тому, как обрабатываются данные других типов: с помощью операторов. Класс string тесно связан с библиотекой STL. Обзор STL Несмотря на большой размер стандартной библиотеки шаблонов и порой пугающий синтаксис, в действительности ее средства довольно легко использовать, если понять, как она построена и из каких элементов состоит. Поэтому, прежде чем переходить к рассмотрению примеров, познакомимся с основными составляющими STL. Ядро стандартной библиотеки шаблонов включает три основных элемента: контейнеры, алгоритмы и итераторы. Они работают совместно один с другим, предоставляя тем самым готовые решения различных задач программирования. Контейнеры — это объекты, которые содержат другие объекты. Контейнеры — это объекты, содержащие другие объекты. Существует несколько различных типов контейнеров. Например, класс vector определяет динамический массив, класс queue создает двустороннюю очередь, а класс list обеспечивает работу с линейным списком. Эти контейнеры называются последовательными контейнерами и являются базовыми в STL. Помимо базовых, библиотека STL определяет ассоциативные контейнеры, которые позволяют эффективно находить нужные значения на основе заданных ключевых значений (ключей). Например, класс map обеспечивает хранение пар "ключ-значение" и предоставляет возможность находить значение по заданному уникальному ключу. Каждый контейнерный класс определяет набор функций, которые можно применять к данному контейнеру. Например, контейнер списка включает функции, предназначенные для выполнения вставки, удаления и объединения элементов. А стек включает функции, которые позволяют помещать значения в стек и извлекать их из стека. Алгоритмы обрабатывают содержимое контейнеров. Алгоритмы обрабатывают содержимое контейнеров. Их возможности включают средства инициализации, сортировки, поиска и преобразования содержимого контейнеров. Многие алгоритмы работают с заданным диапазоном элементов контейнера. Итераторы подобны указателям. Итераторы — это объекты, которые в той или иной степени действуют подобно указателям. Они позволяют циклически опрашивать содержимое контейнера практически так же, как это делается с помощью указателя при циклическом опросе элементов массива. Существует пять типов итераторов. В общем случае итератор, который имеет большие возможности доступа, можно использовать вместо итератора с меньшими возможностями. Например, однонаправленным итератором можно заменить входной итератор. Итераторы обрабатываются аналогично указателям. Их можно инкрементировать и декрементировать. К ним можно применять оператор разыменования адреса *. Итераторы объявляются с помощью типа iterator, определяемого различными контейнерами. Библиотека STL поддерживает реверсивные итераторы, которые являются либо двунаправленными, либо итераторами произвольного доступа, позволяя перемещаться по последовательности в обратном направлении. Следовательно, если реверсивный итератор указывает на конец последовательности, то после инкрементирования он будет указывать на элемент, расположенный перед концом последовательности. При ссылке на различные типы итераторов в описаниях шаблонов в этой книге будут использованы следующие термины. STL опирается не только на контейнеры, алгоритмы и итераторы, но и на другие стандартные компоненты. Основными из них являются распределители памяти, предикаты и функции сравнения. Распределитель памяти управляет выделением памяти для контейнера. Каждый контейнер имеет свой распределитель памяти (allocator). Распределители управляют выделением памяти для контейнера. Стандартный распределитель — это объект класса allocator, но при необходимости (в специализированных приложениях) можно определять собственные распределители. В большинстве случаев стандартного распределителя вполне достаточно. Предикат возвращает в качестве результата значение ИСТИНА/ЛОЖЬ. Некоторые алгоритмы и контейнеры используют специальный тип функции, называемый предикатом (predicate). Существует два варианта предикатов: унарный и бинарный. Унарный предикат принимает один аргумент, а бинарный — два. Эти функции возвращают значения ИСТИНА/ЛОЖЬ, но точные условия, которые заставят их вернуть истинное или ложное значение, определяются программистом. В остальной части этой главы, когда потребуется унарная функция-предикат, на это будет указано с помощью типа UnPred. При необходимости использования бинарного предиката будет применяться тип BinPred. В бинарном предикате аргументы всегда расположены в порядке первый, второй относительно функции, которая вызывает этот предикат. Как для унарного, так и для бинарного предикатов аргументы должны содержать значения, тип которых совпадает с типом объектов, хранимых данным контейнером. Функции сравнения сравнивают два элемента последовательности. Некоторые алгоритмы и классы используют специальный тип бинарного предиката, который сравнивает два элемента. Функции сравнения возвращают значение true, если их первый аргумент меньше второго. Функции сравнения идентифицируются с помощью типа Comp. Помимо заголовков, требуемых различными классами STL, стандартная библиотека C++ включает заголовки Например, в заголовке Шаблоны в заголовке Возможно, наиболее широко используется объект-функция less, который определяет, при каких условиях один объект меньше другого. Объекты-функции можно использовать вместо реальных указателей на функции в алгоритмах STL, о которых пойдет речь ниже. Используя объекты-функции вместо указателей на функции, библиотека STL в некоторых случаях генерирует более эффективный программный код. Материал этой главы не предусматривает использования объектов-функций, и мы не будем применять их напрямую. (Подробное описание объектов-функций можно найти в моей книге Полный справочник по C++, 4-е издание, М. : Издательский дом "Вильямс".) Контейнерные классы Как упоминалось выше, контейнеры представляют собой объекты STL, которые предназначены для хранения данных. Контейнеры, определяемые в STL, представлены в табл. 21.1. В ней также указаны заголовки, которые необходимо включать в программу при использовании каждого контейнера. Но несмотря на то, что класс string также является контейнером, позволяющим хранить и обрабатывать символьные строки, он в эту таблицу не включен и рассматривается ниже в этой главе. Поскольку имена типов в объявлениях шаблонных классов произвольны, контейнерные классы объявляют typedef-версии этих типов, что конкретизирует имена типов. Некоторые из наиболее популярных typedef-имен приведены ниже. Поскольку в одной главе невозможно рассмотреть все контейнеры, в следующих разделах мы представим только три из них: vector, list и map. Если вы поймете, как работают эти три контейнера, у вас не будет проблем с использованием остальных. Векторы Векторы представляют собой динамические массивы. Одним из контейнеров самого широкого назначения является вектор. Класс vector поддерживает динамический массив, который при необходимости может увеличивать свой размер. Как вы знаете, в C++ размер массива фиксируется во время компиляции. И хотя это самый эффективный способ реализации массивов, он в то же время является и самым ограничивающим, поскольку размер массива нельзя изменять во время выполнения программы. Эта проблема решается с помощью вектора, который по мере необходимости обеспечивает выделение дополнительного объема памяти. Несмотря на то что вектор — это динамический массив, тем не менее, для доступа к его элементам можно использовать стандартное обозначение индексации массивов. Вот как выглядит шаблонная спецификация для класса vector: template Здесь T— тип сохраняемых данных, а элемент Allocator означает распределитель памяти, который по умолчанию использует стандартный распределитель. Класс vector имеет следующие конструкторы. explicit vector(const Allocator &a = Allocator()); explicit vector(size_type num, const T &val = T(), const Allocator &a = Allocator()); vector(const vector template Allocator &a = Allocator()); Первая форма конструктора предназначена для создания пустого вектора. Вторая создает вектор, который содержит num элементов со значением val, причем значение val может быть установлено по умолчанию. Третья форма позволяет создать вектор, который содержит те же элементы, что и заданный вектор ob. Четвертая предназначена для создания вектора, который содержит элементы в диапазоне, заданном параметрами-итераторами start и end. Ради достижения максимальной гибкости и переносимости любой объект, который предназначен для хранения в векторе, должен определяться конструктором по умолчанию. Кроме того, он должен определять операции "<" и "==" Некоторые компиляторы могут потребовать определения и других операторов сравнения. (В виду существования различных реализаций для получения точной информации о требованиях, предъявляемых вашим компилятором, следует обратиться к прилагаемой к нему документации.) Все встроенные типы автоматически удовлетворяют этим требованиям. Несмотря на то что приведенный выше синтаксис шаблона выглядит довольно "массивно", в объявлении вектора нет ничего сложного. Рассмотрим несколько примеров. vector vector /* Создание 5-элементного вектора для хранения char-значений. */ vector vector Для класса vector определены следующие операторы сравнения: ==, <, <=, !=, > и >= Для вектора также определен оператор индексации "[]", который позволяет получить доступ к элементам вектора с помощью стандартной записи с использованием индексов. Функции-члены, определенные в классе vector, перечислены в табл. 21.2. Самыми важными из них являются size(), begin(), end(), push_back(), insert() и erase(). Очень полезна функция size(), которая возвращает текущий размер вектора, поскольку она позволяет определить размер вектора во время выполнения программы. Помните, что векторы при необходимости увеличивают свой размер, поэтому нужно иметь возможность определять его величину во время работы программы, а не только во время компиляции. Функция begin() возвращает итератор, который указывает на начало вектора. Функция end() возвращает итератор, который указывает на конец вектора. Как уже разъяснялось, итераторы подобны указателям, и с помощью функций begin() и end() можно получить итераторы для начала и конца вектора соответственно. Функция push_back() помещает заданное значение в конец вектора. При необходимости длина вектора увеличивается так, чтобы он мог принять новый элемент. С помощью функции insert() можно добавлять элементы в середину вектора. Кроме того, вектор можно инициализировать. В любом случае, если вектор содержит элементы, то для доступа к ним и их модификации можно использовать средство индексации массивов. А с помощью функции erase() можно удалять элементы из вектора. Рассмотрим короткий пример, который иллюстрирует базовое поведение вектора. // Демонстрация базового поведения вектора. #include #include using namespace std; int main() { vector // Отображаем исходный размер вектора v. cout << "Размер = " << v.size() << endl; /* Помещаем значения в конец вектора, и размер вектора будет по необходимости увеличиваться. */ for(i=0; i<10; i++) v.push_back(i); // Отображаем текущий размер вектора v. cout << "Текущее содержимое:\n"; cout << "Новый размер = " << v.size() << endl; // Отображаем содержимое вектора. for(i=0; i /* Помещаем в конец вектора новые значения, и размер вектора будет по необходимости увеличиваться. */ for(i=0; i<10; i++ ) v.push_back(i+10); // Отображаем текущий размер вектора v. cout << "Новый размер = " << v.size() << endl; // Отображаем содержимое вектора. cout << "Текущее содержимое:\n"; for(i=0; i cout << endl; // Изменяем содержимое вектора. for(i=0; i cout << "Содержимое удвоено:\n"; for(i=0; i return 0; } Результаты выполнения этой программы таковы. Размер = 0 Текущее содержимое: Новый размер = 10 0 1 2 3 4 5 6 7 8 9 Новый размер = 20 Текущее содержимое: 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 Содержимое удвоено: 0 2 4 6 8 10 12 14 16 18 20 22 24 26 28 30 32 34 36 38 Рассмотрим внимательно код этой программы. В функции main() создается вектор v для хранения int-элементов. Поскольку при его создании не было предусмотрено никакой инициализации, вектор v получился пустым, а его емкость равна нулю. Другими словами, мы создали вектор нулевой длины. Это подтверждается вызовом функции-члена size(). Затем, используя функцию-член push_back(), в конец этого вектора мы помещаем 10 элементов, что заставляет вектор увеличиться в размере, чтобы разместить новые элементы. Теперь размер вектора стал равным 10. Обратите внимание на то, что для отображения содержимого вектора v используется стандартная запись индексации массивов. После этого в вектор добавляются еще 10 элементов, и вектор v автоматически увеличивается в размере, чтобы и их принять на хранение. Наконец, используя опять-таки стандартную запись индексации массивов, мы изменяем значения элементов вектора v. Обратите также внимание на то, что для управления циклами, используемыми для отображения содержимого вектора v и его модификации, в качестве признака их завершения применяется значение размера вектора, получаемое с помощью функции v.size(). Одно из преимуществ векторов перед массивами состоит в том, что у нас есть возможность узнать текущий размер вектора, что в определенных ситуациях является очень полезным средством. Доступ к вектору с помощью итератора Как вы знаете, массивы и указатели в C++ тесно связаны между собой. К элементам массива можно получить доступ как с помощью индекса, так и с помощью указателя. В библиотеке STL аналогичная связь существует между векторами и итераторами. Это значит, что к членам вектора можно обращаться как с помощью индекса, так и с помощью итератора. Эта возможность демонстрируется в следующей программе. // Доступ к вектору с помощью итератора. #include #include using namespace std; int main() { vector // Помещаем значения в вектор. for(i=0; i<10; i++) v.push_back('A' + i); /* Получаем доступ к содержимому вектора с помощью индекса. */ for(i=0; i<10; i++) cout << v[i] << " "; cout << endl; /* Получаем доступ к содержимому вектора с помощью итератора. */ vector while(p != v.end()) { cout << *p << " "; p++; } return 0; } Вот как выглядят результаты выполнения этой программы. A B C D E F G H I J A B C D E F G H I J В этой программе сначала создается вектор нулевой длины. Затем с помощью функции push_back() в конец вектора помещаются символы, в результате чего размер вектора соответствующим образом увеличивается. Обратите внимание на то, как объявляется итератор р. Тип этого итератора определяется контейнерными классами. Поэтому для получения итератора для конкретного контейнера используйте объявление, аналогичное показанному в этом примере: просто укажите для данного итератора имя контейнера. В нашей программе итератор p инициализируется таким образом, чтобы он указывал на начало вектора (с помощью функции-члена begin()). Итератор, который возвращает эта функция, можно затем использовать для поэлементного доступа к вектору, инкрементируя его соответствующим образом. Этот процесс аналогичен тому, как можно использовать указатель для доступа к элементам массива. Чтобы определить, когда будет достигнут конец вектора, используется функция-член end(). Эта функция возвращает итератор, установленный за последним элементом вектора. Поэтому, если значение р равно v.end(), значит, конец вектора достигнут. |