К оглавлению

Полезные функции на C++

С.И.Хашин


vUtil.h - заголовочный файл
vUtil.cpp - реализация.

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

ОГЛАВЛЕНИЕ


ldouble, i64, u64, BYTE

//typedef long double ldouble;
typedef double ldouble;
Visual C++ игнорирует тип long double. Однако стоит сохранить возможность работать с 10-байтовыми числам (long double), пусть и с другими компиляторами. Для этого вместо double будем использовать ldouble. Под Visual C++ это просто double, под другими компиляторами это может быть long double.

Кроме того, для краткости вводятся 8-ми байтовые числа i64, u64 и BYTE.

Вывод сообщений об ошибках

void   vError(const char *format, ...);     // show error function
Вывод указанного сообщения и завершение работы. Аргументы функции те же самые, что и у функции printf, например:
vError("res=%llu\n", tm);

или:

matr a;
char *fname = "lena.bmp";
int code;
if(code=a.loadBMP(fname)) vError("File %s not open, error code=%d", fname, code);

В консольных программах это функция просто выводит сообщения на экран (printf), в оконных приложениях её придется заменить на другую.

Функция вывода сообщения на экран:

void   vShow (const char *format, ...);     // show function

– то же самое, но без завершения работы.
В консольных программах это функция просто выводит сообщения на экран (printf), в оконных приложениях её придется заменить на другую.
void   hWrite(const char *fname, const char *format, ... ); 
// Открыть файл fname, записать в него строку msg и закрыть его

Пример работы:

    hWrite("res.txt", "f(%8.4f)=%10.5f\n", x, f(x));

Символы и строки

char *  toString( const char* format, ... );
char *  toString2(const char* format, ... );

toString(…) – возвращает строку с заданным значением, аргументы функции те же самые, что и у функции printf, например:

 toString(“%s\\file_%04d.jpg”, path, k);

На самом деле функция всегда возвращает указатель на одну и ту же область памяти, в которой при вызове строится (с помощью sprintf) требуемая строка. Следовательно, функция не выделяет новую память и её не требуется освобождать.

С другой стороны, в результате этого функцию toString нельзя использовать дважды одновремено, например вызов

   printf("%s_%s", toString(x), toString(y) )

неверен, так как оба раза функция возвратит один и тот же указатель.

Такая проблема нечасто, но появляется. Здесь можно предложить два выхода:

  1. Заставить функцию возвращать каждый раз новый буфер, выделенный через оператор new. Но тогда в приведенном выше примере эту память никто не освободит.
  2. Сделать еще одну функцию, которая возвращает другой (второй) буфер. При этом, правда, останется проблем с тройными вызовами,
        printf("%s_%s_%s", toString(x), toString2(y), toString2(z) )
    
    но они требуются так редко, что о них не стоит заботиться.
Следующие функции достаточно очевидны.
char *  copyString( const char *s );        // копия строки в куче
char *  nextToken( char *s );               // разбивка строки по символам табуляции

В строке s находит перый символ табуляции и заменяет его на '\0'. Возвращает указатель на символ, следующий за вставленным '\0'. Если табуляция не найдена, ничего не делаем и возвращаем NULL.

const char *FirstWord(const char *src, const char *brk,  char *dst);
        // dst:=1-е слово, ограниченное символами из brk, возвращает указатель на 
        // первый символ после слова

inline bool isRus ( char ch);   // ? Русская буква
inline bool isLat  (char ch);   // ? Латинская буква
inline bool isDig  (char ch);   // ? Цифра
inline bool isLRus (char ch);   // ? Большая русская буква
inline bool islRus (char ch);   // ? маленькая русская буква
inline bool isBlank(char ch)'); // ? ' ', '\t', '\n', '\r'
inline bool isPnt  (char ch);   // ? '.!?'

#define chrKind_REST        1
#define chrKind_DIGIT       2
#define chrKind_RUS         3
#define chrKind_LAT         4
#define chrKind_PNT         5
int  chrKind(char ch);  // тип символа

bool isOnlylRus( char *s);      // в строке только малые русские буквы?

Конвертация символов и строк

Конвертация символов:

unsigned char  char_866_1251 (unsigned char ch);    // dos    -> win
unsigned char  char_Koi8_1251(unsigned char ch);    // koi8-r -> win
unsigned char  char_utf8_1251(unsigned char *&s);   // uft8   -> win, 
    очередной символ строки, s0 переустанавливается на следующий символ

Конвертация строк производится "на месте":

