17.9 — Arytmetyka wskaźników i indeks dolny

W lekcji 16.1 — Wprowadzenie do kontenerów i tablic, wspomnieliśmy, że tablice są przechowywane sekwencyjnie w pamięci. Podczas tej lekcji przyjrzymy się bliżej, jak działa matematyka indeksująca tablice.

Chociaż nie będziemy używać matematyki indeksującej na przyszłych lekcjach, tematy poruszane w tej lekcji dadzą ci wgląd w to, jak w rzeczywistości działają pętle for oparte na zakresach, i przydadzą się później, gdy omówimy iteratory.

Co to jest arytmetyka wskaźników?

Arytmetyka wskaźników to funkcja, która pozwala nam zastosować pewne operatory arytmetyczne na liczbach całkowitych (dodawanie, odejmowanie, zwiększanie lub zmniejszanie) do wskaźnika w celu utworzenia nowego adresu pamięci.

Przy danym wskaźniku ptr, ptr + 1 zwraca adres następny obiekt w pamięci (w zależności od typu, na który wskazuje). Zatem jeśli ptr jest int*, a int ma 4 bajty, ptr + 1 zwróci adres pamięci znajdujący się 4 bajty po ptr, I ptr + 2 zwróci adres pamięci, który jest 8 bajtów po ptr.

#include <iostream>

int main()
{
    int x {};
    const int* ptr{ &x }; // assume 4 byte ints

    std::cout << ptr << ' ' << (ptr + 1) << ' ' << (ptr + 2) << '\n';

    return 0;
}

Na maszynie autora wydrukowało to:

00AFFD80 00AFFD84 00AFFD88

Zauważ, że każdy adres pamięci jest o 4 bajty większy od poprzedniego.

Chociaż jest to mniej powszechne, arytmetyka wskaźników działa również z odejmowaniem. Biorąc pod uwagę pewien wskaźnik ptr, ptr - 1 zwraca adres poprzedni obiekt w pamięci (w zależności od typu, na który wskazuje).

#include <iostream>

int main()
{
    int x {};
    const int* ptr{ &x }; // assume 4 byte ints

    std::cout << ptr << ' ' << (ptr - 1) << ' ' << (ptr - 2) << '\n';

    return 0;
}

Na maszynie autora wydrukowało to:

00AFFD80 00AFFD7C 00AFFD78

W tym przypadku każdy adres pamięci jest o 4 bajty mniejszy niż poprzedni.

Zastosowanie Operatory inkrementacji (++) i dekrementacji (--) wskaźnika wykonują tę samą czynność, co odpowiednio dodawanie i odejmowanie wskaźnika, ale w rzeczywistości modyfikują adres przechowywany przez wskaźnik.

Przyjmując pewną wartość typu int x, ++x jest skrótem od x = x + 1. Podobnie, biorąc pod uwagę pewien wskaźnik ptr, ++ptr jest skrótem od ptr = ptr + 1, który wykonuje arytmetykę wskaźników i przypisuje wynik z powrotem do ptr.

#include <iostream>

int main()
{
    int x {};
    const int* ptr{ &x }; // assume 4 byte ints

    std::cout << ptr << '\n';

    ++ptr; // ptr = ptr + 1
    std::cout << ptr << '\n';

    --ptr; // ptr = ptr - 1
    std::cout << ptr << '\n';

    return 0;
}

Na maszynie autora wydrukowało to:

00AFFD80 00AFFD84 00AFFD80

Skrypty subskrypcyjne są implementowane poprzez arytmetykę wskaźników

W poprzedniej lekcji (17.8 -- Zanikanie tablicy w stylu C), zauważyliśmy, że operator[] można zastosować do wskaźnika:

#include <iostream>

int main()
{
    const int arr[] { 9, 7, 5, 3, 1 };
    
    const int* ptr{ arr }; // a normal pointer holding the address of element 0
    std::cout << ptr[2];   // subscript ptr to get element 2, prints 5

    return 0;
}

