Сортировка.

Примеры:

Sort () – простая сортировка.

Stable_sort () – сохраняет порядок следования одинаковых элементов

(например, это бывает существенно при сортировке по нескольким ключам).

Merge () – склеивает две отсортированные последовательности.

Пример: шаблонная функция find() с тремя параметрами (итератор, с какого начинается поиск, каким заканчивается и искомый элемент). Для реализации целей функции достаточно итератора ввода (из контейнера).

Template < class InputInterator, class T >

InputIterator find (InputIterator first, InputIterator last, const T& value) {

while (first!= last && * first!= value)

first ++;

return first;

}

48. Важнейшие библиотеки С и C++. Заголовочные файлы Microsoft С и C++. Стандартные функции общего назначения (stdlib.h). Преобразование данных. Преобразование числа с плавающей точкой в строку. Преобразование строки в длинное целое.

Стандартные C++ библиотеки представляют собой наборы функций, констант, классов, объектов и шаблонов, которые расширяют язык С++ предоставляя базовую функциональность для выполнения различных задач, таких как: классы для взаимодействия с операционной системой, контейнеры данных, манипуляторы для работы с этими данными и наиболее используемые алгоритмы.
Все элементы стандартных библиотек С++ распределены по различным заголовочным файлам, которые необходимо подключать к программе.

В современной спецификации для языка C++ заголовки указываются с использованием стандартных имен заголовков, которые не имеют расширения.h (т.е. заголовки C++ не означают имена файлов). Это просто стандартные идентификаторы, которые компилятор может обрабатывать так, как считает нужным (т.е. заголовок может быть преобразован в имя файла, но это вовсе необязательно). С++-заголовки приведены ниже. Указанная в скобках аббревиатура STL означает прямую или косвенную связь данного заголовка со стандартной библиотекой шаблонов (Standard Template Library).

Заголовок C++	Что поддерживает
<algorithm>	Различные операции на контейнерах (STL)
<bitset>	Битовые множества (STL)
<complex>	Комплексные числа
<deque>	Двухсторонние очереди (STL)
<exception>	Обработка исключительных ситуаций
<fstrearn>	Работа с файловыми потоками для чтения и записи в один и тот же файл
<functional>	Различные объекты-функции (STL)
<iomanip>	Манипуляторы ввода-вывода
<ios>	Классы ввода-вывода нижнего уровня
<iosfwd>	Упреждающие объявления для систем ввода-вывода
<iostream>	Стандартные классы ввода-вывода
<istream>	Обработка входных потоков
<iterator>	Доступ к содержимому контейнеров (STL)
<limits>	Различные ограничения реализации
<list>	Линейные списки (STL)
<locale>	Информация, связанная с традициями конкретных стран или географических регионов
<map>	Отображения (ключи и значения) (STL)
<memory>	Распределение памяти с помощью распределителей памяти (STL)
<new>	Выделение памяти с помощью оператора new
<numeriс>	Универсальные операции над числами
<ostream>	Обработка выходных потоков
<queue>	Очереди (STL)
<set>	Множества (STL)
<sstream>	Обработка строковых потоков
<stack>	Стеки(SLT)
<stdexcept>	Стандартные исключительные ситуации
<streambuf>	Буферизированная обработка потоков
<string>	Стандартный класс string (STL)
<typeinfo>	Динамическая информация о типе
<utility>	Шаблоны общего назначения (STL)
<valarray>	Операции над массивами, содержащими значения
<vector>	Векторы (динамические массивы) (STL)

В стандартном языке C++ вся информация, связанная со стандартной библиотекой, определена в пространстве имен std. Следовательно, для получения прямого доступа к этим элементам после включения нужного заголовка вам придется использовать следующий оператор using.

stdlib.h — заголовок (заголовочный файл) стандартной библиотеки общего назначения языка Си, который содержит в себе функции, занимающиеся выделением памяти, контроль процесса выполнения программы, преобразования типов и другие. Заголовок вполне совместим с C++ и в C++ известен как cstdlib. Название «stdlib» расшифровывается как «standard library» (стандартная библиотека).

Члены stdlib.h можно разделить на следующие категории: преобразования типов, управление памятью, контроль процесса, сортировка и поиск, математика.

