#include <stdlib.h>
#include <iostream>
using namespace std;

//=== Внешняя функция сравнения переменных типа int
inline int cmp (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;
}



#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;
}



void QuickSort (double *ar, int l, int r)
{
	//========== Рабочие переменные
	double mid, temp;
	//========== Левая и правая границы интервала
	int i = l, j = r;

	//========== Центральный элемент
	mid = ar[(l + r) / 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;
		}
	}
	//========= Цикл повторяется, пока 
	//========= есть нарушения последовательности
	while (i <= j);	

	//========= Если левая часть не упорядочена,
	if (l < j)
		QuickSort (ar, l, 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[i]);
	}

	QuickSort(ar,0,N-1);		// Сортировка

	puts("\n\nAfter Sorting\n");
	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(T *ar, int l, int r)
{
	//======= Рабочие переменные
	T mid, temp;
	//======= Далее следует тот же код, который приведен
	//======= в оригинальной версии функции QuickSort
}



void main()
{
	//======= Размер массива сортируемых чисел
	const int N = 21;
	//	double ar[N];
	int 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[i]);
		printf ("%d\t",ar[i]);
	}

	QuickSort(ar,0,N-1);
	
	puts("\n\nAfter Sorting\n");
	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");
}



#include <iostream>
#include <string>
#include <math.h>

//====== Шаблон классов "Вектор линейного пространства"
template <class T> class Vector
{
//====== Данные класса 
private:
	T *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 T[n];
	size=n;
};

//====== Вспомогательный класс	"Круг"
class Circle
{
private:
	//====== Данные класса 
	int x, y;		// Координаты центра
	int r;			// Радиус
public:
	//====== Два конструктора 
	Circle ()
	{
		x=y=r=0; 
	}

	Circle (int a, int b, int c)
	{
		x=a;
		y=b;
		r=c;
	}

	//====== Метод для вычисления площади круга
	double area()
	{
		return 3.14159*r*r;
	}
};

//====== Глобальное определение нового типа
//====== указателя на функцию
typedef double (*Tfunc)(double);

void main()
{
	//===== Генерируется вектор целых
	Vector <int> x(5);
	int i;
	for (i=0;  i < x.Size();  ++i)
	{
		x[i]=i;					// Инициализация
		cout<<x[i]<<' ';			// Вывод
	}
	cout << '\n';

	//===== Генерируется вектор вещественных
	Vector <float> y(10);
	for (i=0;  i < y.Size();  ++i)
	{
		y[i] = float(i);			// Инициализация
		cout<<y[i]<<' ';			// Вывод
	}
	cout << '\n';

	//==== Генерируется вектор объектов класса Circle
	Vector <Circle> z(4);
	for (i=0; i< z.Size(); ++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[1] = sin;
	f[2] = tan;
	
	for (i=0; i< f.Size(); ++i)
		cout<<f[i](3.)<<' ';			// Вывод

	cout << "\n\n";
}



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 (string& 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 Man& m)
	{
		//======= Упорядочиваем по имени
		return m_Name < m.m_Name;
	}

	friend ostream& operator<< (ostream& os, const Man& m);
};

//========= Внешняя реализация операции вывода
ostream& operator<<(ostream& os, const Man& m)
{
	return os << m.m_Name << ", Age: " << m.m_Age;
}



class Vector <Man>
{
	T *data;
	int size;
public:
	Vector (int n, T* m);
	~Vector () {  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];
}



Man art("Art Davis", 60);		// Отдельный Man

//====== Массив объектов класса Man
Man some[] =
{
	Man("Count Lazy",70),
	Man("Duke Elling",90),
	art,
	Man("Winton Marsh",50),
};



//====== Конструируем вектор объектов
//====== на основе массива объектов
Vector <Man> men(sizeof(some)/sizeof(Man), some);

cout<<"\nVector of Man: ";

//====== Вывод вектора
for (i=0; i< men.Size(); ++i)	
	cout << men[i] << ";  ";



#include <vector>
#include <algorithm>
#include <iostream>

using namespace std;

//======= Вводим тип для сокращения текста (места)
typedef unsigned int uint;

void main ()
{
	//======== Вектор целых
	vector<int> v(4);

	cout << "\nInt 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.end());
	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()
		<< "\nVector's capacity: " << v.capacity() << endl;

	//======== Резервирование
	v.reserve(100);
	cout << "\nAfter reserving storage for 100 elements:\n"
		<< "Size: " << v.size() << 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() << endl
		<< "Maximum size: " << v.max_size() << endl
		<< "Capacity: " << v.capacity() << endl;

	cout << "\n\n";
}



//===== Шаблон функции для вывода с помощью итератора
template <class T> void pr(T& v, string s)
{
	cout<<"\n\n\t"<<s<<"  # Sequence:\n";
	//====== Итератор для любого контейнера
	T::iterator p;
	int i;

	for (p = v.begin(), i=0;  p != v.end();  p++, i++)
		cout << endl << i+1 <<". "<< *p;
	cout << '\n';
}



#include <vector>
#include <string>
#include <algorithm>			// Для sort и distance
#include <functional>		// Для greater<string>()
#include <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 distance\n";

	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;
}



bool LessAge (Man& a, Man& b)
{
	//======== Сравниваем по возрасту
	return a.m_Age < b.m_Age;
}



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.end());
	pr(men,"After default sort");
		
	//======== Используем предикат
	sort(men.begin(), men.end(), LessAge);
	pr(men,"After predicate LessAge sort");

	cout << "\n\n";
}



enum SORTBY { NAME, AGE };	// Режимы сортировки


static SORTBY m_Sort;		// Текущий режим сортировки


	//======= Определение и инициализация
SORTBY Man::m_Sort = NAME;


	//======= Функциональный объект имеет доступ к данным
	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);
	}
};



//========= Используем функциональный объект
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");



//========= Используем стандартный предикат
sort(men.begin(), men.end(),less<Man>());
pr(men,"After less<Man> sort");



//========= Нужна для предиката less<Man>()
friend bool operator< (const Man& a, const Man& b);


bool operator<(const Man& a, const Man& b)
{
	//======== Сравниваем по возрасту
	return a.m_Age < b.m_Age;
}


sort(men.begin(), men.end(),less<Man>());


//========= Используем отрицатель бинарной операции
	sort(men.begin(), men.end(), not2(less<Man>()));
	pr(men,"After not2(less<Man>) sort");



//========= Предикат принадлежности к teenager
friend bool Teen (Man& m);


//========= Предикат принадлежности к teenager
bool Teen(Man& m)
{
	return 13 < m.m_Age && m.m_Age < 19;
}



void main ()
{
	//======== Набор объектов класса Man
	Man	joe("Joe Doe",30),
		joy("Joy Amore",18),
		mary("Mary Poppins",36),
		duke("Duke Elling",90),
		liza("Liza Dale", 17),
		simon("Simon Paul",15),
		zoran("Zoran Todorovitch",27),
		art("Art 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.end(), Teen);
	
	//======== Ручной поиск всех таких объектов
	while (p != men.end())
	{
		cout << "\nTeen:  " << *p;
		
		p = find_if(++p, men.end(), Teen);
	}
	
	cout << "\nNo more Teens\n";
	
	//======== Подсчет всех teenagers
	uint teen = count_if (men.begin(),men.end(), 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.rend();  r++)
		cout<<*r<<";  ";

	//======== Заполняем вектор целых
vector<int> v;
	for (int i=1; i<4; i++)
		v.push_back(i);

	//======== Иллюстрируем алгоритм и адаптивный functor
	transform(v.begin(), v.end(), v.begin(), negate<int>());
	pr(v,"Integer Negation");

	//======== Создаем еще два вектора целых
	vector<int> v1(v.size()), v2(v.size());

	//======== Иллюстрируем алгоритм заполнения вектора
	fill (v1.begin(), v1.end(), 100);

	//======== Иллюстрируем проверку
	assert(v1.size() >= v.size() && v2.size() >= v.size());

	//======== Иллюстрируем вторую версию transform
	transform(v.begin(), v.end(), v1.begin(), v2.begin(),
									plus<int>());
	pr(v2,"Plus");

	cout << "\n\n";
}



void OutTeen(Man& m)
{
	// Если парамтр удовлетворяет предикату, то выводим его
	if (Teen(m))
		cout << "\nTeen:  " << m;
}



//======== Выделяем имя
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;
}



void main ()
{
	Man ar[] =
	{
		joy, joe, zoran, 
		mary, 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";
}



//======== Базовый класс. К сожалению, абстрактным
//======== его не позволит сделать контейнер
struct Stud
{
	virtual bool print()
	{
		cout << "\nI'm a Stud";
		return true;
	}
};

//======== Производный класс
struct GoodStud : public Stud
{
	bool print ()
	{
		cout << "\nI'm a Good Stud";
		return true;
	}
};

//======== Еще один производный класс
struct BadStud : public Stud
{
	bool print ()
	{
		cout << "\nI'm a Bad Stud";
		return true;
	}
};

//======== Иллюстрируем полиморфизм в действии
void main ()
{
	//======== Вектор указателей типа Stud*
	vector<Stud*> v;

	//======== Они могут указывать и на детей
	v.push_back(new Stud());
	v.push_back(new GoodStud());
	v.push_back(new BadStud());

	//======== Выбор тела метода происходит поздно
	//======== на этапе выполнения
	for_each(v.begin(), v.end(), mem_fun(&Stud:: print));

	cout <<"\n\n";
}



void main ()
{
	deque<double> d;
	d.push_back(0.5);
	d.push_back(1.);
	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";
}



void main ()
{
	deque<Man> men;
	
	men.push_front (Man("Jimmy Young",16));
	men.push_front (simon);
	men.push_back (joy);
	pr(men,"Man Deque");

	//======== Поиск точного совпадения
	deque<Man>::iterator p = find(men.begin(),men.end(),joy);

	men.insert(p,mary);
	pr(men,"After inserting mary");
	
	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
	d.assign(3,win);

	//======== Обмениваем данные
	d.swap(men);
	pr(men,"After swap with another deque");

	cout<<"\n\n";
}



void main ()
{
	list<Man> men;

	men.push_front(zoran);
	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(joe);
	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(simon);

	//======== Создаем очередь
	deque<Man> d(men.size());

	//======== Копируем в нее список
	copy(men.begin(), men.end(), d.begin());
	pr(d,"Deque copied from list");

	//======== Создаем вектор
	vector<Man> v(men.size() + d.size());

	//==== Соединяем список и очередь и помещаем в вектор
	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";
}



//========= Создаем список целых
list<uint> lst(6);

//========= Генерируем степенную последовательность
generate (lst.begin(), lst.end(), pows);
pr(lst,"List of generated powers");



uint pows()
{
	static uint r = 1;
	r *= 2;
	return r;
}



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");



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.end(), -1);
	pr(s, "Set of ints");

	//======== Второе множество
	set<int> ss;
	for (int i=1; i<5; i++)
		ss.insert(i*10);

	//======== Вставляем диапазон
	s.insert(++ss.begin(), --ss.end());
	pr(s, "After insertion");

	cout<<"\n\n";
}



//========= Предикат
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;
	}
};



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 B: ";
	set_union(A.begin(), A.end(), B.begin(), B.end(),
				ostream_iterator<const char*>(cout, ", "),
				LessStr());
	//======= Создаем и выводим пересечение двух множеств
	cout << "\n\nIntersection A & B: ";
	set_intersection(A.begin(), A.end(), B.begin(), B.end(),
				ostream_iterator<const char*>(cout, " "),
				LessStr());

	//===== Создаем разность двух множеств
	//===== Используем inserter для заполнения множества C
	set_difference(A.begin(), A.end(), B.begin(), B.end(),
		inserter(C, C.begin()),
		LessStr());

	cout << "\n\nDifference A/B: ";
	//===== Копируем множество прямо в выходной поток
	copy(C.begin(), C.end(),
				ostream_iterator<const char*>(cout, " "));

	C.clear();
	//===== Повторяем в обратную сторону
	set_difference(B.begin(), B.end(), A.begin(), A.end(),
				inserter(C, C.begin()), LessStr());
	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.end(), os);

	//====== Обычные массивы символов
	char D[] = { 'a', 'b', 'c', 'd', 'e', 'f' };
	char E[] = { 'A', 'B', 'C', 'G', 'H', '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++)
		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";
}



void main ()
{
	//========== Массив объектов класса Man
	Man ar[] =
	{
		joy,	duke,	win,
		joy,	art
	};
	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\nInserting: " << *pib.first
		<< "\nResult is: " << pib.second;

	//========== Пробуем вставить повторно
	pib = s.insert(joy);
	cout << "\n\nInserting: " << *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";
}



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\nInserting: " 
		<< (*pib.first).first << ", "
		<< (*pib.first).second
		<< "\nResult is: " << pib.second;

	pib = m.insert(p);
	cout << "\n\nInserting: " 
		<< (*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.insert(*pp);
	delete pp;

	cout<<"\n\n\t <string,int> pairs:\n";

	for (it = m.begin();	it != m.end();  it++)
		cout << "\n(" << it->first<<", "<<it->second<<")";		
	cout<<"\n\n";
}



