Rozważ grę przypominającą Kółko i krzyżyk. Standardową planszą w tej grze jest siatka 3×3, na której gracze na zmianę umieszczają symbole „X” i „O”. Wygrywa ten, kto pierwszy zdobędzie trzy symbole z rzędu.
Chociaż możesz przechowywać dane tablicy jako 9 pojedynczych zmiennych, wiemy, że jeśli masz wiele wystąpień elementu, lepiej jest użyć tablicy:
int ttt[9]; // a C-style array of ints (value 0 = empty, 1 = player 1, 2 = player 2)To definiuje tablicę w stylu C z 9 elementami ułożonymi sekwencyjnie w pamięci. Możemy sobie wyobrazić te elementy ułożone jako pojedynczy wiersz wartości, w następujący sposób:
// ttt[0] ttt[1] ttt[2] ttt[3] ttt[4] ttt[5] ttt[6] ttt[7] ttt[8]
Klasa wymiar tablicy to liczba indeksów potrzebnych do wybrania elementu. Tablica zawierająca tylko jeden wymiar nazywana jest tablicą jednowymiarową lub a tablicą jednowymiarową (czasami w skrócie 1d tablica). ttt powyżej jest przykładem tablicy jednowymiarowej, ponieważ elementy można wybierać za pomocą jednego indeksu (np. ttt[2]).
Ale zauważ, że nasza jednowymiarowa tablica nie przypomina naszej planszy do gry w kółko i krzyżyk, która istnieje w dwóch wymiarach. Można to zrobić lepiej.
Tablice dwuwymiarowe
W poprzednim z lekcji zauważyliśmy, że elementy tablicy mogą być dowolnego typu obiektowego. Oznacza to, że typem elementu tablicy może być inna tablica! Zdefiniowanie takiej tablicy jest proste:
int a[3][5]; // a 3-element array of 5-element arrays of intTablica tablic nazywana jest a tablicą dwuwymiarową (czasami w skrócie tablicą 2d), ponieważ ma dwa indeksy dolne.
W przypadku tablicy dwuwymiarowej wygodnie jest myśleć o pierwszym (lewym) indeksie jako wyborze wiersza, a drugim (prawym) jako indeksie. wybranie kolumny. Koncepcyjnie możemy wyobrazić sobie tę dwuwymiarową tablicę ułożoną w następujący sposób:
// col 0 col 1 col 2 col 3 col 4 // a[0][0] a[0][1] a[0][2] a[0][3] a[0][4] row 0 // a[1][0] a[1][1] a[1][2] a[1][3] a[1][4] row 1 // a[2][0] a[2][1] a[2][2] a[2][3] a[2][4] row 2
Aby uzyskać dostęp do elementów dwuwymiarowej tablicy, po prostu używamy dwóch indeksów dolnych:
a[2][3] = 7; // a[row][col], where row = 2 and col = 3W ten sposób w przypadku planszy kółko i krzyżyk możemy zdefiniować tablicę 2d w następujący sposób:
int ttt[3][3];A teraz mamy siatkę elementów 3×3, którą możemy łatwo manipulować za pomocą wierszy i kolumn indeksy!
Tablice wielowymiarowe
Tablice z więcej niż jednym wymiarem nazywane są tablicami wielowymiarowymi.
C++ obsługuje nawet tablice wielowymiarowe z więcej niż 2 wymiarami:
int threedee[4][4][4]; // a 4x4x4 array (an array of 4 arrays of 4 arrays of 4 ints)Na przykład teren w Minecrafcie jest podzielony na bloki o wymiarach 16x16x16 (tzw. sekcje fragmentów).
Tablice o wymiarach większych niż 3 są obsługiwane, ale rzadkie.
Jak tablice 2d są ułożone w pamięci
Pamięć jest liniowa (1-wymiarowa), więc tablice wielowymiarowe są w rzeczywistości przechowywane jako sekwencyjna lista elementów.
Istnieją dwa możliwe sposoby przechowywania następującej tablicy w pamięci:
// col 0 col 1 col 2 col 3 col 4
// [0][0] [0][1] [0][2] [0][3] [0][4] row 0
// [1][0] [1][1] [1][2] [1][3] [1][4] row 1
// [2][0] [2][1] [2][2] [2][3] [2][4] row 2C++ używa wiersz-główny porządek, gdzie elementy są sekwencyjnie umieszczane w pamięci wiersz po rzędzie, od lewej do prawej, od góry do dołu:
[0][0] [0][1] [0][2] [0][3] [0][4] [1][0] [1][1] [1][2] [1][3] [1][4] [2][0] [2][1] [2][2] [2][3] [2][4]
Niektóre inne języki (np. Fortran) używają kolejności głównej kolumny, elementy są sekwencyjnie umieszczane w pamięci kolumna po kolumnie, od góry do dołu, od lewej do po prawej:
[0][0] [1][0] [2][0] [0][1] [1][1] [2][1] [0][2] [1][2] [2][2] [0][3] [1][3] [2][3] [0][4] [1][4] [2][4]
W C++ podczas inicjowania tablicy elementy są inicjowane w kolejności od głównego wiersza. A podczas przechodzenia przez tablicę najskuteczniejszy jest dostęp do elementów w kolejności, w jakiej są ułożone w pamięci.
Inicjowanie tablic dwuwymiarowych
Aby zainicjować tablicę dwuwymiarową, najłatwiej jest użyć zagnieżdżonych nawiasów klamrowych, przy czym każdy zestaw liczb reprezentuje wiersz:
int array[3][5]
{
{ 1, 2, 3, 4, 5 }, // row 0
{ 6, 7, 8, 9, 10 }, // row 1
{ 11, 12, 13, 14, 15 } // row 2
};Chociaż niektóre kompilatory pozwalają pominąć wewnętrzne nawiasy klamrowe, zdecydowanie zalecamy ich mimo to dołączenie dla czytelności
W przypadku użycia nawiasów wewnętrznych brakujące inicjatory zostaną zainicjowane wartością:
int array[3][5]
{
{ 1, 2 }, // row 0 = 1, 2, 0, 0, 0
{ 6, 7, 8 }, // row 1 = 6, 7, 8, 0, 0
{ 11, 12, 13, 14 } // row 2 = 11, 12, 13, 14, 0
};Zainicjowana tablica wielowymiarowa może pominąć (tylko) specyfikację długości znajdującą się najbardziej po lewej stronie:
int array[][5]
{
{ 1, 2, 3, 4, 5 },
{ 6, 7, 8, 9, 10 },
{ 11, 12, 13, 14, 15 }
};W takich przypadkach kompilator może wykonać obliczenia matematyczne, aby dowiedzieć się, jaka jest długość znajdująca się najbardziej po lewej stronie z liczby inicjatorów.
Pomijanie wymiarów innych niż lewe nie jest dozwolone:
int array[][]
{
{ 1, 2, 3, 4 },
{ 5, 6, 7, 8 }
};Podobnie jak zwykłe tablice, tablice wielowymiarowe można nadal inicjalizować do 0 w następujący sposób:
int array[3][5] {};Dwuwymiarowe tablice i pętle
W przypadku jednowymiarowej tablicy możemy użyć pojedynczej pętli do iteracji po wszystkich elementach tablicy:
#include <iostream>
int main()
{
int arr[] { 1, 2, 3, 4, 5 };
// for-loop with index
for (std::size_t i{0}; i < std::size(arr); ++i)
std::cout << arr[i] << ' ';
std::cout << '\n';
// range-based for-loop
for (auto e: arr)
std::cout << e << ' ';
std::cout << '\n';
return 0;
}W przypadku dwuwymiarowej tablicy potrzebujemy dwóch pętli: jednej do wybrania wiersza, a drugiej do wybrania kolumny.
W przypadku dwóch pętli musimy również określić, która pętla będzie zewnętrzną pętlą, a która będzie być pętlą wewnętrzną. Najbardziej efektywny jest dostęp do elementów w kolejności, w jakiej są ułożone w pamięci. Ponieważ C++ używa kolejności głównych wierszy, selektor wierszy powinien być pętlą zewnętrzną, a selektor kolumn powinien być pętlą wewnętrzną.
#include <iostream>
int main()
{
int arr[3][4] {
{ 1, 2, 3, 4 },
{ 5, 6, 7, 8 },
{ 9, 10, 11, 12 }};
// double for-loop with indices
for (std::size_t row{0}; row < std::size(arr); ++row) // std::size(arr) returns the number of rows
{
for (std::size_t col{0}; col < std::size(arr[0]); ++col) // std::size(arr[0]) returns the number of columns
std::cout << arr[row][col] << ' ';
std::cout << '\n';
}
// double range-based for-loop
for (const auto& arow: arr) // get each array row
{
for (const auto& e: arow) // get each element of the row
std::cout << e << ' ';
std::cout << '\n';
}
return 0;
}Przykład dwuwymiarowej tablicy
Przyjrzyjmy się praktycznemu przykładowi dwuwymiarowej tablicy:
#include <iostream>
int main()
{
constexpr int numRows{ 10 };
constexpr int numCols{ 10 };
// Declare a 10x10 array
int product[numRows][numCols]{};
// Calculate a multiplication table
// We don't need to calc row and col 0 since mult by 0 always is 0
for (std::size_t row{ 1 }; row < numRows; ++row)
{
for (std::size_t col{ 1 }; col < numCols; ++col)
{
product[row][col] = static_cast<int>(row * col);
}
}
for (std::size_t row{ 1 }; row < numRows; ++row)
{
for (std::size_t col{ 1 }; col < numCols; ++col)
{
std::cout << product[row][col] << '\t';
}
std::cout << '\n';
}
return 0;
}Ten program oblicza i drukuje tabliczkę mnożenia dla wszystkich wartości od 1 do 9 (włącznie). Zauważ, że podczas drukowania tabeli pętle for zaczynają się od 1 zamiast od 0. Ma to na celu pominięcie drukowania kolumny 0 i wiersza 0, co byłoby po prostu pęczkiem zer! Oto wynik:
1 2 3 4 5 6 7 8 9 2 4 6 8 10 12 14 16 18 3 6 9 12 15 18 21 24 27 4 8 12 16 20 24 28 32 36 5 10 15 20 25 30 35 40 45 6 12 18 24 30 36 42 48 54 7 14 21 28 35 42 49 56 63 8 16 24 32 40 48 56 64 72 9 18 27 36 45 54 63 72 81
Współrzędne kartezjańskie a indeksy tablicy
W geometrii Kartezjański układ współrzędnych jest często używany do opisu położenia obiektów. W dwóch wymiarach mamy dwie osie współrzędnych, umownie nazywane „x” i „y”. „x” to oś pozioma, a „y” to oś pionowa.
W dwóch wymiarach kartezjańskie położenie obiektu można opisać jako parę {x, y}, gdzie współrzędna x i współrzędna y to wartości wskazujące, jak daleko na prawo od osi x i jak daleko nad osią y znajduje się obiekt. Czasami oś Y jest odwracana (tak, że współrzędna Y opisuje, jak daleko poniżej osi Y coś się znajduje).
Przyjrzyjmy się teraz naszemu układowi tablicy 2D w C++:
// col 0 col 1 col 2 col 3 col 4
// [0][0] [0][1] [0][2] [0][3] [0][4] row 0
// [1][0] [1][1] [1][2] [1][3] [1][4] row 1
// [2][0] [2][1] [2][2] [2][3] [2][4] row 2Jest to również dwuwymiarowy układ współrzędnych, w którym położenie elementu można opisać jako [wiersz][col] (gdzie odwrócona jest oś col).
Podczas gdy każdy z nich układy współrzędnych są dość łatwe do zrozumienia niezależnie, konwersja z kartezjańskiego { x, y } na indeksy tablicy [wiersz][kol] jest nieco sprzeczna z intuicją.
Kluczowym spostrzeżeniem jest to, że współrzędna x w układzie kartezjańskim opisuje, która kolumny jest wybierana w systemie indeksowania tablic. I odwrotnie, współrzędna y opisuje, który wiersz jest wybierany. Dlatego współrzędne kartezjańskie { x, y } przekładają się na współrzędne tablicy [y][x], czyli odwrotnie niż moglibyśmy się spodziewać!
Prowadzi to do pętli 2d, które wyglądają tak:
for (std::size_t y{0}; y < std::size(arr); ++y) // outer loop is rows / y
{
for (std::size_t x{0}; x < std::size(arr[0]); ++x) // inner loop is columns / x
std::cout << arr[y][x] << ' '; // index with y (row) first, then x (col)Zauważ, że w tym przypadku indeksujemy tablicę jako a[y][x], co prawdopodobnie jest odwrotne od oczekiwanego porządku alfabetycznego.