Имя	Описание
Преобразование типов
atof	строка в число двойной точности (НЕ float)
atoi	строка в целое число
atol	строка в длинное целое число
strtod	строка в число двойной точности (double)
strtol	строка в длинное целое число
strtoul	строка в беззнаковое длинное целое число (unsigned long int)
Генерация псевдослучайных последовательностей
rand	генерирует псевдослучайное значение
srand	устанавливает начальное значение генератора псевдослучайных чисел
Выделение и освобождение памяти
malloc calloc realloc	выделяет память из кучи
free	освобождает память обратно в кучу
Контроль процесса выполнения программы
abort	некорректное завершение выполнения
atexit	регистрирует обратный вызов функции для выхода из программы
exit	завершает выполнение программы
getenv	извлекает переменные окружения
system	выполняет внешнюю команду
Сортировка и поиск
bsearch	двоичный поиск в массиве
qsort	сортировка массива
Математика
abs labs	абсолютная величина
div ldiv	деление целых чисел
Многобайтовые операции/ широкие символы
mblen	размер многобайтовых символов^[1]
mbtowc, wctomb, mbstowcs, wcstombs	преобразование многобайтовых и широких символов^[2]

В C++ различают явное и неявное преобразование типов данных. Неявное преобразование типов данных выполняет компилятор С++, а явное преобразование данных выполняет сам программист. Результат любого вычисления будет преобразовываться к наиболее точному типу данных, из тех типов данных, которые участвуют в вычислении.

x	y	Результат деления	Пример
делимое	делитель	частное	x = 15 y = 2
int	int	int	15/2=7
int	float	float	15/2=7.5
float	int	float	15/2=7.5

Явное преобразование необходимо для того чтобы выполнять некоторые манипуляции, тем самым меняя результат вычисления. Пример: необходимо разделить 15 и 2, делим: 15/2=7. Но если сделать незначительные преобразования, например: 15.0/2=7.5 при таком делении число 15 является вещественным, значит и результат будет вещественный.

Еще один способ явного преобразования типов данных:

float(15) / 2 // результат равен 7.5, число 15 преобразуется в вещественный тип данных float. double(15) / 2 // результат равен 7.5

В С++ также предусмотрена унарная операция приведения типа:

static_cast</*тип данных*/>(/*переменная или число*/)

пример: static_cast<float>(15)/2 результат равен 7.5
Пример с переменной:

int ret=15; static_cast<float>(ret)/2 //результат равен 7.5

Переменная ret не преобразуется в тип данных float, а создается временная копия переменной ret с типом данных float.

#include "stdafx.h" #include <iostream> #include <iomanip> using namespace std; int _tmain(int argc, _TCHAR* argv[]) { int int_value15 = 15, int_value2 = 2; // объявляем две переменные типа int float float_value15 = 15, float_value2 = 2; // объявляем две переменные типа float cout << fixed << setprecision(2) // определяем, при выводе чисел с плавающей точкой, два знака после запятой << "15 / 2 = " << int_value15 / int_value2 << endl //неявное преобразование << "15 / 2 = " << int_value15 / float_value2 << endl //неявное преобразование << "15 / 2 = " << float_value15 / int_value2 << endl //неявное преобразование << "15 / 2 = " << float_value15 / float_value2 << endl; //неявное преобразование cout << "15.0 / 2 = " << 15.0 / 2 << endl // явное преобразование, число 15.0 – число с плавающей точкой << "15 / 2.0 = " << 15 / 2.0 << endl; // явное преобразование, число 2.0 - число с плавающей точкой cout << "float(int_value15) / int_value2 = " << float(int_value15) / int_value2 << endl // явное преобразование типа данных << "15 / double(2) = " << 15 / double(2) << endl; // используя приводимый тип как функцию cout << "static_cast<float>(15) / 2 = " << static_cast<float>(15) / 2 << endl // унарная операция приведения типа << "static_cast<char>(15) = " << static_cast<char>(15) << endl // можно печатать различные символы из таблицы ASCII, << "static_cast<char>(20) = " << static_cast<char>(20) << endl; // в скобочках прописываем код символа, который находим в таблице ASCII system("pause"); return 0; }

