Własny Vector "bez wad"

Prowadząc zajęcia z programowania na uczelni zależałoby mi aby mieli ciekawe zadanie i zapamiętali jakie wady ma . Myśląc nad tym przyszedł mi do głowy szalony pomysł: "vector bez wad" - co prawda takie coś nie istnieje, ale pewne częste wady jesteśmy w stanie wyeliminować mając konkretne zastosowanie. Powiedzmy, że nie interesuje nas kolejność elementów. Poza tym w dobie OpenAI nie może być zbyt banalne zadanie.

Oto moje pomysły czym może się on charakteryzować, proszę podrzućcie swoje pomysły:

• unikanie przesuwania - usuwanie elementu ze środka będzie robić swapa z ostatnim elementem
• unikanie realokacji i kopiowania elementów (trochę jak [cpp]std::deque[/cpp]) - trzymamy wskaźniki do tablic (jak [cpp]vector<array<T,N>*>[/cpp]  - gdy brakuje pamięci to jest alokowana kolejna tablica

EDYCJA: Co prawda ten drugi punkt może być przekombinowany. Ale dla samego pierwszego punktu szkoda nazywać to "optymalizacją"
EDYCJA2: Można też rozważyć jak ugryźć temat aby nie było unieważniania iteratorów, przychodzi mi do głowy aby każdy z elementów był wskaźnikiem, czyli:  - ale to nie dość, że jest nakombinowane to jeszcze jest totalnie kiepskie pod względem pamięci cache.

Macie jakieś ciekawe pomysły?

Ewentualnie może ktoś z Was ma pomysł na nietypowy kontener?

Chyba lepiej wymyślić problem jaki chcesz rozwiązać aniżeli wymyślać 'nietypowe' kontenery. Usuwanie elementu 'ze środka' poprzez przesunięcie ostatniego elementu w miejsce usuwania ma 'ograniczone' zastosowanie, ponieważ:
- zmienia kolejność obiektów w kontenerze (przykład: wycinasz jeden znak ze środka) -> efekt będzie niepożądany, gdy wstawisz ostatni znak w to miejsce
- jeżeli kontener zawiera posortowany zbiór danych to automatycznie tracisz tę własność usuwając element ze środka opisanym algorytmem

Skutków ubocznych można znaleźć znacznie więcej w zależności od konkretnego użycia, co nie zmienia faktu, że istnieją takie scenariusze użycia, że algorytm 'wypełniania' luk ostatnim elementem ma sens i nie szkodzi, a wręcz jest idealnym rozwiązaniem.

Tak więc myślę, że lepiej rozwiązywać realne problemy i pokazywać 'jaka struktura' nadaje się najlepiej do rozwiązania danego problemu (i dlaczego), aniżeli próbować na siłę robić z jednego kontenera 'uniwersalne' narzędzie.

Jeśli taką masz potrzebę, to możesz to zrobić z std::vector<>.

Chcesz usuwać wady, czy zalety? Jeśli realokacja jest problemem, powinieneś lepiej szacować ilość potrzebnej pamięci. To jest dosłowne unikanie realokacji i nie wymaga poświęcania zalet wektora.

A jak wtedy chcesz zrobić jakiekolwiek operacje na iteratorach, inne niż dereferencja?

Jakby iterator trzymał wskaźnik nie na konkretny element ale na całą strukturę + indeks to by dało radę przesuwać iteratory.

______________________
Dziękuję Wam za wszystkie uwagi. Faktycznie kombinowanie z Vectorem w taki sposób nie jest dobrym pomysłem.

Natomiast wymyśliłem aby implementowali listę jednokierunkową trzymającą unikalne elementy (bez sortowania) i iteratory do tego. Wydaje się to dobra opcja, bo nie jest życiowo "przekombinowana"

Ale miałeś ich nie unieważniać.

Zależy co dokładnie rozumiemy jako unieważnienie. Bo dla  unieważnienie może być po dodaniu elementu gdziekolwiek (jeśli realokacja lub przesuwanie), lub po usunięciu któregoś z elementów poprzedzających. Jeśli by więc trzymać wskaźniki do elementów to mamy elementy w tym samym miejscu w pamięci i nawet jak coś usuniemy/dodamy/realokacja to dalej przy pomocy wskaźnika będziemy wskazywać na ten sam element.

Tu nie ma pola do interpretacji. Unieważnienie to unieważnienie, za to różne operacje na różnych kontenerach dają różne gwarancje co do ważności wcześniej uzyskanych iteratorów.
Iterator z definicji służy do iterowania - implementuje dereferencję i co najmniej inkrementację. Jak na razie psujesz jedno żeby naprawić drugie.

Faktycznie - chcąc "naprawić" jedną rzecz psuję drugą. Wszystko po to aby ChatGPT nie był w stanie za łatwo rozwiązać.

Niemniej jednak jakby ktoś miał ciekawe pomysły to proszę o podrzucanie - jak nie mi to może innym prowadzącym się to przyda:).