Стандартна библиотека, част 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 библиотеки, които ще разгледаме (особено тези в ). Не ме питайте защо. Понякога ще даваме "грешни" сигнатури на функциите с цел малко по-голяма яснота. |
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)
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;
}
strlen()
#include
unsigned int strlen(const char* 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
Една от много полезните функции, когато създавате тестове (независимо дали да тествате ваше или чуждо решение). Връща произволно цяло число в някакъв интервал.
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' && ch <= '9')
).isalnum()
#include
int isalnum(char ch)
((ch >= 'A' && ch <= 'Z') || (ch >= 'a' && ch <= 'z') || (ch >= '0' && ch <= '9'))
.isalpha()
#include
int isalpha(char ch)
((ch >= 'A' && ch <= 'Z') || (ch >= 'a' && ch <= 'z'))
. Връща 0 ако не е, и различно от 0 число, ако е.islower()
#include
int islower(char ch)
(ch >= 'a' && ch <= 'z')
.isupper()
#include
int isupper(char ch)
Проверява дали аргументът ch е главна латинска буква. Връща 0 ако не е, и различно от 0 число, ако е. Почти еквивалентно е на
(ch >= 'A' && ch <= 'Z')
.isspace()
#include
int isspace(char ch)
' '
), табулация ('\t'
), нов ред ('\r'
или '\n'
), или някой от по-рядко ползваните '\f'
или '\v'
. Връща 0 ако не е, и различно от 0 число, ако е.abs()
#include
Връща абсолютната стойност на аргумента. Понякога не работи с
long long
(зависи от компилатора), но на по-новите GCC-та е окей.__builtin_popcount()
__builtin_popcount(unsigned n)
__gcd()
#include
__gcd(int a, int b)
Допълнителни материали
- Стандартна библиотека, част I (www.informatika.bg)
- Списък с функциите от библиотеката string.h (www.cplusplus.com)
- Списък с функциите от библиотеката stdlib.h (www.cplusplus.com)
- Списък с функциите от библиотеката ctype.h (www.cplusplus.com)
За да предложите корекция, селектирайте думата или текста, който искате да бъде променен,
натиснете Enter и изпратете Вашето предложение.
натиснете Enter и изпратете Вашето предложение.
Страницата е посетена 9319 пъти.