Przyjrzyjmy się bliżej, co się dzieje tutaj.

Okazuje się, że operacja indeksu dolnego ptr[n] jest zwięzłą składnią odpowiadającą bardziej szczegółowemu wyrażeniu *((ptr) + (n)). Zauważysz, że jest to po prostu arytmetyka wskaźników, z dodatkowymi nawiasami, aby zapewnić, że wszystko zostanie obliczone we właściwej kolejności, oraz ukrytym wyłuskiwaniem, aby uzyskać obiekt pod tym adresem.

Najpierw inicjujemy ptr z arr. Podczas oceny arr jest używany jako inicjator, rozpada się na wskaźnik przechowujący adres elementu z indeksem 0. Zatem ptr przechowuje teraz adres elementu 0.

Następnie wypisujemy ptr[2]. ptr[2] jest odpowiednikiem *((ptr) + (2)), co jest równoznaczne z *(ptr + 2). ptr + 2 zwraca adres obiektu znajdującego się dwa obiekty dalej ptr, czyli element o indeksie 2. Obiekt pod tym adresem jest następnie zwracany do wywołującego.

Przyjrzyjmy się innemu przykładowi:

#include <iostream>

int main()
{
    const int arr[] { 3, 2, 1 };

    // First, let's use subscripting to get the address and values of our array elements
    std::cout << &arr[0] << ' ' << &arr[1] << ' ' << &arr[2] << '\n';
    std::cout << arr[0] << ' ' << arr[1] << ' ' << arr[2] << '\n';

    // Now let's do the equivalent using pointer arithmetic
    std::cout << arr<< ' ' << (arr+ 1) << ' ' << (arr+ 2) << '\n';
    std::cout << *arr<< ' ' << *(arr+ 1) << ' ' << *(arr+ 2) << '\n';

    return 0;
}

Na maszynie autora wydrukowało to:

00AFFD80 00AFFD84 00AFFD88
3 2 1
00AFFD80 00AFFD84 00AFFD88
3 2 1

Zauważysz, że arr przechowuje adres 00AFFD80, (arr + 1) zwraca adres 4 bajty później i (arr + 2) zwraca adres adres 8 bajtów później. Możemy wyłuskać te adresy, aby uzyskać elementy pod tymi adresami.

Ponieważ elementy tablicy są zawsze sekwencyjne w pamięci, jeśli arr jest wskaźnikiem do elementu 0 tablicy, *(arr + n) zwróci n-ty element tablicy.

Jest to główny powód, dla którego tablice opierają się na 0, a nie na 1. To sprawia, że ​​matematyka jest bardziej wydajna (ponieważ kompilator nie musi odejmować 1 przy indeksowaniu dolnym)!

Arytmetyka wskaźników i indeks dolny to adresy względne

Kiedy po raz pierwszy poznajesz indeksowanie tablic, naturalnym jest założenie, że indeks reprezentuje stały element w tablicy: Indeks 0 jest zawsze pierwszym elementem, indeks 1 jest zawsze drugim elementem itd…

To iluzja. Indeksy tablic są w rzeczywistości pozycjami względnymi. Indeksy wydają się po prostu stałe, ponieważ prawie zawsze indeksujemy od początku (element 0) tablicy!

Pamiętaj, że biorąc pod uwagę pewien wskaźnik ptr, oba *(ptr + 1) i ptr[1] zwracają następny obiekt w pamięci (w zależności od wskazywanego typu). Dalej jest terminem względnym, a nie absolutnym. Tak więc, jeśli ptr wskazuje na element 0, to oba *(ptr + 1) i ptr[1] zwrócą element 1. Ale jeśli ptr zamiast tego wskazują na element 3, to oba *(ptr + 1) i ptr[1] zwrócą element 4!

Poniższy przykład ilustruje to:

