xion.log » Indeksowanie od tyłu

Indeksowanie od tyłu

2010-01-12 20:58

Pewna 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:

  1. for (int i = 1; i <= n; ++i) // w przód
  2. for (int i = n; i >= 1; --i) // w tył

W przypadku indeksowania od zera pętla odliczająca wstecz jest wyraźnie różna:

  1. for (int i = 0; i < n; ++i) // w przód
  2. 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ą:

  1. 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 :)

Tags: , , ,
Author: Xion, posted under Programming »


6 comments for post “Indeksowanie od tyłu”.
  1. n:
    January 13th, 2010 o 2:25

    Jest jeszcze inne rozwiązanie:

    for (size_t i = x.size() ; i–>0;)

  2. Xion:
    January 13th, 2010 o 8:56

    To prawie jak słynny “operator” ‘dąży do’:

    1. int i = x.size();
    2. while (i --> 0)
  3. Sobol:
    January 13th, 2010 o 10:38

    Xion 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.

  4. Gynvael Coldwind:
    January 13th, 2010 o 14:12

    Wpadki 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
    #include

    int
    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–

  5. Gynvael Coldwind:
    January 13th, 2010 o 18:47

    A propos off-by-one:
    http://xorl.wordpress.com/2010/01/13/cve-2001-0053-openbsd-ftpd-remote-off-by-one-overwrite/

  6. Xion:
    January 13th, 2010 o 19:18

    Sobol: 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.

Comments are disabled.
 


© 2018 Karol Kuczmarski "Xion". Layout by Urszulka. Powered by WordPress with QuickLaTeX.com.