Narkotykowy wektor
W programowaniu komputerowym wektor narkotyku to struktura danych używana do przechowywania informacji o obiekcie danych , zwłaszcza o układzie pamięci .
Zamiar
Wektory Dope są najczęściej używane do opisywania tablic , które zwykle przechowują wiele instancji określonego typu danych jako ciągły blok pamięci. Na przykład tablica zawierająca 100 elementów, z których każdy zajmuje 32 bajty, wymaga 100 × 32 bajtów. Sam taki blok pamięci nie ma miejsca na śledzenie, jak duża jest tablica (lub inny obiekt), jak duży jest każdy element w nim zawarty lub ile elementów zawiera. Dope vector to miejsce do przechowywania takich informacji. Wektory Dope mogą również opisywać struktury , które mogą zawierać tablice lub elementy zmienne.
Jeśli taka tablica jest przechowywana w sposób ciągły, z pierwszym bajtem w lokalizacji pamięci M , to jej ostatni bajt znajduje się w lokalizacji M + 3199 . Główną zaletą tego układu jest to, że zlokalizowanie elementu N jest łatwe: zaczyna się w miejscu M + ( N × 32) . Oczywiście wartość 32 musi być znana (potocznie ta wartość nazywana jest „krokiem” tablicy lub „szerokością” elementów tablicy). Poruszanie się po strukturze danych tablicowych za pomocą indeksu jest nazywane martwym zliczaniem .
Jednak taki układ (bez dodawania wektorów dope) oznacza, że posiadanie położenia elementu N nie wystarczy do odkrycia samego indeksu N; lub krok; lub czy istnieją elementy w N - 1 lub N + 1 . Na przykład funkcja lub metoda może iterować po wszystkich elementach w tablicy i przekazywać każdy z nich do innej funkcji lub metody, która w ogóle nie wie, że element jest częścią tablicy, a tym bardziej, gdzie i jak duża jest tablica.
Bez wektora dope, nawet znając adres całej tablicy, nie można powiedzieć, jak duża jest. Jest to ważne, ponieważ zapis do N + 1 w tablicy, która zawiera tylko N elementów, prawdopodobnie zniszczy niektóre inne dane. Ponieważ wiele języków programowania traktuje ciągi znaków jako rodzaj tablicy, prowadzi to bezpośrednio do niesławnego problemu przepełnienia bufora .
Wektor dope zmniejsza te problemy, przechowując niewielką ilość metadanych wraz z tablicą (lub innym obiektem). Dzięki wektorom dope kompilator może łatwo (i opcjonalnie) wstawić kod, który zapobiega przypadkowemu zapisowi poza końcem tablicy lub innego obiektu. Alternatywnie, programista może uzyskać dostęp do wektora narkotyku, gdy jest to pożądane, ze względów bezpieczeństwa lub w innych celach.
Opis
Dokładny zestaw metadanych zawartych w wektorze dopingu różni się w zależności od języka i/lub systemu operacyjnego, ale wektor dopingu dla tablicy może zawierać:
- wskaźnik do miejsca w pamięci, gdzie zaczynają się elementy tablicy (zwykle jest to identyczne z położeniem elementu zerowego tablicy (element ze wszystkimi indeksami dolnymi 0). (Może to nie być pierwszy rzeczywisty element, jeśli indeksy dolne nie zaczynają się od zero.)
- typ każdego elementu tablicy (liczba całkowita, wartość logiczna, konkretna klasa itp.).
- ranga tablicy .
- zakres tablicy (jej zakres indeksów). (W wielu językach indeks początkowy dla tablic jest ustalony na zero lub jeden, ale indeks końcowy jest ustawiany, gdy tablica jest (ponownie) przydzielana.)
- w przypadku tablic, w których zakres używany w danym czasie może się zmieniać, można przechowywać zarówno maksymalny, jak i bieżący zakres.
- krok tablicy lub ilość pamięci zajmowanej przez każdy element tablicy.
Następnie program może odwoływać się do tablicy (lub innego obiektu używającego wektora domieszek), odwołując się do wektora domieszek. Jest to zwykle automatyczne w językach wysokiego poziomu . Dotarcie do elementu tablicy kosztuje trochę więcej (zwykle jedna instrukcja, która pobiera wskaźnik do rzeczywistych danych z wektora dope). Z drugiej strony wykonywanie wielu innych typowych operacji jest łatwiejsze i/lub szybsze:
- Bez wektora dope określenie liczby elementów w tablicy jest niemożliwe. Dlatego często dodaje się dodatkowy element na końcu tablicy z wartością „zarezerwowaną” (taką jak NULL). Długość można następnie określić, skanując tablicę do przodu, licząc elementy, aż do osiągnięcia tego „znacznika końcowego”. Oczywiście sprawia to, że sprawdzanie długości jest znacznie wolniejsze niż sprawdzanie długości bezpośrednio w wektorze dope.
- Nie znając rozmiaru tablicy, nie można zwolnić () (cofnąć) tej pamięci, gdy nie jest już potrzebna. Tak więc, bez wektorów dope, coś musi przechowywać tę długość gdzie indziej. Na przykład poproszenie określonego systemu operacyjnego o przydzielenie miejsca dla tablicy 3200-bajtowej może spowodować, że przydzieli on 3204 bajty w jakiejś lokalizacji M; następnie zapisze rozmiar w pierwszych 4 bajtach i powie programowi żądającemu, że przydzielone miejsce zaczyna się od M + 4 (aby wywołujący nie traktował dodatkowych 4 bajtów jako części właściwej tablicy). Te dodatkowe dane nie są uważane za wektor narkotyków, ale służą do osiągnięcia tych samych celów.
- Bez wektorów dope, dodatkowe informacje muszą być również przechowywane na temat kroku (lub szerokości) elementów tablicy. W C informacje te są obsługiwane przez kompilator, który musi śledzić rozróżnienie typu danych między „wskaźnikiem do tablicy elementów o szerokości 20 bajtów” a „wskaźnikiem do tablicy elementów o szerokości 1000 bajtów”. Oznacza to, że wskaźnik do elementu w dowolnej tablicy może być zwiększany lub zmniejszany w celu dotarcia do następnego lub poprzedniego elementu; ale oznacza to również, że szerokości tablic muszą być ustalone na wcześniejszym etapie.
Nawet w przypadku wektora domieszki posiadanie (tylko) wskaźnika do określonego elementu tablicy nie umożliwia znalezienia pozycji w tablicy, lokalizacji tablicy lub samego wektora domieszki. Jeśli jest to pożądane, takie informacje można dodać do każdego elementu w tablicy. Takie informacje o elemencie mogą być przydatne, ale nie są częścią wektora narkotyku.
Wektory dope mogą być ogólnym obiektem, współdzielonym przez wiele typów danych (nie tylko tablice i/lub łańcuchy).
Zobacz też
- Bibliografia _ Zelkowitz, M. (1996). Języki programowania: projektowanie i wdrażanie (wyd. 3). Upper Saddle River, NJ : Prentice-Hall . P. 114. ISBN 978-0-13-678012-0 .
- ^ Claybrook, Billy G. (13–15 października 1976). Projekt struktury szablonu dla narzędzia definiowania uogólnionej struktury danych . ICSE '76: 2. międzynarodowa konferencja poświęcona inżynierii oprogramowania. San Francisco, Kalifornia, USA: IEEE Computer Society Press. s. 408–413.