#include <array>
#include <iostream>

int main()
{
    const int arr[] { 9, 8, 7, 6, 5 };
    const int *ptr { arr }; // arr decays into a pointer to element 0

    // Prove that we're pointing at element 0
    std::cout << *ptr << ptr[0] << '\n'; // prints 99
    // Prove that ptr[1] is element 1
    std::cout << *(ptr+1) << ptr[1] << '\n'; // prints 88

    // Now set ptr to point at element 3
    ptr = &arr[3];

    // Prove that we're pointing at element 3
    std::cout << *ptr << ptr[0] << '\n'; // prints 66
    // Prove that ptr[1] is element 4!
    std::cout << *(ptr+1) << ptr[1] << '\n'; // prints 55
 
    return 0;
}

Zauważysz jednak, że nasz program jest znacznie bardziej zagmatwany, jeśli nie można założyć, że ptr[1] jest zawsze elementem o indeksie 1. Z tego powodu zalecamy stosowanie indeksu dolnego tylko przy indeksowaniu od początku tablicy (element 0). Arytmetyki wskaźników używaj tylko podczas pozycjonowania względnego.

Indeksy ujemne

W ostatniej lekcji wspominaliśmy o tym (w przeciwieństwie do standardowych klas kontenerów bibliotek) indeks tablicy w stylu C może być liczbą całkowitą bez znaku lub liczbą całkowitą ze znakiem. Nie zrobiono tego tylko dla wygody — w rzeczywistości możliwe jest indeksowanie tablicy w stylu C z ujemnym indeksem dolnym. Brzmi zabawnie, ale ma sens.

Właśnie omówiliśmy, że *(ptr+1) zwraca następny obiekt w pamięci. ptr[1] to po prostu wygodna składnia pozwalająca zrobić to samo.

Na początku tej lekcji zauważyliśmy, że *(ptr-1) zwraca poprzedni obiekt w pamięci. Chcesz zgadnąć, jaki jest odpowiednik indeksu dolnego? Tak, ptr[-1].

#include <array>
#include <iostream>

int main()
{
    const int arr[] { 9, 8, 7, 6, 5 };

    // Set ptr to point at element 3
    const int* ptr { &arr[3] };

    // Prove that we're pointing at element 3
    std::cout << *ptr << ptr[0] << '\n'; // prints 66
    // Prove that ptr[-1] is element 2!
    std::cout << *(ptr-1) << ptr[-1] << '\n'; // prints 77
 
    return 0;
}

Arytmetyka wskaźników może być używana do poruszania się po tablicy

Jednym z najczęstszych zastosowań arytmetyki wskaźników jest iteracja po tablicy w stylu C bez jawnego indeksowania. Poniższy przykład ilustruje, jak to się robi:

#include <iostream>

int main()
{
	constexpr int arr[]{ 9, 7, 5, 3, 1 };

	const int* begin{ arr };                // begin points to start element
	const int* end{ arr + std::size(arr) }; // end points to one-past-the-end element

	for (; begin != end; ++begin)           // iterate from begin up to (but excluding) end
	{
		std::cout << *begin << ' ';     // dereference our loop variable to get the current element
	}

	return 0;
}

W powyższym przykładzie zaczynamy nasze przechodzenie od elementu wskazywanego przez begin (który w tym przypadku jest elementem 0 tablicy). Ponieważ begin != end jeszcze jest wykonywane ciało pętli. Wewnątrz pętli dostęp do bieżącego elementu uzyskujemy poprzez *begin, który jest jedynie dereferencją wskaźnika. Po treści pętli wykonujemy ++begin, która wykorzystuje arytmetykę wskaźników do zwiększania begin w celu wskazania następnego elementu. Ponieważ begin != end, treść pętli jest wykonywana ponownie. Dzieje się tak aż do begin != end Jest false, co ma miejsce, gdy begin == end.

W ten sposób powyższe wydruki:

