Пакет Vstudio7


         

Ассоциативные контейнеры



Ассоциативные контейнеры

К ассоциативным контейнерам принадлежат: 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
Очередь с приоритетами тоже является адаптером, который позволяет вставку элементов, инспекцию и удаление верхнего (top) элемента. Она не допускает итераций прохода по своим элементам. Ее характерным отличием является то, что верхний элемент является самым большим в том смысле, в котором в шаблоне используется функциональный объект (Compare — сравнение объектов). Для разнообразия приведем объявление шаблона:
template
<



class Type,

class Container=vector<Type>,

class Compare=less<typename Container : : value__type>
>

Отсюда видно, что по умолчанию очередь с приоритетами основана на контейнере типа vector и для сравнения приоритетов она использует предикат lesso. Для объектов класса Man — это внешняя friend-функция operator< (), которая упорядочивает последовательность по возрасту. Но очередь с приоритетами должна расставить элементы по убыванию приоритетов. Проверим это утверждение с помощью следующего фрагмента:

void main () {

//===== Priority queue (by age)

priority_queue<Man> men;

men.push (zoran);

//== Для проверки поведения вставляем объект повторно

men.push (zoran);

men.push (joy);

men.push (mela); men.push (win);

cout«"priority_queue size: "«men. size () «endl;

int i=0;

while ('men.empty())

{

cout « "\n"« ++i«". "«men.top();

men.pop();
}
}

Выходом этой программы будет такой текст:

priority_queue size: 5

1. Winton Kelly, Age: 50

2. Zoran Todorovitch, Age: 27

3. Zoran Todorovitch, Age: 27

4. Joy Amore, Age: 18

5. Melissa Robinson, Age: 9
Как видно, объекты выстроены по убыванию возраста. Очереди и стеки допускают повторение элементов.


Использование 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 раз. Она зависит от размера массива и степени его упорядоченности. Приведем одну из причин такого результата.

Универсальность первого алгоритма реализуется на этапе выполнения за счет вызова generic-функции стр () и преобразования типов указателей.
Универсальность второго подхода реализуется за счет настройки шаблона на конкретный тип переменных, что происходит на этапе компиляции.

Важно помнить, что рекурсия сама по себе стоит дорого, поэтому важны детали реализации конкретного алгоритма. Над деталями реализации алгоритмов библиотеки 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) на этапе выполнения. Выбор определяется конкретной ситуацией — типом объекта, попавшим под родительский перст (указатель) в данный момент времени.



Диалог для исследования решений



Диалог для исследования решений

Сейчас мы быстрыми темпами, не углубляясь в детали, создадим диалог, работающий в немодальном режиме и позволяющий исследовать решения уравнения Пуассона при разных значениях свойств среды, произвольном расположении источников поля и произвольных граничных условиях.

Так как диалог будет вызываться по команде меню, откройте в окне редактора ресурс меню IDR_MAINFRAME и приведите его в соответствие со следующей схемой. В меню File должна быть только одна команда Exit, в меню Edit уберите все команды и вставьте одну команду Parameters, индекс (ID_EDIT_PARAMETERS) ей будет присвоен автоматически. Остальные меню оставьте без изменения. С помощью редактора диалогов создайте новое диалоговое окно (форму), которое имеет вид, изображенный на Рисунок 11.4. Типы элементов управления, размещенных в окне диалога, и их идентификаторы сведены в табл. 11.1. Затем создайте класс для управления диалогом.

Вызовите контекстное меню в форме диалога и выберите команду Add Class.
В качестве типа класса выберите MFC Class.
В окне мастера MFC Class Wizard задайте имя класса CParamDlg, базовый класс CDialog, идентификатор диалога: IDD_PARAM и нажмите кнопку Finish.



Форма диалога для управления параметрами краевой задачи



Рисунок 11.4. Форма диалога для управления параметрами краевой задачи




Учитывая сказанное, создадим программный модуль,


Формирование матрицы

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

//====== Глобально заданная размерность системы

int n;

//====== Граничные условия

double UO, UN;

//====== Функция вычисления коэффициентов

//====== трехдиагональной матрицы

double f ()
{

//====== Разовые начальные установки

static int raw = -1, k = -1, col = 0;

//====== Сдвигаемся по столбцам

col++;

//====== k считает все элементы

//====== Если начинается новая строка

if (++k % n == 0)
{

col =0; // Обнуляем столбец

raw++; // Сдвигаемся по строкам
}

//====== Выделяем три диагонали

return col==raw ? -2.

: col == raw-1 И col==raw+l ? 1.

: 0.;

}

double fu()

{

//==== Вычисления вектора правых частей по формуле (5)
static double

dU = (UN-UO)/(n+1),

d = U0; return d += dU;
}

В функции main создается valarray с трехдиагональной матрицей и производится умножение матрицы на вектор решений. Алгоритм умножения использует сечение, которое вырезает из valarray текущую строку матрицы:

void main()
{

//======= Размерность задачи и граничные условия

n =4;

UO = 100.;

UN = 0 . ;

//======= Размерность valarray (вся матрица)

int nn = n*n;

//======= Матрица и два вектора

valarray<double> a(nn), u(n), v(n);

//======= Генерируем их значения

generate (&а[0], &a[nn], f); generate (&u[0], &u[n], fu);

out ("Initial matrix", a); out ("Initial vector", u);

//======= Умножение матрицы на вектор

for (int i=0; i<n; i++) {

//======= Выбираем i-ю строку матрицы

valarray<double> s = a[slice (i*n, n , 1)];

//======= Умножаем на вектор решений

//======= Ответ помещаем в вектор v <

transform(&s[0], &s[n], &u[0], &v[0], multiplies<double>());

//======= Суммируем вектор, получая

//======= i-ый компонент вектора правых частей

cout « "\nb[" « i « "] = " « v.sum(); }

cout«"\n\n";
}

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

