Язык программирования Си++ (1119468), страница 11

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 11)

*/ max (‘a’, 100); /* ... */ }void f () { /* ... */ max (2.5, 1); /* ... */ }1. Перед одним из параметров можно употреблятьоперацию приведения типа, которая сделаетвозможным использование нужного шаблона иформирование нужного варианта функции, то естьdouble max (double, double):void f () { ... max (2.5, (double) 1); ... }221Шаблоны функций• Параметры могут иметь разные типы:void f () { /* ... */ max (‘a’, 100); /* ... */ }void f () { /* ... */ max (2.5, 1); /* ... */ }2.

Можно написать новый шаблон, который умеетсравнивать данные различных типов3. Можно явно указывать выбираемый шаблон спомощью спецификации типом:void f () { ... max<int> (‘a’, 100);max<double> (2.5, 1);max<long> (4455, 777777);... }222Шаблоны функций• Параметры могут иметь разные типы:void f () { /* ... */ max (‘a’, 100); /* ... */ }void f () { /* ... */ max (2.5, 1); /* ...

*/ }4. Можно перегрузить шаблон функцией, то есть копределению шаблона добавить определениеодноимённой функции:int max (char x, int y) { return x > y ? (int) x : y; } // или так:int max (int x, int y){ return x >= y ? x : y; }223Шаблоны функций• При конфликтах шаблонов и функций работаетмодифицированный алгоритм определения перегруженнойфункции, отличающийся тем, что в нём дополнительноприменяется шаг а’, который рассматривается после того, какне сработал шаг по пункту а алгоритма• Если будет обнаружена функция с формальными параметрами,в точности соответствующими фактическим параметрамвызова (без каких-либо дополнительных преобразованийфактических параметров), она и будет вызвана• Только в противном случае будут искаться пригодные длявызова шаблоны функций, так как явно написанная с точнымипараметрами функция всегда имеет предпочтение передшаблонами функций224Шаблоны функций• Исследование возможности генерации функции по шаблонуможет привести к генерации новой функции или киспользованию уже сгенерированной по шаблону функции:void f () { /* ...