//======= 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, mary));
	h.insert (ManPair (115, joe));
	h.insert (ManPair (100, win));
	h.insert (ManPair (100, art));
	h.insert (ManPair (115, liza));
	h.insert (ManPair (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<ManMapIt, 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";
}



void main()
{
	//========= Создаем стек целых
	stack<Man> s;
	s.push(joy);
	s.push(joe);
	s.push(art);

	//========= Проверяем очевидные вещи
	assert(s.size() == 3);
	assert(s.top() == art);
	
	cout << "Stack contents:\n\n";
	while (s.size())
	{
		cout << s.top() << ";  ";
		//========= Уничтожает top-элемент
		s.pop();
	}
	
	assert(s.empty());
}



void main ()
{
	//========== Массив объектов класса Man
	Man ar[] =
	{
		joy,	mary,	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; i<size; i++)
		q.push(ar[i]);
	
	cout << "\n\nQueue of Man:\n\n";
	while (q.size())
	{
		cout << q.front() << ";  ";
		q.pop();
	}

	cout<<"\n\n";
}



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();
	}
}



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> > StrIn;
	typedef ostream_iterator<string, char,
									char_traits<char> > StrOut;

	//========== Копируем контейнер в выходной поток
	copy(v.begin(), v.end(), StrOut(os,"\n"));
	os.close();

	//========== Открываем файл для чтения
	ifstream 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(StrIn(is),StrIn(),back_inserter(v));

	pr(v,"After reading from file");
	cout<<"\n\n";
} 



//====== Две тестовые текстовые строки
string source("Test"), target;

//====== Ссылка на второй символ в строке
char& c = source[1];

//====== Если данные не копируются при присвоении
target = source;
//====== то это присвоение изменит обе строки
c = 'z';
//====== Этот тест позволяет выяснить ситуацию
cout << (target[1] == 'z' ? "\nWrong" : "\nRight");



//====== Множество пустых символов
char White " \n\t\r";

//====== Ищем реальное начало строки
//====== и усекаем лишние символы слева
s = s.substr(s.find_first_not_of(White));

//====== Переворачиваем строку и повторяем процедуру
reverse(s.begin(), s.end());
s = s.substr(s.find_first_not_of(White));

//====== Вновь ставим строку на ноги
reverse(s.begin(), s.end());



//====== Преобразование строки по принципу Pig Latin
string PigLatin (const string& s)
{
	string res;

	//======= Перечень разделителей слов
	string sep(" .,;:?");

	//======= Длина всей строки
	uint size = s.length();

	for (uint start=0, end=0, cur=0;  cur < size;  cur=end+1)
	{
		//==== Ищем позицию начала слова, начиная с 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+1, end-start) + s[start] +"ay";
	}
	return res;
}



#include <limits>
#include <climits> 
#include <cfloat>
#include <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>::digits10;

	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_exponent10;

	cout << "\n The maximum exponent is: "
		<< numeric_limits<float>::max_exponent;

	cout << "\n The maximum exponent in base 10: "
		<< numeric_limits<float>::max_exponent10;

	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;




#include <iostream>
#include <algorithm>
#include <valarray>
#include <limits> 

using namespace std;
.
void main()
{
	//======== Вспомогательные переменные
	double	PI = atan(1.)*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 x=0.;  x < xf;  x += dx)
		vx[i++] = x;

	//======== Ординаты вычисляются без помощи цикла
	vy = sin(vx);

	cout<<"Valarrays of x and sin(x)\n";
	for (i=0;  i < size;  i++)
		cout<<"\nx = " << vx[i] <<"   y = "<< vy[i];
}



//======= Конструктор создает 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=1;  i < size;  i++)
	cout<<"\nx = " << vx[i] <<"   y = "<< vd[i];



//======= Функциональный объект, применяемый к каждому
//======= элементу valarray
double Sharp (double x)
{
	return x != 0. ? 1/(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();
}



	//======== Циклический сдвиг на 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);



int	n = 5,			// Размерность матрицы n (точнее, nn)
		nn = n*n; 	// Размерность valarray

//==== Создаем матрицу (одномерную последовательность)
valarray<double> a(nn);

//==== Генерируем ее элементы по закону f (Пока его нет)
generate (&a[0], &a[nn], f);

//====== Создаем сечение
slice s (0, n , 1);

//====== Выделяем сечение (первую строку,
//====== если матрица хранится по строкам)
valarray<double> v = a[s];