Тестирование обнаруживает появление численных погрешностей (в пределах Ю"15), обусловленных ограниченностью разрядной сетки, в случаях когда диапазон изменения искомой величины не кратен размеру расчетной области. Стоит отметить, что сечения хоть и являются непривычным инструментом, для которого хочется найти наилучшее применение, но в рамках нашей задачи вполне можно обойтись и без него. Например, алгоритм умножения матрицы на вектор можно выполнить таким образом:

for (int i=0, id=0; i<n; i++, id+*n)
{

transform(&a[id], &a[id+n], &u[0], &v[0],

multiplies<dovible> () ) ;

cout « "\nb[" « i « "] = " « v.sum();
}

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



Класс графика



Класс графика

С помощью Studio.Net введите в состав проекта новый generic-класс CGraph, не указывая имени базового класса и не включая флажок Virtual destructor. В файл декларации нового класса введите вручную вспомогательный класс CDPoint, необходимость в котором мы обсуждали ранее. Затем добавьте объявление структуры TData, которая собирает воедино все данные, используемые при построении графика. Начальная буква Т в имени класса осталась со времен работы в среде Borland. Там принято все классы именовать начиная с буквы Т (Туре), означающей создание нового типа данных. Но в отличие от старой реализации графика, которая, возможно, знакома читателю по книге «Технологии программирования на языке C++» (Издательство СПбГТУ, 1997), мы введем в класс CGraph некоторые новые возможности:

#pragma once

class CDPoint

{

public:

//=== Две вещественные координаты точки на плоскости

double x, у;

//======= Стандартный набор конструкторов и операций

CDPoint () {

х=0.; у=0.;

}

CDPoint(double xx, double yy) {

х=хх;

У=УУ;

}

CDPoints operator=(const CDPointi pt) {

x = pt.x;

У = pt.y; return *this;

}

CDPoint(const CDPointS pt) {

*this - pt; } };

//===== Вспомогательные данные, характеризующие

//== последовательность координат вдоль одной из осей

struct TData (

//===== Порядок в нормализованном представлении числа

int Power; //===== Флаг оси X

bool bХ; double

//======= Экстремумы

Min, Max,

//======= Множитель -(10 в степени Power)

{

Factor,

//======= Шаг вдоль оси (мантисса)

Step,

//======= Реальный шаг

dStep,

//==== Первая и последняя координаты (мантиссы)

Start, End,

// ======= Первая и последняя координаты

dStart, dEnd; };

//===== Класс, реализующий функции плоского графика

class CGraph { public:

//===== Данные, характеризующие данные вдоль осей

TData m_DataX, m_DataY;

//===== Контейнер точек графика

vector <CDPoint>& m_Points;

//===== Текущие размеры окна графика

CSize m_Size;

//===== Экранные координаты центра окна

CPoint m_Center;

//===== Заголовок и наименования осей

CString m_sTitle, m_sX, m_sY;

//===== Перо для рисования

CPen m_Pen;

//===== Два типа шрифтов

CFont m_TitleFont, m_Font;

//===== Высота буквы (зависит от шрифта)

int m_LH,

//===== Толщина пера

m_Width;

//===== Цвет пера COLORREF m_Clr;

//======= Методы для управления графиком

CGraph(vector<CDPoint>& pt, CString sTitle, CString sX, CString sY) ;

virtual -CGraph();

//===== Заполнение TData для любой из осей

void Scale(TDataS data);

//===== Переход к логическим координатам точек

int MapToLogX (double d);

int MapToLogY (double d);

//===== Изображение в заданном контексте

void Draw (CDC *pDC);

//===== Изображение одной линии

void DrawLine(CDC *pDC) ;

//===== Подготовка цифровой метки на оси

CString MakeLabel(bool bx, doubles d);

};

Класс CGraph сделан с учетом возможности развития его функциональности, так чтобы вы могли добавить в него нечто и он мог бы справиться с несколькими кривыми одновременно. Фактически он представляет собой упрощенную версию того класса, которым мы пользуемся для отображения результатов расчета поля в двухмерной постановке. Отметьте, что структура TData используется как для последовательности абсцисс, так и ординат.

Алгоритм нормирования абсцисс и ординат проще создать, чем кратко и понятно описать. Тем не менее попробуем дать ключ к тому, что происходит. Мы хотим, чтобы размеры графика отслеживали размеры окна, а числа, используемые для разметки осей, из любого разумного диапазона, как можно дольше оставались читабельными. Задача трудновыполнимая, если динамически не изменять шрифт. В данной реализации мы не будем подбирать, а используем только два фиксированных шрифта: для оцифровки осей и для вывода заголовка графика. Обычно при построении графиков числа, используемые для оцифровки осей (мантиссы), укладываются в некоторый разумный диапазон и принадлежат множеству чисел, кратных по модулю 10, стандартным значениям шага мантиссы (2, 2.5, 5 и 10). Операцию выбора шага сетки, удовлетворяющую этим условиям, удобно выполнить в глобально определенной функции, не принадлежащей классу CGraph. Это дает возможность использовать функцию для нужд других алгоритмов и классов. Ниже приведена функция gScale, которая выполняет подбор шага сетки. Мы постепенно дадим содержимое всего файла Graph.срр, поэтому вы можете полностью убрать существующие коды заготовки. Начало файла имеет такой вид:

#include"StdAfx.h"

#include "graph.h"

//===== Доля окна, занимаемая графиком

#define SCAT,F,_X 0 . 6

#define SCALE_Y 0.6

//=== Внешняя функция нормировки мантисс шагов сетки

void gScale (double span, doubles step)

{

//== Переменная span определяет диапазон изменения

//== значаний одной из координат точек графика

//== Вычисляем порядок числа, описывающего диапазон

int power = int(floor(loglO(span)));

//===== Множитель (zoom factor)

double factor = pow(10, power);

//===== Мантисса диапазона (теперь 1 < span < 10)

span /= factor;

//===== Выбираем стандартный шаг сетки if (span<1.99)

step=.2;

else if (span<2.49)

step=.25;

else if (span<4.99)

step=.5;

else if (span<10.)

step= 1.;

//===== Возвращаем реальный шаг сетки (step*10~power)

step *= factor;

}

Результатом работы функции gScale является значение мантиссы дискретного шага сетки, которая наносится на график и оцифровывает оду из осей. Самым сложным местом в алгоритме разметки осей является метод CGraph:: Scale. Он по очереди работает для обеих осей и поэтому использует параметр с данными типа TData, описывающими конкретную ось. Особенностью алгоритма является реализация идеи, принадлежащей доценту СПбГТУ Александру Калимову и заключающейся в том, чтобы как можно дольше не переходить к экспоненциальной форме записи чисел. Обычно Калимов использует форму с фиксированной запятой в диапазоне 7 порядков изменения чисел (10~3+104), и это дает максимально удобный для восприятия формат, повышая читабельность графика:

void CGraph::Scale (TDatai data)

{

//===== С пустой последовательностью не работаем

if (m_Points.empty()) return;

//===== Готовимся искать экстремумы

data.Max = data.bX ? m_Points [0] .х : m_Points [0] .у;

data.Min = data.Max;

//===== Поиск экстремумов

for (UINT j=0; j<ra_Point5.size(); j++)

{

double d = data.bX ?

m_Points [ j] .x

: m_Points [ j] . y;

if (d < data.Min) data.Min = d;

if (d > data.Max) data.Max = d;

}

//===== Максимальная амплитуда двух экстремумов

double ext = max(fabs(data.Min),fabs(data.Max));

//===== Искусственно увеличиваем порядок экстремума

//===== на 3 единицы, так как мы хотим покрыть 7 порядков,

//===== не переходя к экспоненцеальной форме чисел

double power = ext > 0.? loglO(ext) +3. : 0.;

data.Power = int(floor(power/7.));

//===== Если число не укладывается в этот диапазон

if (data.Power != 0)

//===== то мы восстанавливаем значение порядка

data.Power = int(floor(power)) - 3;

//===== Реальный множитель

data.Factor = pow(10,data.Power);

//===== Диапазон изменения мантиссы

double span = (data.Max - data.Min)/data.Factor;

//===== Если он нулевой, if (span == 0.)

span = 0.5; // то искусственно раздвигаем график

// Подбираем стандартный шаг для координатной сетки

gScale (span, data.Step);

//===== Шаг с учетом искусственных преобразований

data.dStep = data.Step * data.Factor;

//== Начальная линия сетки должна быть кратна шагу

//====и быть меньше минимума

data.dStart = data.dStep *

int (floor(data.Min/data.dStep));

data.Start = data.dStart/data.Factor;

//===== Вычисляем последнюю линию сетки

for (data.End = data.Start;

data.End < data.Min/data.Factor + span-le-10;

data.End += data.Step)

data.dEnd = data.End*data.Factor;

}



Класс окна для отображения графика



Класс окна для отображения графика

Откройте файл ChildView.cpp, который содержит коды реализации методов класса CChildView. Его имя содержит ложный намек на происхождение от CView. На самом деле он происходит от класса CWnd и инкапсулирует функциональность окна, оккупирующего клиентскую область окна рамки, которое управляется классом CMainFrame. Простое окно, как вы помните, для перерисовки своего содержимого, вместо метода OnDraw использует метод OnPaint. Найдите этот метод в классе CChildView и убедитесь, что в нем контекст устройства создается, а не приходит в качестве параметра от каркаса приложения, как это было в приложениях, поддерживающих архитектуру документ — представление. Вставьте внутрь этого метода вызов конструктора класса CGraph с последующим сообщением Draw:

void CChildView::OnPaint() {

CPaintDC dc(this);

CGraph(m_Points, "Field Distribution", "x[m]","Field").Draw(&dc); }

Класс CGraph разработаем позже. Он будет создавать двухмерный график функции — решения краевой задачи, автоматически масштабируемый и подстраивающийся под текущий размер окна CChildView. Перейдите к файлу с определением оконного класса (ChildFrame.h) и введите следующие коррективы:

# pragma once

#include "Graph.h"

Class CChildView : public CWnd

{

// Вспомогательные классы будут пользоваться данными

friend class CParamDlg;

friend class CGraph;

private:

//===== Контейнер координат точек графика

vector<CDPoint> m_Points;

//===== Вектор источников и свойств среды (см. f и р)

vector<double> m_f, m_r;

//===== Размерность задачи (см. N)

int m_n;

//===== Параметры

double m_k, // Коэффициент k

m_L, // Протяженность расчетной области

m_g0, // Коэффициенты, задающие ГУ слева

m_d0,

m_gn, // Коэффициенты, задающие ГУ справа m_dn ;

CParamDlg *m_pDlg; // Немодальный диалог параметров

public:

CChildView();

virtual -CChildViewO;

virtual BOOL PreCreateWindow(CREATESTRUCT& cs);

//===== Изменение размерности задачи

void Resize();

//===== Решение системы методом прогонки

void Solve();

protected:

afx_msg void OnPaint();

DECLARE_MESSAGE_MAP() };

Точки графика будем хранить в контейнере объектов класса CDPoint, который мы неоднократно использовали, так как исследователи реальных систем работают с вещественными координатами. Переход к экранным координатам будет произведен в классе CGraph. Инициализацию данных проведите в конструкторе оконного класса:

CChildView: :CChildView()

{

m_n = 200;

m_k = -0.0005;

m_L = 200.;

//====== Слева ГУ первого рода Uo=100

m_g0 = 0.;

m_d0 =100.;

m_gn = 0.;

m_dn = 0.;

Resize () ;

m_pDlg = 0;

}

В деструктор вставьте коды освобождения памяти, занимаемой контейнерами:

CChildView::~CChildView()

{

m_Points.clear();

m_f.clear();

m_r.clear();

}

При работе с диалогом по управлению параметрами пользователь будет иметь возможность изменять количество узлов разбиения расчетной области, поэтому мы должны изменять размерность используемых контейнеров:

void CChildView::Resize ()

{

//===== Число узлов равно N+1 (с учетом 0-го узла)

int n = m n + 1;

m_Points.resize(n, CDPoint(0.,0.));

m_f.resize(n, 0.);

m_r.resize(n, 1.); }

Функция Solve решает систему уравнений методом прогонки:

void CChildView::Solve()

{

Resize () ;

int n = m_n + 1;

//======= Коэффициенты разностных уравнений

vector<double> a(n), b(n), c(n);

//======= Коэффициенты прогонки

vector<double> d(n), e(n);

double h = m L / m_n, // Размер шага вдоль оси х

hh = h * h;

// Квадрат шага

//======= Коэффициенты с 0-м индексом не используются

а[0] = 0.;

b[0] = 0.;

с[0] = 0.;

//=== Вычисляем координаты х и коэффициенты уравнений

m_Points[0].х = 0.;

for (int i=1; i < m_n; i++)

{

m_Points[i],x = i * h;

//======= Смотри формулы (4)

a[i] = m_r[i-l]/hh;

c[i] = m_r[i]/hh;

b[i] = - a[i] - c[i] + m_k;

}

m_Points[m_n].x = m_L;

//======== -Прямой ходпрогонки

d[0] = m_gO; //ГУ слева e[0] * m_d0; double den;

for (i=1; i < m_n; 1++)

{

//======= Общий знаменатель

den = a[i) * d[i-l] + b[i] ; d[i] = -c[i] / den;

e[i] = <m_f[i] - a[i] * e[i-l]) / den;

}

//======= Готовимся к обратному ходу

den = 1. - m_gn * d[m_n-l];

//======= Случай некорректно поставленной задачи

if (den==0.)

{

MessageBox ("ГУ заданы некорректно", "Ошибка-",МВ_ОК) ;

return;

}

//====== Два последних узла используют ГУ справа

//======= Смотри формулы (13)

m_Points[m_n-l].у = (e[m_n-l] + m_dn * d[m_n-l])/den;

m_Points[m_n].y = (m_dn + m_gn* e[m_n-l])/den;

//======= Обратный ход прогонки

for (i = m_n-2; i >= 0; i--)

m_Points[i].y = d[i) * m_Points[i+1].у + e[i]; Invalidate();

}

С помощью инструментов Studio.Net введите в класс CChildView реакцию на сообщение о создании окна WM_CREATE и вставьте в нее единственную строку, которая вызывает функцию Solve. Она формирует и решает систему разностных уравнений, определенную данными по умолчанию. Позже мы создадим диалог по изменению этих данных:

int CChildView::OnCreate(LPCREATESTRUCT IpCreateStruct)

{

if (CWnd::OnCreate(IpCreateStruct) == -1)

return -1;

//======= Решаем систему, определенную по умолчанию

Solved;

return 0;

}



Конструктор CGraph



Конструктор CGraph

Если вы поняли, что происходит в методе Scale, то дальнейшие манипуляции с данными графика не вызовут у вас затруднений. Рассмотрим конструктор класса CGraph. В первом параметре по ссылке он получает контейнер с точками графика. Для того чтобы исключить копирование всех точек внешнего контейнера, мы инициализируем в заголовке конструктора свою собственную ссылку m_Points на входной контейнер. Кроме контейнера с точками графика пользователь объектом CGraph должен передать два текста, помечающих оси графика (sX, SY) и текст его заголовка (sTitle). В теле конструктора готовим два объекта типа TData для данных о разметке двух осей, создаем два шрифтовых объекта и инициализируем переменные управления параметрами линии графика. В данной реализации мы убрали диалог по изменению атрибутов пера, который вы можете сделать по своему вкусу.

Примечание 1
Примечание 1

Следует отметить, что при изображении нескольких кривых функциональных зависимостей на одном графике необходимо дать пользователю возможность управлять стилем пера для каждой кривой в отдельности. В начале книги мы рассматривали, как это делается. Кроме того, следует учитывать существующие традиции изображения научной графики. Например, можно помечать кривые крестиками, ноликами и т. д. Это делается с помощью цикла прохода по точкам кривой и вывода в определенных местах растровых изображений, маркирующих кривую. Эти возможности ввиду необходимости описывать объекты классов Stingray Objective Grid мы также убрали из данной реализации.

//======= Конструктор класса CGraph

CGraph::CGraph (vector<CDPoint>S pt,

CString sTitle, CString sX, CString sY)

: m_Points(pt)

{

//===== Готовим данные, характеризующие оси координат

ZeroMemory(Sra_DataX, sizeof(TData));

ZeroMemory(sm_DataY, sizeof(TData));

m_DataX.bX = true;

m_DataY.bX = false;

m_sTitle = sTitle;

m_sX = sX;

m_sY = sY;

//======= Создаем шрифт для оцифровки осей

m_Font.CreateFont(16,0,0,0,100,0,0,0,DEFAULT_CHARSET,

OUT_RASTER_PRECIS,CLIP_DEFAULT_PRECIS,

DEFAULT_QUALITY,FF_DONTCARE,"Arial");

//======= Выясняем вертикальный размер буквы

TEXTMETRIC tm; CClientDC dc(0);

dc.SelectObject(Sm_Font);

dc.GetTextMetrics(Stm);

m_LH = tm.tmHeight;

//======= Создаем шрифт для вывода заголовка

m_TitleFont.CreateFont(24,О,О,0,100, 0, 0, 0,

DEFAULT_CHARSET, OUT_RASTER__PRECIS,

CLIP_DEFAULT_PRECIS, DEFAULT_QUALITY, FF_DONTCARE,

"Times New Roman");

//======= Задаем параметры пера

m_Clr = RGB(0,0,255); m_Width = 2;

}



Метод прогонки



Метод прогонки

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

В предыдущем разделе была сформулирована так называемая первая краевая задача, в которой требуется найти значения функции во внутренних узлах сетки при условии, что на границах области они известны. В теории и на практике рассматриваются задачи с более сложными граничными условиями. Например, когда на одной из границ известна не функция, а ее первая производная — граничное условие второго рода. Имеют место и постановки задач с граничными условиями третьего рода, когда на границе должно выполняться какое-то известное заранее соотношение между функцией и ее первой производной. С точки зрения численной реализации все три типа задач можно описать с помощью соотношений одного и того же вида:

U0=y0U1+б0, (6)

Un=ynUn-1+бn, (7)

Они связывают значения разностных аналогов Ui, непрерывной функции U(x) в двух узлах, прилегающих к левой или правой границе. Так, граничное условие первого рода иUo = с может быть задано с помощью пары параметров: у0= 0, б0 = с, а условие второго рода dU/dx|0= с с помощью другой лары: у0 = 1,бo=ch, где h — это шаг сетки. В нашем приложении будет работать немодальный диалог, который позволит пользователю задавать различные типы граничных условий, изменяя численные значения четырех коэффициентов уo, бo, yn, бn

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

b1U1+c1U2=-a1U0,

видим, что оно совпадает по форме с обобщенным граничным условием (6) и связывает между собой два соседних значения U1, и U2. Перепишем его в виде:

d1U2+e=U1, (8)

где d1 и е1вычисляются по известным значениям. Наблюдательный читатель заметит, что это справедливо только для задач первого рода. Чуть позже мы получим общее решение. Теперь мы можем исключить £/, из уравнения для следующей тройки узлов:

a2U1+b2U2+c2U2=f2,

подставив значение U1 из уравнения (8). После этой процедуры последнее уравнение также может быть приведено к виду:

d3U3+e2=U2,

Подстановки можно продолжать и дальше, но для получения рекуррентного соотношения, достаточно рассмотреть одну из них для произвольного индекса i. Подставив

di-1Ui+ei-1=Ui-1,

в уравнение

aiUi-1+biUi+ciUi+1=fi,

получим:

Ui=-[CiUi+1/(aidi-1+bi)]+[fi-ai+1*ei+1/(aidi-1+bi)] (9)

Это соотношение дает две рекуррентные формулы для коэффициентов:

di=-Ci/(ai*di-1+bi) (10)

ei=(fi-ai*ei-1)/(aidi-1+bi) (11)

Цикл вычисления последовательности коэффициентов в соответствии с этими формулами носит название прямого хода прогонки. Начальные значения коэффициентов определяются предварительно заданным граничным условием (6):

do=yo, eo=бo,

Цикл прямого хода повторяется N-1 раз. Последними будут вычислены коэффициенты dN-1 и eN-1, которые связывают функции в двух узлах вблизи правой границы:

Un-1=dn-1Un+en-1 (12)

Если на правой границе задано условие первого рода Un = с, то уже можно вычислить Un-1 по формуле (12) и далее продолжать обратный ход прогонки, используя уравнения (9) при I = N - 1,..., 1, 0. Если условие более сложное, то вместе с уравнением (12) надо рассмотреть уравнение (7), определяющее граничное условие на правой границе. Напомним его:

Un=ynUn-1+бn (7)

Соотношения (7) и (12) составляют систему из двух уравнений с двумя неизвестными. Используя определители, запишем ее решение.

Un-1=(en-1+бndn-1)/(1-yndn-1) (13)

Un=(бn+ynen-1)/(1-yndn-1)

Таким образом, мы нашли значения в двух узлах, лежащих вблизи правой границы расчетной области. Теперь, используя формулу (9) и уменьшая индекс i от N= 2 до 0, можно вычислить все неизвестные £/.. Этот процесс носит название обратного хода прогонки. Почему-то в голову приходит лозунг нашего времени: «Цели ясны, задачи определены. За работу, товарищи!» Нам осталось всего лишь реализовать описанный алгоритм в виде MFC-приложения.



Отображение графика



Отображение графика

График отображается в такой последовательности. Сначала рисуется ограничивающий прямоугольник (рамка), затем дважды вызывается функция Scale, которая подготавливает данные для разметки осей. После этого выводятся экстремальные значения функции. В этот момент в более сложном случае следует создавать и выводить так называемую легенду графика — информацию о соответствии маркеров и стилей линий определенным кривым. Так как мы изображаем только одну кривую, то эта часть работы сведена к минимуму. Перед тем как отобразить координатную сетку, следует создать и выбрать в контекст другое перо (gridPen). Сама сетка изображается в двух последовательных циклах прохода по диапазонам координат, подготовленных в методе Scale.

В каждом цикле мы сначала нормируем текущую координату, затем преобразовываем ее в оконную, вызывая одну из функций типа MapToLog*. Одновременно с линией сетки выводится цифровая метка. В ходе процесса нам несколько раз приходится менять способ выравнивания текста (см. вызовы SetTextAlign). Подстройка местоположения текста осуществляется с помощью переменной m_LH (better Height), значение которой зависит от выбранного размера шрифта. После вывода координатной сетки происходит вывод трех строк текста: метки осей и заголовок графика. В последнюю очередь происходит вывод самой кривой графика. В более сложном случае, который не реализован, мы в цикле проходим по всем объектам класса MyLine и просим каждую линию изобразить себя в нашем контексте устройства. Каждая линия при этом помнит и использует свой стиль, толщину, цвет и маркировку:

void CGraph::Draw(CDC *pDC) {

//====== С помощью контекста устройства

//====== узнаем адрес окна, его использующего

CWnd *pWnd =pDC->GetWindow();

CRect r;

pWnd->GetClientRect(ir);

//====== Уточняем размеры окна

m_Size = r.Size();

m_Center = CPoint(m_Size.cx/2, m_Size.cy/2);

//====== Сохраняем атрибуты контекста

int nDC = pDC->SaveDC();

//====== Создаем черное перо для изображения рамки

CPen pen(PS_SOLID, О, COLORREF(0));

pDC->SelectObject(Spen);

//====== Преобразуем координаты рамки

int It = MapToLogX(-0.S),

rt = MapToLogX(0.S),

tp = MapToLogY(0.S),

bm = MapToLogY(-0.S);

pDC->Rectangle (It, tp, rt, bm);

//====== Задаем цвет и выравнивание текста

pDC->SetTextColor (0);

pDC->SetTextAlign(TA_LEFT | TA_BASELINE);

//====== Выбираем шрифт

pDC->SelectObject (&m_Font);

//====== Вычисляем атрибуты координатных осей

Scale(m_DataX); Scale(m_DataY);

//====== Выводим экстремумы функции

CString s;

s.Format("Min = %.3g",m_DataY.Min);

pDC->TextOut(rt+m_LH, tp+m_LH, s) ;

s.Format("Max = %.3g",m_DataY.Max);

pDC->TextOut(rt+m_LH, tp+m_LH+m_LH, s);

//====== Готовимся изображать координатную сетку

CPen gridPen(PS_SOLID, 0, RGB(92,200, 178));

pDC->SelectObject(SgridPen);

pDC->SetTextAlign(TA_CENTER | TA_BASELINE);

//======



Преобразование координат



Преобразование координат

В контейнере точек графика, на который ссылается переменная m_Points, хранятся мировые координаты, то есть числа, заданные в тех единицах измерения, которыми пользуется исследователь, решающий дифференциальное уравнение. Это удобно с той точки зрения, что пользователь видит и редактирует величины, к которым он привык. Для изображения графика на экране следует преобразовать мировые координаты в логические, с которыми работает подсистема GDI. На этот раз мы не будем пользоваться услугами Windows для преобразования логических координат в физические. А используем тот факт, что в режиме преобразования MMJTEXT, принятом по умолчанию, логические координаты соответствуют оконным, физическим. Мы сами будем нормировать координаты точек графика, загоняя их в диапазон (-0.5... 0.5), отслеживать изменения в размерах окна и пропорционально изменять размеры графика. По умолчанию у нас выбраны пропорции 0.6 х 0.6, что означает, размеры графика будут составлять 0.6 от размеров клиентской области окна. Преобразование координат производят два метода MapToLogX и MapToLogY. Каждый из них получает нормированную координату, а возвращает оконную. Изображение центрируется в окне с помощью переменной cpoint m_Center, значение которой должно корректироваться при каждой перерисовке. Размеры изображения зависят от текущих размеров окна (переменная csize m_size;), которые также вычисляются при каждой перерисовке:

int CGraph::MapToLogX (double d)

{

return m_Center.x + int (SCALE_X * m_Size.cx * d); }

int CGraph::MapToLogY (double d)

{

return m_Center.y - int (SCALE_Y * m_Size.cy * d); }

//======= Деструктор

CGraph::-CGraph(){}

Деструктор не производит никаких действий, так как в классе CGraph мы не используем динамических типов данных. Контейнер точек m_Points является всего лишь ссылкой на одноименный контейнер, который хранится в классе CChildView. Там же и происходит освобождение его памяти.



Пример с матрицей МКР



Пример с матрицей МКР

Для начала рассмотрим пример использования valarray л его сечения в задаче, более близкой к жизни, чем все другие учебные примеры, приводившиеся ранее. Когда-то вы слышали о том, что электронные вычислительные машины (ЭВМ) изобрели для того, чтобы решать дифференциальные уравнения. Не удивлюсь, узнав, что существуют успешно зарабатывающие на жизнь программированием молодые люди, которые об этом не знают. Однако это правда. Рассмотрим npot стое уравнение, которое способно довольно сносно описать многие процессы и явления нашей жизни j

d/dx(p*(dU/dx))+kU=-f

Это уравнение Пуассона и оно, например, (при k = 0 и f = 0) способно описать стационарное тепловое поле в самом простом одномерном случае, когда температура U = U(x) почему-то зависит только от одной координаты х. Например, в длинном неоднородном стержне, теплоизолированном с боков. Символ р в этом случае имеет смысл коэффициента теплопроводности материала стержня, который в принципе может зависеть от координаты р = р(х), а символ f = f(x) имеет смысл точечного источника тепла. Если f тождественно равна нулю, то мы имеем частный случай — уравнение Лапласа. Источником теплового поля в этом случае является известная температура или скорость ее изменения на границах расчетной области. Отсюда происходит термин краевая задача, то есть задача, в которой заданы граничные условия (условия на краях расчетной области). В задачах такого рода требуется найти все значения температуры внутри области. Областью расчета в одномерном случае является отрезок прямой линии. Например, слева жарко, а справа холодно. Спрашивается, а как распределена температура внутри отрезка?

Считается, что в макромире температура распределена непрерывно, то есть в каждой точке, число которых не поддается счету, она имеет свое собственное значение. При попытке решить задачу на компьютере (сугубо дискретной структуре) надо отказаться от идеи бесконечности и ограничиться каким-то разумным числом точек, например N = 300. По опыту знаю, что график из трехсот точек вполне прилично выглядит на экране. Приняв это решение, разбивают всю область 300 точками на 299 отрезков и заменяют (аппроксимируют) производные дифференциального уравнения конечными разностями. Такова основная идея метода конечных разностей (МКР). При этом одно дифференциальное уравнение заменяется 298 алгебраическими уравнениями по числу внутренних точек, так как две граничные точки не требуют аппроксимации. Вот мы и пришли к необходимости решать систему алгебраических уравнений из 298 уравнений с 298 неизвестными температурами во внутренних точках расчетной области.

Примечание 1
Примечание 1

Точно такое же уравнение описывает и многие другие физические явления. Изменяется лишь смысл параметров р и k. Например, магнитное поле в центральном поперечном сечении электрической машины с некоторыми незначительными поправками, вызванными переходом к цилиндрической системе координат, тоже с успехом может быть описано подобным уравнением.

Для того чтобы поместить матрицу системы алгебраических уравнений в последовательность типа valarray и начать орудовать его сечениями (slice), надо сначала немного потрудиться и хотя бы понять структуру матрицы. Затем следует выработать алгоритм вычисления ее коэффициентов, и только после этого использовать динамические структуры данных и алгоритмы STL для решения задачи.

Тем, кто почувствовал себя неуютно в незнакомой обстановке, скажем, что это нетрудно и даже интересно. Поэтому не торопитесь отбросить книгу, а продолжайте чтение и, может быть, вы еще завоюете мир, разработав великолепный инструмент для решения краевых задач в трехмерной постановке. Для начала рассмотрите схему расчетной области, которая приведена на Рисунок 11.1.



Распределение поля для набора данных по умолчанию



Рисунок 11.3. Распределение поля для набора данных по умолчанию




Разработка SDIприложения



Разработка SDI-приложения

Создайте новый проект типа MFC Application и назовите его Heat, несмотря на то что наша задача немного переросла задачу расчета стационарного теплового поля.

При выборе типа приложения установите переключатель Select application type в положение Single Document и снимите для разнообразия флажок Document/View architecture support.
На странице User Interface Features установите флажок Maximized, с тем чтобы окно приложения при начальном запуске открывалось полностью. На странице Advanced Features можно снять флажок ActiveX Controls.
Нажмите кнопку Finish.

Если вам хочется увидеть, как ведет себя заготовка подобного рода, то запустите приложение (Ctrl+F5) и убедитесь, что его возможности соответствуют стандарту SDI. Откройте файл StdAfx.h и вставьте сакраментальные коды подключения нужных библиотек:

#include <vector> using namespace std;



Решаем краевую задачу



Решаем краевую задачу
Пример с матрицей МКР
Метод прогонки
Разработка SDI-приложения
Класс окна для отображения графика
Класс графика
Конструктор CGraph
Диалог для исследования решений

В этом разделе мы разработаем MFC приложение с SDI-интерфейсом, которое использует контейнеры STL для хранения последовательностей величин, участвующих в формулировке простейшей одномерной краевой задачи матфизики. Сама задача формулируется в виде дифференциального уравнения, связывающего искомую функцию, пространственную координату и параметры, зависящие от свойств среды. Решение системы разностных уравнений, полученных путем аппроксимации дифференциального уравнения на сетке узлов, будет производиться методом прогонки. Контейнеры будут хранить дискретные значения коэффициентов уравнения и разностного аналога непрерывной функции.



Рисуем вертикальные линии сетки



Рисуем вертикальные линии сетки

for (double x = m_DataX.Start;

X < m_DataX.End - m_DataX.Step/2.;

x += m_DataX.Step) {

//====== Нормируем координату х

double xn = (x - m_DataX.Start) /

(m_DataX.End - m_DataX.Start) - 0.5;

//====== Вычисляем оконную координату

int xi = MapToLogX(xn);

//====== Пропускаем крайние линии,

//====== так как они совпатают с рамкой

if (x > m_DataX.Start && x < m_DataX.End)

{

pDC->MoveTo(xi, bm);

pDC->LineTo(xi, tp); )

//====== Наносим цифровую метку

pDC->TextOut (xi, bm+m_LH, MakeLabel(true, x)); }

//=== Повторяем цикл для горизонтальных линий сетки

pDC->SetTextAlign(ТА RIGHT | TA_BASELINE);

for (double у = m_DataY.Start;

у < m_DataY.End - m_DataY.Step/2.; у += m_DataY.Step)

{

double yn = (y - m_DataY.Start) /

(m_DataY.End - m_DataY.Start) - 0.5;

int yi = MapToLogY(yn);

if (y > m_DataY. Start &S, у < m_DataY.End)

{

pDC->MoveTo(lt, yi) ;

pDC->LineTo(rt, yi) ;

pDC->TextOut(lt-m_LH/2,yi,MakeLabel(false, y));

}

}

//====== Вывод меток осей

pDC->TextOut(lt-m_LH/2, tp - m_LH, m_sY);

pDC->SetTextAlign(TA_LEFT | TA_BASELINE);

pDC->TextOut(rt-m_LH, bm + m_LH, m_sX);

//====== Вывод заголовка

if (ra_sTitle.GetLength() > 40)

m_sTitle.Left(40);

pDC->SelectObject(Sm_TitleFont);

pDC->SetTextAlign(TA_CENTER | TA_BASELINE);

pDC->TextOut((It+rt)/2, tp - m_LH, m_sTitle);

//====== Вывод линии графика

DrawLine(pDC);

//====== Восстанавливаем инструменты GDI

pDC->RestoreDC(nDC);

}

Вывод линии графика начинается с создания и выбора пера. Эти действия можно вынести и поместить в какой-нибудь диалог по изменению атрибутов пера, но мы не будем этого делать, так как данное действие целесообразно только в случае, когда график состоит из нескольких линий. Обе координаты каждой точки сначала нормируются переходом к относительным значениям в диапазоне (-0.5*0.5), затем приводятся к оконным. После чего точки графика последовательно соединяются с помощью GDI-функции LineTo:

void CGraph::DrawLine(CDC *pDC) {

//====== Уничтожаем старое перо

if (m_Pen.m_hObject)

m_Pen.DeleteObject() ; //====== Создаем новое

m_Pen.CreatePen(PS_SOLID, m_Width, m_Clr);

pDC->SelectObject(im_Pen);

double x0 = m_DataX.dStart,

y0 = m_DataY.dStart,

dx = m_DataX.dEnd - x0,

dy = m_DataY.dEnd - y0;

//====== Проход по всем точкам

for (UINT i=0; i < m_Points.size(); i++) {

//====== Нормируем координаты

double x = (ra_Points[i].x - xO) / dx - .5,

у = (m_Points[i].у - y0) / dy - .5;

//====== Переход к оконным координатам

CPoint pt (MapToLogX(x) ,MapToLogY(y)) ;

//====== Если точка первая, то ставим перо

if (i==0)

pDC->MoveTo(pt);

else

pDC->LineTo(pt);

}

}



Распределение поля



Рисунок 11.6 Распределение поля в неоднородной среде при наличии осточнтков




Схема расчетных узлов по методу МКР



Рисунок 11.1. Схема расчетных узлов по методу МКР


Напомним, что нашей задачей является найти значения температуры или любой другой функции U во всем множестве точек М = {1, 2, ..., N-2, N-1}, считая, что в двух точках {О, N} она известна. Переход к конечным разностям производится с помощью трехточечного шаблона, который изображен на Рисунок 11.2.



Идентификаторы элементов управления



Таблица 11.1. Идентификаторы элементов управления

Элемент

Идентификатор

Диалог

IDD_PARAM

Окно редактирования Source

IDC_SOURCE

Окно редактирования Start группы Source

IDC_SOURCE1

Окно редактирования End группы Source

IDC_SOURCE2

Окно редактирования Value

IDC_PROP

Окно редактирования Start группы Properties

IDCLPROP1

Окно редактирования End группы Properties

IDC_PROP2

Окно редактирования Nodes

IDC.NODES

Окно редактирования Distance

IDCJHST

Окно редактирования Decrement

IDC_DECR

Окно редактирования g группы Left Boundary

IDC_LEFTG

Окно редактирования d группы Left Boundary

IDCJ.EFTD

Окно редактирования g группы Right Boundary

IDC_RIGHTG

Окно редактирования d группы Right Boundary

IDC_RIGHTD

Кнопка Add группы Source

IDC_ADDSOURCE

Кнопка Add группы Properties

IDC_ADDPROP

Кнопка Apply

IDC_APPLY

Кнопка Close

IDCANCEL

Вручную введите изменения в файл с объявлением класса, так чтобы он стал: ftpragma once

class CParamDlg : public CDialog {

//===== Будем общаться с окном

friend class CChildView;

DECLARE_DYNAMIC(CParamDlg)

public:

//===== Будем помнить его адрес

CChildView *m_pView;

//===== В конструкторе запросим его адрес

CParamDlg(CChildView* р) ;

virtual ~CParamDlg () ;

// Dialog Data

enum { IDD = IDD_PARAM );

protected:

virtual void DoDataExchange(CDataExchange* pDX) ;

DECLARE_MESSAGE_MAP() );

Для всех четырех кнопок на форме диалога создайте обработчики уведомлений, или, используя терминологию Microsoft, Control Event типа BN_CLICKED. Вы помните, что это делается с помощью небольшой кнопки Control Event, которая расположена на панели инструментов окна Properties. В это окно надо входить в тот момент, когда фокус находится на соответствующей кнопке. Во всяком случае, именно так это работает в бета-версии Studio.Net.

Для обмена данными с шестью окнами редактирования (IDC_SOL)RCE, IDC_SOURCE1, IDC_SOURCE2, IDC_PROP, IDC_PROP1, IDC_PROP2) создайте с помощью мастера Add Member Variable Wizard шесть переменных:

//==== Интенсивность источника поля

double m_Source;

// Индекс ячейки сетки, где расположено начало источника

int m_Src!dl;

// Индекс ячейки сетки, где расположен конец источника

int m_Srdd2;

//==== Значение физического свойства ячейки сетки

double m_Prop;

// Индексы начала и конца области со свойством

m_Prop int m_PropIdl;

int m_PropId2;

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

void CParamDlg::DoDataExchange(CDataExchange* pDX) {

DDX_Text (pDX, IDC_PROP2, m_Prop!d2);

DDXJText(pDX, IDC_PROP1, m_Prop!dl);

DDX_Text(pDX, IDC_PROP, m_Prop);

DDX_Text(pDX, IDC_SOURCE2, m_Srdd2);

DDX_Text(pDX, IDC_SOURCE1, ra_SrcIdl);

DDX_Text(pDX, IDC_SOURCE, m_Source);

//===== Обмен с переменными оконного класса

DDX_Text(pDX, IDC_NODES,m_pView->m__n);

DDX_Text(pDX, IDC_DIST, m_pView->m_L);

DDX_Text(pDX, IDC_DECR, m_pView->m_k);

DDX_Text(pDX, IDC_LEFTG, m_pView->m_g0);

DDX_Text(pDX, IDC_LEFTD, ra_pView->m_d0);

DDX_Text(pDX, IDC_RIGHTG, mj?View->m_gn);

DDX_Text(pDX, IDC_RIGHTD, m_pView->m_dn);

CDialog::DoDataExchange(pDX);

}

При нажатии на одну из кнопок Add в соответствующем контейнере параметров системы (m_f или m_r) должны произойти замены значений по индексам, определяемым диапазоном (m_Srddl, m_Srdd2) ИЛИ (m_Prop!dl, m_Prop!d2). В первом случае вы вводите новые источники поля, а во втором — изменяете свойства среды. В уже существующие заготовки функций обработки нажатия на кнопки введите такие коды:

void CParamDlg::OnClickedApply(void) {

//====== Считываем данные из окон

UpdateDataO ;

//====== Заново решаем систему и выводим график

m_jpView->Solve () ; }

void CParamDlg::OnClickedAddsource(void)

{

UpdateData();

//====== Изменяем контейнер m_f (источников поля)

for (int i=m_Src!dl; i <= m_Srdd2; i + + ) {

if (0 <= i && i < m_pView~>m_n)

m_pView->m_f[i] = -m_Source; )

m_pView->Solve0; }

void CParamDlg::OnClickedAddprop(void) { UpdateDataO ;

//====== Изменяем контейнер m_r (свойств среды)

for (int i=m_Prop!dl; i <= m_PropId2; i++) {

if (0 <= i &i i < m_pView->m_n && m_Prop > 0.)

m_pView->ra_r[i] = m_Prop; }

m_pView->Solve(); }

