Ассоциативные контейнеры
Ассоциативные контейнеры
К ассоциативным контейнерам принадлежат: set, multiset, hash set, hash multiset, map, multimap, hash_map, hash_multimap. Они поддерживают эффективный поиск значений (values), связанных с ключом (key). Они позволяют вставить и удалить элемент, но в отличие от последовательностей не позволяют вставить элемент в заранее определенную и указанную позицию. Различают сортированные ассоциативные контейнеры (set, multiset, map, multimap) и хешированные (hashed) ассоциативные контейнеры (hash_set, hash_multiset, hash_map, hash_ / multimap).
Сортированные контейнеры соблюдают отношение порядка (ordering relation) для своих ключей, причем два ключа считаются эквивалентными, если ни один из них не меньше другого. Например, если отношение порядка не учитывает регистр, то ключ "strict rules" эквивалентен ключу "Strict Rules". Сортированные контейнеры хороши тем, что они гарантируют логарифмическую эффективность (complexity) большинства своих операций. Это гораздо более сильная гарантия, чем та, которую предоставляют хешированные ассоциативные контейнеры. Последние гарантируют постоянную эффективность только в среднем, а в худшем случае — линейную.
Хешированные ассоциативные контейнеры основаны на той или иной реализации хэш-таблиц (см. монографию Кнут Д. Искусство программирования, т. 3, Сортировка и поиск, 1999). Элементы в таком контейнере не упорядочены, хотя их можно добывать последовательно. Если вы вставите или удалите элемент, то последовательность оставшихся элементов может измениться, то есть она не гарантируется. Преимуществом рассматриваемого типа контейнеров является то, что в среднем они значительно быстрее сортированных ассоциативных контейнеров. Удачно подобранная функция хеширования позволяет выполнять вставки, удаления и поиск за постоянное, не зависящее от п, время. Кроме того, она обеспечивает равномерное распределение хешированных значений и минимизирует количество коллизий.
Примечание 1
Примечание 1
Поясним кратко суть хеширования. Она состоит в том, что каждому ключу (key) ставится в соответствие значение (value). Например, ключом могло бы быть имя абонента — строка символов, а значением — номер его телефона. Поиск значения по ключу осуществляется с помощью хеш-таблицы (hash table), которая ассоциирует ключевой объект с объектом типа значение. Эффективность работы зависит от алгоритма хеширования, который преобразует ключ в число из какого-то диапазона. Это число еще не value, а скорее индекс для выбора значения (value). При этом возможна ситуация коллизии (collision), когда два разных ключа будут преобразованы в одно и то же число. В таких случаях производится обработка коллизии по специальному алгоритму. Обычно используются списки для хранения ключей, случайно попавших в коллизию, или, как говорят, в одно ведро (bucket). Списки — это потеря эффективности поиска, но хорошие алгоритмы хеширования гарантируют очень низкую вероятность коллизий.
Если ключи не уникальны, то можно выбрать не hаsh_mар-контейнер, а контейнер типа hash_multimap. Если нужно просто хранить множество каких-то объектов, например строк текста, не ассоциируя их с другими объектами, то стоит подумать о контейнере типа hash_set. Ну а в случае, если среди этих объектов могут попасться одинаковые, то выбором может стать контейнер типа hash_multiset.
Хешируемые типы контейнеров все-таки упорядочивают контролируемую ими последовательность, вызывая встроенный в него объект hash Traits класса value_compare. Вы имеете доступ к этому объекту с помощью метода key_comp. В общем случае два элемента признаются либо одинаковыми, либо какой-либо из них признается меньшим. Но реальная упорядоченность элементов зависит от функции хеширования, функции, задающей отношение порядка и текущего размера хэш-таблицы, поэтому в общем случае невозможно предсказать порядок следования элементов. Важной характеристикой ассоциативных контейнеров является то, что вставка элементов не портит итераторы, а удаление делает недействительными только те итераторы, которые указывают на удаляемый элемент.
с приоритетами тоже является адаптером,
|
Контейнеры типа priority_queue |
Использование STL
Использование STL
В подобных ситуациях владение стандартными динамическими структурами данных и алгоритмами может сэкономить массу усилий, так как их разработчики уже выполнили большую часть неблагодарной черновой работы, тщательно отладили динамику жизни структур данных и все ветви алгоритмов. Кроме того, они провели анализ эффективности алгоритмов и привели их оценки. Сравним для примера две реализации алгоритма сортировки. Все знают, что рекурсивный алгоритм быстрой сортировки Quicksort, —изобретенный С. A. R. Ноаге в 1960 году, считается одним из самых эффективных в смысле количества необходимых операций для выполнения работы. Так, для сортировки массива в п элементов этому алгоритму понадобится всего лишь O(n Iog2 n) операций.
В библиотеке, подключаемой файлом заголовков stdlib.h, есть функция qsort, которая использует алгоритм Quicksort для сортировки массива элементов произвольного типа. Кроме сортируемого массива в функцию qsort необходимо передать адрес функции, которая сравнивает два элемента между собой. Алгоритм использует это сравнение для упорядочивания массива. Следующая программа демонстрирует, как можно воспользоваться функцией qsort для сортировки массива целых, вводимого пользователем. Для ее отладки я воспользовался проектом Console консольного типа, процедура создания которого была описана ранее. Из-за ошибок, связанных с использованием бета-версии Studio.Net, мне пришлось изменить конфигурацию проекта с Debug на Release. Это можно сделать, дав команду Build > Configuration Manager и выбрав Release в окне Active Solution Configuration:
#include <stdlib.h>
#include <iostream>
using namespace std;
//=== Внешняя функция сравнения переменных типа int
inline int crop (const void *a, const void *b)
{
int i = *(int *)a, j = *(int *)b;
return (i < j) ? -1 : (i > j) ? 1 : 0;
}
void main()
{
int array [1024],
// Сортируемый массив n - 0;
// Счетчик элементов
cout «"Enter some integers (Press Ctrl+z to stop)\n";
//=== Вводим по принципу "пока не надоест". Для выхода
//=== из цикла надо ввести EOF (то есть Ctrl+z, Enter)
while (cin » array[n++])
//==== Шаг назад, так как мы сосчитали EOF n—;
qsort (array, n, sizeof(int), cmp) ;
for (int i = 0; i < n; i++)
cout « array[i] « endl;
cout « endl;
}
Теперь сравним этот фрагмент с тем, который использует стандартный контейнер vector и алгоритм sort из библиотеки STL (Standard Template Library):
#include <algorithm>
#include <vector>
#include <iostream>
using namespace std;
void main ()
{
vector<int> v; // Сортируемый контейнер
int i; // Рабочая переменная
cout «"Enter some integers (Press Ctrl+z to stop)\n";
while (cin » i) // Вводим те же числа
v.push_back (i); // Помещаем в конец контейнера
//======= Сортируем контейнер, используя тип
//======= упорядочения, принятый по умолчанию
sort (v.begin () , v.end());
for (i =0; i < int(v.size()); i++)
cout « v[i] « endl;
cout « endl;
}
По умолчанию алгоритм sort использует для сравнения элементов операцию меньше, то есть сортирует контейнер по возрастанию. Сравнительная оценка эффективности двух реализаций, которую проводили специалисты (числа, конечно, вводились не вручную), показывает, что эффективность второй версии выше в 10-20 раз. Она зависит от размера массива и степени его упорядоченности. Приведем одну из причин такого результата.
Универсальность второго подхода реализуется за счет настройки шаблона на конкретный тип переменных, что происходит на этапе компиляции.
Важно помнить, что рекурсия сама по себе стоит дорого, поэтому важны детали реализации конкретного алгоритма. Над деталями реализации алгоритмов библиотеки STL потрудились специалисты, и результатом их труда является достаточно высокая эффективность, которую отмечают многие разработчики. К сожалению, возможности STL очень скудно описаны в MSDN, хотя в мире существуют книги, где библиотека и технология ее использования для решения конкретных задач описаны достаточно подробно. Среди доступных нам книг на русском языке, конечно, следует отметить последнюю книгу Б. Страуструпа «Язык программирования C++», 3-е изд. — СПб: «Невский Диалект», 1999. Но она описывает библиотеку концептуально. В ней почти нет текстов программ, готовых к употреблению в среде Visual Studio. Поэтому мне захотелось дать быстрый путь к овладению некоторыми возможностями библиотеки тем читателям, которые обладают хорошим алгоритмическим мышлением, имеют некоторый опыт работы с динамическими структурами данных, но не знакомы с особенностями структуры и использования STL. Ниже будут приведены примеры практического использования контейнеров и алгоритмов STL, но не будет подробного описания заложенных в них принципов.
Из жизни студентов
Из жизни студентов
Использование STL
Вектор объектов класса
Предикаты и функциональные объекты
Связыватели и адаптеры
Последовательности
Контейнеры
Работа с потоками
Полезные константы
Как показывает практика, студенты по-разному относятся к тому факту, что доля курсовых проектов, которые необходимо выполнять в виде компьютерных приложений, непрерывно растет. Некоторые их очень любят, так как подобные проекты позволяют продемонстрировать неординарность мышления, изобретательность и свой собственный «неподражаемый» стиль программирования, другие ненавидят, так как работающее приложение невозможно создать без тщательной проработки почти всех деталей, в том числе и тех, которые кажутся мелкими и незначительными. Сначала компилятор языка, а затем и операционная система хладнокровно бракуют малейшую неточность, непоследовательность, недоговоренность и пренебрежение деталями. В устном докладе и даже в письменном отчете можно скрыть или завуалировать перечисленные дефекты, но компьютерный проект обнажит их, продемонстрирует со всей очевидностью, а зачастую и усилит.
Контейнер типа set
Контейнер типа set
Множество (set) является ассоциативным контейнером, который хранит объекты типа key. В этом случае говорят о типе Simple Associative Container, имея в виду, что как value, так и key имеют один тип key. Говорят также о Unique Associative Container, имея в виду, что в контейнере типа set не может быть одинаковых элементов. Рассмотрим работу контейнера на примерах. Не забудьте вставить директиву #include <set>:
void main ()
{
//======== Создаем множество целых
set<int> s;
s.insert(1);
s.insert(2);
s.insert (3);
//======= Повторно вставляем единицу (она не пройдет)
s.insert (1);
//==== Два раза вставляем "в конец последовательности"
s. insert (--s.end() , 4); s.insert(—s.endO, -1);
pr(s,"Set of ints");
//======== Второе множество
set<int> ss;
for (int i=l; i<5; i++) ss.insert (i*10);
//======== Вставляем диапазон
s. insert (++ss. begin () , —s s.end() );
pr(s, "After insertion"); cout«"\n\n";
}
Эта программа выведет в окно Output следующие строки:
Set of ints # Sequence:
1. -1
2. 1
3. 2
4. 3
5. 4
After insertion # Sequence:
1. -1
2. 1
3. 2
4. 3
5. 4
6. 20
7. 30
Как видно из распечатки, несмотря на то что и 4 и -1 были вставлены в конец последовательности, контейнер сам распорядился порядком следования и разместил элементы в порядке возрастания ключей. Вставка диапазона из другого множества также происходит по этим законам. Следующий содержательный пример я обнаружил на сайте компании Silicon Graphics. Он приведен в слегка измененном виде:
//========= Предикат
inline bool NoCase(char a, char b)
{
// Определяет отношение less для обычных символов
// без учета регистра (Подключите stdlib.h)
return tolower(a) < tolower (b) ; !;
}
//========= Функциональный объект
struct LessStr
{
//==== Определяет отношение less для C-style строк
bool operator()(const char* a, const char* b) const
{
return strcmp(a, b) < 0;
}
};
Два отношения порядка для типов данных, хорошо вам знакомых (char и char*), для разнообразия заданы: одно в виде предиката, другое в виде функционального объекта. Ниже они будут использованы в конструкторе шаблона классов set. Тем самым определен порядок сортировки элементов контейнера:
void main ()
{
//====== Обычные неупорядоченные массивы символов
const int N = 6; const char* a[N] =
{
"Set", "Pet", "Net", "Get", "Bet", "Let"
};
const char* b[N] =
{
"Met", "Wet", "Jet",
"Set", "Pet", "Net",
} ;
//======== Создаем два множества обычных строк,
//======== определяя отношение порядка
set<const char*, LessStr> A(a, a + N);
set<const char*, LessStr> B(b, b + N);
//======== Создаем пустое множество
set<const char*, LessStr> C;
//======== Выходной итератор привязываем к cout
cout « "Set A: {";
copy (A.begin (), A.end.(),
ostream_iterator<const char*>(cout, "; "));
cout « ' } ' ;
cout « "\n\nSet B:
copy (B.begin (), B.end(), .. ostream_iterator<const char*>(cout, ", "));
//======= Создаем и выводим объединение двух множеств
cout « "\n\nUnion A U В: ";
set_union (A.begin () , A.end(), B.begin(), B.end(),
ostream_iterator<const char*>(cout, ", "),
LessStr () )';
//======= Создаем и выводим пересечение двух множеств
cout « "\n\nlntersection А & В: ";
set_intersection (A.begin () , A.end(), B.beginO, B.end(), ostream_iterator<const char*>(cout, " "), LessStrO);
//===== Создаем разность двух множеств
//===== Используем inserter для заполнения множества С
set_dif ference (A.begin () , A.end(), B.beginO, B.end(),
inserter (С, C.begin()),
LessStr() ) ;
cout « "\n\nDifference A/B: ";
//===== Копируем множество прямо в выходной поток сору
С. begin () , С.
end ();
ostream_iterator<const char*>(cout, " "));
С. clear () ;
//===== Повторяем в обратную сторону
set_dif ference (В. begin () , B.endO, A.begin(), A.end(),
inserter (С, C.begin()), LessStrO);
cout « "\n\nDifference B/A: ";
copy (C.begin (), C.end(),
ostream_iterator<const char*>(cout, " "));
cout « "\n\n";
//====== Выводим разделитель
vector<char> line(50, ' = ');
ostream_iterator<char> os(cout, "") ;
copy (line .begin О , line.endO, os) ;
//====== Обычные массивы символов
char D[] = { 'a', 'b', 'с', 'd', ' e', 'f' };
char E[] = { 'A', 'B', 'C1, 'G', 'H1, 'H' };
cout « "\n\nSet D: ";
for (int i=0; i<N; i++) cout « D[i] « ", ";
cout « "\n\nSet E: ";
for (int i=0; i<N; i + -i-)
cout « E[i]«",";
cout « "\n\nSymmetric Difference D/E (nocase): ";
//====== Используем алгоритм set_symmetric_difference
//====== для обычных массивов символов
set_symmetric_difference(D, D + N, E, E + N,
ostream_iterator<char>(cout, " "), NoCase);
cout«"\n\n"; }
Новые возможности STL, которые использованы в этом фрагменте, — это использование адаптера insert_iterator и копирование содержимого контейнера прямо в выходной поток (см. ostream_iterator). Вывод в поток осуществляется с помощью особого типа итератора ostream_iterator, который осуществляет форматируемый вывод объектов типа Т в указанный выходной поток (ostream). Шаблон класса ostream_iterator настраивается на тип данных, в нашем случае const char*, а затем char, и берет в качестве параметров объект потокового вывода (cout) и разделитель, который мы специально изменяем по ходу дела для того, чтобы вы его обнаружили.
Insert_iterator — это адаптер (настройщик) итератора, который настраивает операнд, являющийся мишенью операции. Присвоение с помощью (сквозь призму) такого итератора вставляет объект в контейнер, раздвигая его, то есть, используя метод insert. Он следит за текущей позицией в контейнере (insertion point) и производит вставку перед ней. Здесь вы, однако, должны учесть различную семантику операции вставки в различные типы контейнеров. Если это последовательность (sequence), то все происходит именно так, как только что было сказано, но если это сортируемый ассоциативный контейнер, то вы не можете управлять позицией вставки. Для таких контейнеров указание места вставки служит лишь отправной точкой для поиска реальной позиции в контейнере. В результате вставки при выводе вы увидите упорядоченную по возрастанию ключа последовательность. Порядок вставки в сортируемые ассоциативные контейнеры не влияет на порядок элементов, который вы увидите на экране. Однако он может повлиять на эффективность процесса вставки.
Пары
Парой называется шаблон класса, который хранит пару объектов различного типа. Пара похожа на контейнер в том, что она владеет своими элементами, но она не является контейнером, так как не поддерживает стандартных методов и итераторов, присущих контейнерам. У пары есть два элемента данных (first, second), которые дают возможность манипулировать вложенными объектами. Следующий фрагмент иллюстрирует логику использования пары:
pair<bool, double> result = FindRoot();
if (result.first)
print(result.second);
else
report_error() ;
Ассоциативные контейнеры используют тип пар _Pairib. Он определяет пару:
pair<iterator, bool>
Первый элемент каждой такой пары является итератором соответствующего типа, а второй — результатом какого-либо действия. Например, метод insert возвращает пару типа _Pairib, анализируя которую вы можете узнать результат вставки (успех или неудача). Рассмотрим пример:
void main ()
{
//========== Массив объектов класса Man
Man ar[] =
{
joy,duke, win, joy,charlie
);
uint size = sizeof(ar)/sizeof(Man);
//========== Создаем множество объектов класса Man
set<Man> s (ar, ar+size); pr(s, "Set of Man");
//========== Ищем объект и удаляем его
set<Man>::iterator p = s.find(joy);
if (p != s.end() )
{
s.erase(p);
cout « "\n\n"« joy «" found and erased";
}
pr(s,"After erasure");
//========== Объявляем пару
set<Man>::_Pairib pib;
//========== Пробуем вставить объект
pib = s.insert(joy);
//========== Анализируем результат вставки
cout « "\n\nlnserting: " « *pib.first « "\nResult is: " « pib.second;
//========== Пробуем вставить повторно
pib = s.insert(joy);
cout « "\n\nlnserting: " « *pib.first « "\nResult is: " « pib.second;
//========== Сравниваем ключи
cout « "\n\ns.key_comp() (zoran,count) returned "
« s.key_comp()(zoran,ar[0]);
cout « "\n\ns.key_comp()(count,zoran) returned "
« s.key_comp()(ar[0],zoran);
cout <<"\n\n";
}
Приведем результат работы этой программы:
Set of Man # Sequence:
1. Joy Amore, Age: 18
2. Winton Kelly, Age: 50
3. Charlie Parker, Age: 60
4. Duke Ellington, Age: 90
Joy Amore, Age: 18 found and erased After erasure # Sequence:
1. Winton Kelly, Age: 50
2. Charlie Parker, Age: 60
3. Duke Ellington, Age: 90
Inserting: Joy Amore, Age: 18
Result is: 1
Inserting: Joy Amore, Age: 18
Result is: 0
s.key_comp()(zoran,count) returned 0 s.key_comp()(count,zoran) returned 1
Контейнеры библиотеки STL
Контейнеры библиотеки STL
Теперь, когда вы вспомнили, что такое шаблоны функций и шаблоны классов, мы можем исследовать возможности стандартной библиотеки шаблонов STL. В июле 1994 года специальный комитет Международной организации по принятию стандартов (ANSI/ISO C++) проголосовал за то, чтобы принять STL в качестве части стандарта языка C++. Предложение было основано на исследовании обобщенного (generic) программирования и концепции библиотеки (generic software library), которое проводили Alex Stepanov, Meng Lee и David Musser. Главной целью при разработке библиотеки было достижение общности (generality) подхода к различным структурам данных и алгоритмам их обработки без ущерба эффективности кода.
В STL определены два типа контейнеров — последовательности (sequence containers) и ассоциативные контейнеры. Все контейнеры предназначены для хранения данных любого типа. Последовательности предполагают последовательный доступ к своим элементам, а ассоциативные контейнеры работают по принципу ассоциации ключа (key) с его значением (value). Можно считать, что ассоциативные контейнеры хранят пары произвольных элементов и производят поиск по ключу, используя технику hash-таблиц. В STL существует три типа последовательных контейнеров: vector, deque И list.
Контейнеры типа hash_multimap
Контейнеры типа hash_multimap
Хешированный ассоциативный контейнер типа hash_multimap основан на встроенной реализации хэш-таблиц. Вы помните, что преимуществом такого типа контейнеров является быстродействие, которое в среднем значительно выше, чем у сортированных ассоциативных контейнеров. Упорядоченность элементов в таком контейнере не гарантируется, но вы можете по определенной системе добывать их С ПОМОЩЬЮ метода hash_multimap: :equal_range.
Предположим, что ваша база данных содержит сведения о сотрудниках — объектах класса Man, многих отделов какой-то организации. В примере мы возьмем только два отдела (100 и 115). Так как мы хотим быстро получать информацию о сотрудниках, то выбираем в качестве структуры для хранения данных в памяти хешированный ассоциативный контейнер. Очевидно, что если в качестве ключевого поля для него выбрать номер отдела, то поле не будет уникальным. Этот факт окончательно определяет выбор типа контейнера— hash_multimap.
Вы также, вероятно, помните, что все контейнеры типа тар — это Pair Associative контейнеры, так как они хранят пары типа pair<const Key, Data>. В нашем случае этой парой является pair<int, Man>, где первый элемент задает номер отдела, а второй сотрудника этого отдела. Для удобства пользования контейнером введем новые типы данных:
//======= ManPair - это тип используемых пар
typedef pair <int, Man> ManPair;
//======= ManMap - это тип контейнера
typedef hash_multimap <int, Man> ManMap;
//======= ManMapIt — это тип итератора
typedef ManMap::const_iterator ManMapIt;
Отметьте, что мы выбрали самый простой способ определения контейнера. Более точным описанием, которое намекает вам на возможность усложнения структуры, будет:
typedef hash_multimap <int, Man,
hash_compare <int, less<int> > > ManMap;
Отсюда ясно, что можно изменить предикат, по которому производится сравнение элементов контейнера. Для выбора всех сотрудников определенного отдела мы собираемся использовать метод:
equal_range(int /*Номер отдела*/);
который возвращает пару итераторов. Первый итератор пары указывает на начало диапазона внутри контейнера из сотрудников указанного отдела, а второй — на конец этого диапазона. Теперь пора в бой. Надо писать код, реализующий работу контейнера.
void main( )
{
typedef pair <int, Man> ManPair;
typedef hash_multimap <int, Man> ManMap;
typedef ManMap::const_iterator ManMapIt;
//====== Создаем пустой контейнер типа hash_multimap ManMap h;
//====== Наполняем его сотрудниками
h.insert (ManPair (100, тагу));
h.insert (ManPair (115, joe));
h.insert (ManPair (100, win));
h.insert (ManPair (100, charlie));
h.insert (ManPair (115, liza));
h.insert TManPair (115, joy));
//====== При выводе пользуемся парой
cout « "Contents of Hash Multimap\n\n";
for (ManMapIt p = h.begin();
p != h.end(); p++)
cout « "\n" « p->first
«". " « p->second;
//====== Выбираем диапазон (сотрудники 100-го отдела)
pair<ManMap!t, ManMapIt> pp = h.equal_range(100);
//====== Вновь пользуемся парой
cout « "\n\nEmployees of 100 department\n\n";
for (p = pp.first; p != pp.second; ++p)
cout « "\n" « p->first
«"." « p->second; cout « "\n\n";
}
He лишнее напомнить, что приведенный код надо дополнить объявлениями объектов класса Man и вставкой директивы #include <hash_map>. Директивы должны копиться. Я надеюсь, что с этой задачей вы справитесь самостоятельно. Объявления людей мы приводили где-то в начале урока. Программа должна произвести такой вывод:
Contents of Hash Multimap
115. Liza Dale, Age: 17
115. Joy Amore, Age: 18
115. Joe Doe, Age: 30
100. Winton Kelly, Age: 50
100. Charlie Parker, Age: 60
100. Mary Poppins, Age: 36
Employees of 100 department
100. Winton Kelly, Age: 50
100. Charlie Parker, Age: 60
100. Mary Poppins, Age: 36
Контейнеры типа map
Контейнеры типа map
Отображение (map) является сортируемым ассоциативным контейнером, который ассоциирует объекты типа key с объектами типа value. Map — это Pair Associative Container, так как он хранит пары типа pair<const Key, Data>. Говорят также о Unique Associative Container, имея в виду, что в контейнере типа тар не может быть одинаковых элементов. Отображения являются одними из самых мощных и удобных типов контейнеров. Рассмотрим их работу на примерах. Не забудьте вставить директиву #include <map>:
void main ()
{
//========= Создаем отображение строки в целое
map<string,int> m;
map<string,int>::_Pairib pib;
map<string,int>::iterator it;
//========= Создаем новый тип для удобства
typedef pair<string, int> MyPair; MyPair p("Monday", 1); m.insert(p);
//========= Изменяем компоненты пары
p.first = "Tusday";
p.second = 2;
pib = m.insert(p);
cout « "\n\nlnserting: "
« (*pib.first).first « ","
« (*pib.first).second
« "\nResult is: " « pib.second;
pib = m.insert(p);
cout « "\n\nlnserting: "
« (*pib.first).first « ","
« (*pib.first).second
« "\nResult is: " « pib.second;
//========= Работаем с индексом
m["Wednesday"] = 3;
m["Thirsday"] = 4;
m["Friday"] = 5;
//========= Работаем с динамической памятью
MyPair *pp = new MyPair("Saturday", 6);
m.iftsert(*pp);
delete pp;
cout«"\n\n\t <string,int> pairs :\n";
for (it = m.begin ();
if != m.end(); it++)
cout « "\n(" « it->first«","<<it->second«") ";
cout«"\n\n";
}
Результат работы этого фрагмента выглядит так:
Inserting: Tusday, 2 Result is: 1
Inserting: Tusday, 2 Result is: 0
<string,int> pairs:
(Friday, 5) (Monday, 1) (Saturday, 6) (Thirsday, 4) (Tusday, 2) (Wednesday, 3)
Как видите, пары отсортированы в лексикографическом порядке. Если потребуется восстановить естественный порядок, то это можно сделать, поменяв порядок следования аргументов при объявлении шаблона на
map<int, string> m;
Такую замену придется сделать и для всех других, связанных с шаблоном типов данных. Отметьте также, что при работе с отображениями недостаточно разадресо-вать итератор (*it), чтобы получить объект им указываемый. Теперь вы должны писать (*it) .first или it->first, чтобы получить какой-то объект. Характерно, что эти выражения могут стоять как в левой, так и в правой части операции присвоения, то есть вы можете записать:
it->first = "Sunday";
int n = it->second;
Контейнеры типа queue
Контейнеры типа queue
Очередь — это тоже,адаптер, который предоставляет ограниченное подмножество функциональности контейнера. Говорят, что очередь — это структура данных с дисциплиной доступа "first in first out" (FIFO). Элементы, вставляемые в конец очереди, могут быть выбраны спереди. Это означает, что метод queue:: front () возвращает самый «старый» элемент, то есть тот, который был вставлен в очередь least recently — первым из тех, что еще живы. Очередь, так же как и стек, не допускает итераций прохода по своим элементам. По умолчанию она основана на контейнере типа deque. Сравнение стека и очереди приведены в следующем фрагменте (Подключите <queue>):
void main ()
{
//========== Массив объектов класса Man
Man ar[] =
{
joy, mаrу, win
};
uint size = sizeof(ar)/sizeof(Man);
//========== Создаем с.тек объектов класса Man
stack<Man> s;
for (uint i=0; i<size; i++) s.push(ar[i]);
cout « "Stack of Man:\n\n";
while (s.size ())
{
cout « s.top() « "; ";
s.pop ();
}
//========== Создаем очередь объектов класса Man
queue<Man> q;
for (i=0; Ksize; i++) q.push(ar[i]);
cout « "\n\nQueue of Man:\n\n";
while (q.size ())
{
cout « q.front() « "; ";
q.pop(); }
cout«"\n\n";
}
Поиск с помощью предиката
Поиск с помощью предиката
Поиск первого объекта, который удовлетворяет условию, заданному предикатом, осуществляется с помощью шаблона функции f ind_if. В качестве третьего, параметра она требует задать имя функции-предиката. Введите в состав класса объявление такой функции:
//========= Предикат принадлежности к teenager
friend bool Teen (Man& m);
Тело этой функции определите глобально, то есть вне класса:
//========= Предикат принадлежности к teenager
bool Teen(Man& m)
{
return 13 < m.m_Age && m.m_Age < 19;
}
Теперь покажем, как искать в контейнере первый элемент, удовлетворяющий предикату, а также все элементы, удовлетворяющие этому условию. Ниже нам понадобятся несколько объектов класса Man, поэтому мы ввели их объявление в начало функции main. Далее везде мы будем считать, что эти объекты присутствуют в функции main, но не будем приводить их заново:
void main ()
{
//======== Набор объектов класса Man
Man joe("Joe Doe",30),
joy ("Joy Amore", 18) ,
Mаrу("Mary Poppins",36),
duke("Duke Ellington",90),
liza("Liza Dale", 17),
simon("Simon Paul",15),
zoran("Zoran Todorovitch",27) ,
Charlie("Charlie Parker",60),
win("Winton Kelly",50),
mela("Melissa Robinson",9);
vector<Man> men;
men.push_back (zoran);
men.push_back (liza);
men.push_back (simon);
men.push_back (mela);
// Поиск первого объекта, удовлетворяющего предикату
vector<Man>::iterator p =
find_if (men .begin () ,
men.endO, Teen);
//======== Ручной поиск всех таких объектов
while (p != men.end())
{
cout « "\nTeen: " « *p;
p = find_if(++p, men.endO, Teen);
}
cout « "\nNo more Teens\n";
//======== Подсчет всех teenagers
uint teen = count_if (men.begin (),men.endO , Teen);
cout « "\n\n Teen totals: " « teen;
//======== Выполняем функцию для всех объектов
for_each(men.begin(),men.end(),OutTeen) ;
//======== Используем обратный итератор
cout«"\n\nMan in reverse\n";
for (vector<Man>::reverse_iterator
r = men.rbegin();
r != men.rendO; r++) cout«*r«";
//======== Заполняем вектор целых
vector<int> v;
for (int i=l; i<4; i++) v.push_back(i);
//======== Иллюстрируем алгоритм и адаптивный functor
transform(v.begin () , v.end(), v.begin (), negate<int> () ) ;
pr(v,"Integer Negation");
//======== Создаем еще два вектора целых
vector<int> vl(v.size()), v2 (v.size());
//======== Иллюстрируем алгоритм заполнения вектора
fill (vl.begin (), vl.endO, 100);
//======== Иллюстрируем проверку
assert (vl .size () >= v.size() && v2.size() >= v.sizeO);
//======== Иллюстрируем вторую версию transform
transform(v.begin(), v.end(), vl.begin(), v2.begin(),
plus<int>() ) ;
pr(v2,"Plus");
cout « "\n\n";
}
В рассмотренном фрагменте мы иллюстрируем использование алгоритма count_if, который проходит по заданному диапазону последовательности и возвращает количество объектов, удовлетворяющих предикату. Алгоритм f or_each позволяет выполнить определенное действие для заданного диапазона последовательности. В примере функция OutTeen вызывается для всех элементов контейнера. Приведем тело этой функции:
void OutTeen(Man& m)
{
// Если парамтр удовлетворяет предикату, то выводим его
if (Teen(m))
cout « "\nTeen: " « m;
}
Далее в коде демонстрируется, как использовать обратный итератор reverse_ iterator. Для него справедливы позиции rbegin — последний элемент последовательности и rend — барьер, ограничивающий последовательность спереди. Операция ++ сдвигает итератор на один элемент в сторону к началу последовательности.
Последний фрагмент функции main демонстрирует использование алгоритма transform, который воздействует на каждый элемент указанного диапазона и модифицирует его в соответствии либо с unary function (первая версия), либо с binary function (вторая версия). Суть модификации определяется последним параметром. В нашем случае мы используем negator (отрицатель) и бинарную операцию plus, настроенную на тип int. Сложить два контейнера можно и другими способами.
Если вы подключите файл заголовков <assert. h>, то сможете осуществлять логические проверки с помощью функции assert. Она проверяет свой аргумент и, если он равен false, выводит на экран сообщение вида:
Assertion failed: s.topQ == joy,
file C:\My ProjectsXStack.cpp, line 29
abnormal program termination
Затем прекращает процесс вызовом функции abort. Если результатом выражения (аргумента функции assert) будет true, то выполнение продолжается.
Полезные константы
Полезные константы
STL имеет много полезных констант. Проверьте свои знания основ информатики. Знаете ли вы смысл констант, приведенных ниже? Для их использования вам потребуется подключить такие файлы заголовков:
#include <limits>
#include <climits>
#finclude <cfloat>
#finclude <numeric>
Вот фрагмент, который выводит некоторые из констант и по-английски описывает их смысл. Русский язык отказывается работать на моем компьютере в окне консольного приложения. Думаю, что существуют программисты, которые зарабатывают свой хлеб, имея смутное представление о существовании этих констант:
//===== Сначала простые, которые знают все
cout « "\n Is a char signed? "
« numeric_limits<char>::is_signed;
cout « "\n The minimum value for char is: "
« (int)numeric_limits<char>::min();
cout « "\n The maximum value for char is: "
« (int)numeric_limits<char>::max();
cout « "\n The minimum value for int is: "
« numeric_limits<int>::min();
cout « "\n The maximum value for int is: "
« numeric_limits<int>::max();
cout « "\n Is a integer an integer? "
« numeric_limits<int>::is_integer;
cout « "\n Is a float an integer? "
« numeric_limits<float>::is_integer;
cout « "\n Is a integer exact? "
« numeric_limits<int>::is_exact;
cout « "\n Is a float exact? "
« numeric_limits<float>::is_exact;
//===== Теперь более сложные
cout « "\n Number of bits in mantissa (double) : "
« DBL_MANT_DIG; cout « "\n Number of bits in mantissa (float): "
« FLT_MANT_DIG;
cout <<"\n The number of digits representble " "in base 10 for float is "
« numeric_limits<float>::digitslO;
cout « "\n The radix for float is: "
« numeric_limits<float>::radix;
cout « "\n The epsilon for float is: "
« numeric_limits<float>::epsilon() ;
cout « "\n The round error for float is: "
« numeric_limits<float>::round_error();
cout « "\n The minimum exponent for float is: "
« numeric_limits<float>::min_exponent;
cout « "\n The minimum exponent in base 10: "
« numeric_limits<float>::min_exponentlO;
cout « "\n The maximum exponent is: "
« numeric_limits<float>::max_exponent;
cout « "\n The maximum exponent in base 10: "
« numeric_limits<float>::max_exponentlO;
cout « "\n Can float represent positive infinity? "
« numeric_limits<float>::has_infinity;
cout « "\n Can double represent positive infinity? "
« numeric_limits<double>::has_infinity;
cout « "\n Can int represent positive infinity? "
« numeric_limits<int>::has_infinity;
cout « "\n Can float represent a NaN? "
« numeric_limits<float>::has_quiet_NaN;
cout « "\n Can float represent a signaling NaN? "
« numeric_limits<float>::has_signaling_NaN;
//===== Теперь еще более сложные
cout « "\n Does float allow denormalized values? "
« numeric_limits<float>::has_denorm;
cout « "\n Does float detect denormalization loss? "
« numeric_limits<float>::has_denorm_loss;
cout « "\n Representation of positive infinity for"
" float: "« numeric_limits<float>::infinity();
cout « "\n Representation of quiet NaN for float: "
« numeric_limits<float>::quiet_NaN();
cout « "\n Minimum denormalized number for float: "
« numeric_limits<float>::denorm_min();
cout « "\n Minimum positive denormalized value for"
" float " « numeric_limits<float>::denorm_min();
cout « "\n Does float adhere to IEC 559 standard? "
« numeric_limits<float>::is_iec559; cout « "\n Is float bounded? "
« numeric_limits<float>::is_bounded;
cout « "\n Is float modulo? "
« numeric_limits<float>::is_modulo;
cout « "\n is int modulo? "
« numeric_limits<float>::is_modulo;
cout « "\n Is trapping implemented for float? "
« numeric_limits<float>::traps;
cout « "\n Is tinyness detected before rounding? "
« numeric_limits<float>::tinyness_before;
cout « "\n What is the rounding style for float? "
« (int)numeric_limits<float>::round_style;
cout « "\n What is the rounding style for int? "
« (int)numeric_limits<int>::round_style;
//===== Теперь из другой оперы
cout « "\n Floating digits " « FLT_DIG;
cout « "\n Smallest such that 1.0+DBL_EPSILON !=1.0: "
« DBL_EPSILON;
cout « "\n LDBL_MIN_EXP: " « LDBL_MIN_EXP;
cout « "\n LDBL_EPSILON: " « LDBL_EPSILON;
cout « "\n Exponent radix: " « _DBL_RADIX;
Незнание констант типа DBL_EPSILON или DBL_MANT_DIG довольно сильно ограничивает квалификацию программиста, поэтому советую внимательно исследовать вывод, производимый данным фрагментом, и, возможно, обратиться к специальным изданиям по архитектуре компьютера или учебникам с целью ликвидировать пробелы в знаниях в этой области.
Последовательности типа deque
Последовательности типа deque
Контейнер типа deque (очередь с двумя концами) похож на vector в том смысле, что допускает выбор элемента по индексу и делает это быстро. Отличие состоит в том, что он умеет эффективно вставлять новые элементы как в конец, так и в начало последовательности. Deque не имеет некоторых методов, которые имеет vector, например capacity и reserve. Вместо этого он имеет методы, которых нет у вектора, например push_f ront, pop_back и pop_f ront. Далее мы будем исследовать возможности различных контейнеров, и каждый новый контейнер требует подключения своего файла заголовков. В данный момент не забудьте вставить директиву препроцессора tinclude <deque>:
void main ()
{
deque<double> d;
d.push_back(0.5) ;
d.push_back(l.);
d.push_front(-1.);
pr(d,"double Deque");
//======== Ссылки на два крайних элемента
deque<double>::reference
rf = d.front(),
rb = d.back();
//======== Присвоение с помощью ссылок
rf = 100.;
rb = 100.;
pr(d,"After using reference");
//======== Поиск с помощью связывателя
deque<double>::iterator p = find_if(d.begin(), d.end(),
bind2nd(less<double>(),100.));
//======== Вставка в позицию перед позицией,
//======== на которую указывает итератор
d.insert(p,-1.);
pr(d,"After find_if and insert");
//======== Второй контейнер
deque<double> dd(2,-100.);
//======== Вставка диапазона значений
d.insert (d.begin ()+1, dd.begin(), dd.end());
pr(d,"After inserting another deque");
cout«"\n\n";
}
Следующий фрагмент демонстрирует, как можно копировать контейнеры (сору) и обменивать данные между ними (swap). Шаблон функций find позволяет найти объект в любой последовательности. Он откажется работать, если в классе объектов не определена операция operator== (). Отметьте также, что после вставки или удаления элемента в контейнер типа deque все итераторы становятся непригодными к использованию (invalid), так как произошло перераспределение памяти. Однако удаление с помощью pop_back или pop_f ront портит только те итераторы, которые показывали на удаленный элемент, остальные можно использовать. При использовании фрагмент надо дополнить объявлениями объектов класса Man:
void main ()
{
deque<Man> men;
men.push_front (Man("Jimmy Young",16));
men.push_front (simon);
men.pushjoack (joy);
pr(men,"Man Deque");
//======== Поиск точного совпадения
deque<Man>::iterator p =
find(men.begin(),men.end() , joy);
men.insert(p,тагу);
pr(men,"After inserting тагу");
men.pop_back(); men.pop_front ();
pr(men,"After pop_back and pop_front");
p = find(men.begin(),men.end(),joy);
if (p == men.end())
cout « '\n' « joy « " not found!";
men.push_front(win); men.push_back(win);
pr(men,"After doubly push win");
//======== Второй контейнер
deque<Man> d(3,joy); men.resize(d.size ());
//======== Копируем d в men
copy(d.begin(), d.end(), men.begin()); pr(men,"After resize and copy");
//======== Изменяем контейнер
d.assign(3,win);
//======== Обмениваем данные
d.swap(men);
pr(men,"After swap with another deque"); cout«"\n\n";
}
Последовательности типа list
Последовательности типа list
Контейнеры типа list представляют собой двусвязные списки, то есть упорядоченные последовательности, допускающие проходы как вперед, так и назад. Операции вставки и удаления одинаково эффективны в любое место списка. Однако операции поиска и выбора элементов линейны относительно размера контейнера. Выбор по индексу вовсе невозможен. Важным свойством списка является то, что операции вставки не портят итераторы, связанные с ним, а удаление делает недействительным только тот итератор, который указывал на удаленный элемент.
В шаблоне класса list определены методы merge, reverse, unique, remove и remove_if, которые оптимизированы для списков. Не путайте их с одноименными шаблонами функций, которые определены в алгоритмах. В примере, который приведен ниже, обратите внимание на операции слияния как списков, так и контейнеров различной природы. При исследовании списков не забудьте вставить директиву #include <list>, а также приведенный выше набор объектов класса Man:
void main 0
{
list<Man> men;
men.push_front(zorah);
men.push_back(mela);
men.push_back(joy);
pr(men,"Man List");
//======== Поиск объекта
list<Man>::iterator p = find (men.begin(),men.end(),mela);
//======== Вставка перед элементом
p = men.insert (p,joe);
// одного объекта men.insert(p,2,joe);
// двух объектов pr(men,"After inserting 3 joes");
//======== Удаление всех вхождений joe
men.remove(j oe);
men.sort(less<Man>() ) ;
pr(men,"After removing all joes and sort");
//======== Создаем второй список
list<Man> li(3,simon);
//======== Сливаем его с первым
. men.merge (li, less<Man>'() );
pr(men,"After merging with simons list");
//==== После слияния второй список полностью исчез
cout « "\n\tAfter merging simons li.size: "
« li.size() « endl;
men.remove(s imon);
//======== Создаем очередь
deque<Man> d(men.size());
//======== Копируем в нее список
copy(men.begin(), men.end(), d.begin());
pr(d,"Deque copied from list");
//======== Создаем вектор
vector<Man> v (men. size () + d.sizeO);
//==== Соединяем список и очередь и помещаем в вектор merge(men.begin(),men.end(),d.begin(),d.end(), v.begin() ) ;
pr(v,"Vector after merging list and deque");
pr(d,"Deque after merging with list");
cout«"\n\n";
}
После слияния (merge) двух списков (men и li) размер второго списка стал нулевым, так как он полностью влился в первый. При слиянии методом list: emerge элементы не копируются, а вливаются в список-мишень операции. При слиянии с помощью алгоритма merge контейнеры операнды остаются невредимыми, так как они копируются в контейнер-мишень. Если операнды операции слияния упорядочены, то при слиянии методом list::merge упорядоченность не нарушается, чего не наблюдается при слиянии шаблоном функции merge. Приведем для ясности результат работы рассматриваемой программы:
Man List # Sequence:
1. Zoran Todorovitch, Age: 27
2. Melissa Robinson, Age: 9
3. Joy Amore, Age: 18
After inserting 3 joes # Sequence:
1. Zoran Todorovitch, Age: 27
2. Joe Doe, Age: 30
3. Joe Doe, Age: 30
4. Joe Doe, Age: 30
5. Melissa Robinson, Age: 9 6. Joy Amore, Age: 18
After removing all joes and sort # Sequence:
1. Melissa Robinson, Age: 9
2. Joy Amore, Age: 18
3. Zoran Todorovitch, Age: 27
After merging with simons list # Sequence: 1. Melissa Robinson, Age: 9
2. Simon Paul, Age: 15
3. Simon Paul, Age: 15
4. Simon Paul, Age: 15
5. Joy Amore, Age: 18
6. Zoran Todorovitch, Age: 27
After merging Simons li.size: 0 Removing simons
Deque copied from list # Sequence:
1. Melissa Robinson, Age: 9
2. Joy Amore, Age: 18
3. Zoran Todorovitch, Age: 27
Vector after merging list and deque f Sequence:
1. Melissa Robinson, Age: 9
2. Joy Amore, Age: 18
3. Melissa Robinson, Age: 9
4. Joy Amore, Age: 18
5. Zoran Todorovitch, Age: 27
6. Zoran Todorovitch, Age: 27
Deque after merging with list # Sequence:
1. Melissa Robinson, Age: 9
2. Joy Amore, Age: 18
3. Zoran Todorovitch, Age: 27
Генерирование последовательности
С помощью алгоритма generate удобно создавать последовательности, имеющие строго определенную структуру. Например, если объявлен список целых из шести элементов, то его можно заполнить значениями, сгенерированными с помощью функции generate:
//========= Создаем список целых
list<uint> 1st (6);
//========= Генерируем степенную последовательность
generate (1st.begin (), Ist.end(), pows);
pr(1st,"List of generated powers");
Здесь pows — это внешняя функция, которая при каждом обращении возвращает возрастающую степень двойки. Эффект достигается за счет того, что static-переменная г инициализируется единицей во время компиляции, а затем помнит свое предыдущее значение:
uint pows()
{
static uint r = 1;
return r <= 1;
}
Если надо добиться обратного эффекта, то есть убрать закономерность в последовательности чисел, то можно воспользоваться шаблоном функции random_shuffle, которая переставляет элементы последовательности в одно из п! состояний. Например:
vector <int> v;
for (int i = 0; i <= 6; i++ ) v.push_back(i+1);
random_shuffle(v.begin() , v.end()) ;
pr(v,"Vector of shuffled numbers");
Последовательности типа vector
Последовательности типа vector
Для их использования необходимо подключить файл заголовков <vector> и сделать доступным (видимым) стандартное (std) пространство имен:
#include <vector> using namespace std;
Обратите внимание на отсутствие расширения .h в директиве подключения файла заголовков. Дело в том, что STL используется на множестве различных платформ с применением разных компиляторов. Файлы заголовков в разных условиях имеют разные расширения. Они могут иметь расширение Н, НРР или НХХ. Для того чтобы одинаково запутать всех разработчиков, было решено вовсе не использовать расширение для файлов заголовков библиотеки STL. Пространство имен std позволяет избежать конфликта имен. Если вы назовете какой-то свой класс тем же именем, что и класс из STL (например, string), то обращение вида std: : string однозначно определит принадлежность класса стандартной библиотеке. Директива using позволяет не указывать (многократно) операцию разрешения области видимости std: :, поэтому можно расслабиться и не писать std: : string, a писать просто — string.
Вектор является шаблоном класса, который настраивается с помощью двух параметров:
vector<class T, allocator<class T> >
Объект, который управляет динамическим выделением и освобождением памяти типа т, называется allocator. Для большинства типов контейнеров он обычно объявляется по умолчанию в конструкторе. Для «хитрых» данных, например требующих памяти в глобальном heap, видимо, можно изобрести индивидуальный распределитель памяти. Но в большинстве случаев работает вариант по умолчанию. Кроме того, с типом vector обычно связаны.4 типа сущностей:
Pointer — ведет себя как указатель на тип т; const pointer — не позволяет изменить данные типа т, на которые он указывает;reference — ссылки на данные типа т;
const reference— не позволяет изменить данные типа т, на которые она ссылается.
Обычно эти сущности являются тем, чем и должны являться, но это не гарантируется. Они могут быть более сложными объектами.
Итак, vector является аналогом обычного массива в языке С, за исключением того, что он может автоматически изменять память по мере надобности. Доступ к данным обеспечивается с помощью операции выбора [ ]. Вставка новых элементов эффективна только в конец контейнера (push_back). Удаление — тоже. Данные операции в начале или середине влекут сдвиги всего массива данных, что резко снижает эффективность работы контейнера. Такие операции называются линейными, имея в виду тот факт, что время их выполнения линейно зависит от количества элементов в контейнере. Вставка или удаление в конце называются константными операциями, так как время их выполнения является константой для данной реализации и не зависит от количества элементов. Вот простая программа, иллюстрирующая использование вектора. Так как в приложениях консольного типа обычно возникают проблемы с русификацией, то для вывода текста мы используем английский язык:
#include <vector>
#include <algorithm>
#include <iostream> using namespace std;
//======= Вводим тип для сокращения текста (места)
typedef unsigned int uint;
void main ()
{
//======== Вектор целых
vector<int> v(4);
cout « "\nlnt Vector:\n";
for (uint i=0; i<v.size(); i++)
{
v[i] = rand()%10 + 1;
cout « v[i] « "; ";
}
//======= Сортировка по умолчанию sort (v.begin (), v.end());
cout « "\n\nAfter default sort\n";
for (i=0; i<v.size(); i++) cout « v[i] « "; ";
//======== Удаление элементов
v.erase(v.begin());
cout « "\n\nAfter first element erasure\n";
for (i=0; i<v.size(); i++) cout « v[i] « "; ";
v. erase (v. end ()-2, v.endO);
cout « "\n\nAfter last 2 elements erasure\n";
for (i=0; i<v.size(); i++)
cout « v[i] « "; ";
//======== Изменение размеров
int size = 2; v.resize(size);
cout « "\n\nAfter resize, the new size: " « v.size()
« endl; for (i=0; i<v.size(); i++)
cout « v[i] « "; ";
v.resize(6,-1);
cout « "\n\nAfter resize, the new size: " « v.size()« endl;
for (i=0; i<v.size(); i++)
cout « v[i] « "; ";
//======== Статистика .
cout « "\n\nVector's maximum size: " « v.max_size() « "XnVector's capacity: " « v.capacity() « endl
//======== Резервирование
v.reserve (100);
cout « "\nAfter reserving storage for 100 elements:\n"
« "Size: " « v.sizeO « endl :
« "Maximum size: " « v.max_size() « endl
« "Capacity: " « v.capacity() « endl;
v.resize(2000);
cout « "\nAfter resizing storage to 2000 elements:\n"
« "Size: " « v.size() « end1
« "Maximum size: " « v.max_size() « end1
« "Capacity: " « v.capacity() « endl; cout « "\n\n";
}
Для того чтобы лучше уяснить смысл и различие методов size, resize, max_size и capacity, мы несколько раз повторяем вызовы этих методов. Если вы читаете книгу вдалеке от компьютера, то вам, возможно, будет интересно узнать, что программа выведет в окно консольного приложения:
Int Vector:
2; 8; 5; 1;
After default sort
1; 2; 5; 8;
After first element erasure
2; 5; 8;
After last 2 elements erasure 2;
After resize, the new size: 2,
Vector capacity: 4 2; 0 ;
After resize, the new size:
6 2; 0; -1; -1; -1; -1;
Vector's maximum size: 1073741823
Vector's capacity: 6 After reserving storage for 100 elements:
Vector's size: 6
Vector's maximum size: 1073741823
Vector's capacity: 100
After resizing storage to 2000 elements:
Vector's size: 2000
Vector's maximum size: 1073741823
Vector's capacity: 2000
Шаблон функции вывода содержимого контейнера
Демонстрация функционирования контейнеров требует часто выводить их содержимое, поэтому будет целесообразно написать шаблон функции, которая выводит содержимое контейнера любого типа. Первый параметр (т& v) функции рг () задает тип контейнера. Он же является параметром шаблона. Второй параметр (string s) задает строку текста (заголовок), который будет выведен в начале блока данных контейнера:
//===== Шаблон функции для вывода с помощью итератора
template <class T> void pr(T& v, string s)
{
cout«"\n\n\t"«s«" # Sequence: \n";
//====== Итератор для любого контейнера
Т::iterator p;
int i;
for (p = v.begin(), i=0; p != v.end(); p++, i++)
cout « endl « i + 1 «". "« *p; cout « '\n';
}
Для пробега по всем элементам любого контейнера используется обобщенный, или абстрактный, указатель, который объявлен как т:: iterator. С помощью итератора, так же как и с помощью обычного указателя, можно получить доступ к элементу, используя операции *, ->. К нему также применима операция ++ — переход к следующему элементу последовательности, но в отличие от указателя с итератором не связана адресная арифметика. Вы не можете сказать, что значение итератора изменится на 4 байта при переходе к следующему элементу контейнера целых чисел, хотя для некоторых типов контейнеров это так и будет. Заметьте, что операция ++ в применении к итератору позволяет перейти к следующему элементу как вектора — элементы расположены в памяти подряд, так и списка — элементы расположены в памяти не подряд. Поэтому итератор — это более сложный механизм доступа к данным, чем простой указатель. Полезно представить итератор в виде рабочего, приставленного к контейнеру и призванного перебирать его элементы.
Возможное присвоение p = v. end (); не означает, что итератор устанавливается на последний элемент последовательности. Вы помните, какую роль играет ноль для обычного указателя при работе с динамическим списком? Примерно такую же роль для итератора выполняет значение v. end () — конец последовательности. Его можно представить в виде итератора, указывающего на воображаемый элемент, следующий за последним элементом контейнера (past-the-end value). Однако инициализатор p = v.begin (); устанавливает итератор в точности на первый элемент последовательности.
Вектор объектов класса
Следующий фрагмент демонстрирует работу с вектором строк типа string. Теперь в контейнере будут храниться объекты класса string, который также является составной частью STL. Этот класс содержит ряд замечательных методов, которые позволяют легко и удобно работать со строками символов произвольной длины. В частности, вы можете складывать строки — осуществлять их конкатенацию, искать подстроки, удалять и заменять подстроки:
#include <vector>
#include <string>
#include <algorithm> // Для sort и distance
#include <functional> // Для greater<string>() tinclude <iostream>
using namespace std;
void main ()
{
//========= Вектор строк текста
vector<string> v;
v.push_back("pine apple");
v.push_back("grape") ;
v.push_back("kiwi fruit");
v.push_back("peach") ;
v.push_back("pear") ;
v.push_back("apple") ;
v.push_back("banana") ;
//========= Вызываем наш шаблон вывода
pr(v, "String vector");
sort (v.begin () , v.end());
pr(v, "After sort"); '
//========= Изменяем порядок сортировки, на обратный
//========= тому, который принят по умолчанию
sort(v.begin(), v.end(), greater<string>()) ;
pr(v, "After predicate sort");
cout « "\nDistance from the 1st element to the end: ";
vector<string>::iterator p = v.begin ();
vector<string>::difference_type d;
d = distance(p, v.end());
//========= Отметьте, что end() возвращает адрес
//========= за концом последовательности
cout « d « endl;
cout « "\n\nAdvance to the half of that distanceXn";
advance (p, d/2);
cout « "Now current element is: " « *p « endl;
d = distance(v.begin (), p);
cout « "\nThe distance from the beginning: " « d « endl;
d = distance(p, v.begin ());
cout « "\nThe distance to the beginning: "
« d « endl;
}
Здесь мы демонстрируем, как можно с помощью бинарного предиката greater <Туре> изменить порядок сортировки элементов последовательности. Предикатом называется функция, область значений которой есть множество { false, true } или { 0, 1 }. В нашем случае этот предикат пользуется результатом операции operator > (), определенной в классе string. Кроме того, мы показываем, как можно пользоваться шаблоном функций distance, который позволяет определить количество приращений типа dif ference_type между двумя позициями, адресуемыми итераторами. Другой шаблон функций — advance позволяет продвинуться вдоль контейнера на число позиций, задаваемое параметром, который может быть и отрицательным.
Предикаты и функциональные объекты
Предикатом, как определено в курсе математической логики, называется любая функция многих переменных, областью значений которой является множество {false, true} или {0, 1}. Покажем, как можно отсортировать по имени контейнер объектов класса Man, который мы определили в этом уроке выше. Алгоритм sort по умолчанию использует для сортировки бинарное отношение, задаваемое операцией operator< (). Так как в классе Man эта операция была определена в виде метода класса, то алгоритм справится с поставленной задачей. Однако если мы захотим изменить порядок и отсортировать последовательность объектов по возрасту, то нам придется воспользоваться другим отношением. Решить эту задачу можно двумя способами:
использовать конструкцию, называемую функциональным объектом.
Первый способ реализуется путем создания глобальной функции, на вход которой поступают два сравниваемых объекта, а на выходе должен быть результат их сравнения, например типа bool. Второй способ реализуется созданием функционального объекта (function object или functor), являющегося структурой, в которой определена операция operator (). Этот термин, однако, используется для обозначения не только описанного объекта, но и для любого другого, который можно вызвать так, как вызывают функцию. Собственно, кроме описанного случая, роль функционального объекта может выполнять обычная функция и указатель на функцию.
Покажем, как создать предикат. В описание класса Man следует добавить объявление внешней функции в качестве friend-объекта, так как в ее теле будут анализироваться private-данные класса Man. Добавьте в класс Man такое описание:
//======== Предикат, задающий отношение порядка
friend bool LessAge (Mans a, Man& b);
Затем вставьте коды этой функции после объявления класса, но до тела функции main:
bool LessAge (Man& a, Man& b)
{
//======== Сравниваем по возрасту
return a.m_Age < b.m_Age;
}
Теперь можно создать контейнер объектов класса Man и убедиться в возможности его сортировки двумя способами. В момент создания контейнер может быть инициализирован элементами обычного массива. Ниже мы показываем, как это сделать:
void main ()
{
//======== Массив объектов класса Man
Man ar[] =
{
Man("Mary Poppins",36),
Man("Joe Doe",30),
Man("Joy Amore",18),
Man("Zoran Todorovitch",27)
};
uint size = sizeof(ar)/sizeof(Man);
//======== Создаем контейнер на основе массива
vector<Man> men(ar, ar+size); pr(men,"Man Vector");
//======== Реверсируем обычный массив
reverse(ar, ar+size);
cout « "\n\tAfter reversing the array\n\n";
for (uint i=0; i<size; i++)
cout « i+1 « ". " « ar[i] « '\n';
//======== Сортиуем по умолчанию
sort (men.begin (), men.endO);
pr(men,"After default sort");
//======== Используем предикат
sort (men .begin () , men.endO, LessAge);
pr(men,"After predicate LessAge sort");
cout « "\n\n";
}
Алгоритм переворота последовательности (reverse) может работать как с контейнером, так и с обычным массивом. Для успешной работы ему надо задать диапазон адресов (range). Обратите внимание на то, что в качестве конца последовательности этому алгоритму, как и многим другим в STL, надо подать во втором параметре адрес ar+size, выходящий за пределы массива. Как объяснить тот факт, что шаблон функции reverse, требуя в качестве параметров переменные типа iterator, тем не менее работает, когда ему подают обычный указатель типа Man*? В документации вы можете найти такое объяснение. Указатель — это итератор, но итератор — это не указатель. Итератор — это обобщение (generalization) указателя.
Результат работы программы выглядит так:
Man Vector # Sequence:
1. Mary Poppins, Age: 36
2. Joe Doe, Age: 30
3. Joy Amore, Age: 18
4. Zoran Todorovitch, Age: 27
After reversing the array
1. Zoran Todorovitch, Age: 27
2. Joy Amore, Age: 18
3. Joe Doe, Age: 30
4. Mary Poppins, Age: 36
After default sort # Sequence:
1. Joe Doe, Age: 30
2. Joy Amore, Age: 18
3. Mary Poppins, Age: 36 /
4. Zoran Todorovitch, Age: 27
After predicate LessAge sort # Sequence:
1. Joy Amore, Age: 18
2. Zoran Todorovitch, Age: 27
3. Joe Doe, Age: 30
4. Mary Poppins, Age: 36
Здесь мы убрали сообщения, которые выводит деструктор класса Man. Они носят чисто учебный характер. В частности, они позволяют обозначить те моменты из жизни объектов класса Man, когда они уничтожаются, то есть когда система вызывает для них деструктор.
Сейчас мы намерены создать функциональный объект и использовать его для выбора режима сортировки по имени или по возрасту. Текущий выбор удобно хранить в static-переменной класса Man. Такие переменные, как вы знаете, являются общими для всех объектов класса. Изменяя их значение, можно управлять общими установками, касающимися всех объектов класса. Мы будем управлять текущим режимом сортировки. Для удобства чтения кода введем глобальное определение типа SORTBY - перечисление режимов сортировки:
enum SORTBY { NAME, AGE }; // Режимы сортировки
Декларацию static-переменной следует вставить в public-секцию класса Man:
static SORTBY m_Sort; // Текущий режим сортировки
Определение static-переменной, согласно законам ООП, должно быть глобальным:
//======= Определение и инициализация
SORTBY Man::m_Sort = NAME;
Сам функциональный объект должен быть объявлен как внешняя глобальная friend-конструкция. Вставьте следующее объявление внутрь класса Man:
//======= Функциональный объект имеет доступ к данным
friend struct ManLess;
Затем объявите сам функциональный объект, который, надо признать, имеет несколько непривычный вид:
//======== Функциональный объект
struct ManLess
{
bool operator()(Man& a, Man& b)
{
return a.m_Sort==NAME ? (a.m_Name < b.m_Name)
: (a.m_Age < b.m_Age);
}
};
Как вы видите, он имеет вид структуры (возможен и класс), в которой определена единственная операция operator (). В нем мы анализируем текущее значение флага сортировки и в зависимости от него возвращаем результат сравнения двух объектов, поступивших в качестве параметров, по тому или иному полю. Использование функционального объекта иллюстрируется следующим кодом, который вы можете вставить в конец существующей функции main:
//========= Используем функциональный объект
Man::m_Sort = NAME;
//========= Сортируем по имени
sort (men .begin (), men.end(), ManLess ());
pr(men,"After function object name sort");
Man::m_Sort = AGE;
//========= Сортируем по возрасту
sort (men. begin (), men.end(), ManLess ());
pr(men,"After function object age sort");
Аналогично предикату greater<Type>, который мы уже использовали, в STL определен предикат less<Type>, который обеспечивает упорядочивание контейнера, задаваемое операцией operator< (). Но, если вы вставите в функцию main такой код:
//========= Используем стандартный предикат
sort(men.begin(), men.end(),less<Man>() ) ;
pr(men,"After less<Man> sort");
то получите сообщение об ошибке, так как он будет искать реализацию operator< () в виде внешней функции с двумя сравниваемыми параметрами. Напомню, что мы уже реализовали эту операцию, но в виде метода класса с одним параметром. Для решения проблемы вы можете, не убирая старой версии, вставить новую. Декларируйте в классе Man внешнюю friend-функцию:
//========= Нужна для предиката less<Man>()
friend bool operator< (const Man& a, const Man& b);
Затем дайте внешнее тело этой функции. Отношение порядка здесь намеренно изменено по сравнению с предыдущей реализацией operators (). Как оказалось, обе версии будут работать в различных ситуациях. Первая — при сортировке по умолчанию, а вторая — при сортировке предикатом less<Man> .
bool operator<(const Man& a, const Man& b)
{
//======== Сравниваем по возрасту
return a.m_Age < b.m_Age;
}
Проверьте результат, запустив приложение. Проследите, чтобы в main был при этом код с вызовом алгоритма сортировки с тремя Параметрами:
sort(men.begin (), men.end(),less<Man>());
Здесь же уместно добавить, что в STL есть шаблоны, которые называются negators (отрицатели). Шаблон not2, например, позволяет инвертировать результат бинарной операции. Вставьте в конец функции main следующий фрагмент:
//========= Используем отрицатель бинарной операции
sort(men.begin (), men.endf), not2 (less<Man>()));
pr(men,"After not2(less<Man>) sort");
и убедитесь в том, что последовательность отсортирована теперь по убыванию возраста.
Примеры использования string
Примеры использования string
Тип string является специализацией шаблона basic_string для элементов типа char и определен как:
typedef basic_string<char> string;
Шаблон basic_string предоставляет типы и методы, схожие с теми, что предоставляют стандартные контейнеры, но он имеет много специфических методов, которые позволяют достаточно гибко манипулировать как строками, так и их частями (подстроками). Минимизация операций копирования строк, которой гордится MFC-класс cstring, на самом деле приводит к труднообнаруживаемым и невоспроизводимым (irreproducible) ошибкам, которые очень сильно портят жизнь программистам. Я с интересом узнал, что члены комиссии по утверждению стандарта C++ анализируют ошибки, возникающие из-за совместного использования двумя переменными строкового типа одной и той же области памяти, и пытаются выработать спецификации относительно времени жизни ссылок на символы строки. Если вы запутались в этой фразе, то следующий фрагмент программы, который комиссия использует в качестве теста, должен прояснить ситуацию. При выполнении он выведет строку «Wrong» или «Right», что означает, что ваша реализация string ненадежна или, скорее всего, надежна. Если она выведет строку «Right», то это еще не означает, что ваша реализация надежна. Ошибки могут всплыть в многопоточных приложениях, когда разные потоки работают с одной строкой символов:
//====== Две тестовые текстовые строки
string source("Test"), target;
//====== Ссылка на второй символ в строке
char& с = source[1];
//=====- Если данные не копируются при присвоении
target = source;
//====== то это присвоение изменит обе строки
с = ' z ' ;
//====== Этот тест позволяет выяснить ситуацию
cout « (target[l] == 'z1 ? "\nWrong" : "\nRight");
Здесь мы использовали ссылку, но аналогичное поведение обнаруживает и итератор. Вы можете объявить и использовать его так:
string::iterator it = source.begin()+1; *it = z1 ;
В рассматриваемой версии Studio.Net я с удовлетворением отметил, что тест выводит строку «Right». Следующий фрагмент демонстрирует технику обрезания «пустого» текста в начале и конце строки. Она не очень эффективна, но вполне пригодна для строк небольшого размера:
//====== Множество пустых символов
char White " \n\t\r";
//====== Ищем реальное начало строки
//====== и усекаем лишние символы слева
s = s.substr(s.find_first_not_of(White));
//====== Переворачиваем строку и повторяем процедуру
reverse (s .begin () , s.endO);
s = s.substr(s.find_first_not_of(White));
//====== Вновь ставим строку на ноги
reverse (s .begin (), s.end());
Интересный пример, иллюстрирующий работу со строками, я увидел в MSDN. Нечто вроде секретного детского языка под названием Pig Latin (свинячья латынь). Алгоритм засекречивания слов состоит в том, что от каждого слова отрывают первую букву, переставляют ее в конец слова, а затем добавляют туда окончание «ау». Игра, очевидно, имеет свою историю. Приведем коды функции, которая реализует этот алгоритм и возвращает засекреченную строку:
//====== Преобразование строки по принципу Pig Latin
string PigLatin (const strings s)
{
string res;
//======= Перечень разделителей слов
string sep(" .,;:?");
//======= Длина всей строки
uint size = s.lengthO;
for (uint start=0, end=0, cur=0; cur < size; cur=end+l)
{
//==== Ищем позицию начала слова, начиная с cur
start = s.find_first_not_of(sep, cur) ;
//==== Копируем разделители между словами
res += s.substr(cur, start - cur) ;
//==== Ищем позицию конца слова, начиная со start
end = s.find_first_of(sep, start) ;
//==== Корректируем позицию конца слова
end = (end >= size) ? size : end - 1 ;
//==== Преобразуем по алгоритму
res += s. substr (start-t-1, end-start) + s [start] +"ay"; )
return res;
}
Проверьте работу алгоритма с помощью следующего теста, который надо вставить внутрь функции main:
string s("she,sells;
sea shells by the sea shore");
cout « "Source string: " « s « endl;
cout « "\nPig Latin(s): " « PigLatin(s);
В результате вы увидите такой текст:
Source string: she,sells;
sea shells by the sea shore
Pig Latin(s): hesay,ellssay;
easay hellssay ybay hetay easay horesay
Работа с потоками
Работа с потоками
Шаблон класса if stream позволяет работать с файловыми потоками и производить ввод объектов произвольного типа. Удобно вводить объекты прямо в контейнер. Специальный итератор (istream_iterator) помогает в этом случае воспользоваться алгоритмами (например, сору). При достижении конца потока (end of stream) итератор принимает специальное значение, которое служит барьером выхода за пределы потока (past-the-end iterator). В примере, приведенном ниже, используется еще один тип итератора (back_insert_iterator). Он является адаптером, позволяющим вставлять элементы в конец последовательности. Если использовать прямой inserter, то при чтении из файла последовательность будет реверсирована (перевернута). Позиционирование в потоке осуществляется с помощью метода seekg, техника использования которого также демонстрируется в примере:
void main ()
{
//========== Вектор строк
vector<string> v;
v.push_back("Something in the way ");
v.push_back("it works distracts me ");
v.push_back("like no other matter");
pr(v,"Before writing to file");
//========== Запрашиваем имя файла
cout « "\nEnter File Name: ";
string fn, text; cin » fn;
//========== Приписываем расширение
int pos = fn.rfind(".");
if (pos > 0)
fn.erase(pos);
fn += ".txt";
//========== Создаем и открываем поток
ofstream os(fn.c_str());
//========== Определяем входной и выходной потоки
typedef istream_iterator<string, char,
char_traits<char> > Strln;
typedef ostream_iterator<string, char,
char_traits<char> > StrOut;
//========== Копируем контейнер в выходной поток
copy (v.begin(), v.end(), StrOut(os,"\n"));
os.close();
//========== Открываем файл для чтения
if stream is(fn.c_str());
//========= Пропуск 17 символов
is.seekg(17) ;
is » text;
cout « "\n\nStream Positioning:\n\n" « "17 bytes:\t\t" « text « endl;
//========== Устанавливаем в начало потока
is.seekg(0, ios_base::beg);
is » text;
cout « "0 bytes:\t\t" « text « endl;
//========== Сдвигаем на 8 символов от конца
is.seekg(-8, ios_base::end);
is » text;
cout « "-8 bytes from end:\t" « text « "\n\n";
//========== Устанавливаем в начало потока
is.seekg(0, ios_base::beg);
v.clear () ;
//========== Копируем в контейнер
copy(Strln(is),Strln(),back_inserter(v));
pr(v,"After reading from file");
cout«"\n\n"; }
Программа производит следующий выход:
Before writing to file # Sequence:
1. Something in the way
2. it works distracts me
3. like no other matter
Enter File Name: test
Stream Positioning:
17 bytes: way
0 bytes: Something
-8 bytes from end: matter
After reading from file # Sequence:
1. Something
2. in
3. the
4. way
5. it
6. works
7. distracts
8. me
9. like
10. no
11. other
12. matter
Сечения массива
Сечения массива
Проблемы оптимизации работы с матрицами давно волнуют создателей компиляторов. В то далекое время, когда решения задач электродинамики и вообще краевых задач матфизики еще интересовали влиятельных людей нашей страны (скорее, научные авторитеты убеждали их, что такие задачи следует решать), мы, используя язык PL/I или FORTRAN, конечно же, хранили и обрабатывали матрицы в одномерных массивах. Дело в том, что выбор одного элемента из более естественного для матриц двухмерного массива обходился дорого. Выработалась особая техника работы с одномерными массивами, хранящими матрицы (обычно разреженные). В языке C++ операция выбора элемента из двухмерного динамического массива не намного дороже, чем из одномерного (да и скорости изменились), поэтому острота проблемы спала. Тем не менее проблема экономии времени при решения сложных краевых задач не ушла в прошлое.
STL имеет пару вспомогательных классов: slice и gslice, которые созданы для того, чтобы было удобно работать со срезами (сечениями) одномерных массивов. Если вы храните двухмерную матрицу в последовательности типа valarray, то элементы одной строки матрицы или одного ее столбца можно представить в виде сечения, то есть определенной части всей последовательности. Конструктор класса slice определяет закономерность, в соответствии с которой будут выбираться элементы последовательности, чтобы образовать срез. Например, объект slice s(0, n , 2); представляет собой сечение из п элементов последовательности. Элементы выбираются начиная с нулевого, через один, то есть с шагом 2. Если вы храните матрицу пхп в последовательности типа valarray и при этом она упорядочена по строкам (сначала первая строка, затем вторая, и т. д.), то третью строку матрицы можно выбрать с помощью сечения:
slice s (2*n, n , 1);
Действительно, параметры указывают, что надо пропустить 2*n элементов, затем выбрать n элементов с шагом по одному. Если матрица хранится a la FORTRAN, то есть по столбцам, то для выбора той же строки надо определить сечение:
slice s (2, n , n);
Пропускаются два элемента, затем выбирается n элементов с шагом п. Вы, конечно, поняли, как создать сечение, но не поняли, какое отношение оно имеет к последовательности valarray, так как она не фигурирует в приведенных выражениях. Да, синтаксис, связывающий срез с valarray, несколько необычен, хотя вполне логичен:
int n = 5, // Размерность матрицы n (размером пхп) пп = п*п;
// Размерность valarray
//=== Создаем матрицу (одномерную последовательность)
valarray<double> a (nn);
//=== Генерируем ее элементы по закону f (Пока его нет)
generate (&a[0], &a[nn], f) ;
//====== Создаем сечение
slice s (0, n , 1);
//====== Выделяем сечение (первую строку,
//====== если матрица хранится по строкам)
valarray<double> v = a[s];
Вы видите, что объект s класса slice помещается в то место, куда мы обычно помещаем целочисленный индекс массива или последовательности. Такая интерпретация операции [ ] непривычна. Вы, вероятно, догадались, что роль объекта s в приведенном фрагменте является чисто эпизодической. Можно обойтись и без него, заменив его временным безымянным объектом, который создаст компилятор. При этом конструкция выражения будет более эффективной, но и более головоломной. Последние две строки фрагмента можно заменить одной строкой:
valarray<double> v = afslice (0, n , 1);
Подведем итоги. В этом уроке мы оценили возможности библиотеки STL и сделали вывод, что она, очевидно, имеет гораздо больше достоинств, чем недостатков. Необходимо регулярно тренировать технику ее использования. В этой задаче может помочь сеть Интернет, в которой появляется все больше сайтов, уделяющих внимание STL. Кроме того, мы:
узнали, что стандартные контейнеры делятся на последовательности и ассоциативные контейнеры;
узнали, как пользоваться предикатами и функциональными объектами; познакомились с возможностями связывателей, адаптеров и отрицателей;
узнали, как шаблоны пар помогают работать с ассоциативными контейнерами типа тар;
получили представление об использовании очередей и стека; оценили возможности текстовых строк типа string;
научились пользоваться итераторами различного типа, в том числе и для управления потоками ввода-вывода;
узнали о наличии большого количества полезных констант;
поработали с последовательностями типа valarray и их сечениями;
опробовали некоторые алгоритмы управления последовательностями.
Шаблон функции быстрой сортировки
Шаблон функции быстрой сортировки
Приведем пример реализации вышеупомянутого рекурсивного алгоритма сортировки массива переменных Quicksort. Его идея состоит в том, что меняются местами элементы массива, стоящие слева и справа от выбранного «центрального» (mid) элемента массива, если они нарушают порядок последовательности. Интервал, в котором выбирается центральный элемент, постепенно сжимается, «расправляясь» сначала с левой половиной массива, затем с правой. Функция Quicksort, приведенная ниже, реализует рекурсивный алгоритм быстрой сортировки. Далее следует код, который позволяет протестировать работу функции. Сортируется массив вещественных чисел, элементы которого заданы случайным образом:
void Quicksort (double *ar, int 1, int r)
{
//========== Рабочие переменные
double mid, temp;
//========== Левая и правая границы интервала
int i = 1, j = r;
//========== Центральный элемент
mid = ar[ (1 + г) /2];
//========== Цикл, сжимающий интервал
do
//== Поиск индексов элементов, нарушающих порядок
while (ar[i] < mid)
i++; // слева
while (mid < ar[j])
j--; // и справа
//== Если последовательность нарушена,
if (i <= j)
{
//===== то производим обмен
temp = ar[i];
ar[i++] = ar[j];
ar[j-—] = temp;
}
}
//========= Цикл do-while повторяется, пока
//========= есть нарушения последовательности
while (i <= j);
//========= Если левая часть не упорядочена,
if (I < j)
Quicksort (ar, 1, j); // то занимаемся ею
// Если правая часть не упорядочена,
if (i < r)
Quicksort (ar, i, r); // то занимаемся ею }
//========== Тестируем алгоритм
void main()
{
//========= Размер массива сортируемых чисел
const int N = 21;
double ar[N]; // Сам массив
puts("\n\nArray before Sorting\n");
for (int i=0; i<N; i++)
{
ar[i] = rand()%20;
if (i%3==0)
printf ("\n");
printf ("ar[%d]=%2.0f\t",i,ar[ij);
}
Quicksort(ar,0,N-1); // Сортировка
puts("\n\nAfter SortingNn");
for (i=0; i<N; i++)
{
if (i%3==0)
printf ("\n");
printf ("ar[%d]=%2.0f\t",i,ar[i]);
}
puts ("\n");
}
Для того чтобы сортировать массивы любого типа, целесообразно на основе данной функции создать шаблон. Оказывается, что для этого нужно приложить совсем немного усилий. В уже существующий код внесите следующие изменения:
template <class T>
void Quicksort (Т *ar, int 1, int r)
{
//======= Рабочие переменные
Т mid, temp;
//======= Далее следует тот же код, который приведен
//======= в оригинальной версии функции Quicksort
}
Проверьте функционирование, вставив в функцию main вызовы функции с другими типами параметров. Например:
void main()
{
//======= Размер массива сортируемых чисел
const int N = 21;
// double ar[N];
int ar[N];
puts("\n\nArray before SortingXn");
for (int i=0; i<N; i++)
{
ar[i] = rand()%20; if (i%3==0)
printf ("\n"); // printf ("ar[%d]=%2.0f\t",i,ar[i]);
printf ("%d\t",ar[i]);
}
Quicksort(ar,0,N-1);
puts("\n\nAfter SortingXn");
for (i=0; i<N; i + + ) ;
{
if (i%3==0)
printf ("\n"); // printf ("ar[%d]=%2.0f\t",i,ar[i]);
printf ("%d\t",ar[i]);
}
puts("\n");
}
В данный момент функция main настроена на сортировку массива целых. Внесите приведенные изменения и проверьте работу шаблона для массива целых. Уберите комментарии там, где они есть, но вставьте комментарии в строки программы, следующие ниже. После этой процедуры функция main будет настроена на проверку шаблона функции сортировки для массива вещественных. Проверьте и этот случай. Шаблон должен справиться с обоими.
Примечание 1
Примечание 1
Перед запуском консольных приложений настройте консольное окно так, чтобы его размеры вмещали весь выходной текст. Для этого вызовите контекстное меню на заголовке консольного окна и дайте команду Properties. Откройте страницу на вкладке Layout и подстройте размеры окна в полях Width и Height группы Window Size.
Шаблон классов valarray
Шаблон классов valarray
Этот шаблон разработан для оптимизации вычислений, производимых над массивами чисел фиксиррванного размера. Valarray похож на контейнер, но он им не является. Вы не можете динамически и эффективно наращивать его размер. Он, как и контейнер, может изменять свои размеры, используя метод resize, но при этом имеющиеся данные разрушаются. Главным преимуществом использования valarray является эффективность проведения операций сразу над всеми элементами последовательности. Предположим, вы хотите построить график функции у = sin(x) и имеете процедуру, которая сделает это с учетом масштабирования, оцифровки осей и всяких других удобств. Вашей задачей является лишь сформировать данные для графика и подать их на вход этой процедуры. Использование valarray даст преимущество в легкости манипулирования данными и эффективности выполнения. Для простоты выберем шаг изменения координаты х, равный л/3,
Примечание 1
Примечание 1
C целью экономии места я обычно не привожу директивы препроцессора, которые, конечно же, должны предшествовать каждому из рассматриваемых фрагментов. Большинство читателей, я уверен, успешно решают эту проблему сами, так как сообщения об ошибках обычно довольно ясно указывают на недостающее описание. Но при работе с библиотекой STL окно сообщений ведет себя не совсем так, как при работе с MFC. Незначительный пропуск или неточность со стороны программиста порой приводят к лавине предупреждений и ошибок, анализ которых превращается в испытание для нервной системы. Здесь у компании Microsoft еще довольно много работы. Учитывая сказанное, следующий фрагмент приведен со списком директив, необходимых для его работы.
#include <iostream>
#include <algorithm>
#include <valarray>
#include <limits>
using namespace std;
void main() { //======== Вспомогательные переменные
double PI = atan(l.)*4.,
dx = PI/3., // Шаг изменения
xf = 2*PI - dx/2.;
// Барьер
int i = 0,
size = int(ceil(xf/dx)); // Количество точек
//======== Создаем два объекта типа valarray
valarray<double> vx(size), vy(size);
//======== Абсциссы точек вычисляются в цикле
for (double х=0.;
х < xf; х += dx) vx[i++] = х;
//======== Ординаты вычисляются без помощи цикла
vy = sin(vx);
cout«"Valarrays of x and sin(x)\n";
for (i=0; i < size; i++)
cout«"\nx = " « vx[i] «" у = "« vy[i];
}
Теперь усложним задачу. Представим, что надо численно продифференцировать функцию, заданную в дискретном множестве точек. Вы знаете, что конечные разности позволяют аппроксимировать производные, то есть производить численное дифференцирование. В STL есть алгоритм adjacent_dif ference, который вычисляет первые конечные разности в указанном диапазоне последовательности. Здесь важно вспомнить, что valarray не является контейнером и поэтому не поддерживает итераторов. Но алгоритмы STL принимают в качестве аргументов как итераторы, так обычные указатели. Мы воспользуемся этим фактом, а также тем, что элементы valarray расположены в памяти подряд.
Результат дифференцирования надо поместить в другую последовательность типа valarray, которую после этого можно эффективно нормировать, поделив сразу все ее элементы на шаг дискретизации вдоль оси х. Добавьте директиву # include <numeric>, вставьте следующий текст в конец предыдущего фрагмента и, пожалуй, увеличьте количество точек, заменив присвоение dx = Pi/З. на dx = Pi/10:
//======= Конструктор создает valarray нужного размера
valarray<double> vd(size);
//======= Алгоритм вычисляет конечные разности
adjacent_difference(&vy[0], &vy[size], &vd[0]);
//======= Все элементы valarray делятся на dx
vd /= dx;
//======= Мы проверяем результат
cout«"\n\nValarray of differences\n";
for (i=l; i < size; i++)
cout«"\nx = " « vx[i] «" у = "« vd[i];
Отметьте, что в первой точке (с нулевым индексом) будет ошибка, поэтому мы ее не выводим. Остальные элементы результирующей последовательности чисел (valarray vd) должны вести себя как у = cos(x). В качестве третьего параметра функции adjacent_dif ference нельзя задать просто vd, так как в отличие от обычного массива имя vd не является адресом его первого элемента. Шаблон классов valarray имеет некоторое, весьма ограниченное количество методов, которые позволяют производить манипуляции с данными, среди которых стоит отметить: min, max, sum, shift, cshift, apply. Приведем фрагмент, иллюстрирующий их использование:
//======= Функциональный объект, применяемый к каждому
//======= элементу valarray
double Sharp (double x)
{
return x != 0. ? l/(x*x) : DBL_MAX;
}
//======= Функция для вывода valarray
void out(char* head, valarray<double>& v)
{
cout « '\n' « head << '\n';
for (unsigned i=0; i < v.size(); i++)
cout«"\nv[" « i « "] = " « v[i];
cout «'\n';
}
void main()
{
int size = 11;
valarray<double> vx(size), vy(size);
//======== Заполняем диапазон от -1 до 1
for (int i=0; i < size; i++)
{
vx[i] = i/5. - 1.;
}
out("Initial valarray", vx);
//======== Вычисляем сумму всех элементов
cout « "\nsum = " « vx.sum() « endl;
//======== Применяем свое преобразование
vy = vx.apply (Sharp);
//======== Получили "острую" функцию
out("After apply", vy);
//======== Вычисляем min и max
cout « "\n\nmin = " « vy.min() « " max = " « vy.max();
}
При положительных значениях аргумента метод shift используется для сдвига всей последовательности влево или при отрицательных значениях — вправо. Метод cshif t представляет собой циклическую модификацию метода shift. Заметьте, что все рассмотренные методы возвращают новую последовательность типа valarray и не имеют модификаций, работающих в режиме in-place, что, на мой взгляд, является ощутимым недостатком этого типа данных. Вы можете проверить работу сдвигов, добавив такие строки:
//======== Циклический сдвиг на 2 позиции влево
valarray<double> r =vy.cshift(2);
out("After cyclic 2 digits left shift", r) ;
//======== Сдвиг на 2 позиции вправо
r =r.shift(-2);
out("After 2 digits right shift", r);
Шаблоны
Шаблоны
STL — это библиотека шаблонов. Прежде всего вспомним, что такое шаблон. Различают шаблоны функций и шаблоны классов. Шаблон функций (function template) является средством языка C++, позволяющим избежать рутинного переписывания кодов функций, которые имеют сходный алгоритм, но разные типы параметров. Классическим примером, иллюстрирующим выгоды шаблона, является множество реализаций функции max (a, b) . При отсутствии механизма шаблонов для придания функции max () универсального характера следует создать несколько функций, разделяющих одно и то же имя. Например:
long max (long a, long b);
double max (double a, double b);
MyType max (mytype a, mytype b);
Vectors max (Vectors a, Vectors b);
Очевидно, что тела всех функций могут выглядеть совершенно одинаково для многих типов параметров. Например, коды функции max могут иметь вид:
return (a>b) ? а : b;
В таких случаях удобно использовать шаблон функции. Шаблон задается ключевым словом template:
template <class Т> Т max(Т х, Т у)
{
return (х>у) ? х : у;
};
Описатель <class т> — это аргумент шаблона. Символ т (type) означает произвольный тип данных т, который будет задан при использовании шаблона, т выполняет роль формального параметра, поэтому сам символ (т) может быть и другим, но везде одинаковым. При фактическом использовании шаблона место т заменяет какой-то уже описанный тип. Им может быть как стандартный, встроенный тип языка, так и новый тип, определенный пользователем. В том числе он может быть именем класса, определенного ранее. Важно, чтобы для типа был определен смысл операции > (больше). Если т заменяется классом, то в классе должна быть предварительно реализована операция operator> ().
Примечание 1
Примечание 1
Не идите на поводу у ложного друга — переводчика термина operator. В английском языке он имеет смысл операции (например, операция + или операция <, операция логического или |, и т. д.). То, что мы называем оператором языка (например, оператор while, оператор for, условный оператор if, и т. д.), имеет английский аналог — statement (например, conditional statement if).
Если задан шаблон, то компилятор генерирует подходящие коды функции max () в соответствии с конкретными типами фактических параметров, использованных при вызове функции. Например, встретив во внешней функции коды:
Man a("Alex Black", 54), b("Galina Black", 44), с;
с = max (a, b);
cout « "\n Старший: " « с;
компилятор в сгенерированной по шаблону копии функции max при сравнении объектов класса Man использует функцию operator > (), которая должна быть определена внутри класса Man. Например, так:
int operator >(Man& m) { return m__Age > m. m_Age; }
Если в той же внешней функции встретится оператор:
cout « "\n max (10,011) = " « max (10,011);
то компилятор в другой копии функции max, сгенерированной по тому же шаблону, использует операцию >, определенную для стандартного типа данных int. Один раз написав шаблон функции max, мы можем вызывать ее для всех типов данных, для которых определена операция operator> (). Если для какого-то типа данных тело функции max не годится, то можно отменить (override) действие шаблона функции для этого типа. Например, определив функцию:
char* max (char* s, char *t)
{
return (strcmp (s, t) >0) ?s : t;
}
мы отменяем действие шаблона для символьных строк, так как функция, скроенная по шаблону, осуществляла бы ничего не значащее сравнение указателей s и t. При использовании шаблона следует строго соблюдать типы параметров и не надеяться на стандартные преобразования типов, по умолчанию осуществляемые компилятором при вызове обычных функций. Например, явно заданную функцию, скрывающую (отменяющую) шаблон:
double max (double, double);
можно вызывать с аргументами (int, double) или (float, long). Компилятор при этом автоматически преобразует параметры к типу double. Однако если явная декларация функции, скрывающей шаблон, отсутствует, то шаблон
template <class T> T max(Т х, Т у)
не позволит смешивать типы при вызове функции max. Таким образом, обращение int i=max (9, 8.); вызывает сообщение об ошибке: "Could not find a match for max (int, double) ", которое означает, что не найдена функция max () для пары аргументов типа (int, double).
Шаблоны классов
Шаблоны классов
Шаблон классов (class template) в руководствах программиста иногда называется generic class или class generator. Шаблон действительно помогает компилятору сгенерировать определение конкретного класса по образу и подобию заданной схемы. Разработчики компилятора C++ различают два термина: class template и template class. Первый означает абстрактный шаблон классов, а второй — одно из его конкретных воплощений. Пользователь может сам создать template class для какого-то типа данных. В этом случае созданный класс отменяет (overrides) автоматическую генерацию класса по шаблону для этого типа данных. Рассмотрим стандартный пример, иллюстрирующий использование шаблона для автоматического создания классов, которые реализуют функционирование абстрактного типа данных «Вектор линейного пространства». Элементами вектора могут быть объекты различной природы. В примере создаются векторы целых, вещественных, объектов некоторого класса circle (вектор окружностей) и указателей на функции. Для вектора из элементов любого типа тела методов шаблона одинаковы, поэтому и есть смысл объединить их в шаблоне:
#include <iostream>
#include <string>
#include <math.h>
//====== Шаблон классов "Вектор линейного пространства"
template <class T> class Vector
{
//====== Данные класса
private:
Т *data; // Указатель начала массива компонентов
int size; // Размер массива
//====== Методы класса
public:
Vector(int);
~Vector()
{
delete[] data;
}
int Size()
{
return size;
}
T& operator [](int i)
{
return data[i];
}
};
//====== Внешняя реализация тела конструктора
template <class T> Vector<T>::Vector(int n)
{
data = new Т[n];
size = n; };
//====== Вспомогательный класс"Круг"
class Circle
{
private:
//====== Данные класса
int х, у; // Координаты центра
int r; // Радиус
public:
//====== Два конструктора
Circle ()
{
х = у = r = 0; }
Circle (int a, int b, int с) {
x = a;
У = b;
r = с;
}
//====== Метод для вычисления площади круга
double area ()
{
return 3.14159*r*r;
}
};
//====== Глобальное определение нового типа
//====== указателя на функцию
typedef double (*Tfunc) (double);
//====== Тестирование ч
void main ()
{
//===== Генерируется вектор целых
Vector <int> x(5) ;
for ( int i=0; i < x.SizeO; ++i)
{
x[i] = i; // Инициализация
cout « x[i] « ' ' ; // Вывод
}
cout « ' \n ' ;
//===== Генерируется вектор вещественных Vector <float> y(10);
for (i=0; i < y.SizeO; ++i)
{
y[i] = float (i); // Инициализация cout « y[i] « ' ' ; // Вывод
}
cout « ' \n' ;
//==== Генерируется вектор объектов класса Circle
Vector <Circle> z(4);
for (i=0; i< z.SizeO; ++i) // Инициализация
z[i] = Circle(i+100,i + 100,i+20) ;
cout « z[i].area() « " "; // Вывод
}
cout « ' \n' ;
//==== Генерируется вектор указателей на функции
Vector <Tfunc> f(3);
cout«"\nVector of function pointers: " ;
f[0] = sqrt; // Инициализация
f[l] = sin;
f[2] = tan;
for (i=0; i< f.Size(); ++i)
cout « f[i](3.) « ' '; // Вывод cout « "\n\n";
}
Обратите внимание на синтаксис внешней реализации тела конструктора шаблона классов. Vector<T> — это имя шаблона, a Vector (int n) — имя метода шаблона (конструктор). При использовании шаблона для генерации конкретного вектора объектов необходимо задать в угловых скобках тип данных, известный к этому моменту и видимый в этой области программы. Использование шаблона всегда предполагает наличие описателя типа при имени класса (Vector <type>). Имя Vector теперь не может быть использовано без указания конкретного типа элементов.
В рассмотренном примере операция [ ] определена в шаблоне как общая для всех типов Т, однако метоД area () определен только для объектов класса Circle и он применяется к объекту z [i] класса circle, вектор из четырех элементов которого автоматически создается компилятором при объявлении Vector <circle> z (4);. Работая с вектором указателей на функции, мы в цикле по переменой i вызываем i-ю функцию и посылаем ей в качестве аргумента вещественное число 3 (см. вызов f [i] (3.) ).
Если для какого-то типа переменных автоматически сгенерированный по шаблону класс не подходит, то его следует описать явно. Созданный таким образом класс (template class) отменяет автоматическое создание класса по шаблону только для этого типа. Например, предположим, что создан новый класс Man:
class Man
{
private:
string m_Name;
int m_Age;
public:
//======= Конструкторы
Man{}
{
m_Name = "Dummy";
m_Age = 0; }
Man (char* n, int a)
{
m_Name = string(n); m_Age = a;
}
Man (strings n, int a)
{
m_Name = n;
m_Age = a;
}
Man& operator=(const Man& m)
{
m_Name = m.m_Name;
m_Age = m.m_Age;
return *this;
}
Man(const Man& m)
{
*this = m;
}
//======== Деструктор
~Man()
{
cout « "\n+ + " « m_Name « " is leaving";
m_Name.erase (); }
bool operator==(const Man& m)
{
return m_Name == m.m_Name;
}
bool operator<(const Mans m)
{
//======= Упорядочиваем по имени
return m_Name < m.m_Name;
}
friend ostreams operator«(ostreams os, const Mans m);
};
//========= Внешняя реализация операции вывода
ostream& operator«(ostreams os, const Mans m)
{
return os « m.m_Name « ", Age: " « m.m_Age;
}
Для класса Man мы не хотим использовать class template Vector, но хотим со здать вектор объектов класса, работающий несколько иначе. С этой целью явн описываем новое конкретное воплощение (template class) класса Vector дл. типа Man.
class Vector <Man>
{
Т *data;
int size;
public:
Vector (int n, T* m);
~Vector 0 { delete [] data;
}
int Size()
{
return size;
}
T& operator [] (int i)
{
return data[i];
}
};
Vector <Man> : : Vector (int n, T* m)
{
size = n;
data = new Man [n] ;
for (int i=0; i<size; i++)
data [i] = m[i] ;
}
Отличие от шаблона состоит в том, что конструктор класса vector <Man> имеет теперь два параметра, а не один, как было в шаблоне. Теперь массив указателей data инициализируется данными массива объектов, поданного на вход конструктора. Цель этого нововведения — показать технику частного воплощения шаблона. Для проверки функционирования вектора из элементов типа Man следует создать какой-то тестовый массив, например:
Man miles ("Miles Davis", 60); // Отдельный Man
//====== Массив объектов класса Man
Man some [ ] =
{
Man("Count Basis", 70),
Man ("Duke Ellingtcnton", 90) ,
miles,
Man("Winton Marsales", 50) ,
};
а в функцию main ( ) добавить манипуляции с реальным вектором типа Man. В коде, который приведен ниже, обратите внимание на то, что при создании вектора men из четырех объектов класса Man вторым параметром передается адрес обычного массива объектов, инициализирующий все элементы (внутреннего для шаблона) массива data:
//====== Конструируем вектор объектов
//====== на основе массива объектов
Vector <Man> men (sizeof (some) /sizeof (Man) , some);
cout«"\nVector of Man: ";
//====== Вывод вектора
for (i=0; i< men. Size (); ++i)
cout « men[i] « "; ";
В шаблоне классов могут быть объявлены static данные и функции. При этом следует иметь в виду, что каждый конкретный класс, образованный по шаблону,
будет иметь свои собственные копии static членов. Эти члены будут общими для всех объектов конкретного класса, но различными для всех классов — реализаций шаблона.
Параметры шаблона
При описании шаблона можно задать более одного параметра. Например:
template <class T, int size=256> class Stack {...};
Теперь при создании конкретной реализации класса можно задать размер стека
Stack <int, 2048>;
или
Stack <double, 8*N>;
Важно запомнить, что числовой параметр должен быть константой. В примере переменная N могла быть описана как const int N=1024; но не могла быть переменной int N=1024;. При создании конкретного класса по шаблону возможно вложенное определение класса, например, если был описан частный случай класса — шаблон структур вида:
template <class T> struct Buffer {...};
то после этого можно создать конкретную структуру, в качестве типа которой задать структуру, созданную по этому же шаблону, например:
Buffer <Buffer <int> > buf;
Между двумя закрывающими угловыми скобками » надо вставить символ пробела, так как в языке C++ операция >> имеет самостоятельный смысл, и не один. Существует возможность генерировать по шаблону классы, которые являются производными от какого-то базового класса. Например, если описать базовый класс TList, в котором не определен тип элементов хранения, то есть используется тип void, то целесообразно ввести описание шаблона производных классов:
class TList
//======== Начало списка
void *First;:
public:
void insert (void*);
int order (void*, void*, int);
//======== Другие методы
};
template <class T> class List :
public TList T *First;
public:
void insert (T *t)
{
TList::insert(t);
}
int order (T *pl, T *p2, int n)
{
return TList::order(pi, p2, n);
}
//======= Другие методы
};
В этих условиях становится возможным декларация списка, состоящего из элементов одного определенного типа, например List <int> intList;, или гетерогенного списка, состоящего из элементов различных типов, образованных от какого-то одного базового класса. Например, объявление List <Device> DevList; генерирует класс для работы со списком приборов, из иерархии классов Device, то есть в списке могут быть объекты классов, производных от Device. Аналогичный результат даст объявление List <Man> ManList; и т. д. Вспомните, что работать с объектами производных классов можно с помощью указателей на базовый класс.
Стек — это несложно
Стек — это несложно
Стек — это адаптер (container adaptor), который предоставляет ограниченное подмножество всей функциональности контейнера. Термин адаптер в применении к структуре данных STL означает, что она реализована на основе какой-то другой структуры. По умолчанию стек основан на контейнере типа deque, но при объявлении можно явно указать и другой тип контейнера. Стек поддерживает вставку, удаление и инспекцию элемента, расположенного в первой (top) позиции контейнера. Стек не допускает итераций прохода по своим элементам. Говорят, что стек является структурой данных с дисциплиной доступа "last in first out" (LIFO). Вверху стека расположен элемент, который был помещен в него последним. Только он и может быть выбран в настоящий момент. При отладке следующего фрагмента не забудьте вставить директиву #include <stack>:
void main()
{
//========= Создаем стек целых
stack<Man> s;
s.push(joy);
s.push(joe);
s.push(charlie);
//========= Проверяем очевидные вещи
assert (s.size () == 3);
assert(s.top() == Charlie);
cout « "Stack contents:\n\n";
while (s.size())
{
cout « s.top() « "; ";
//========= Уничтожает top-элемент
s.pop(); }
assert(s.empty());
}
Связыватели и адаптеры
Связыватели и адаптеры
* Связывателями (binders) называются вспомогательные шаблоны функций, которые создают некий объект (adaptor) , подстраивающий или преобразующий бинарный функциональный объект в унарный путем привязывания недостающего аргумента. Звучит запутанно, но суть достаточно проста. Представьте, что надо найти в нашей последовательности людей первого человека, который моложе, чем
Man win("Winton Kelly", 50);
Для объектов класса Man уже определена бинарная операция operator< (), которой пользуется предикат less<Man> (), и мы показали использование этого предиката в алгоритме сортировки по возрасту. В том примере функция sort сама подставляла оба параметра в бинарную функцию operator< (), сравнивая объекты для нужд сортировки. Теперь мы используем связыватель bind2nd, для того чтобы зафиксировать (привязать) второй параметр этой функции и сделать его равным объекту win. Первый параметр при этом остается свободным, он будет пробегать по всему контейнеру. Таким образом, мы сможем сравнить все объекты последовательности с одним фиксированным объектом win.
В этом же фрагменте мы покажем, как использовать другой адаптер mem_f un_ref, который тоже является вспомогательным шаблоном функции для вызова какой-либо функции, являющейся членом класса, в нашем случае Man. Вызов осуществляется для всех объектов класса в процессе прохода по контейнеру. Введите в состав класса Man две public-функции, выделяющие имя и фамилию человека. В коде этих функций попутно демонстрируются методы класса string, которые позволяют осуществлять поиск и выделение подстроки:
//======== Выделяем имя
Man FirstName()
{
//======== Ищем первое вхождение пробела
int pos = m_Name.find_first_of(string(" "),0);
string name = m_Name.substr(0, pos);
cout « '\n' « name;
return *this;
}
//======== Выделяем фамилию
Man SurName()
{
//======== Ищем последнее вхождение пробела
int pos = m_Name.find_last_of(" "), num = m_Name.length () - pos;
string name = m_Name.substr(pos + 1, num);
cout « '\n' « name; return *this;
}
Вектор заполняется элементами, взятыми из массива а г, и при этом используется метод assign, который стирает весь массив и вновь заполняет его элементами, копируя их из диапазона памяти, задаваемого параметрами. Далее мы показываем, как используется связыватель bind2nd и адаптер члена-функции mem_f un_ref:
void main ()
{
Man ar[] =
{
joy, joe, zoran, тагу, simon, liza, Man("Lina Groves", 19)
};
uint size = sizeof(ar)/sizeof(Man);
vector<Man> men;
men.assign(ar, ar+size);
pr(men,"Man Vector");
//======= Привязка второго аргумента
vector<Man>::iterator p = find_if(men.begin(),
men.end(), bind2nd(less<Man>(), win));
if (p != men.end())
cout « "\nFound a man less than " « win « "\n\t" « *p;
//======= Использование метода класса (mem_fun_ref)
cout « "\n\nMen Names:\n";
for_each (men.begin(), men.end(), mem_fun_ref(&Man::SurName));
cout « "\n\nMen First Names:\n";
for_each (men.begin (), men.end(), mem_fun_ref(&Man::FirstName));
cout « "\n\n";
}
Напомним, что для успешной работы вы должны вставить в функцию main тот набор объектов класса Man, который был приведен ранее.
Примечание 1
Примечание 1
При анализе этого кода бросается в глаза неестественность прототипов функций SurName и FirstName. Логика использования этих функций совсем не требует возвращать какое-либо значение, будь то Man, или переменная любого другого типа. Естественным выбором будет прототип void SurNameQ;. Но, к сожалению, этот выбор не проходит по неизвестным мне причинам ни в Visual Studio б, ни в Studio.Net 7.O. Я достаточно много времени потратил на бесполезные поиски ответа на этот вопрос и пришел к выводу, что это ошибка разработчиков. В подтверждение такого вывода приведу следующие аргументы. Во-первых, измените тип возвращаемого значения на любой другой, но не void, и программа будет работать. Например, возьмите прототип string SurName(); и возвращайте return "MicrosoftisOK"; (или другую пару: int и-127). Во-вторых, все примеры на (mem_fun_ref) в документации MSDN возвращают загадочный bool. В-третьих, в документации SGI (Silicon Graphics) приведены аналогичные примеры с функциями, возвращающими void. Там, как вы знаете, используется другая платформа (IRIS). В-четвертых, наш пример (без void) проходит в Visual Studio б и не работает в бета-версии Studio.Net. Будем надеяться, что ситуация со временем выправится.
Адаптер mem_fun в отличие от mem_fun__ref используется с контейнерами, хранящими указатели на объекты, а не сами объекты. Хорошим примером использования mem_f un, в котором иллюстрируется полиморфизм позднего связывания (late binding polymorphism), является следующий:
//======== Базовый класс. К сожалению, абстрактным
//======= его не позволит сделать контейнер
struct Stud
virtual bool print()
{
cout « "\nl'm a Stud";
return true;
}
};
//===== Производный класс struct GoodStud : public Stud
{
bool print ()
{
cout « "\nl'm a Good Stud";
return true;
}
};
//======= Еще один производный класс
struct BadStud : public Stud
{
bool print ()
{
cout « "XnI'm a Bad Stud";
return true;
}
};
//======= Иллюстрируем полиморфизм в действии
void main () {
//====== Вектор указателей типа Stud*
vector<Stud*> v;
//====== Они могут указывать и на детей
v.push_back (new StudO);
v.push_back (new GoodStudO);
v.push_back(new BadStud(J);
//====== Выбор тела метода происходит поздно
//====== на этапе выполнения
for_each(v.begin(), v.end(), mem_fun(&Stud:: print));
cout <<"\n\n";
}
Конечно же, эта программа выведет:
I'm a Stud
I'm a Good Stud
I'm a Bad Stud
так как mem_fun будет вызвана с помощью указателя типа stud* (на базовый класс) — непременное условие проявления полиморфизма, то есть выбора конкретной версии виртуальной функции (адреса функции из vtable) на этапе выполнения. Выбор определяется конкретной ситуацией — типом объекта, попавшим под родительский перст (указатель) в данный момент времени.