*/ max (‘a’, ‘a’); /* ... */ }==>max<char> (‘a’, ‘a’);• Следующие шаги модифицированного алгоритма будутобычными: расширения целочисленных и вещественныхпараметров, другие стандартные, а затем пользовательскиепреобразования параметров, именно в соответствии с этимишагами алгоритма будет обрабатываться вызовvoid f () { /* ... */ max (‘a’, 100); /* ... */ }225Перегрузка шаблонов функций• При выборе подходящей функции осуществляется поискспециализации, наилучшим образом соответствующей спискуфактических параметров вызова, фактически выбор функциипроводится по её собственным уже специализированнымпараметрам, что позволяет вводить несколько шаблоновфункций с одним и тем же именем:template<class T>T max (T* p, int size) { /* ...

*/ }template<class T>T& max (T&X, T&Y){return ( X < Y ? Y : X);}template<class T,class Pr> T& max (T&X, T&Y, Pr P) {return (P (X, Y)? Y : X);}• Шаблонной функцией можно пытаться находить максимум вклассе комплексных чисел complex:complex a (1, 2), b (3, 4); void f () { /*...*/ max (a, b); /*...*/ }// T≡complex226Шаблоны функций• Механизм шаблонов обеспечивает проверку отсутствияошибок не только при определении, но и при проведении ихинстанциирования• Если в шаблоне предполагается использование некоторыхопераций, определённых для одного типа данных, но неопределённых для другого, то выявить возможные ошибкиможно, при проверке конкретных специализаций шаблона• Для комплексных чисел можно создать, например, такуюоперацию сравнения на “больше”:#include <math.h>bool complex::operator > (const complex & a) const{ return re * re + im * im > a.re * a.re + a.im * a.im; }227Шаблоны классов• Шаблоны создаются не только для функций, но и для классов(структур), имеющих общую логику работы:template<список_формальных_параметров_шаблона_типа>class имя_класса { /*...*/ };• Шаблоны классов могут иметь не только ти́ повые параметры,но и обычные параметры-переменные разрешённых типов(интегральные, перечислимые, указатели и ссылки),использующиеся в дальнейшем в теле шаблона:имя_класса<список_фактических_параметров>объект;228Шаблоны классов• Класс векторов лучше оформлять шаблоном класса:template <class T> class Vector { T * p; int size; /* … */public: explicit Vector (int);T & operator [] (int); // индексация};Vector<int> X (20);// Для массивов нуженVector<complex> y (10); // конструктор умолчания!• Любой метод шаблонного класса есть шаблоннаяфункция:template <class T> T & Vector <T> :: operator [] (int) { ...

}229Шаблоны классов• Инстанцирования шаблона и определения объектов:template<class T, int size> class buffer { /* ... */ };buffer <char, 1024> X;buffer <char, 512*2> Y;buffer <int, 1024> Z;// Объекты X и Z имеют разные типы!• Типы X и Y считаются одинаковыми• Значения перечислимых типов при инстанциированиишаблона приводятся к интегральным типам• Значения неинтегральных типов не могут бытьпараметрами шаблонов230Шаблоны классов• Шаблон может в качестве своего параметра иметьдругой шаблон (это может быть только шаблонкласса):template<class T, template<class> class C> class Cont{ C<T> mem;C<T*> ref;/* ... */ };• Такое определение класса C, заданного как классшаблон с одним ти́ повым параметром, даётвозможность создавать специализации этого типа вовремя инстанциирования типа Cont:Cont<Entry, vector> vect1;Cont<Record, list> list2;// ссылки в виде вектора// ссылки в виде списка231Шаблоны классов• Имена шаблонов классов (как и классов вообще)нельзя перегружать• Если в программе имеется определение шаблона,попытка включить в ту же область видимости этойпрограммы любое из последующих определенийкласса с тем же именем будет ошибкой:template<class T> class Tmax { T * p; int size; public: Tmax (); };template<class T> class Tmax{ ...

}; // ОШИБКАtemplate<class T> struct Tmax{ ... }; // ОШИБКАtemplate<class U> class Tmax{ ... }; // ОШИБКАtemplate<class T, class U> class Tmax { ... }; // ОШИБКАclass Tmax { ... }; // ОШИБКА232Стандартная библиотека• Адекватная поддержка объектно-ориентированногопрограммирования, проектирование библиотечныхэлементов в виде иерархий классов, использованиеабстрактных классов и виртуальных функций• Активное использование шаблонов для повышенияуровня абстракции базовых алгоритмов• Использование механизма исключительных ситуацийи иерархии стандартных классов для передачизначений при возбуждении исключительных ситуаций• Технология “обобщённого программирования”:максимальное обобщение структур и алгоритмов приодновременном сохранении их эффективности 233Стандартная библиотека• Стандартная библиотека – средство разработкиконтекстно-ориентированных библиотек• Стандартная библиотека предоставляет совокупностьпонятий, в терминах которых можно проектироватьпрограммы, и набор типовы́ х решений сиспользованием этих понятий• Стандартная библиотека – это объединениенескольких компонентов, каждый из которыхпредоставляет набор примитивов и типовы́ х решений,позволяющих строить наборы конкретных классов ифункций для некоторой прикладной области234Взаимодействие элементовстандартной библиотекиРаспределителипамятиЯзыковая поддержкаСтрокии диагностикаКонтейнерыЛокализация типовИтераторыВвод и вывод235Средства стандартной библиотеки• Средства стандартной библиотеки определены в единомпространстве имён std с помощью заголовочных файлов• Стандартная библиотека предоставляет: Расширяемый набор классов и определений, необходимых дляподдержки понятий языка Си++ (управление памятью, информация отипах во время выполнения программы, обработка исключений, средствазапуска программы, зависящие от реализации аспекты языка) Поддержки диагностики пользовательских приложений Утилиты общего назначения Контейнеры и итераторы Обобщённые структуры данных и алгоритмы Средства локализации программ Классы и функции для математических вычислений Средства работы со строками Ввод/вывод236Принципы разработки STL• Библиотека STL представляет собой набор совместно работающих,хорошо структурированных компонентов Си++ Все используемые в шаблонах алгоритмы работают не только сбиблиотечными структурами данных, но также и со встроеннымиструктурами данных языка, в частности, все алгоритмы работают собычными указателями Использован принцип ортогональности: имеется возможностьиспользовать библиотечные структуры данных с собственнымиалгоритмами, а библиотечные алгоритмы с собственнымиструктурами данных• Эффективность реализации: каждый шаблонный компонентбиблиотеки имеет обобщённую реализацию, не отличающуюся поэффективности от “ручной” реализации более, чем на несколькопроцентов• Теоретическая обоснованность237Программные компоненты STLВ обычнойбиблиотекетребуется i * j * kвариантовпрограммАлгоритмы (k)…перестановкасортировкапоисквекторы…целый…плавающий…символьныйТипы данных (i)…списки …Контейнеры (j)В библиотеке STLтребуется только j + kвариантов программ238Базовые компоненты STL• Контейнеры, управляющие элементами данных• Итераторы, обеспечивающие доступ к элементамданных• Распределители памяти (аллокаторы),инкапсулирующие информацию о моделях памяти• Алгоритмы, определяющие вычислительныепроцедуры, отделённые от конкретных реализацийструктур данных и не связанные с конкретнымиконтейнерами• Функциональные объекты• Адаптеры, обеспечивающие преобразования239интерфейсовКонтейнеры STL•••••••Контейнеры управляют наборами ячеек памятиКонтейнеры – это объекты (классы), содержащие другие объекты (списки,векторы, очереди, деревья, простые и ассоциативные массивы и т.

