Стандартна библиотека, част II

Standard Library

Някои често ползвани функции: memset(), memcpy(), strlen(), rand(), clock(), assert()

Автор: Александър Георгиев

В предходната тема за стандартната библиотека на C++ разгледахме нейното подразделение STL. Сега ще по-говорим за някои полезни функции, които са наследени още от C, но въпреки това често биват ползвани на състезания.

memset()

#include

memset(void
*
 mem,
 unsigned
 char
 value,
 int
 count)

?	В истинската сигнатура на функцията `value` всъщност е `int`, но се интерпретира като `unsigned char`. Това е така и в редица други C библиотеки, които ще разгледаме (особено тези в ). Не ме питайте защо. Понякога ще даваме "грешни" сигнатури на функциите с цел малко по-голяма яснота.

Какво прави тази функция? Пълни първите count байта от паметта, сочена от указателя mem със стойност value. Обикновено се ползва ако имате някакъв масив (от какъвто и да е тип) array: memset(array, some_value, sizeof(array)).

Тази функция бива бъркана много често от хора, които нямат опит с нея. Най-важното нещо, което трябва да забележите, е, че стойността, с която пълним масива, се интерпретира като char. Това е само един байт!. Следователно ако сложите голяма стойност (примерно 1337), то ще се получи overflow. Но това е направено, защото функцията инициализира паметта байт по байт! Тоест дори да сложите стойност, която се побира в unsigned char, като например 42, то пак няма да работи за, да кажем, int масив.

Да видим какво точно се случва при ползването й:

#include <cstdio>
#include <cstring>

int
 main(void) {
    int
 array[2
] =
 {0
,
 0
};
    /*
      Масивът първоначално е инициализран с нули. Тоест двойката 4-байтови числа
      върху които се простира той, изглеждат по следния начин:
      [00000000000000000000000000000000][00000000000000000000000000000000]
      или, разделяйки го на байтове:
      [00000000|00000000|00000000|00000000][00000000|00000000|00000000|00000000]
    */
    memset(array,
 42
,
 sizeof
(array));
    /*
      Всеки от *байтовете* на масива бива инициализиран с числото 42.
      42, представено в един байт, е 00101010. Така паметта на масива става:
      [00101010|00101010|00101010|00101010][00101010|00101010|00101010|00101010]
      или, разглеждайки го обратно като int-ове:
      [00101010001010100010101000101010][00101010001010100010101000101010]
      Тоест всеки от елементите е със стойност 00101010001010100010101000101010
      което е 707,406,378 в десетична бройна система.
    */
    fprintf(stdout
,
 "%d\n"
,
 array[0
]);
 // Печата "707406378"
    return
 0
;
}

Все пак, тази функция е доста полезна, тъй като работи забележимо по-бързо от цикъл, който инициализира масива. Освен това можете да инициализирате N-мерен масив с един единствен ред, без да се притеснявате за размерностите му - sizeof(array) все още връща правилния размер дори при двумерни и многомерни масиви.

Как, тогава да я ползваме? Няколко полезни стойности, които работят са:

0, тъй като тя се представя само с нули в двоичен запис и съответно няма значение дали инициализирате char, int и дори double масив - всички ще се инициализират правилно с нула.
-1, тъй като се представя като само единици в двоичен запис и съответно няма значение дали инициализирате char, int или какъвто и да е друг целочислен тип.
Принципно може да ползвате някаква голяма стойност (да кажем 127) за да инициализирате с почти INT_MAX някакъв int масив. Бих ви препоръчал, обаче, да ползвате 63, тъй като стойността е достатъчно малка да не овърфлоува при събиране с друго такова число и все пак достатъчно голяма за infinity в повечето задачи.
Просто като съвет, ако решите да инициализирате с memset() масив със стойност различна от 0 или -1, изпечатайте произволен елемент от масива (примерно [0][0]...[0]) и вижте каква е стойността му. Ако е окей - оставете го така. Ако не, пробвайте други стойности в мемсет-а, докато получите такава, каквато ви върши работа.

memcpy()

#include

memcpy(void
*
 dest,
 void
*
 source,
 unsigned
 numBytes)

Копира numBytes байта памет от паметта, сочена от source в паметта, сочена от dest.. Най-често се ползва ако искате да копирате стойностите на масив в друг със същия тип и размери. Обикновено ще копирате целите масиви, като в този случай за последен аргумент можете да ползвате sizeof() някой от масивите.

#include <cstring>

const
 int
 MAX_N =
 42
;
const
 int
 MAX_M =
 666
;
const
 int
 MAX_K =
 128
;