void CParamDlg::OnClickedCancel(void)

{

//====== Закрываем немодальный диалог

m_pView->m_pDlg = 0;

DestroyWindow(); }

Измените коды конструктора класса так, чтобы запоминался обратный указатель на объект оконного класса. Заодно сверьте начало файла ParamDlg.h с тем фрагментом, что приведен ниже:

#include "stdafx.h"

#include "Heat.h"

#include"ParamDlg.h"

IMPLEMENT_DYNAMIC(CParamDlg, CDialog)

CParamDlg::CParamDlg(CChildView* p)

: CDialog(CParamDlg::IDD, p)

{

m_pView = p;

//===== Начальное значение свойств среды

//===== не должно равняться нулю

m_Prop =1.0;

m_Prop!dl = 0;

m_Prop!d2 = 0;

m_Source =0.0;

m_Src!dl = 0;

m_Srdd2 = 0;

}

CParamDlg::~CParamDlg()

{

}

Инициализация диалога, как вы помните, должна производиться в обработчике сообщения WM_INITDIALOG. Здесь я опять попадаю в ловушку. В рамках Visual C++ Studio.Net вы не найдете WM_INITDIALOG в списке доступных сообщений, но вместо этого найдете функцию OnlnitDialog в списке виртуальных функций (overrides). Введите в класс CParamDlg эту функцию. В ней мы просто отодвинем окно диалога, чтобы оно при появлении на экране не заслоняло график. Другие установки должны происходить автоматически:

