Indeksowanie od tyłu
2010-01-12 20:58Pewna programistyczna mądrość ludowa uczy, że jedynymi liczbami bezpośrednio występującymi w kodzie powinny być tylko 0 lub 1. Brak lub nadmiar tej drugiej jest przy tym często pojawiającym się błędem, który zyskał swoją własną nazwę pomyłek o jedynkę (off-by-one errors).
Okazji do popełnienia tego rodzaju gaf jest sporo, a objawiają się one przede wszystkim wtedy, gdy mamy do czynienia z tablicami, łańcuchami znaków, kolekcjami, itd. – innymi słowy wszystkim, co da się indeksować. Jako rzecze C++ i większość innych “normalnych” języków, indeksy tablic rozpoczynają się od zera. Startowanie ich od jedynki ma aczkolwiek pewną zaletę: pętle przeglądające zawartość tablic mają wtedy prawie identyczne postaci niezależnie od kierunku przeglądania:
- for (int i = 1; i <= n; ++i) // w przód
- for (int i = n; i >= 1; --i) // w tył
W przypadku indeksowania od zera pętla odliczająca wstecz jest wyraźnie różna:
- for (int i = 0; i < n; ++i) // w przód
- for (int i = n - 1; i >= 0; --i) // w tył
Pisząc ją, trzeba więc zwrócić baczniejszą uwagę na to, co się robi.
Jednak nawet wtedy można potknąć się o pewien kruczek, gdy pod n podstawimy rzeczywiście używane wartości. Niech to będzie np. wielkość kolekcji STL czy długość łańcucha znaków std::string – a więc coś w stylu x.size(). Otóż takie wyrażenie zwraca liczbę typu równoważnego size_t, który z kolei jest równy ni mniej, ni więcej, jak tylko unsigned int. Jest to więc liczba bez znaku.
W zwykłej wersji pętli (liczonej do przodu) powoduje to ostrzeżenie kompilatora o niezgodności typów ze znakiem i bez znaku (signed/unsigned mismatch) w warunku i < x.size(), gdy i jest typu int. Jednym ze sposobów na pozbycie się tego warninga jest oczywiście zamiana typu licznika na size_t. Jeśli teraz mamy wystarczająco zły dzień, to przez analogię będziemy licznikiem tego typu indeksować również pętlę odwrotną:
- for (size_t i = x.size() - 1; i >= 0; --i) // no i zonk
I nieszczęście gotowe. Zauważmy bowiem, że odliczanie do tyłu tablicy/kolekcji indeksowanej od zera wymaga, by na koniec licznik przyjął na koniec wartość ujemną; inaczej warunek i >= 0 nigdy nie stanie się fałszywy. To się jednak nigdy nie stanie, gdy i jest liczbą bez znaku; zamiast tego nastąpi przekręcenie na maksymalną wartość dodatnią. Skutkiem będzie pętla nieskończona lub (częściej) access violation.
Co z tego wynika? Ano to, żeby… indeksowania generalnie unikać :) Po to bowiem zarówno STL, jak i każda inna biblioteka pojemników w każdym sensownym języku ma inne sposoby dostępu do elementów – choćby iteratory – aby z nich korzystać. I unikać takich “ciekawych” błędów jak powyższy :)
-
n:
January 13th, 2010 o 2:25Jest jeszcze inne rozwiązanie:
for (size_t i = x.size() ; i–>0;)
-
Xion:
January 13th, 2010 o 8:56To prawie jak słynny “operator” ‘dąży do’:
- int i = x.size();
- while (i --> 0)
-
Sobol:
January 13th, 2010 o 10:38Xion co do iteratorów i tego typu rozwiązań – zauważ, że zawsze mają pewien narzut i pamięciowy i obliczeniowy. Jeśli robię coś co ma kluczowe znaczenie dla wydajności to nigdy nie stosuję iteratorów.
-
Gynvael Coldwind:
January 13th, 2010 o 14:12Wpadki z off-by-one są częste przy korzystaniu z funkcji ze standardowej biblioteki C, typu strncat czy scanf, które oczekują nie wielkości tablicy, a wielkości tablicy-1 (czyli zakładają że tablica jest większa o jeden element, i wstawiają tam terminator ).
Zresztą standardowe lib C ma zwyczaj mieszać ludziom. Np funkcja strncpy, w przeciwieństwie do strncat, dostaje wielkość bufora, i w razie czego NIE WSTAWIA terminatora (a strncat wstawi po buforze).
Spójność.. prawie jak ;>–kod testowy–
#include
#include
#includeint
main(void)
{
static char buf[16];// Zalozenie: buf ma 4 bajty
memset(buf, ‘A’, 15);
strncpy(buf, “xxxxxxxx”, 4);
puts(buf);
// wynik: xxxxAAAAAAAAAAA (czyli brakuje terminatora)memset(buf, ‘A’, 15);
buf[0] = ”;
strncat(buf, “xxxxxxxx”, 4);
puts(buf);
// wynik: xxxx (czyli 4*x + 1*, razem 5!)memset(buf, ‘A’, 15);
sscanf(“xxxxxxxx”, “%4s”, buf);
puts(buf);
// wynik: xxxx (czyli 4*x + 1*, razem 5!)return 0;
}–koniec–
-
Gynvael Coldwind:
January 13th, 2010 o 18:47A propos off-by-one:
http://xorl.wordpress.com/2010/01/13/cve-2001-0053-openbsd-ftpd-remote-off-by-one-overwrite/ -
Xion:
January 13th, 2010 o 19:18Sobol: Wydajność iteratorów zależy ściśle od kolekcji, którą przeglądamy. I tak np. iteratory wektorów w implementacjach STL bez włączonego trybu debug są często po prostu wskaźnikami, więc w istocie działają wręcz szybciej niż indeksowanie. Dla bardziej skomplikowanych pojemników może być aczkolwiek inaczej.
Recent posts