int
 main(void) {
    static
 int
 array[MAX_N][MAX_M][MAX_K];
    // Четем входа в array
    // ...

    static
 int
 copyOfArray[MAX_N][MAX_M][MAX_K];
    memcpy(copyOfArray,
 array,
 sizeof
(array));
    // copyOfArray[][][] съдържа точно копие на array[][][]
    //...
    return
 0
;
}

Забележете, че успяваме да копираме целия тримерен масив на един единствен ред. Така спестяваме известно количество код и възможността за грешки - дори ако след време променим размерите на масивите! Като допълнителен бонус, тази функция използва low-level копиране, което е значително по-бързо, отколкото би бил кодът ни ако правихме три вложени цикъла.

strlen()

#include

unsigned
 int
 strlen(const
 char
*
 str)

Повечето от вас сигурно вече са чували за тази функция - тя връща дължината на даден C-style стринг (тоест char array). Което може би не знаете е как е имплементирана тя. Тъй като стринговете в C се терминират с 0 (за което си има специален символ '\0'), то тази функция не представлява нищо друго от цикъл, който търси тази нула и казва колко позиции е минал преди да я намери. Като цяло нищо сложно, но има два проблема. Първо, ако стрингът ви не е терминиран с нула, функцията може да се счупи много брутално. Второ, каква е сложността на следния код, който изтрива първата буква на стринга str?

void
 eraseFirstChar(char
* str) {
    for
 (int
 i =
 0
;
 i <
 (int
)strlen(str);
 i+
+)
        str[i] =
 str[i +
 1
];
}

Мислите си, че е O(N) (ако стрингът е с дължина N)? Неее! Тъй като викате strlen() при всяка итерация на цикъла, реално го обхождате отново и отново и отново за да намерите тази знаменита терминираща нула. Тоест кодът ви реално е със сложност O(N²).

rand()

#include
Една от много полезните функции, когато създавате тестове (независимо дали да тествате ваше или чуждо решение). Връща произволно цяло число в някакъв интервал.

RAND_MAX

Константата RAND_MAX указва горната граница на числото, което бива връщано. На различни компилатори и операционни системи тази константа може да е различна! Например под Windows тя стандартно е 32,767, докато под Linux обикновено е 2,147,483,647.

rand()

Връща произволно цяло число в интервала [0, RAND_MAX]. Върнатите числа не са абсолютно случайни, но вършат задоволителна работа за повечето реални приложения (и особено за тестове на задачи).

srand()

Върнатите числа от rand() са едни и същи всеки път, когато пускате програмата си. Например за компилатора MinGW първите пет са винаги (в този ред): 41, 18467, 6334, 26500, 19169. За щастие е предвидена функция, чрез която да променяме получаващата се случайна редица! Това е функцията srand(unsigned seed). В зависимост от нейния аргумент seed, получената редица се "разбърква" по някакъв начин. Така, ако в началото на генератора на тестове извикате srand(13) и генерирате някакъв тест, след това направите srand(42) и генерирате друг тест, то те ще са с голяма вероятност различни.

clock()

#include
Връща изминалото време от стартирането на програмата. Забележете, че върнатата стойност не е секунди, стотни или каквато и да е стандартна времева единица! Тя представлява "кликания на системния часовник", което би трябвало нищо да не ви говори. Затова има предоставена константа CLOCKS_PER_SEC, която задава колко такива кликания изминават в една секунда. Така, за да измерим времето, за кеото върви дадена функция, можем да направим:

#include <cstdio> // fprintf()
#include <cstdlib> // rand()
#include <ctime> // clock()
#include <algorithm> // swap()

int
 main(void) {
    const
 int
 MAX =
 32768
;
    // Генерираме масив с MAX на брой числа
    static
 int
 a[MAX];
    for
 (int
 i =
 0
;
 i <
 MAX;
 i+
+)
        a[i] =
 rand();

    // Ще сортираме числата с BubbleSort,
    // като ще измерим колко време ще отнеме това
    unsigned
 sTime =
 clock();
    for
 (int
 i =
 0
;
 i <
 MAX;
 i+
+)
        for
 (int
 c =
 i;
 c +
 1
 <
 MAX;
 c+
+)
            if
 (a[c +
 1
] <
 a[c]) std:
:
swap(a[c +
 1
],
 a[c]);
    unsigned
 eTime =
 clock();

    fprintf(stdout
,
 "BubbleSort sorted %d numbers in %.3lf seconds.\n"
,
            MAX,
 (double
)(eTime -
 sTime) /
 CLOCKS_PER_SEC);
    return
 0
;
}

Ако помните, същото това нещо ползвахме за да измерим колко бързо вървят трите алгоритъма, които сравнявахме, в статията за сложност на алгоритми.