unsigned char* cnv1251_866(unsigned char *s);       // win    -> dos  (in place)
unsigned char* cnv866_1251(unsigned  char *s);      // dos    -> win  (in place)
unsigned char* cnvKoi8_1251(unsigned char *s);      // koi8-r -> win  (in place)

Обратите внимание, что в тексте этой функции задана длинная строка из 257 символов. Её ни в коем случае нельзя изменять, ни один пробел не должен пропасть!

unsigned char* cnv_utf8_1251(unsigned char *s);     // uft8   -> win  (in place)

В этой функции все символы, которые нельзя закодировать в кодовой странице cp-1251 будут заменены на пробелы.
Строка может стать короче!

Определение кодировки русского текста

#define rCP_unknown     0
#define rCP_1251        1
#define rCP_866         2
#define rCP_koi8r       3
#define rCP_utf8        4

int    rCodePage(unsigned char *s);
inline int rCodePage(char *s);

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

Внимание! Результат не абсолютный, а лишь "вероятный"!

Удаление лишнего

void ltrim(char *s);            // удалить начальные пробелы из строки
void rtrim(char *s);            // удалить конечные пробелы из строки
void trim (char *s);            // удалить начальные и конечные пробелы из строки

char* toLatLow(char *txt);      // Большие латинские сделать маленькими
char* toRusLow(char *txt);      // Оставить в строке только малые русские буквы и пробелы

В этой функции все знаки, кроме русских букв заменяются на пробелы.

char* toRusLowP(char *txt);     // Оставить в строке только малые русские буквы, точки и пробелы

В этой функции все знаки, кроме русских букв и точки заменяются на пробелы.

char* txtPress(char *txt);      // trim + сжатие пробелов и точек в один

Например, после выполнения вот такого кода

    char s[] = "char* toRusLow(char *txt);      // Оставить в строке только малые русские буквы и пробелы\n\
        Продолжение    строки. end\t.\n";
    char *s1 = toRusLow(s);
    s1 = txtPress(s1);

в s1 оказывается строка:

"оставить в строке только малые русские буквы и пробелы продолжение строки"

В последней функции из строки удаляются начальные и конечные пробелы, несколько пробелов подряд заменяются на один пробел.

Функции для работы с целыми числами

Полезнейшие константы:

const   int million = 1000000;
const   int billion = 1000000000;
int  iDivide( int a, int b );       // round(a/b)
int  mod    ( int a, int b );       // math: a mod b
int  iround ( int x, int k );       // округлить целое до кратного k
int  iSquare( int x );              // возведение в квадрат
BYTE clip256( int x );              // меньшие 0 заменяем на 0, большие 255 на 255.
int  ilog2  ( unsigned x );         // максимальная степень 2, <= x, ilog2(0)=ilog2(1)=0, ilog2(2)=ilog2(3)=1, ...
void swapInt( int &a, int &b);      // перестановка чисел
u64  binomial( int n, int k );      // n!/(k!*(n-k)!, binomial(3,2)=3

Будьте внимательны!
binomial(62,31) = 465 428 353 255 261 088 (correct)
binomial(63,31) = 148 894 686 314 746 622 (wrong, correct value 916 312 070 471 295 267 too large!)

bool odd(int x);                    // нечетное?

Отображаем целые числа в натуральные и обратно:
0, 1, 2, ... -> 0, 2, 4, ...,
-1,-2, ... -> 1, 3, ....

int  toNatural(int x);      // map signed x to positive integer   
int  fromNatural(int x);    // remap positive x to signed integer
// max/min
int     imax2( int a, int b );
int     imax3(int a, int b, int c);
int     imax4(int a, int b, int c, int d);
int     imin2( int a, int b );
int     imin3( int a, int b, int c );
int     imin4(int a, int b, int c, int d);
    
int  imax(int N, int *a, int &k);   // максимум в массиве a[0..N-1], k - его индекс в массиве
int  imin(int N, int *a, int &k);   // минимум  в массиве a[0..N-1], k - его индекс в массиве

void corrMinMax(int x, int &min, int &max); // коррекция минимума и максимума

void iShiftR(int N, int *a);        // циклический сдвиг вправо: a[0]->a[1]->...->a[N-1]->a[0]
void iShiftL(int N, int *a);        // циклический сдвиг влево : a[0]<-a[1]<-...<-a[N-1]<-a[0]

int  byteAdd(int a, int b);         // побайтовое сложение целых чисел
int  quantil ( int k, unsigned *hist, int p ); // в гистограмме hist размера k найти квантиль p
int  quantilr( int k, unsigned *hist, int p ); // в гистограмме hist размера k найти правый квантиль p

Поясним две последние функции. Допустим, дан массив h[10] целых чисел:
  h[10] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
При вызове функции
    quantil(10, h, 9);
в массиве неотрицательных чисел hist[0..9] будем искать наименьшее s такое, что сумма первых s чисел ≥ p. Если же сумма всех чисел оказалась меньше p, то возвращаем -1. В данном случае
  h[0] + h[1] + h[2]        =  1+2+3   = 6 < 9, 
Сумма первых трех чисел меньше 9.
  h[0] + h[1] + h[2] + h[3] = 1+2+3+4 = 10 ≥ 9, 

Сумма первых четырех чисел ≥ 9. Таким образом, функция вернет результат 4.

Аналогичным образом, при вызове функции

    quantilr(10, h, 19);
получаем:
  h[9]       =  10    < 19, 
Последнее число меньше 19.
  h[9] + h[8] = 10+9 = 19 ≥ 19, 

Сумма последних двух чисел ≥ 19. Таким образом, функция вернет результат 2.

Функции для работы с действительными числами

#define dPi    3.14159265358979324
#define TwoPi  6.28318530717958648
#define macheps (2.2e-16)                   // машинная точность double
#define dbl_MAX (9e+307)                    // 2*dbl_MAX = #inf
#define round(x) ((int)floor((x)+0.5 ))     // округлить до целого

В прежних версиях С++ не было функции lround(). Что бы не путаться с версиями, ввёл функцию (макрос) round().

ldouble dSquare(ldouble x);                 // возвести аргумент в квадрат
ldouble noise2psnr( ldouble x );            // 20*log10(255/x)
ldouble psnr2dfd  ( ldouble x );            // 255/exp(0.1151*x)
void    swapDbl( ldouble &a, ldouble &b);
ldouble angle( ldouble x,   ldouble y);      // угол (0..2Pi) вектора (x,y) с осью X.
ldouble hypot2( ldouble x1, ldouble x2            );// sqrt(x1*x1+x2*x2);
ldouble hypot3( ldouble x1, ldouble x2, ldouble x3);// sqrt(x1*x1+x2*x2+x3*x3);
// max/min
ldouble  dmax2( ldouble a, ldouble b );
ldouble  dmax3(ldouble a, ldouble b, ldouble c);
ldouble  dmax4(ldouble a, ldouble b, ldouble c, ldouble d);
ldouble  dmin2( ldouble a, ldouble b );
ldouble  dmin3( ldouble a, ldouble b, ldouble c );
ldouble  dmin4(ldouble a, ldouble b, ldouble c, ldouble d);

Следующая функция сортирует три числа по возрастанию:

void    dblSort3( ldouble &a, ldouble &b, ldouble &c); // make: a <= b <= c
bool    isMultiple(ldouble a, ldouble b, ldouble eps);  // a - кратно b с точностью до eps

Работа с векторами из действительных чисел

// vectors of ldouble
void    vdbl_set  (int N, ldouble *a, ldouble  k);          // a[i] = k
void    vdbl_add  (int N, ldouble *a, ldouble *b);          // A += B
void    vdbl_cop  (int N, ldouble *a, ldouble *b);          // A := B
void    vdbl_mul  (int N, ldouble *a, ldouble  k);          // A *= k
void    vdbl_div  (int N, ldouble *a, ldouble  k);          // A /= k
void    vdbl_addmul(int N,ldouble *a, ldouble *b,ldouble k);// A += k*B
ldouble vdbl_len2 (int N, ldouble *a);                      // |A|^2
ldouble vdbl_len  (int N, ldouble *a);                      // |A|
void    vdbl_norm (int N, ldouble *a);                      // |A| := 1
ldouble vdbl_dist2(int N, ldouble *a, ldouble *b);          // |A-B|^2
ldouble vdbl_dist (int N, ldouble *a, ldouble *b);          // |A-B|
ldouble vdbl_sprod(int N, ldouble *a, ldouble *b);          // scalar product(A,B)
ldouble vdbl_max  (int N, ldouble *a, int  &ind);           // maximal value and its index
ldouble vdbl_min  (int N, ldouble *a, int  &ind);           // minimal value and its index

Непрерывные (цепные) дроби. Для данного x находим его наилучшее рациональное приближение со знаменателем <= maxQ

// Continued fraction
ldouble chainFract(ldouble x, i64 &p, i64 &q, i64 maxQ); // optimal rat.approx p/q of x, q<=maxQ, return tolerance

Функции для работы с текстовыми файлами

bool    fileExist( const char *fileName );  // существует ли указанный файл
void    fileClear( const char *fileName );  // опустошить файл
int     fileSize ( const char *fileName );  // размер файла
const char*fileExt(const char *fileName );  // расширение   
void    chExt(char *fileName, const char *ext);// изменить расширение файла на ext
int     NLines(const char *fileName);       // количество строк в текстовом файле
int     NLines1(const char *fileName);      // количество непустых строк в текстовом файле

Для открытия существующего файла на "добавление", обычно пишут так:

    FILE *f = fopen("ttt.txt", "a");

Но если файла с таким именем не существует, возникает ошибка.
Если вам надо открыть текстовый файл на добавление, если он существует, а в противном случае создать новый, это можно сделать одним оператором:

FILE   *aopen(const char *fname);   // открыть (или создать) текстовый файл для добавления

Далее,

bool    writeFile(char *fname, const BYTE *buf, unsigned bsize);
        // сохранить буфер в файл
BYTE   *fileRead(const char *fname, unsigned &fsize);
        // Прочитать файл в двоичный буфер (в конце добавлен ещё один нулевой байт). 

int     iCadr( char *s );           // извлечь номер кадра из имени файла
void    nextFname(char *s);         // следующее имя файла

Функция iCadr. После вызова

char fname[64] = "c:\\a\\frame\f_0234.bmp";
int k = iCadr(fname);
переменная k будет равна 234.

После вызова

next(fname);
строка fname окажется равна
 "c:\\a\\frame\f_0235.bmp";
Отметим, что если написать
char *fname = "c:\\a\\frame\f_0234.bmp";
то строка fname будет лежать в статической памяти, которую запрещено изменять во время выполнения и функция nextFrame даст ошибку.

Время

long long getMillisec();            // время в миллисекундах
ldouble getSec();                   // время в секундах

Точное время в тактах таймера (только под Windows)
Отметим, что измеряются не такты процессора, а такты некоторого высокоточного таймера, получается примерно 3.5 миллиона тактов в секунду.

i64 TimerCounter();                 // счётчик циклов
i64 TimerFrequency();               // тактовая частота таймера

Рассмотрим пример.

    double dtm = -getSec();         // секунды
    u64 ms = -getMillisec();        // миллисекунды
    i64 tm = -TimerCounter();       // начальное время со знаком минус

    unsigned sum = 0;
    for (unsigned i = MAX32; i>0; i--) // это цикл - просто задержка вычислений
        sum += i;

    tm  += TimerCounter();          // прибавили текущее время, получили разность в тактах таймера
    ms += getMillisec();
    dtm += getSec();

    double tm2=(double)tm;
    tm2 /= TimerFrequency();        // теперь dtm - время выполнения блока в секундах
    printf("sec = %10.5f, ms = %10llu\n", dtm, ms);
    printf("tm=%11llu tacts (%10.6f sec)\n", tm, tm2);

Получим результат:

    sec = 0.83200, ms = 832
    tm = 2847755 tacts (0.832221 sec)

Cлучайные числа

Число p = 264 - 59 является простым, причем 2 будет первообразным корнем по модулю p. Поэтому последовательность {1,2,4,8, ...} mod p будет иметь период p-1.

Если мы будет вызывать наш датчик по 1 млрд. раз в секунду, то для обхода всего цикла потребуется около 500 лет. Таким образом, с практической точки зрения эта последовательность никогда не будет повторяться.

Алгоритм умножения на 2 по модулю p = 264 - 59 можно предложить следующий:

Пусть x — 8-байтовое число без знака (unsigned long long).

Если x ≤ 263-30 то для вычисления 2x переменную x надо просто умножить на 2.

Если x > 263-30 то для вычисления 2x надо взять 2*x+59.

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

(hRandom_value + 0x12345678abcdefL) ^ 0x4937837937219836L;
void     hRandomize(unsigned init=0);// it init=0 then initialization by time
u64      hRandom_next();             // очередное случайное число
int      hRandom(unsigned k);        // int random 0..k-1
ldouble  hRand();                    // random 0..1

ldouble  hRand_Std();
         // нормальная случайная величина с мат.ожиданием 0 и дисперсией 1

ldouble  hRand_Normal(ldouble m, ldouble s);
         // нормальная случайная величина с мат.ожиданием m и дисперсией s^2
Нормальная случайная величина hRand_Std() получается у нас как сумма 12 величин равномерно распределённых на отрезке [-0.5…0.5]. Этого достаточно для практических приложений. Если вам нужна большая точноcть, придётся реализовывать более сложные алгоритмы.

Для того, чтобы обойти все точки из множества [0,1,...,N-1] в некотором псевдослучайном порядке поступим следующим образом. Выберем простое число p, больше или равное N и первообразный корень a по модулю N. Тогда в последовательности

    [1, a, a2 mod p,..., ap-2 mod p] 
все числа от 1 до p-1 встречаются ровно по одному разу. Если из них оставить только числа ≤ N получим все числа от 1 до N ровно по одному разу. А если из них вычесть единицу, то получим решение исходной задачи.

Для эффектиной работы требуется для данного N найти простое p, которое не слишком превосходит N и соответствующие первообразные корни. Они были выбраны следующие:

   p (prime)    a mod p   
          0,          0, //   0
          3,          1, //   1
          5,          2, //   2
         11,          6, //   3
         17,          5, //   4
         37,         13, //   5
         67,         18, //   6
        131,         37, //   7
        257,         65, //   8
        521,        134, //   9
       1031,        257, //  10
       2053,        516, //  11
       4099,       1032, //  12
       8209,       2049, //  13
      16411,       4098, //  14
      32771,       8196, //  15
      65537,      16385, //  16
     131101,      32777, //  17
     262147,      65538, //  18
     524309,     131073, //  19
    1048583,     262145, //  20
    2097169,     524304, //  21
    4194319,    1048577, //  22
    8388617,    2097153, //  23
   16777259,    4194308, //  24
   33554467,    8388611, //  25
   67108879,   16777217, //  26
  134217757,   33554435, //  27
  268435459,   67108870, //  28
  536870923,  134217732, //  29
 1073741827,  268435458, //  30
 2147483659,  536870920, //  31

Здесь выбрано, что p[k] - это первое простое число, большее 2k, a[k] - первый первообразный корень, больший p/4.

Для данного N находим первое простое число из этого списка, превосходящее N.

Начинать обход можно с любой точки, но последовательность точек будет всегда одна и та же. Для получения другой последовательности можно взять натуральное b взаимно простое с N и некоторое целое d. Тогда последовательность b*x[i]+d, где x[i] - последовательность, описанная выше, опять будет обходить все точки от 0 до N-1 по одному разу.

Прочее

Копирование массива целых чисел, расположенных с некоторым шагом в другой массив, также расположенный в памяти с некоторым шагом.
void    copyBuf( int *dst, int stepDst, int *src, int stepSrc, int size );

Следующая фукнция предназначена для обхода целочисленные точки плоскости по спирали

void    nextPoint( int &x, int &y );

         |               |
         |              182
    -----+----> x   ----705---> x
         |              463
         | y             | y
         v               v

   0)  0  0
   1)  1 -1
   2)  1  1
   3) -1  1
   4) -1 -1
   5)  1  0
   6)  0  1
   7) -1  0
   8)  0 -1
   9)  2 -2
  10)  2  2

В компьютерной графике иногда требуется для произвольного вектора (x,y) найти среди восьми векторов

    (-1,-1) ( 0,-1) ( 1,-1) 
    (-1, 0)         ( 1, 0) 
    (-1, 1) ( 0, 1) ( 1, 1) 
наиболее близкий к (x,y) по направлению. Это выполняет функция
void    length1( int &x, int &y);       // довести вектор (x,y) до координат [-1,0,1]
Если исходный вектор равен 0, то он и остается нулевым.

Для преобразования между форматами представления цвета RGB ↔YUV используются следующие функции:

void    rgb_yuv( int  r, int  g, int  b, int &y, int &u, int &v );
void    yuv_rgb( int &r, int &g, int &b, int  y, int  u, int  v );
int     rgb_int( int r, int g, int b );                 // (r,g,b) -> x
void    int_rgb( int x, int &r, int &g, int &b);        // x -> (r,g,b)
Прямоугольник на плоскости задается четырьмя числами: верхним левым углом и его размерами:
    int x0, y0, dx, dy;   
Для работы с точками на границе прямоугольника предназначены следующие три функции:
bool boxBord(int x0, int y0, int dx, int dy, int x1, int y1);   
        // лежит ли точка (x1,y1) на границе прямоугольника

void boxNext(int x0, int y0, int dx, int dy, int &x1, int &y1); 
        // (x1,y1) - следующая на границе по часовой стрелке

void boxPrev(int x0, int y0, int dx, int dy, int &x1, int &y1); 
        // (x1,y1) - следующая на границе против часовой стрелки

К оглавлению


free counters