Jak poszedłbyś o ustaleniu, czypozycja jest już zajęta czy nie? Kiedy pamięć jest przydzielana, wszystko, co w niej jest, to śmieci (w C ++, czyli używam atm). Myślałem o użyciu pomocniczej tablicy booli, aby wiedzieć, czy pozycja jest zajęta, ale to wymagałoby sporo dodatkowej pamięci.
Mógłbym również ustawić wartość dla każdej pozycji, alewtedy nie byłbym w stanie użyć tej wartości. W obu przypadkach straciłbym także pewną wydajność inicjalizującą wartości (na przykład wartość bools to false, a inne wartości do 0 wskazują, że pozycja jest wolna).
Jakieś inne rozwiązania?
Odpowiedzi:
2 dla odpowiedzi № 1Zwykle używasz specjalnego elementu zastępczego dowskaż puste wartości. W najprostszym przypadku może to być wskaźnik zerowy, ale to oczywiście oznacza, że wprowadzasz pośrednie; nie możesz przechowywać swoich wartości bezpośrednio. We wszystkich innych przypadkach musisz uwzględnić rzeczywisty typ. Na przykład, jeśli zapisałeś 32-bitowe liczby całkowite, musisz zarezerwować przynajmniej jedną wstępnie zdefiniowaną wartość (np. 0) jako element wartownika, zmniejszając w ten sposób zakres wartości, które mogą być przechowywane w tabeli skrótów.
Dodatkowa tablica z flagami jest całkiem niezłarozwiązanie. Weź pod uwagę, że tablica ta może zostać zmniejszona co najmniej 8-krotnie poprzez przechowywanie flag bitowych zamiast zmiennych całobajtowych (lub nawet boolów, które wymagałyby 4 bajtów każda na większości architektur).
0 dla odpowiedzi nr 2
Możesz użyć boost::optional do tego zamiast surowej wartości. Z tego powodu został utworzony, aby dodać niezainicjowaną wartość do elementu. Ma wydajność podobną do inicjalizacji wartości w pierwszej kolejności, ale wymaga tylko niewielkiej ilości dodatkowej pamięci na element.