assert()

#include

assert(int
 condition)

Проверява дали някакво условие е изпълнено и прекъсва програмата, ако не е. Преди напускане на програмата изписва информативно съобщение на стандартния изход за грешка (stderr). Съобщението съдържа реда, на който се намира assert()-а, както и какво е било условието.

Функцията е много полезна, когато искаме да гарантираме, че променливите в определени точки от програмата са смислени. Например можем да проверяваме дали сме прочели правилно входа, като сравняваме прочетените стойности с ограниченията на задачата. Също така тя помага значително и за дебъгване, тъй като изписва точния ред, на който е грешният assert.

С друг хубав пример, където е удачно да ползваме assert(), вече се сблъскахме по-рано. Помните ли, че когато писахме структурите данни сет, стек, опашка и т.н., изпечатвахме съобщение за грешка ако потребителят поиска елемент, който не съществува. Но все пак връщахме някакъв резултат и програмата продължаваше. Тук е по-удачно да проверим с assert() дали индексът е валиден и да прекъснем програмата, ако това не е така.

Например функцията getKth() в set-а, който написахме, би изглеждала по следния начин, с ползване на assert():

int
 getKth(int k) {
    assert(k >
=
 0
 &
&
 k <
 setSize);
    return
 setValues[k];
}

isdigit()

#include

? Внимавайте с върнатата стойност! Веднъж ми се наложи да дебъгвам близо час if (isdigit(someChar) == 1). Тъй като върнатата стойност е int и я сравнявам с int, то никое от двете не се convert-ва към bool. Съответно ако върнатата стойност не е 0, но не е и 1 (някое друго non-zero value) аз ще счета, че не е цифра, макар и всъщност да е.

int
 isdigit(char
 ch)

Проверява дали символът ch е цифра. Връща 0 ако не е, и различно от 0 число, ако е. Почти еквивалентно е на (ch >= '0' && ch <= '9')).

isalnum()

#include

int
 isalnum(char
 ch)

Проверява дали аргументът ch е латинска буква (независимо дали малка или голяма) или цифра. Връща 0 ако не е, и различно от 0 число, ако е. Замества ((ch >= 'A' && ch <= 'Z') || (ch >= 'a' && ch <= 'z') || (ch >= '0' && ch <= '9')).

isalpha()

#include

int
 isalpha(char
 ch)

Проверява дали аргументът ch е латинска буква (независимо дали малка или голяма). Еквивалентно е на ((ch >= 'A' && ch <= 'Z') || (ch >= 'a' && ch <= 'z')). Връща 0 ако не е, и различно от 0 число, ако е.

islower()

#include

int
 islower(char
 ch)

Проверява дали аргументът ch е малка латинска буква. Връща 0 ако не е, и различно от 0 число, ако е. Почти еквивалентно е на (ch >= 'a' && ch <= 'z').

isupper()

#include

int
 isupper(char
 ch)

Проверява дали аргументът ch е главна латинска буква. Връща 0 ако не е, и различно от 0 число, ако е. Почти еквивалентно е на (ch >= 'A' && ch <= 'Z').

isspace()

#include

int
 isspace(char
 ch)

Проверява дали аргументът ch е някакъв вид празно пространство - шпация (' '), табулация ('\t'), нов ред ('\r' или '\n'), или някой от по-рядко ползваните '\f' или '\v'. Връща 0 ако не е, и различно от 0 число, ако е.

abs()

#include
Връща абсолютната стойност на аргумента. Понякога не работи с long long (зависи от компилатора), но на по-новите GCC-та е окей.

__builtin_popcount()

__builtin_popcount(unsigned
 n)

Функцията не е стандартна! Поддържа се от някои GCC компилатори и можете да я ползвате в TopCoder. Връща броя единицици в двоичния запис (Хеминговото тегло) на аргументa.

__gcd()

#include

__gcd(int
 a,
 int
 b)

Функцията не е стандартна! Поддържа се от някои GCC компилатори и може да я ползвате в TopCoder. Връща най-големия общ делител на числата a и b.

Допълнителни материали

За да предложите корекция, селектирайте думата или текста, който искате да бъде променен,
натиснете Enter и изпратете Вашето предложение.

Страницата е посетена 9718 пъти.

Стандартна библиотека, част II

Standard Library

memset()

memcpy()

strlen()

rand()

RAND_MAX

rand()

srand()

clock()

assert()

isdigit()

isalnum()

isalpha()

islower()

isupper()

isspace()

abs()

__builtin_popcount()

__gcd()

Допълнителни материали

Предложете корекция