9 7 5 3 1

Zauważ to end jest ustawione na jeden za końcem tablicy. Trzymanie end tego adresu jest w porządku (o ile nie usuniemy odwołania end, ponieważ pod tym adresem nie ma prawidłowego elementu). Robimy to, ponieważ sprawia to, że nasze obliczenia i porównania są tak proste, jak to tylko możliwe (nie ma potrzeby dodawania ani odejmowania 1 gdziekolwiek).

W poprzedniej lekcji 17.8 -- Zanikanie tablicy w stylu C wspomnieliśmy, że rozpad tablicy utrudnia refaktoryzację funkcji, ponieważ pewne rzeczy działają z tablicami, które nie uległy rozkładowi, ale nie z tablicami z rozpadem (jak std::size). Ciekawą rzeczą związaną z przechodzeniem przez tablicę w ten sposób jest to, że możemy zrefaktoryzować część pętli z powyższego przykładu do osobnej funkcji dokładnie tak, jak napisano, i to nadal będzie działać:

#include <iostream>

void printArray(const int* begin, const int* end)
{
	for (; begin != end; ++begin)   // iterate from begin up to (but excluding) end
	{
		std::cout << *begin << ' '; // dereference our loop variable to get the current element
	}
    
	std::cout << '\n';
}

int main()
{
	constexpr int arr[]{ 9, 7, 5, 3, 1 };

	const int* begin{ arr };                // begin points to start element
	const int* end{ arr + std::size(arr) }; // end points to one-past-the-end element

	printArray(begin, end);

	return 0;
}

Zauważ, że ten program kompiluje i generuje poprawny wynik, mimo że nigdy jawnie nie przekazujemy tablicy do funkcji! I dlatego, że nie mijamy arr, nie musimy zajmować się zepsutym arr w printArray(). Zamiast, begin i end zawierają wszystkie informacje potrzebne do przejścia przez tablicę.

Na przyszłych lekcjach (kiedy omówimy iteratory i algorytmy) przekonamy się, że biblioteka standardowa jest pełna funkcji korzystających z begin i end pair, aby zdefiniować, na jakich elementach kontenera ma działać funkcja.

Pętle for oparte na zakresach w tablicach w stylu C są implementowane przy użyciu arytmetyki wskaźników

Rozważ następującą pętlę for opartą na zakresie:

#include <iostream>

int main()
{
	constexpr int arr[]{ 9, 7, 5, 3, 1 };

	for (auto e : arr)         // iterate from `begin` up to (but excluding) `end`
	{
		std::cout << e << ' '; // dereference our loop variable to get the current element
	}

	return 0;
}

Jeśli spojrzysz na dokumentacja w przypadku pętli for opartych na zakresie zobaczysz, że zazwyczaj są one implementowane w podobny sposób:

{
    auto __begin = begin-expr;
    auto __end = end-expr;

    for ( ; __begin != __end; ++__begin)
    {
        range-declaration = *__begin;
        loop-statement;
    }
}

Zastąpmy pętlę for opartą na zakresie z poprzedniego przykładu następującą implementacją:

#include <iostream>

int main()
{
	constexpr int arr[]{ 9, 7, 5, 3, 1 };

	auto __begin = arr;                // arr is our begin-expr
	auto __end = arr + std::size(arr); // arr + std::size(arr) is our end-expr

	for ( ; __begin != __end; ++__begin)
	{
		auto e = *__begin;         // e is our range-declaration
		std::cout << e << ' ';     // here is our loop-statement
	}

	return 0;
}

Zwróć uwagę, jak podobny jest to przykład, który napisaliśmy w poprzedniej sekcji! Jedyna różnica polega na tym, że przypisujemy *__begin Do e i używanie e a nie tylko używać *__begin bezpośrednio!

Czas quizu

Pytanie nr 1

a) Dlaczego arr[0] taki sam jak *arr?

Pokaż rozwiązanie