Этот документ описывает библиотеку AP, адаптированную для языка C++. Библиотека AP для С++ содержит базовый набор математических функций и классы-коллекции, которые требуются для работы программ с сайта "Библиотека алгоритмов".
Данная библиотека должна быть совместима с любым компилятором С++.
В состав библиотеки входят файлы ap.h и ap.cpp. Для начала работы достаточно подключить файл ap.cpp к проекту.
В заголовочном файле ap.h определяется пространство имен ap. Следует учитывать, что имена функций, констант и классов, приведенные дальше, следует предварять префиксом ap::
AP_WIN32
Этот символ, если он определен пользователем, сообщает библиотеке, что она компилируется в Win32. Определение этого символа позволяет использовать библиотеку ABLAS (базовые алгоритмы линейной алгебры с поддержкой SSE2), если она установлена в системе.
AP_ASSERT
Этот символ включает проверку границ массива. Если он определен директивой define, то при каждом обращении к элементам динамического массива проверяется правильность переданного индекса. В случае ошибки генерируется исключение ap_error. Проверка границ массива делает программу более надежной, но замедляет работу.
NO_AP_ASSERT
Этот символ отключает проверку границ массива. Если он определен директивой define, то при обращении к элементу динамического массива выход индекса за границы массива не проверяется.
UNSAFE_MEM_COPY
Директива define, определяющая этот символ, отключена. Не включайте её. Библиотека не содержит никакой документации по поводу этого символа.
machineepsilon
Эта константа определяет точность машинных операций, т.е. минимальное число, такое, что 1+machineepsilon≠1 на данной разрядной сетке. Константа может быть взята "с запасом", т.е. реальная точность может быть ещё выше.
maxrealnumber
Эта константа определяет максимальное положительное вещественное число, представимое на данной машине. Константа может быть взята "с запасом", т.е. реальная граница может быть ещё выше.
minrealnumber
Эта константа определяет минимальное положительное вещественное число, представимое на данной машине. Константа может быть взята "с запасом", т.е. реальная граница может быть ещё ниже.
int sign(double x)
Возвращает:
+1, если X>0
-1, если X<0
0, если X=0
double randomreal()
Возвращает случайное вещественное число в полуинтервале [0,1).
int randominteger(int maxv)
Возвращает случайное целое число в полуинтервале [0, maxv).
double round(double x)
Округление к ближайшему целому. Если X находится точно посередине между двумя целыми, то результат функции зависит от реализации.
double trunc(double x)
Отбрасывание дробной части X.
trunc(1.3) = 1
trunc(-1.3)= -1
double pi()
Возвращает константу π
double sqr(double x)
Возвращает x2
double maxreal(double m1, double m2)
Возвращает максимум из двух вещественных чисел.
double minreal(double m1, double m2)
Возвращает минимум из двух вещественных чисел.
int maxint(int m1, int m2)
Возвращает максимум из двух целых чисел.
int minint(int m1, int m2)
Возвращает минимум из двух целых чисел.
Это класс исключения, которое выбрасывается при различных ошибках библиотеки AP, в частности - при неверном указании индекса массива, если включена проверка границ массива. Текущая версия класса не содержит никаких полей и не позволяет определить причину, по которой исключение было сгенерировано.
Здесь мы рассмотрим общие принципы работы с классами-массивами, после чего будут рассмотрены сами классы и их методы.
Классы, входящие в состав стандартной библиотеки, позволяют оперировать с матрицами и векторами (одномерными и двухмерными массивами) переменного размера, с переменной нумерацией элементов, т.е. нумерация может начинаться с любого числа, заканчиваться любым числом и динамически меняться. Так как классы массивов являются шаблонами, то массивы одной размерности обладают одинаковым набором функций-членов. А поскольку функции-члены массивов разных размерностей отличаются только количеством аргументов, то двумерные и одномерные массивы мало чем отличаются друг от друга.
Работа с массивом начинается с создания массива. Следует различать создание экземпляра класса-массива и выделение памяти под массив. При создании экземпляра класса может использоваться конструктор без параметров, создающий массив без элементов, а могут использоваться конструкторы копий и присваивания, копирующие один массив в другой. В случае создания массива конструктором по умолчанию он не содержит элементов и попытка обратиться к ним может привести к краху программы. Если при копировании массив-источник не имеет выделенной памяти под элементы, то массив-копия тоже не будет содержать элементов. Если массив-источник имеет выделенную под элементы память, то массив-копия выделяет тот же объем памяти и копирует в неё элементы. Т.е. при копировании получаются два полностью независимых массива с одинаковым содержимым.
После создания пустого массива следует выделить память под элементы при помощи метода
Для обращения к элементам массива используется перегруженный
integer_1d_array factarr(int n)
{
integer_1d_array result;
result.setbounds(1,n);
result(1) = 1;
for(int i=2; i<=n; i++)
result(i) = result(i-1)*i;
return result;
}
Это класс-шаблон динамического одномерного массива с переменными верхней и нижней границами. На основе этого класса получены следующие классы:
typedef template_1d_array<int> integer_1d_array; typedef template_1d_array<double> real_1d_array; typedef template_1d_array<bool> boolean_1d_array; typedef template_1d_array<complex> complex_1d_array;
template_1d_array()
Конструктор. Создание пустого массива.
~template_1d_array()
Деструктор. При вызове освобождается выделенная под массив память
template_1d_array(const template_1d_array &rhs)
Конструктор копий массива. При этом выделяется отдельная область памяти, в которую копируется содержимое массива-источника.
const template_1d_array& operator=(const template_1d_array &rhs)
Присваивание массива. При этом содержимое массива-приемника удаляется и освобождается выделенная под него память, затем заново выделяется отдельная область памяти, в которую копируется содержимое массива-источника.
T& operator()(int i)
Обращение к элементу массива с номером i
void setbounds(int iLow, int iHigh)
Выделение памяти под массив. При этом старое содержимое массива удаляется и освобождается выделенная под него память, затем заново выделяется отдельная область памяти размера iHigh-iLow+1 элементов.
Нумерация элементов в новом массива начинается с iLow и заканчивается iHigh. Содержимое нового массива не определено.
void setcontent(int iLow, int iHigh, const T *pContent)
Метод аналогичен методу setbounds() за тем исключением, что после выделения памяти в неё копируется содержимое массива pContent[].
T* getcontent()
Метод позволяет получить указатель на содержимое массива. Данные, на которые указывает возвращенный указатель, можно изменять, и при этом изменится содержимое массива.
int getlowbound()
int gethighbound()
Методы используются для получения информации о нижней и верхней границах массива.
raw_vector<T> getvector(int iStart, int iEnd)
Метод используется базовыми подпрограммами линейной алгебры для получения доступа к внутренней памяти массива. Метод возвращает объект, содержащий в себе указатель на часть вектора (начиная с элемента с индексом iStart и заканчивая индексом iEnd). Если iEnd<iStart, то считается, что задан пустой вектор.
const_raw_vector<T> getvector(int iStart, int iEnd) const
Метод используется базовыми подпрограммами линейной алгебры для получения доступа к внутренней памяти массива. Метод возвращает объект, содержащий в себе указатель на часть вектора (начиная с элемента с индексом iStart и заканчивая индексом iEnd). Если iEnd<iStart, то считается, что задан пустой вектор. Возвращенный объект позволяет получать доступ только для чтения.
Это класс-шаблон динамического двухмерного массива с переменными верхней и нижней границами. На основе этого класса получены следующие классы:
typedef template_2d_array<int> integer_2d_array; typedef template_2d_array<double> real_2d_array; typedef template_2d_array<bool> boolean_2d_array; typedef template_2d_array<complex> complex_2d_array;
template_2d_array()
Конструктор. Создание пустого массива.
~template_2d_array()
Деструктор. При вызове освобождается выделенная под массив память
template_2d_array(const template_2d_array &rhs)
Конструктор копий массива. При этом выделяется отдельная область памяти, в которую копируется содержимое массива-источника
const template_2d_array& operator=(const template_2d_array &rhs)
Присваивание массива. При этом содержимое массива-приемника удаляется и освобождается выделенная под него память, затем заново выделяется отдельная область памяти, в которую копируется содержимое источника.
T& operator()(int i1, int i2)
Обращение к элементу массива с индексом [i1,i2]
void setbounds(int iLow1, int iHigh1, int iLow2, int iHigh2)
Выделение памяти под массив. При этом старое содержимое массива удаляется и освобождается выделенная под него память, затем заново выделяется отдельная область памяти размером (iHigh1-iLow1+1)*(iHigh2-iLow2+1) элементов.
Нумерация элементов в новом массива по первой размерности начинается с iLow1 и заканчивается iHigh1, аналогично для второй размерности.
Содержимое нового массива не определено.
void setcontent(int iLow1, int iHigh1, int iLow2, int iHigh2, const T *pContent)
Метод аналогичен методу setbounds() за тем исключением, что после выделения памяти в неё копируется содержимое массива pContent[].
Массив pContent содержит двухмерный массив, записанный построчно, т.е. первым идет элемент [iLow1, iLow2], затем [iLow1, iLow2+1] и т.д.
int getlowbound(int iBoundNum)
int gethighbound(int iBoundNum)
Методы используются для получения информации о нижней и верхней границах массива по размерности с переданным номером.
raw_vector
const_raw_vector
Параметр iColumn должен быть допустимым номером столбца (т.е. находиться в пределах выделенной под массив памяти). Если iRowEnd<iRowStart, то считается, что задан пустой столбец.
raw_vector
const_raw_vector
Параметр iRow должен быть допустимым номером строки (т.е. находиться в пределах выделенной под массив памяти). Если iColumnEnd<iColumnStart, то считается, что задана пустая строка.
Базовые подпрограммы линейной алгебры библиотеки AP по своей функциональности близки к Level 1 BLAS, позволяя осуществлять простейшие операции с векторами, а также со строками и столбцами матриц.
Работа с подпрограммами осуществляется следующим образом. Сначала необходимо получить объект типа raw_vector или const_raw_vector, указывающий на обрабатываемую часть матрицы или массива при помощи методов getcolumn/getrow (для матрицы) или getvector (для массива). Объект содержит в себе указатель на начало строки (или столбца), число элементов в обрабатываемой строке и интервал между двумя соседними элементами. При использовании стандартной схемы хранения матриц в памяти (т.е. при хранении по строкам) интервал между элементами одной строки равен 1, а интервал между элементами одного столбца равен числу столбцов. Полученный объект передается в качестве аргумента в соответсвующую подпрограмму, которая осуществляет операции над частью матрицы, на которую указывает внутренний указатель объекта.
Ниже приведен список базовых подпрограмм линейной алгебры, доступных в составе библиотеки AP.
template<class T> T vdotproduct(const_raw_vector<T> v1, const_raw_vector<T> v2)
Подпрограмма вычисляет скалярное произведение переданных векторов.
template<class T> void vmove(raw_vector<T> vdst, const_raw_vector<T> vsrc)
template<class T> void vmoveneg(raw_vector<T> vdst, const_raw_vector<T> vsrc)
template<class T, class T2> void vmove(raw_vector<T> vdst, const_raw_vector<T> vsrc, T2 alpha)
Это семейство подпрограмм служит для различных видов копирования содержимого одного вектора на место другого вектора: простого копирования, копирования с умножением на -1, копирования с умножением на число.
template<class T> void vadd(raw_vector<T> vdst, const_raw_vector<T> vsrc)
template<class T, class T2> void vadd(raw_vector<T> vdst, const_raw_vector<T> vsrc, T2 alpha)
Это семейство подпрограмм служит для различных видов добавления одного вектора к другому: простого добавления или добавления с умножением на число.
template<class T> void vsub(raw_vector<T> vdst, const_raw_vector<T> vsrc)
template<class T, class T2> void vsub(raw_vector<T> vdst, const_raw_vector<T> vsrc, T2 alpha)
Это семейство подпрограмм служит для различных видов вычитания одного вектора из другого: простого вычитания или вычитания с умножением на число.
template<class T, class T2> void vmul(raw_vector<T> vdst, T2 alpha)
Эта подпрограмма служит для умножения вектора на число с сохранением результата в том же месте.
В случае если оба операнда являются векторами с интервалом между элементами, равным 1, и длиной N, можно использовать альтернативный синтаксис.
template<class T> T vdotproduct(const T *v1, const T *v2, int N)
template<class T> void vmove(T *vdst, const T *vsrc, int N)
template<class T> void vmoveneg(T *vdst, const T *vsrc, int N)
template<class T, class T2> void vmove(T *vdst, const T *vsrc, int N, T2 alpha)
template<class T> void vadd(T *vdst, const T *vsrc, int N)
template<class T, class T2> void vadd(T *vdst, const T *vsrc, int N, T2 alpha)
template<class T> void vsub(T *vdst, const T *vsrc, int N)
template<class T, class T2> void vsub(T *vdst, const T *vsrc, int N, T2 alpha)
template<class T, class T2> void vmul(T *vdst, int N, T2 alpha)
Библиотека AP содержит класс ap::complex, который позволяет осуществлять операции с комплексными числами. Доступ к действительной и мнимой частям комплексного числа осуществляется через открытые (public) поля x и y. Поддерживаются арифметические операции, как со встроенными типами данных, путем перегрузки операций сложения, вычитания, умножения и деления. Сложение, вычитание и умножение осуществляются обычным способом (т.е. по определению, которое можно найти в любом учебнике алгебры), операция деления осуществляется с использованием т.н. "безопасного" алгоритма, который никогда не приводит к переполнению при вычислении промежуточных результатов. Также библиотека включает в себя несколько функций, осуществляющих элементарные операции с комплексными числами.
const double abscomplex(const complex &z)
Функция возвращает модуль комплексного числа. Следует отметить, что вычисление модуля осуществляется с использованием т.н. "безопасного" алгоритма, который никогда не приводит к переполнению при вычислении промежуточных результатов.
const complex conj(const complex &z)
Функция возвращает комплексное число, сопряженное своему аргументу.
const complex csqr(const complex &z)
Функция возвращает квадрат аргумента.