д.)Контейнеры не являются производными от некоторого общего базовогокласса, каждый контейнер реализует все стандартные контейнерныеинтерфейсыНекоторые контейнеры обладают свойством реверсивности, в дополнение кобычным требованиям к ним предъявляются требования обеспечениядоступа с помощью обратных итераторовДля любого контейнера определены операции, позволяющие вводитьуказатели и итераторы на объекты, содержащиеся внутри него, определятьрасстояние между элементами контейнера и размеры этих элементовСреди элементов контейнера выделяются начальный и конечный элементыЭлементы контейнера можно сравнивать между собой и менять местами240Контейнеры STL•••••Выделяются две категории контейнеров: контейнеры-последовательности иассоциативные контейнерыПоследовательности организованы в виде конечных множеств элементоводного типа, эти множества имеют строгую линейную упорядоченностьАссоциативные контейнеры позволяют обеспечить быстрый доступ кэлементам с помощью ключейДва ключа считаются равными, если ни один из них не меньше и не большедругого: неправильно считать, что для ключей можно использоватьоперацию сравнения ‘==’ и что для определяют равенство ключей так:k1 == k2 // ОШИБКАПравильным подходом к выявлению равенства ключей являетсяпоследовательное использование пользовательского критерия сравнения:comp (k1, k2) == false && comp (k2, k1) == falseгде comp () есть сравнивающий функциональный объект, которыйпередаётся шаблону контейнера в качестве фактического параметра 241Контейнеры STL• Для разных контейнеров определяются семантически сходные иодинаково поименованные функции: для контейнеров-последовательностей определены функцииinsert () (вставка элементов) и erase () (удаление элементов) для контейнеров-последовательностей имеются функцииpush_back (), создающая один дополнительный элемент в концеконтейнера, и pop_back (), уничтожающая элемент в концеконтейнера для ассоциативных контейнеров определены операции insert () иerase () ( вставка и уничтожение элементов по заданному ключу), атакже поиска элементов и диапазонов по заданному ключу (find ())• Вставка элементов в ассоциативный контейнер (и исключениеэлемента из него), в отличие от похожих операций надпоследовательностями, не разрушает ранее построенные итераторы,указывающие на какие-либо другие элементы этих же контейнеровКонтейнеры STL•К контейнерам-последовательностям относятся вектор или динамическиймассив (vector), линейный список (list), двусторонняя очередь (deque)•К ассоциативным контейнерам относятся ассоциативный массив (map),множественный ассоциативный массив (multimap), множество (set – массивс ключами и без элементов) и множество с одинаковыми ключами (multiset)•Квазиконтейнеры: встроенный массив (array), строка (string), массивзначений (valarray), битовый набор (bitset)•Квазиконтейнеры содержат внутри себя элементы, как обычныеконтейнеры, но обладают некоторыми ограничениями: для них неопределяются отдельные операции, которые нельзя реализовать стребуемой для библиотечных элементов эффективностью•На основе стандартных контейнеров-последовательностей с помощьюадаптеров строятся производные контейнеры очередь (queue), стек (stack),очередь с приоритетами (priority_queue)243Контейнеры STL• Каждый контейнер в своей открытой части содержит сериюопределений типов, где введены стандартные имена типов:value_type – тип элементаallocator_type – тип распределителя памятиsize_type – тип, используемый для индексацииiterator, const_iterator – тип итератораreverse_iterator, const_reverse_iterator – тип обратного итератораpointer, const_pointer – тип указателя на элементreference, const_reference – тип ссылки на элемент• Эти имена определяются внутри каждого контейнера так, как этонеобходимо в каждом конкретном случае, что позволяет писатьпрограммы с использованием контейнеров, не зная о настоящихтипах, в частности, можно составить программу, которая будетработать с любым контейнером244Итераторы STL•••••••Итераторы (обобщение указателей) предоставляют алгоритмам средствадля перемещения по контейнерам и доступа к данным контейнеровИтераторы поддерживают абстрактную модель данных какпоследовательности объектовПонятия “нулевой, никуда не указывающий итератор” не существует, приорганизации циклов происходит сравнение с концом последовательностиКаждый контейнер обеспечивает свои итераторы, также поддерживающиестандартный набор итерационных операций со стандартными именами исмысломОписания классов итераторов находятся в заголовочном файле <iterator>Итераторы есть объекты, для которых определена унарная операцияoperator*, возвращающая значение некоторого класса или встроенноготипа, называемого типом значения (value type) итератораВсякая шаблонная функция, работающая с итераторами, одновременноможет работать и с обычными указателями245Итераторы STL• Имеется пять видов итераторов:1.

Характеристики

Список файлов лекций