BOOL CParamDlg::OnInitDialog(void) {

CDialog:rOnlnitDialog();

CRect r;

//===== С помощью контекста устройства

//===== узнаем размеры всего экрана CClientDC dc(this);

int w = dc.GetDeviceCaps(HORZRES);

int h = dc.GetDeviceCaps(VERTRES);

//===== Узнаем размеры окна диалога GetWindowRect(&r);

//===== Смещаем его вправо и вниз

r.OffsetRect(w-r.right-10,h-r.bottom-30);

MoveWindow(Sr);

return TRUE;

}

В данный момент полезно запустить приложение и поучиться сражаться с ошибками, которые вызваны тем, что классы приложения не очень хорошо знакомы между собой. Добавьте директиву:

#include "ChildView.h"

в список директив файла ParamDlg.cpp, а также директиву

#include "ParamDlg.h"

в список директив файла ChildView.cpp. После этого исправления вы увидите еще одно сообщение об ошибке, которое напомнит вам о том, что еще не реализована работа с диалогом в немодальном режиме. Для этого надо немного потрудиться. Введите в класс CChildView реакцию на событие выбора пользователем команды меню ID_EDIT_PARAMETERS. Напомним, что это делается с помощью кнопки Events окна Properties. В обработчике мы открываем диалог в немодальном режиме:

void CChildView::OnEditParameters(void) {

//===== Если диалог не открыт,

if (!m_pDlg)

{

//== Динамически создаем объект диалогового класса

m_pDlg = new CParamDlg(this);

//== и после этого создаем окно диалога

m_pDlg->Create(IDD_PARAM);

}

}

В окне свойств для формы диалога установим в True свойство visible. В классе cParamDlg следует переопределить виртуальную функцию PostNcDestroy, в теле которой необходимо освободить память, занимаемую объектом диалогового класса:

void CParamDlg::PostNcDestroy(void)

{

delete this;

}

После этого диалог должен работать. Задайте точечный источник поля в узле 100, и вы увидите график решения, которое имеет вид, показанный на Рисунок 11.5.



Трехточечный шаблон аппроксимации второй производной



Рисунок 11.2. Трехточечный шаблон аппроксимации второй производной


Мы имеем три точки и два отрезка, которых вполне достаточно, чтобы справиться со второй производной при попытке ее приближенного вычисления. Индексы 1, г и с означают left, right и center. Обозначение pi принято для коэффициента, учитывающего свойства среды левого отрезка, например теплопроводности, а рг — правого. Шаги разбиения области вдоль оси х считаются одинаковыми и равными h. Теперь вы должны представить себе, что центр этого шаблона по очереди приставляется ко всем точкам из множества М. В результате этой процедуры мы по одному будем получать все |М| = N - 1 алгебраических уравнений, приближенно заменяющих одно дифференциальное уравнение Пуассона, которое, как говорят физики, удовлетворяется во всех точках этой части реального пространства.

