Witam, chcę stworzyć własną klasę vector (podobną do tej w STL). Zastanawia mnie jednak jedna rzecz. Z tego co wiem, vector w STL przechowuje swoje elementy nie w liście, tylko w normalnej tablicy przyzielanej dynamicznie. Ale to w takim razie, każda operacja "push_back()", powoduje, iż trzeba utworzyć, nową tablicę o n+1 elementów, przepisać do niej stare elementy, i w tym miejscu n+1 umiescic ten nowy. Nie jest to zbyt czasochłonne? Czy oby na pewno tak działa ten oryginalny vector z STL? Przy vectorze 5000 elementów, dodanie do niego 5001 elementu, powoduje iż trzeba utworzyć tablice 5001 elementow, przepisac do nie te stare 5000 elementów, i ten nowy 5001 element.
0
1
Zamiast zwiększać rozmiar tablicy o 1 zazwyczaj się go podwaja.
0
Acha, ale to mimo to, kiedy trzeba powiekszyc tablice, tworzona jest nowa, i zawartosc starej jest kopiowana do nowej? Bo nie jestem pewien czy tak to zaimplementować...
0
Tak
1
Dlatego rozmiar jest podwajany - żeby nie wykonywać kopiowania zbyt często. Dobrze też jest nie zaczynać od małego rozmiaru np. 2 ;)
0
a nie można skorzystać z listy jedno lub dwukierunkowej?
0
Elementy klasy vector powinny znajdować się jeden za drugim w ciągłym obszarze pamięci, tego zdaje się wymaga standard języka ale pewności nie mam. W każdym razie dostęp do elementu po indeksie powinien odbywać się w czasie O(1).
1
Lista jest złym wyborem, na współczesnych procesorach jest w 90 % przypadków o wiele gorsza niż rozszerzalna tablica (cache), np. wstawienie elementu w środku jest zdecydowanie szybsze w vectorze niż w liście ponieważ przejście po liście jest drogie (oczywiście jak już ma się miejsce do wstawienia to lista będzie szybsza, ale rzadko się to zdarza w praktyce). Maksymalna średnia ilość dodatkowych kopiowań przy używaniu dynamicznej tablicy powiększanej dwukrotnie to dwa na element, z wprowadzeniem konstruktora przenoszącego praktycznie nigdy nie powoduje to mierzalnych spadków wydajności. Jak kopiowanie elementu jest drogie, to zawsze można użyć wskaźników. C++ w swojej "ogromnej" bibliotece standardowej posiada też dość sprytną strukturę danych oszczędzającą kopiowanie, mianowicie deque. Nie gwarantuje ona ciągłości w pamięci wszystkich elementów ale pozwala na szybki dostęp do elementów po indeksie i oczywiście szybkie operacje na początku/końcu.
2
"Lista jest złym wyborem" czyli o wyższości kilofa nad łopatą. Ehhh, przecież cechy które wymieniłeś będą zaletą/wadą w zależności od sytuacji. Lista będzie lepsza tam, gdzie będzie lepsza.
0
@Zjarek cache chyba nie ma aż tyle do tego (bo przecież teoretycznie do cache można wrzucić elementy listy...), co "czytanie z wyprzedzeniem", czyli załadowanie całej tablicy do cache w jednym czytaniu.
Ale z tym wstawianiem to nie do końca tak jest. Faktycznie przejście po liście będzie kosztowne jeśli nie mamy jej w cache, ale sama operacja wstawienia nie będzie taka kosztowna jak kopiowanie połowy wektora.
0
Podwajanie rozmiaru wektora nie jest takie kosztowne przede wszystkim dlatego, że jest z założenia rzadkie.
Warto jednak zacząć od jakiejś sensownej wartości początkowej – często stosuje się tu 16 elementów na start.
Można też pomyśleć o zmniejszaniu wektora o połowę gdy ilość elementów spadnie poniżej 1/4 pojemności.
0
@matieti: poczytaj o reserve i resize.
http://www.cplusplus.com/reference/stl/vector/reserve/
Jeśli znasz liczbę elementów, które będziesz wstawiał hurtowo to dobrze jest odpalić reserve - zmniejsza to liczbę realokacji.
Z kolei przy kasowaniu:
- jeśli niszczysz cały obiekt vector to oczywiście nie musisz kasować jego elementów
- jeśli vector o dużej ilości elementów czyścisz a potem masz ich mniej do wstawienia to możesz zaoszczędzić pamięć używając swap - jest to jakby odwrócenie reserve: