 |
Динамическая идентификация типов
|
|
|
|
Динамическая идентификация типа (RTTI–Run-Time Type Identification) характерна для языков, в которых поддерживается полиморфизм. В этих языках возможны ситуации, в которых тип объекта на этапе компиляции неизвестен.
В С++ полиморфизм поддерживается через иерархии классов, виртуальные функции и указатели базовых классов. При этом указатель базового класса может использоваться либо для указания на объект базового класса, либо для указания на объект любого класса, производного от этого базового.
Информацию о типе объекта получают с помощью оператора typeid, при использовании которого следует подключить заголовочный файл <typeinfo.h>
Оператор typeid имеет две формы:
1. typeid (объект)
2. typeid (имя_типа)
Оператор typeid возвращает ссылку на объект типа type_info.
В классе type_info определены следующие открытые члены:
bool operator==(const type_info&ob)const;
bool operator!=(const type_info&ob)const;
const char* name()const;
Перегруженные операции == и!= обеспечивают сравнение типов.
Функция name() возвращает указатель на имя типа.
Оператор typeid имеет одно ограничение. Он работает корректно только с объектами, у которых определены виртуальные функции. Когда оператор typeid применяют к неполиморфному классу (в классе нет виртуальной функции), получают указатель или ссылку базового типа.
Пример 7.2.1.
#include<iostream.h>
#include<typeinfo.h>
class Base{
virtual void f(){};
//…
};
class Derived: public Base{
//…
};
void main()
{int i;
Base ob,*p;
Derived ob1;
cout<<typeid(i).name(); //Выводится int
p=&ob1;
cout<<typeid(*p).name(); //Выводится Derived
}
Пример 7.2.2.
#include<iostream.h>
#include<typeinfo.h>
class Base{
virtual void f(){};
//…
};
class Derived: public Base{
//…
};
void WhatType(Base& ob)
{cout<< typeid(ob).name()<<endl;
}
void main()
{
Base ob;
Derived ob1;
WhatType(ob); // Выводится Base
WhatType(ob1); // Выводится Derived
}
Пример 7.2.3.
|
|
|
class X{
virtual void f(){};
};
class Y{
virtual void f(){};
};
void main()
{X x1,x2;
Y y1;
if(typeid(x1)==typeid(x2))cout<<“тип одинаков”;
else cout<<“тип не одинаков”;
if(typeid(x1)!=typeid(y1)) cout<<“тип неодинаков”;
…
if(typeid(x1)==typeid(X)) cout<<“x1 имеет тип X”;
…
}
При использовании указателей на объект, например typeid(*p), если p==NULL, то возникает исключительная ситуация bad_typeid.
Безопасное приведение типа
Приведение типа вида (имя_типа) выражение, определенное в стандарте языка С, может привести к ошибкам. Ошибка может произойти, когда вы попытаетесь привести один объект к другому при их несовместимости.
Пример 7.3.1.
struct A
{int i};
struct B
{char* s;}
void f(A* x)
{B* p=(B*)x;
cout<<p–>s;}
void main()
{B b;
A a,*r;
b.s=new char[5];
b.s=“abcd”;
a.i=15;
r=&a;
f(r);//Здесь ошибка
r=(A*)(&b);
f(r);//А так ошибки нет
}
Для решения проблемы безопасного приведения типов в С++ введены операторы:
dynamic_cast, static_cast, const_cast, reinterpret_cast.
Оператор dynamic_cast
Оператор dynamic_cast предназначен для безопасного приведения типа одного указателя или ссылки в другой. Основное назначение оператора dynamic_cast заключается в реализации приведения полиморфных типов.
Синтаксис оператора dynamic_cast:
dynamic_cast<целевой_тип>(выражение)
Здесь ‘целевой_тип’ – это тип, которым должен стать тип параметра ‘выражение’ после выполнения приведения типа. Оператор выполняется успешно, когда указатель (или ссылка) после приведения типа становится указателем на объект целевого типа либо на объект производного от целевого типа. При невозможности приведения результатом является либо NULL, если приводятся указатели, либо возбуждается исключительная ситуация bad_cast, если приводятся ссылки.
Пример 7.3.2.
Base* bp,b;
Derived* dp,d;
bp=&d;
dp= dynamic_cast<Derived*>(bp);
if(dp)cout<<“приведение прошло успешно”;
bp=&b;
dp=dynamic_cast<Derived*>(bp);
if(!dp)cout<<“приведение невозможно”;
Оператор dynamic_cast в некоторых случаях можно использовать вместо typeid.
Base* bp;
Derived* dp;
Приведение типов можно выполнить так
|
|
|
if (typeid(*bp)==typeid(Derived))dp=(Derived*)bp;
А можно и короче
dp=dynamic_cast<Derived*>(bp);
Оператор const_cast
const_cast<целевой_тип>(выражение)
Используется в том случае, когда вам необходимо удалить атрибут const из объекта.
void f(const int* p)
{int* v;
v=const_cast<int*>(p);
*v=2*(*v);
}
Оператор static_cast
static_cast<целевой_тип> (выражение)
Предназначен для выполнения операции приведения типов над объектами неполиморфных классов. Например, его можно использовать для приведения типа указателя базового класса к типу указателя производного класса. Кроме этого, он подойдет и для выполнения любой стандартной операции преобразования, но только не в динамическом режиме.
int i;
float f;
f=199.22;
i=static_cast<int>(f);
Оператор reinterpret_cast
reinterpret_cast<целевой_тип>(выражение)
Дает возможность преобразовать указатель одного типа в указатель совершенно другого типа. Он также позволяет приводить указатель к типу целого или целое к типу указателя. Это преобразование также опасно, как и старый С-стиль преобразования.
int i;
char* p=“Это строка”;
i=reinterpret_cast<int>(p);
cout<<i;
8. Стандартная библиотека шаблонов
8.1. Введение в STL
Создание стандартной библиотеки шаблонов (Standard Template Library, STL) является результатом многолетних исследований под руководством Александра Степанова и Менга Ли из компании Hewlett-Packard и Девида Мюссера из Rensselaer Polytechnic Institute.
Одна из наиболее необычных идей STL – это обобщенные алгоритмы. Обобщенные алгоритмы в STL напоминают классы-шаблоны. Но есть принципиальная разница между принципами ООП и принципами, лежащими в основе STL.
В ООП хорошо разработанный объект старается инкапсулировать всё состояние и поведение, необходимые для выполнения задачи, и в то же время скрывает как можно больше деталей внутреннего устройства. Во многих предшествующих объектно-ориентированных библиотеках этот подход воплощался в контейнерных классах, обладающих широкой функциональностью и богатым интерфейсом.
Разработчики STL пошли в другом направлении. Поведение, обеспечиваемое их стандартными компонентами, является минимальным. Вместо этого каждый компонент предназначен для функционирования совместно с большим набором обобщенных алгоритмов (шаблонов), имеющихся в библиотеке. Эти алгоритмы не зависят от контейнеров и поэтому могут работать со многими различными типами.
|
|
|
Отделяя функционирование алгоритмов от контейнерных классов, библиотека STL много выигрывает в размере – как в объёме самой библиотеки, так и в генерируемом коде. Вместо того, чтобы дублировать алгоритмы для многих контейнерных классов, одно-единственное описание библиотечной функции может использоваться с любым контейнером. Более того, описание этих функций является настолько общим, что они могут применяться с обычными массивами и указателями и с другими типами данных.
Парадигму обобщенного программирования можно сформулировать следующим образом:
Реши, какие требуются алгоритмы; параметризуй их так, чтобы они могли работать со множеством подходящих типов и структур данных.
STL обеспечивает общецелевые, стандартные классы и функции, которые реализуют наиболее популярные и широко используемые алгоритмы и структуры данных.
Поскольку STL строится на основе шаблонов классов, входящие в неё алгоритмы и структуры применимы почти ко всем типам данных
Ядро библиотеки образуют три элемента: контейнеры, алгоритмы и итераторы.
Контейнеры (containers) – это объекты, предназначенные для хранения других элементов. Вектор, линейный список, множество.
Ассоциативные контейнеры (associative containers) позволяют с помощью ключей получить быстрый доступ к хранящимся в них значениям.
В каждом классе-контейнере определен набор функций для работы с ними. Например, список содержит функции для вставки, удаления и слияния элементов.
Алгоритмы (algorithms) выполняют операции над содержимым контейнера. Существуют алгоритмы для инициализации, сортировки, поиска, замены содержимого контейнеров. Многие алгоритмы предназначены для работы с последовательностью (sequence), которая представляет собой линейный список элементов внутри контейнера.
Итераторы (iterators) – это объекты, которые по отношению к контейнеру играют роль указателей. Они позволяют получить доступ к содержимому контейнера примерно так же, как указатели используются для доступа к элементам массива.
|
|
|
Вдобавок к контейнерам, алгоритмам и итераторам в STL поддерживается ещё несколько стандартных компонентов. Главными среди них являются распределители памяти, предикаты и функции сравнения.
У каждого контейнера имеется определенный для него распределитель памяти (allocator), который управляет процессом выделения памяти для контейнера.
По умолчанию распределителем памяти является объект класса allocator. Можно определить собственный распределитель.
В некоторых алгоритмах и контейнерах используется функция особого типа, называемая предикатом. Предикат может быть унарным и бинарным. Возвращаемое значение: истина либо ложь. Точные условия получения того или иного значения определяются программистом. Тип унарных предикатов UnPred, бинарных – BinPred. Тип аргументов соответствует типу хранящихся в контейнере объектов.
Специальный тип бинарного предиката для сравнения двух элементов называется функцией сравнения (comparison function). Функция сравнения возвращает истину, если первый элемент меньше второго. Типом функции является тип Comp.
Для поддержки контейнерных классов STL включает так называемые классы-утилиты Utility-классы. Заголовочные файлы <utility.h> и <function.h>. Например, шаблон класса pair (пара) для хранения пары объектов.
Шаблоны из заголовочного файла <function.h> помогают создавать объекты, определяющие оператор-функцию operator(). Эти объекты называются объектами-функциями (function objects) и во многих случаях могут использоваться вместо указателей на функции, что позволяет генерировать более эффективный код. Например, класс-функция less (меньше), который позволяет определить, является значение одного объекта меньше, чем другого. Это предикат.
template<class T> struct less: public binary_function<T,T,bool>
{bool operator()(const T& x,const T& y)const
//возвращает результат сравнения x<y
{return x<y;}
};
Для поддержки единого определения типов аргументов и типа возвращаемого значения для различных объектов-функций с двумя аргументам в STL введен вспомогательный базовый класс
template<class Arg1,class Arg2,class Result> struct binary_function{}
typedef Arg1 first_argument_type;
typedef Arg2 second_argument_type;
typedef Result result_type;
Итераторы
Итератор–это специальный вспомогательный объект, который поставляется разработчиком контейнерного класса. Единственное назначение такого объекта – обеспечить доступ к элементам контейнера без показа внутренней структуры контейнера (один элемент за одно обращение).
Обычно итератор содержит указатель, с которым производятся различные манипуляции.
В STL итератор – это фундамент, на котором основано использование контейнерных классов и алгоритмов.
|
|
|
Итераторы применяются для различных целей:
· Итератор может обозначать конкретное значение.
· Пара итераторов может задавать диапазон значений. При этом второе значение (второй итератор) рассматривается не как часть определяемого диапазона, но как запредельный элемент, описывающий значение, следующее за последним значением из заданного диапазона.
Основное действие, которое модифицирует итератор, – это операции инкремент ++, декремент -- и увеличение +.
Для доступа к данным, определяемым итератором используется оператор разыменования *.
Итератор является шаблоном, параметром которого является контейнерный класс. Существует пять типов итераторов:
Итераторы ввода (input_iterator) поддерживают операции равенства, разыменования и автоинкремента. Итераторы, отвечающие этим условиям, могут использоваться для однопроходных алгоритмов, которые читают значения данных в одном направлении. Специальным случаем итератора ввода является istream_iterator.
==,!=, *i, ++i, i++, *i++.
Итераторы вывода (output_iterator) поддерживают разыменование, допустимое только с левой стороны присваивания, и инкремент:
++i, i++, *i=t, *i++=t
Однонаправленные итераторы (forward_iterator) поддерживают все операции итераторов ввода-вывода и, кроме того, позволяют без ограничений применять присваивание. Для них из i==j следует ++i==++j, что не всегда истинно для итераторов ввода. Т.е. forward-итераторы сохраняют позицию внутри структуры данных (контейнера) при многократных проходах. Таким образом, их можно использовать в алгоритмах с многократным проходом.
==,!=, =, *i, ++i, i++, *i++.
Двунаправленные итераторы (biderectional_iterator) обладают всеми свойствами forward-итераторов, а также возможностью прохода контейнера в обоих направлениях, т.е. имеют дополнительная операции –декремент
--i, i--, *i--.
Итераторы произвольного доступа (random_access_iterator) обладают всеми свойствами двунаправленных итераторов, а также поддерживают операции сравнения и адресной арифметики, т.е. непосредственный доступ по индексу.
i+=n, a+n, i-=n, a-n, i-j, i[n], i<j, i<=j, i>j, i>=j.
Таким образом, с их помощью можно написать такие алгоритмы, как алгоритмы быстрой сортировки, которые требуют эффективного произвольного доступа.
С итераторами можно работать так же, как с указателями. К ним можно применить операции *, инкремента, декремента. Типом итератора объявляется тип iterator, который определен соответствующим образом в различных контейнерах. В STL также поддерживаются обратные итераторы (reverse iterators). Обратными итераторами могут быть либо двунаправленные итераторы, либо итераторы произвольного доступа, но проходящие последовательность в обратном направлении. То есть если обратный итератор указывает на последний элемент последовательности, то инкремент этого итератора приведет к тому, что он будет указывать на предпоследний элемент.
8.3. Классы-контейнеры
В STL определены два типа контейнеров – последовательности и ассоциативные контейнеры.
Встроенные массивы, строки string, векторы valarray (векторы, оптимизированные для численных расчетов) и битовые поля bitset содержат элементы и, следовательно, могут считаться контейнерами. Однако эти типы не являются полностью разработанными стандартными контейнерами. Если бы они являлись таковыми, это помешало бы их основному назначению.
Ниже перечислены основные классы-контейнеры с указанием заголовочных файлов, которые необходимо подключить при их использовании.
bitset множество битов <bitset>
deque двусторонняя очередь <deque>
list линейный список <list>
map ассоциативный список для хранения пар ключ/значение, где с каждым ключом связано одно значение <map>
multimap с каждым ключом связано два или более значений <map>
multiset множество, в котором каждый элемент не обязательно уникален <set>
priority_queue очередь с приоритетом <queue>
queue очередь <queue>
set множество <set>
stack стек <stack>
vector динамический массив <vector>
Ключевая идея для стандартных контейнеров заключается в том, что, когда это представляется разумным, они должны быть логически взаимозаменяемыми. Пользователь может выбирать между ними, основываясь на соображениях эффективности и потребности в специализированных операциях. Например, если часто требуется поиск по ключу, можно воспользоваться map (ассоциативным массивом). С другой стороны, если преобладают операции, характерные для списков, можно воспользоваться контейнером list. Если добавление и удаление элементов часто производится в концы контейнера, следует подумать об использовании очереди queue, очереди с двумя концами deque, стека stack. По умолчанию пользователь должен использовать vector; он реализован, чтобы хорошо работать для самого широкого диапазона задач. Кроме того, пользователь может разработать дополнительные контейнеры, вписывающиеся в рамки стандартных контейнеров.
Идея обращения с различными видами контейнеров – и в общем случае со всеми видами источников информации – унифицированным способом ведет к понятию обобщенного программирования, о чем говорилось выше.
Поскольку имена типов элементов, входящих в объявление класса-шаблона, могут быть самыми разными, в классах-контейнерах с помощью ключевого слова typedef объявляются некоторые согласованные версии этих типов. Эта операция позволяет конкретизировать имена типов. Ниже перечислены имена этих типов.
size_type интегральный тип, эквивалентный типу size_t, являющемся беззнаковым целочисленным типом, представляющим результат операции sizeof.
reference тип ссылки на элемент контейнера.
const_reference тип константной ссылки на элемент контейнера
iterator тип итератора
const_iterator тип константного итератора
reverse_iterator тип обратного итератора
const_reverse_iterator тип константного обратного итератора
value_type тип хранящегося в контейнере значения.
allocator_type тип распределителя памяти.
key_type тип ключа в ассоциативных контейнерах
mapped_type тип отображенного значения в ассоциативных контейнерах
key_compare тип функции, которая сравнивает два ключа.
value_compare тип функции, которая сравнивает два значения
Следующие компонентные функции контейнеров используют итераторы в качестве возвращаемого значения:
iterator begin() указывает на первый элемент
iterator end() указывает на элемент, следующий за последним
reverse_iterator begin() указывает на первый элемент в обратной последовательности
reverse_iterator rend() указывает на элемент, следующий за последним в обратной последовательности
Следующие компонентные функции контейнеров используют итераторы в качестве возвращаемого ссылки
reference front() ссылка на первый элемент
reference back() ссылка на последний элемент
reference operator[]() доступ по индексу без проверки
reference at () доступ по индексу с проверкой
Следующие компонентные функции контейнеров включают элементы в контейнер
insert() включает элемент (последовательность элементов) в контейнер
push_back() добавление х в конец
push_front() добавление нового первого элемента (только для списков и очередей с двумя концами)
Следующие компонентные функции контейнров удаляют элелементы из контейнера
pop_back() удаление последнего элемента
pop_front() удаление первого элемента (только для списков и очередей с двумя концами)
erase() удаление заданной последовательности элементов
clear() удаление всех элементов контейнера
Операция доступа к элементу контейнера по индексу
reference operator[] (size_type pos);
Операции для ассоциативных контейнеров:
T& operator[](const key_type& k)
доступ к элементу с ключом k
iterator find(const key_type&k)
находит элемент с ключом k
iterator lower_bound(const key_type&k)
находит первый элемент с ключом k
iterator upper_bound(const key_type&k)
находит первый элемент с ключом большим k
pair<iterator,iterator>equal_range(const key_type&k)
находит lower_bound (нижнюю границу) и upper_bound (верхнюю границу) элементов с ключом k
Другие операции для контейнеров
size_type size()const возвращает число элементов в контейнере
bool empty()const проверяет, пуст ли контейнер
size_type capacity()const возвращает размер памяти, выделенная под контейнер-вектор
void reserve(size_type n) выделяет память под вектор
void resize(size_type n,T obj=T()) изменяет размер контейнера (только для векторов, списков и очередей с двумя концами)
swap(x) обмен местами двух контейнеров
==, !=, < операции сравнения контейнеров
Для создания контейнеров имеются следующие конструкторы:
container() создается пустой контейнер
container(n) создается контейнер, содержащий n элементов со значением по умолчанию
container(n,x) создается контейнер, содержащий n копий элементов х
container(first,last) создается контейнер, содержащий элементы из диапазона [first:last]
container(x) конструктор копирования
Контейнер vector
В качестве примера подробнее рассмотрим контейнер vector.
Контейнер вектор представляет собой динамический массив с доступом к его элементам по индексу. Возможность доступа к элементам по индексу обеспечивает поддерживаемый контейнером итератор произвольного доступа. Шаблон класса vector определен следующим образом:
template<class T, class Allocator=allocator<T> >
class std:: vector{/*члены класса*/};
T – тип предназначенных для хранения данных.
Allocator задает распределитель памяти, который по умолчанию является стандартным.
В классе определены следующие конструкторы.
explicit vector (const Allocator& a=Allocator());
explicit vector (size_type число,const T&значение=T(),const Allocator&a=Allocator());
vector (const vector<T,Allocator>&объект);
template<class InIter> vector (InIter начало,InIter конец, const Allocator&a=Allocator());
Описатель explicit подавляет неявное преобразование типов из типа аргумента в тип класса конструктора.
Первая форма представляет собой конструктор пустого вектора.
Во второй форме конструктора вектора число элементов – это число, а каждый элемент равен значению значение. Параметр значение может быть значением по умолчанию.
Третья форма конструктора вектор – это конструктор копирования.
Четвертая форма – это конструктор вектора, содержащего диапазон элементов, заданный итераторами начало и конец.
Пример 8.4.1.
vector<int> a;
vector<double> x(5);
vector<char> c(5,’*’);
vector<int> b(a);
Для любого объекта, который будет храниться в векторе, должен быть определен конструктор по умолчанию. Кроме того, для объекта должны быть определены операторы < и ==.
Для класса вектор определены следующие операторы сравнения
==, <, <=,!=, >, >=.
Кроме этого, для класса vector определяется оператор доступа по индексу [].
Новые элементы могут включаться в контейнер с помощью функций:
1)iterator insert (iterator i,const T&значение=T());
Вставляет параметр значение перед элементом, заданным итератором i. Возвращает итератор элемента.
2)void insert (iterator i,size_type число,const T&значение);
Вставляет число копий параметра значение перед элементом, заданным итератором i.
3)template<class InIter>void insert (iterator i,InIter начало,InIter конец);
Вставляет последовательность, определенную между итераторами начало и конец, перед элементом, заданным итератором i.
4)void push_back (const T&значение);
Добавляет в конец вектора элемент, значение которого равно параметру значение.
5)void resize (size_type число,T значение=T());
Изменяет размер вектора в соответствии с параметром число. Если при этом вектор удлиняется, то добавление в конец вектора. Элементы получают значение, заданное параметром значение.
6)template<class InIter>void assign(InIter начало,InIter конец);
Присваивает вектору последовательность, определенную итераторами начало и конец.
Существующие элементы могут удаляться с помощью функций:
1). iterator erase (iterator i);Удаляется элемент заданный итератором i.
2). iterator erase (iterator начало, iterator конец);
Удаляет элементы последовательности, определенной итераторами начало и конец.
3). void pop_back ();
Удаляет последний элемент.
4). void clear () const;Удаляет все элементы. Контейнер становится пустым.
5). void resize (size_type число,T значение=T());
Изменяет размер вектора в соответствии с параметром число. Если размер уменьшается, последние элементы удаляются.Доступ к отдельным элементам осуществляется с помощью итераторов:
1)iterator begin ();
Возвращает итератор на первый элемент.
2). iterator end ();
Возвращает итератор на конец последовательности.
3). reference operator[] (size_type pos);
Возвращает ссылку на элемент в позиции pos без контроля.
4). reference at (size_type pos);
Возвращает ссылку на элемент в позиции pos с контролем. При выходе индекса за границу генерируется исключение out_of_range
5). reference front (); Возвращает ссылку на первый элемент.6). reference back ();Возвращает ссылку на последний элемент.Манипулирование контейнером: сортировка, поиск в нем и тому подобное возможно с помощью глобальных функций файла-заголовка <algorithm.h>.
Два вектора х и у считаются равными (==), если x.size()==y.size() и x[i]=y[i] для любого допустимого индекса i.
Вектор х меньше вектора у (<), если первый x[i], не равный соответствующему y[i], меньше, чем y[i], или x.size()<y.size() при равенстве всех x[i] соответствующим y[i].
Пример 8.4.2. Создание массива целых чисел и заполнение его числами от 0 до 10.
#include<iostream.h>
#include<vector.h>
using namespace std;
int main()
{vector<int> v;
int i;
for(i=0;i<10;i++)v.push_back(i);
cout<<“size=”<<v.size()<<“\n”;
for(i=0;i<10;i++)cout<<v[i]<<“ ”;
cout<<endl;
for(i=0;i<10;i++)v[i]=v[i]+v[i];
for(i=0;i<v.size();i++)cout<<v[i]<<“ ”;
cout<<endl;
return 0;
}
Пример 8.4.3. То же, что и предыдущий, но используется итератор
int main()
{vector<int> v;
int i;
for(i=0;i<10;i++)v.push_back(i);
//доступ к вектору через итератор
vector<int>::iterator p=v.begin();
while(p!=v.end()){cout<<*p<<“ ”; p++;}
return 0;
}
Пример 8.4.4.
int main()
{vector<int> v(5,1);
vector<int>::iterator p=v.begin();
while(p!=v.end()){cout<<*p<<“ ”; p++;}
p=v.begin();
p+=2;//указывает на третий элемент
/*вставка в вектор v на то место, куда указывает итератор р, десять новых элементов, каждый из которых равен 9*/
v.insert(p,10,9);
//вывод
p=v.begin();
while(p!=v.end()){cout<<*p<<“ ”; p++;}
//удаление вставленных элементов
p=v.begin();
p+=2;
v.erase(p,p+10);
//вывод
p=v.begin();
while(p!=v.end()){cout<<*p<<“ ”; p++;}
return 0;
}
Пример 8.4.5. Массив объектов пользовательского класса.
#include<iostream.h>
#include “student.h”
using namespace std;
int main()
{vector<STUDENT> v(3);
int i;
v[0]= STUDENT(“Иванов”,21);
v[1]= STUDENT(“Петров”,19);
v[2]= STUDENT(“Попов”,20);
for(i=0;i<3;i++)cout<<v[i];
return 0;
}
8.5. Многомерные массивы
Многомерный массив можно представить как вектор с компонентами типа вектор
vector<vector<int>> v;
Так создаётся вектор векторов с целыми элементами, который в начале не содержит ни одного элемента. Проинициализируем его в матрицу 3х5.
v.resize(3);//теперь вектор содержит три пустых вектора
for(int i=0;i<v.size();i++)
{v[i].resize(5);//каждый из векторов содержит пять элементов
//проинициализируем их
for(int j=0;j<v[i].size();j++)v[i][j]=10*i+j;}
Вектора vector<int> в векторе vector<vector<int>> не обязаны иметь один и тот же размер.
Каждая реализация шаблона vector содержит указатель на его элементы плюс число элементов. Как правило, элементы содержатся в массиве.
| мv: |
| vv[0]: |
| vv[1]: |
| vv[2]: | 55 5 |
Доступ к элементам осуществляется путем двойного индексирования.
for(int i=0;i<v.size();i++){
for(int j=0;j<v[i].size();j++)cout<<v[i][j]<<“ ”;
Можно перегрузить операции << и >> для вектора.
ostream& operator<< (ostream& out,const vector<int>& v){
vector<int>::iterator p;
for(p=v.begin();p!=v.end();++p)out<<*p<<’\t’;
out<<endl;
return out;}
istream& operator>> (istream& in,vector<int>& v){
vector<int>::iterator p;
for(p=v.begin();p!=v.end();++p)in>>*p;
return in;}
Можно написать также функцию суммирования элементов вектора
int sum(vector<int>::iterator first,vector<int>::iterator last,
int initial_val)
{vector<int>::iterator p;
int sum=initial_val;
for(p=first;p!=last;p++)sum+=*p;
return sum;
}
Программа 8.1. Напишите функцию быстрой сортировки массива целых чисел.
Функцию быстрой сортировки сложно запрограммировать из-за многочисленных индексов, которые отслеживаются в традиционной реализации. Мы будем использовать контейнер vector и заменим индексирование итераторами.
Вначале запишем рекурсивную функцию сортировки:
void quicksort(vector<int>::iterator from,vector<int>::iterator to)
{
vector<int>::iterator mid;
if(from<(to-1)){
mid=partition(from,to);
quicksort(from,mid);
quicksort(mid+1,to);}
}
Здесь используется функция partition, которая в соответствиии с алгоритмом разделяет массив на две части.
Запишем эту функцию.
vector<int>::iterator
partition(vector<int>:: iterator from, vector <int>:: iterator to)
{
vector<int>::iterator front=from+1;
vector<int>::iterator back=to-1;
int compare=*from;
while(front<back){
while((front<back)&&(compare>*front))++front;
while((front<back)&&(compare<=*back))--back;
swap(*front,*back);}
if(compare>*front)
{swap(*from,*front);
return front;}
else{
swap(*from,*(front-1));
return front-1;}
}
Используемая здесь функция swap() меняет местами два элемента.
inline void swap(int& i,int& j)
{int temp=i;
i=j;
j=temp;}
Напишем также функцию print() для вывода массива:
void print(vector<int> v)
{
for(int i=0;i<v.size();i++)cout<<v[i]<<' ';
cout<<endl;
}
И,наконец, запишем функцию main():
int main()
{
srand((unsigned)time(NULL));
vector<int> v(10);
for(int i=0;i<v.size();i++)v[i]=rand()/10;
print(v);
quicksort(v.begin(),v.end());
print(v);
return 0;
}
Не забудьте подключить заголовочные файлы и указать пространство имен
#include<iostream>
#include<vector>
#include <stdio.h>
#include <time.h>
using namespace std;
В программе определяется вектор, заполняется случайными числами и сортируется.
В качестве самостоятельной работы напишите шаблон функции быстрой сортировки последовательностей любого типа.
Ассоциативные контейнеры
Ассоциативные контейнеры – это обобщение понятия ассоциативного массива.
Ассоциативный массив – это один из самых полезных и универсальных типов, определяемых пользователем. Фактически в языках, занимающихся главным образом обработкой текстов и символов, это зачастую встроенный тип.
Ассоциативный массив, часто называемый отображением (map), а иногда словарем (dictionary),содержит пары значений. Зная одно значение, называемое ключом (key), мы можем получить доступ к другому, называемому отображенным значением (mapped value).
Ассоциативный массив можно представить как массив, для которого индекс не обязательно должен иметь целочисленный тип:
template<class K,class V> class Assoc{
public:
V& operator[](const K&);
//…
}
Здесь operator[] возвращает ссылку на элемент V, соответствующий ключу K.
STL содержит два вида контейнеров, построенных как ассоциативные массивы: map и multimap, set и multiset, причем set и multiset можно рассматривать как вырожденные ассоциативные массивы, в которых ключу не соответствует никакого значения
(т.е. set содержит одни ключи).
Контейнеры map и multimap
Это последовательность пар (ключ,значение),которая обеспечивает быстрое получение значения по ключу. Контейнер map предоставляет двунаправленные итераторы.
Контейнер map требует, чтобы для типов ключа существовала операция “<”. Он хранит свои элементы отсортированными по ключу так, что перебор происходит по порядку.
Спецификация шаблона для класса map:
template<class Key,classT,class Comp=less<Key>,
class Allocator=allocator<pair>> class std::map
В классе map определены следующие конструкторы:
explicit map (const Comp& c=Comp(),
const Allocator& a=Allocator());
map (const map<Key,T,Comp,Allocator>& ob);
template<class InIter> map (InIter first,InIter last,const Comp& c=Comp(),const Allocator& a=Allocator());
Первая форма представляет собой конструктор пустого ассоциативного контейнера. Вторая – конструктор копии. Третья – конструктор ассоциативного контейнера, содержащего диапазон элементов.
В классе определена операция присваивания:
map& operator= (const map&);
Определены также следующие операции сравнения: ==, <, <=,!=, >, >=.
Копирование контейнера требует выделение памяти для элементов и создание копии каждого элемента. Это может оказаться очень дорого, и делать это нужно лишь при необходимости. Поэтому такие контейнеры часто передаются по ссылке.
Пары ключ/значение хранятся в контейнере в виде объектов типа pair. Тип pair – это класс, точнее шаблон класса.
template<class Key,class V> struct pair{
typedef Key TFirst;//тип ключа
typedef V TSecond;//тип значения
Key first;//ключ
V second;//значение
pair ():first(Key()),second(V()){}
pair (const Key& x,const V& y):first(x),second(y){}
template<class A,class B> pair (const pair<A,B>& ob): first(ob.first),second(ob.second){}
};
Последний конструктор существует для того, чтобы позволить преобразование в инициализаторе. Например:
pair<int,double> f(char c,int i)
{return pair<int,double>(c,i);}
Создавать пары ключ/значение можно не только с помощью конструкторов класса pair, но и с помощью функции make_pair, которая создает объекты типа pair, используя типы данных в качестве параметров.
template<class T1,classT2> pair<T1,T2>
std::make_pair(const T1& t1,const T2& t2){
return pair<T1,T2>(t1,t2);}
Преимущество этой функции в том, что она дает возможность компилятору автоматически распознавать типы предназначенных для хранения объектов, и вам не нужно указывать их явно. Таким образом, map – это последовательность.
Что касается реализации контейнера map, то он, скорее всего, реализован с использованием какой-либо формы дерева, и итераторы для map обеспечивают некоторый способ прохода по дереву. Такая реализация обеспечивает быстрый поиск значения по ключу.
|
|
|