Возвращаясь к шаблону из трех точек, напомним, что производная по х — это в некотором роде степень изменения функции, то есть скорость ее роста или падения вдоль этой координаты. Приближенно она равна:

dU/dx=(Ur-Uc)/h

для правого отрезка и

dU/dx=(Uc-Ul)/h

для левого. Теперь надо записать приближенную оценку для второй производной с учетом коэффициента теплопроводности. Он может иметь разные значения (р! и рг) в левой и в правой частях шаблона:

d/dx(pdU/dx)={(pr[Ur-Uc])/h-(pl[Uc-Ul])/h}/h (2)

Произведя подстановку в исходное дифференциальное уравнение (1) и упростив выражение, получим алгебраическое уравнение:

aUl+bUc+cUr=0 (3)

связывающее температуры трех соседних узлов сетки с физическими свойствами прилежащих участков пространства, так как значения коэффициентов уравнения зависят от р, k и h:

a=pl/h^2; c=pr/h^2; b=-a-c+k; (4)

Коэффициент а описывает свойства левой части шаблона, а с — правой, а Ь — обеих вместе. Чуть позже мы увидим, что коэффициент b попадет в диагональ матрицы. Теперь надо примерить шаблон ко всем узлам сетки. Узел номер 1 даст уравнение:

a1U0+b1U1+c1U2=0,

узел номер 2:

a2U1+b2U2+c2U3=0,

и т. д. Здесь важно следить за индексами. Для простоты пока считаем, что коэффициенты а,, b,, с, не изменяются при переходе от узла к узлу. В узлах сетки вблизи границ (то есть в узле 1 и узле N-1) уравнения упрощаются, так как £/„ и UN считаются известными и поэтому перемещаются в правую часть уравнения. Так, первое уравнение системы станет:

b1U1+c1U2=0,

а последнее:

an-1Un-2+bn-1Un=+1=0,

Все остальные уравнения будут иметь вид (3). Теперь пора изобразить всю систему уравнений, используя матричные обозначения и не отображая многочисленные нули. Для простоты будем считать, что N = 5:

b1 c1 U1 -a1U0
a2 b2 c2 U2 0
a3 b3 c3 U3 = 0
a4 b4 U4 -c4U5

Вы видите, что матрица системы уравнений имеет характерную регулярную трех-диагональную структуру, а структура вектора правых частей тоже легко прочитывается. Граничные; условия краевой задачи заняли подобающие им крайние места, а внутренние позиции — нули.

Решать такую систему следует специальным методом, который называется методом прогонки и является модификацией метода Гаусса. Он работает во много раз быстрее самого метода Гаусса. Мы реализуем его немного позже, а сейчас попробуем применить алгоритм generate из библиотеки STL для генерации матрицы, имеющей рассмотренную структуру, и вектора решений U. В простых случаях он известен и легко угадывается. Затем с помощью сечений произведем умножение Матрицы на вектор и убедимся в том, что вектор правых частей системы уравнений будет иметь правильную структуру и значения. Эту часть работы рассматривайте как дополнительное упражнение по использованию структур данных типа valarray и slice. В процессе решения краевой задачи мы будем пользоваться контейнерами другого типа (vector), так как метод прогонки не требует применения каких-то особых приемов работы с сечениями.

Если для простоты принять р = 1, h = 1, U0 = 100, a UN =0, то коэффициенты матрицы будут равны ai = сi = 1, bi. = -2 , k = 0, а решение U(x) известно заранее. Это — линейно спадающая от 100 до 0 функция, а в более общем случае — функция произвольных граничных условий:

U(x)=U0+[Un-U0]x/L

где L — длина всей расчетной области. Правильность решения проверяется прямой подстановкой в уравнение (1).



Управление параметрами краевой задачи из диалога



Рисунок 11.5. Управление параметрами краевой задачи из диалога




Вспомогательная функция



Вспомогательная функция

Напомним, что идеи, заложенные в алгоритме выработки цифровой метки на оси графика, принадлежат Александру Калимову, а сам алгоритм разрабатывался при его активном участии. Функция Make Label понадобилась нам в связи с тем, что переход к экспоненциальной форме числа требует некоторых усилий. Мы надеемся, что он будет происходить достаточно редко, так как алгоритм генерации цифровой метки использует методику «жизни без порядка в диапазоне семи порядков», описанную выше. Однако если все-таки диапазон изменения функции или даже координаты X выйдет за обозначенные пределы, то экспоненциальная форма неизбежна. При всем этом мы должны попытаться не делать метку слишком длинной. Экспоненциальная форма создается нами так, чтобы она была более компактной. Если доверить эту работу функциям системы, то они припишут ' знак порядка и лидирующие нули, от которых необходимо избавиться. Но если ее укоротить слишком сильно, то невозможно будет различить две соседние метки. Поэтому при определении количества необходимых разрядов мантиссы анализируется шаг сетки вдоль текущей оси графика. Вся эта черновая работа и производится в теле функции MakeLabel:

CString CGraph::MakeLabel(bool bX, doubles v) {

CString s = "0.0";

if (v == 0.)

return s;

//====== Сначала делаем грубую прикидку

//====== Пробуем поместиться в 20 позиций

s.Format("%20.10f",v);

//====== Выясняем порядок шага сетки,

//====== переворачивая его знак (трюк)

int nDigits = int(ceil(-loglO(bХ ?m_DataX.Step

: m_DataY.Step)) ) ;

//====== Если все изменения происходят до запятой,

//====== то цифры после запятой нас не интересуют

if (nDigits <= 0)

nDigits = -1;

else

if(bХ)

nDigits++; // Эстетическая добавка

//====== Слева усекаем все

s .TrimLeft () ;

//====== Справа оставляем минимум разрядов

s = s.Left(s.Find(".") + nDigits + 1);

int iPower = bX ? m_DataX.Power : m_DataY.Power;

( //====== Нужен ли порядок?

if (iPower != 0)

{

//=== Нужен, если не поместились в (10"-3, 10А+4)

CString add;

add.Format("-e%+d",iPower);

s += add;

}

return s;

}

В настоящий момент можно запустить проект на выполнение. Вы должны увидеть распределение поля, изображенное на Рисунок 11.3.

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