vector vs tab

4. Porównanie Struktur Pamięciowych: Raw Array vs std::array vs std::vector

Segmenty pamięci i zachowanie w runtime

• Surowa tablica lokalna (Raw Array na stosie):
  • Umieszczana bezpośrednio w ramce stosu.
  • Obciążona sztywnym limitem stosu (zazwyczaj 1 MB na Windows, 8 MB na Linux).
  • Duże deklaracje tablic lokalnych skutkują natychmiastowym błędem przepełnienia stosu (Stack Overflow).
  • Ulega degradacji do wskaźnika (array decay) przy przekazaniu do funkcji, co uniemożliwia weryfikację jej rozmiaru przez kompilator.
• Tablica statyczna / globalna (Sekcja .bss):
  • Alokowana w segmencie danych programu bez narzutu na stos i alokator sterty.
  • Strony pamięci są zerowane na poziomie jądra systemu operacyjnego z wykorzystaniem techniki Copy-on-Write (strony fizyczne są mapowane dopiero w chwili faktycznego zapisu).
  • Adres bazowy jest stały i znany na etapie konsolidacji (linkowania), co eliminuje konieczność dereferencji wskaźnika bazowego.
• Kontener std::array:
  • Cienki obiektowy wrapper na surową tablicę o zerowym narzucie pamięciowym (0 B).
  • Nie podlega degradacji do wskaźnika, zachowuje pełne metadane o rozmiarze i wspiera semantykę wartości.
• Kontener std::vector:
  • Alokuje bufor danych wyłącznie na stercie (Heap) i zarządza nim w modelu RAII.
  • Sam obiekt zajmuje na stosie 24 bajty (trzy 64-bitowe wskaźniki: początek bufora, koniec danych, koniec zaalokowanej przestrzeni).
  • Odczyt wymaga dereferencji wskaźnika bazowego, a powiększenie bufora wiąże się z reallokacją i przeniesieniem elementów.

---

5. Wytyczne Decyzyjne (Engineering Rules of Thumb)

1. Gęsty zbiór kluczy o znanym, niewielkim limicie ($\le 10^7$):
   Wybierz statyczną tablicę bezpośrednią w sekcji .bss ze znacznikiem 64-bitowym. Gwarantuje to maksymalną przepustowość odczytu/zapisu bez alokacji dynamicznej.
2. Dowolne, rzadkie identyfikatory bez limitu:
   Wybierz płaską mapę haszującą (flat hash map), minimalizując zużycie pamięci do rozmiaru zbioru roboczego.
3. Klucze rzadkie z twardym rygorem pamięciowym:
   Zastosuj strukturę typu Bounded LRU Cache, która odcina nadmiarowe wpisy i zapobiega wyciekom pamięci.
4. Zmienna liczba elementów znana dopiero w runtime:
   Zastosuj dynamiczny bufor na stercie (std::vector), chroniący przestrzeń stosu przed przepełnieniem.