dynamiczna tablica i dynamiczna jej wielkość

Hey,
Mam takie pytanko: jest coś takiego jak dynamiczna alokacja pamięci w C++. wykonuje się ją mniej więcej tak:

int wielkosc;
cin>>wielkosc;
double * tablica = new double[wielkosc];
 

Moje pytanie brzmi: a gdyby się nagle okazało, że wpisana wielkość jest za mała? to jak powiększyć tą wielkość? Jak zrobić classę z dynamicznie powiększającą się tablicą?
Przykładowo gdy jest klasa string to nigdy nie wiadomo jak długa tablica będzie potrzeba, żeby przechować wszystkie znaki. Co jakiś czas ta wielkość jest zwiększana ale czy byłby ktoś tak miły i pokazał mi na przykładzie jak stworzyć taką klasę, która co jakiś czas powiększa rozmiar swojej tablicy?
Z góry dziękuję za pomoc i pozdrawiam!

Robisz coś takiego:

wielkosc++;

Tworzysz dwie zmienne: pojemność i rozmiar. Pojemność to rozmiar tablicy, a rozmiar to ilość zajętych komórek. Jeżeli dodajesz element do pełnej tablicy to po prostu tworzysz kolejną, większą i kopiujesz do niej zawartość starej, a potem usuwasz starą i od tej pory używasz nowej. Podobnie jeżeli ilość zajętych komórek spadnie dużo poniżej pojemności, np powyżej 70% tablicy jest wolne to też przepisujesz zawartość do nowej tablicy, ale tym razem mniejszej. Dzięki temu oszczędzasz pamięć.

Wibowit napisał(a)

Tworzysz dwie zmienne: pojemność i rozmiar. Pojemność to rozmiar tablicy, a rozmiar to ilość zajętych komórek. Jeżeli dodajesz element do pełnej tablicy to po prostu tworzysz kolejną, większą i kopiujesz do niej zawartość starej, a potem usuwasz starą i od tej pory używasz nowej. Podobnie jeżeli ilość zajętych komórek spadnie dużo poniżej pojemności, np powyżej 70% tablicy jest wolne to też przepisujesz zawartość do nowej tablicy, ale tym razem mniejszej. Dzięki temu oszczędzasz pamięć.

Hey, dziękuję za wyjaśnienie. W takim razie mam rozumieć, że nie ma innego sposobu jak stworzenie "bufora", który będzie przechowywać nasze stare wartości -> następnie wykasowanie starej i stworzenie nowej większej tablicy a następnie przekopiowanie wszystkiego z "bufora" do tej nowej tablicy?
Ten sposób jest nawet ok, jednak obawiam się troszkę o wydajność przy większych tablicach. Ciężko mi sobie wyobrazić takie operacje z większymi tablicami - np. kopiowanie tekstu jakiejś książki za każdym razem, gdy będę dodawał nowe zdanie...

Na pewno nie ma innego wyjścia? :Bo rozumiem, że tak nie można?

int wielkosc;
cin>>wielkosc;
double* tablica = new double[wielkosc];
wielkosc = wielkosc+100; //tablica powiększona o 100 elementów

Czy można? :/ Bodajże **Szewemu **o coś takiego chodziło? (chyba, że źle zinterpretowałem wartosc++)

Pozdrawiam

Dodam, że mniej więcej tak implementowane są dynamiczne listy oparte na tablicach - czyli właśnie to, o co pytasz.

iooi napisał(a)

Dodam, że mniej więcej tak implementowane są dynamiczne listy oparte na tablicach - czyli właśnie to, o co pytasz.

Hey, czy mógłbyś to troszkę rozwinąć bo ja się trochę pogubiłem i nie wiem o której wersji mówisz? czy chodzi Ci o tą wersję z buforem?
Pozdrawiam

Nie, on pisał o czymś innym.

Ogólnie algorytm powinien wyglądać trochę inaczej niż sobie wymyśliłeś - żaden bufor nie jest potrzebny.
1)tworzysz nową tablicę
2)kopiujesz do nowej elementy
3)usuwasz starą
4)ewentualnie stary wskaźnik ustawiasz na nową tablicę

Jest też sposób pośredni, ale odbije się to na czasie dostępu do elementów, ale nie będzie za to straty czasu na usuwaniu/dodawaniu elementów - tworzysz listę (jedno/dwu kierunkową), albo hybrydę tablicy i listy(elementami listy mogą być tablice o pewnym rozmiarze) - w tym wypadku dostęp będzie szybszy niż listy, ale dodawanie/usuwanie elementów w środku będzie praktycznie tak samo wolny jak w wypadku zwykłej tablicy, za to powiększenie czy zmniejszanie takiej struktury jest tanie.

To co opisałem jest powszechnie stosowane w bibliotekach standardowych, czy to std::vector w STLu, czy ArrayList w Javie, itd Jeśli chcesz mieć mało przepisań to ustawiasz większe współczynniki, np powiększasz tablicę trzykrotnie jeżeli jest pełna i zmniejszasz tablicę tylko, gdy jest wypełniona w mniej niż trzeciej części. Koszt zamortyzowany dodania czy usunięcia jednego elementu z takiej tablicy wynosi wtedy Theta(1).

Najlepiej by było, gdybyś po prostu użył std::vector (C++) czy ArrayList (Java). Generalnie są to już dobrze zoptymalizowane implementacje, wszechstronne i przetestowane.

Hey, dzięki wielkie za pomoc! Oczywiście mogę korzystać z vectora ale chodziło mi o zrozumienie problemu :)
rzeczywiście zwiększanie tablicy o 1 jest bez sensu - lepiej ją np. podwajać lub robić to o jakiś procent -> tak jak wspomniałeś.

Pozdrawiam!

Zastanawiałem się nad tym problemem (tylko eksperyment myślowy) i wyszło mi, że nie ma dużych strat na wydajności spowodowanych rozszerzaniem tablicy np. dwukrotnie. Jeżeli do tablicy ma być dodanych n elementów po kolei, to alokujemy nową pamięć tylko log2(n) razy, co można pominąć. Łączna ilość przenosin elementów jest maksymalnie równa 3n (dla n=2^p+1). Jeżeli dane pochodzą z jakiś operacji (np. wczytanie z stdio), to nie ma co się przejmować wydajnością powiększania tablicy. Jeszcze nigdy nie zaobserwowałem przyspieszenia programu spowodowanego użyciem tablicy o stałym rozmiarze (np. tylko raz zaalokwanej) w porównaniu do użycia std::vector.