Выполняется преобразование строки в число благодаря штатным библиотекам функций atoi, atof, atol. Эти функции входит в стандартную библиотеку языка и присутствует в любом компиляторе. Их объявления выглядит так:

int atoi (const char * str)

long atol (const char * str)

double atof (const char * str)

На вход они принимают указатель на строку, завершенную нулем, а возвращают - число, которое этой строкой описывается. atoi и atol воспринимают следующий формат числа:
[ пробелы ][ знак ] цифры
а atof, соответственно:

[ пробелы ][ знак ][ цифры ][. цифры ][{ d | D | e | E }[ знак ] цифры ]
Здесь пробелы - любой из знаков пробела, табуляции (\t), вертикальной табуляции (\v) - они игнорируются. Знак - символ '+' или '-'. Если не указан, то считается, что число положительное. Цифры - символы от '0' до '9'. Для числа с плавающей точкой, если не указаны цифры до знака '.', то должна быть указана хотя бы одна цифра после него. После дробной части может быть указана экспонента, следующая за одним из символов-префиксов экспоненты.
Основной недостаток этих функций заключается в том, что они никак не сигнализируют об ошибке, если таковая произошла в процессе разбора переданной строки.
Эту проблему решает следующий набор библиотечных функций, также включенных в стандартную библиотеку:

long strtol (const char * str, char ** end_ptr, int radix)

unsigned long strtoul (const char * str, char ** end_ptr, int radix)

double strtod (const char * str, char ** end_ptr)

Эти функции имеют следующие отличия от предыдущей группы:

• Через параметр end_ptr они возвращают указатель на первый символ, который не может быть интерпретирован как часть числа.
• Контролируют переполнение и, если таковое произошло, сигнализируют об этом выставлением значения переменной errno в ERANGE, а также возвращают, соответственно, LONG_MAX/LONG_MIN, ULONG_MAX/ULONG_MIN и +/-HUGE_VAL в зависимости от знака числа в переданной строке.
• strtod использует информацию о текущих установленных (через setlocale) региональных настройках, таким образом может корректно интерпретировать числа с символом ',' в качестве разделителя целой и дробной части.
• Для функций strtol и strtoul можно указать основание системы счисления. При этом, если в качестве основания передан 0, то основание определяется автоматически по первым символам числа. Если это символ '0', а сразу за ним идет цифра - то основание принимается равным 8. Если первая цифра '0', а за ней идет символ 'x' или 'X', то основание принимается равным 16. В остальных случаях основание принимается равным 10. В качестве цифр в этом случае можно использовать символы '0' - '9' и 'A' - 'Z' или 'a' - 'z', а основание может принимать значения от 2 до 36.
• Если варианты этих функций для преобразования чисел, описанных unicode-строками. Они, соответственно, носят названия wcstol wcstoul и wcstod.

char* end_ptr;

long val = strtol(str, &end_ptr, 10);

if (*end_ptr)

{// Сигнализируем об ошибке в строке

}

if ((val == LONG_MAX || val == LONG_MIN) && errno == ERANGE)

{// Сигнализируем о переполнении

}// Продолжаем штатную работу.

Преобразование вещественного числа в строку символов:

1. char *ectv(double value, int ndig, int *dec, int *sign);
2. char *fctv(double value, int ndig, int *dec, int *sign);

Функции возвращают указатель на статический буфер памяти с выходной строкой, содержащей только цифры числа. Буфер обновляется при каждом вызове функции. Для функции ectv() ndig является числом цифр в выходной строке, для fctv() - числом цифр в выходной строке после десятичной точки. Параметр dec показывает положение десятичной точки в выходной строке, которая явно не присутствует. Параметр sign принимает отличное от нуля значение для отрицательных чисел.

Преобразование вещественного числа в строку:

1. char *gctv(double value, int ndec, char *buf);

Функции возвращают указатель на буфер buf памяти с выходной строкой, содержащей готовое к печати символьное представление числа из ndec цифр в формате F Фортрана, если возможно. В противном случае число будет представлено в формате e функции printf().

Работа со строковыми функциями. Сравнение содержимого двух строк. Поиск в строке одного из нескольких символов. Первое вхождение одного символа в строке. Определение длины строки. Нахождение одной строки внутри другой. Приведение символов к верхнему регистру.

Дата добавления: 2015-09-03