Hmmm ... z drugiej odpowiedzi brzmi, jakby wektor nie był zaimplementowany jako połączona lista? Czy mam rację? Używam tej listy jako zbioru, który będzie miał dość dużą rotację obiektów dodawanych i usuwanych z niej. Czy ta tablica jest rzeczywiście najlepszą implementacją? Czy jest dostępna wersja z listą połączoną?
interstar
5
@interstar - absolutnie poprawne. Jeśli naprawdę chcesz semantyki listy połączonej, użyj std::list, chociaż wtedy tracisz indeksowalność (nie operator[]), więc tak naprawdę nie jest to tablica. listktóry ma swoje własne cechy charakterystyczne, które vectorczęsto są lepszym wyborem. W standardowych kontenerach C ++ będziesz musiał pójść na kompromis w taki czy inny sposób. Spójrz deque, to może zaoferować ci lepszą wydajność. Jest (stosunkowo) łatwy do zmierzenia vectorvs dequevs, listponieważ są one w dużej mierze wymienne w kodzie - po prostu użyj typedef dla swojego kontenera, np typedef vector<MyObj> MyList.
Steve Townsend
cóż, najpierw spróbuję wektora. Ponieważ indeks jest przydatny. Jeśli jest zbyt wolny, mogę przejść do listy połączonej. Dzięki
interstar
2
@interstar, ArrayListjak można się domyślić z nazwy, również nie jest zaimplementowana jako lista połączona. Możesz o tym pomyśleć LinkedList. Ponadto, nawet jeśli masz dość dużą rotację obiektów dodawanych i usuwanych z listy, vectormoże to być szybsze niż listtak długo, jak na początku przydzielisz wystarczającą ilość miejsca, aby nie trzeba było ponownie przydzielać (tj. maksymalnej przestrzeni, jakiej kiedykolwiek potrzebował).
Kyle Strand
@KyleStrand To interesujące. Zawsze zakładałem, że ArrayList oznaczało „rzecz przypominającą tablicę, która jest zaimplementowana jako lista połączona”, a nie „rzecz podobną do listy połączonej, która jest zaimplementowana jako tablica”.
interstar
63
Kilka dodatkowych punktów ponownie wykorzystaj vectortutaj.
W przeciwieństwie ArrayListoraz Arrayw Javie, nie musisz robić nic specjalnego traktować vectorjako tablicę - bazowego przechowywanie w C ++ jest gwarantowana być ciągłe i efektywne wiertła.
W przeciwieństwie do tego ArrayList, a vectormoże skutecznie przechowywać typy pierwotne bez hermetyzacji jako pełnoprawny obiekt.
Podczas usuwania elementów z pliku vector należy pamiętać, że elementy powyżej usuniętego elementu muszą zostać przesunięte w dół, aby zachować ciągłe przechowywanie. W przypadku dużych pojemników może to być kosztowne.
Upewnij się, że jeśli przechowujesz złożone obiekty w tym, vectorże ich konstruktor kopiujący i operatory przypisania są wydajne. Pod osłonami C ++ STL używa ich podczas porządkowania kontenerów.
Porady dotyczące umieszczania reserve()pamięci z góry (tj. Podczas konstruowania wektora lub czasu inicjalizacji), aby zminimalizować realokację pamięci przy późniejszych rozszerzeniach, są przenoszone z języka Java na C ++.
Odpowiedzi:
Użyj
std::vectorklasy z biblioteki standardowej.źródło
std::list, chociaż wtedy tracisz indeksowalność (nieoperator[]), więc tak naprawdę nie jest to tablica.listktóry ma swoje własne cechy charakterystyczne, którevectorczęsto są lepszym wyborem. W standardowych kontenerach C ++ będziesz musiał pójść na kompromis w taki czy inny sposób. Spójrzdeque, to może zaoferować ci lepszą wydajność. Jest (stosunkowo) łatwy do zmierzeniavectorvsdequevs,listponieważ są one w dużej mierze wymienne w kodzie - po prostu użyj typedef dla swojego kontenera, nptypedef vector<MyObj> MyList.ArrayListjak można się domyślić z nazwy, również nie jest zaimplementowana jako lista połączona. Możesz o tym pomyślećLinkedList. Ponadto, nawet jeśli masz dość dużą rotację obiektów dodawanych i usuwanych z listy,vectormoże to być szybsze niżlisttak długo, jak na początku przydzielisz wystarczającą ilość miejsca, aby nie trzeba było ponownie przydzielać (tj. maksymalnej przestrzeni, jakiej kiedykolwiek potrzebował).Kilka dodatkowych punktów ponownie wykorzystaj
vectortutaj.W przeciwieństwie
ArrayListorazArrayw Javie, nie musisz robić nic specjalnego traktowaćvectorjako tablicę - bazowego przechowywanie w C ++ jest gwarantowana być ciągłe i efektywne wiertła.W przeciwieństwie do tego
ArrayList, avectormoże skutecznie przechowywać typy pierwotne bez hermetyzacji jako pełnoprawny obiekt.Podczas usuwania elementów z pliku
vectornależy pamiętać, że elementy powyżej usuniętego elementu muszą zostać przesunięte w dół, aby zachować ciągłe przechowywanie. W przypadku dużych pojemników może to być kosztowne.Upewnij się, że jeśli przechowujesz złożone obiekty w tym,
vectorże ich konstruktor kopiujący i operatory przypisania są wydajne. Pod osłonami C ++ STL używa ich podczas porządkowania kontenerów.Porady dotyczące umieszczania
reserve()pamięci z góry (tj. Podczas konstruowania wektora lub czasu inicjalizacji), aby zminimalizować realokację pamięci przy późniejszych rozszerzeniach, są przenoszone z języka Java na C ++.źródło