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

Standard Library

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

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

memset()

#include <cstring>
memset(
void
*
mem
,
unsigned
char
value
,
int
count)
?В истинската сигнатура на функцията value всъщност е int, но се интерпретира като unsigned char. Това е така и в редица други C библиотеки, които ще разгледаме (особено тези в <cctype>). Не ме питайте защо. Понякога ще даваме "грешни" сигнатури на функциите с цел малко по-голяма яснота.
Какво прави тази функция? Пълни първите 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) все още връща правилния размер дори при двумерни и многомерни масиви.

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

memcpy()

#include <cstring>
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 <cstring>
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(N2).

rand()

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

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 <ctime>
Връща изминалото време от стартирането на програмата. Забележете, че върнатата стойност не е секунди, стотни или каквато и да е стандартна времева единица! Тя представлява "кликания на системния часовник", което би трябвало нищо да не ви говори. Затова има предоставена константа 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 <cassert>
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 <cctype>
?Внимавайте с върнатата стойност! Веднъж ми се наложи да дебъгвам близо час 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 <cctype>
int
isalnum(
char
ch)
Проверява дали аргументът ch е латинска буква (независимо дали малка или голяма) или цифра. Връща 0 ако не е, и различно от 0 число, ако е. Замества ((ch >= 'A' && ch <= 'Z') || (ch >= 'a' && ch <= 'z') || (ch >= '0' && ch <= '9')).

isalpha()

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

islower()

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

isupper()

#include <cctype>
int
isupper(
char
ch)

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

isspace()

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

abs()

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

__builtin_popcount()

__builtin_popcount(
unsigned
n)

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

__gcd()

#include <algorithm>
__gcd(
int
a
,
int
b)

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

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

  1. Стандартна библиотека, част I (www.informatika.bg)
  2. Списък с функциите от библиотеката string.h (www.cplusplus.com)
  3. Списък с функциите от библиотеката stdlib.h (www.cplusplus.com)
  4. Списък с функциите от библиотеката ctype.h (www.cplusplus.com)


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

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

Selected text (if you see this, there is something wrong)

(Незадължително) E-mail за обратна връзка: