std :: vector kontra std

283

Jakie są różnice między a std::vectora std::arrayC w C ++? Kiedy należy być lepszym od drugiego? Jakie są zalety i wady każdego z nich? Wszystko, co robi mój podręcznik, pokazuje, jak są takie same.

c++ arrays vector

— Zud
źródło

1

Szukam porównania std::vectorvs std::arrayi tego, jak różnią się warunki.

— Zud,

Zud, std::arrayto nie to samo, co tablica C ++. std::arrayto bardzo cienkie opakowanie wokół tablic C ++, którego głównym celem jest ukrycie wskaźnika przed użytkownikiem klasy. Zaktualizuję swoją odpowiedź.

— ClosureCowboy,

Zaktualizowałem tytuł pytania i tekst, aby odzwierciedlić twoje wyjaśnienie.

— Matteo Italia,

318

std::vectorto klasa szablonów, która obudowuje tablicę dynamiczną ¹ , przechowywaną w stercie, która rośnie i kurczy się automatycznie po dodaniu lub usunięciu elementów. Zapewnia wszystkie haki ( begin(), end()iteratory itp.), Które sprawiają, że działa dobrze z resztą STL. Ma również kilka przydatnych metod, które pozwalają wykonywać operacje, które na normalnej tablicy byłyby uciążliwe, takie jak np. Wstawianie elementów na środku wektora (obsługuje całą pracę związaną z przenoszeniem następujących elementów za kulisy).

Ponieważ przechowuje elementy w pamięci przydzielone na stercie, ma pewne obciążenie w stosunku do tablic statycznych.

std::arrayto klasa szablonów, która obudowuje tablicę o rozmiarze statycznym, przechowywaną wewnątrz samego obiektu, co oznacza, że jeśli utworzysz instancję klasy na stosie, sama tablica będzie na stosie. Jego rozmiar musi być znany w czasie kompilacji (jest przekazywany jako parametr szablonu) i nie może się powiększać ani zmniejszać.

Jest bardziej ograniczony niż std::vector, ale często bardziej wydajny, szczególnie w przypadku małych rozmiarów, ponieważ w praktyce jest to głównie lekkie opakowanie wokół tablicy w stylu C. Jest to jednak bezpieczniejsze, ponieważ niejawna konwersja na wskaźnik jest wyłączona, i zapewnia wiele funkcji związanych z STL std::vectorinnych kontenerów, dzięki czemu można go łatwo używać z algorytmami i współpracownikami STL. W każdym razie, dla samego ograniczenia stałego rozmiaru, jest on znacznie mniej elastyczny niż std::vector.

Aby std::arrayzapoznać się ze wstępem , zapoznaj się z tym artykułem ; w celu szybkiego wprowadzenia std::vectori możliwych operacji na nim możesz zajrzeć do jego dokumentacji .

Właściwie myślę, że w standardzie są one opisane w kategoriach maksymalnej złożoności różnych operacji (np. Losowy dostęp w stałym czasie, iteracja wszystkich elementów w czasie liniowym, dodawanie i usuwanie elementów na końcu w stałym zamortyzowanym czasie, itp.), ale AFAIK nie ma innej metody spełnienia takich wymagań niż użycie dynamicznej tablicy. Jak stwierdził @Lucretiel, norma faktycznie wymaga, aby elementy były przechowywane w sposób ciągły, więc jest to tablica dynamiczna, przechowywana tam, gdzie umieszcza ją przypisany alokator.

— Matteo Italia
źródło

6

Odnośnie przypisu: Chociaż jest to prawda, standard gwarantuje również, że arytmetyka wskaźników na elementach wewnętrznych działa, co oznacza, że musi to być tablica: & vec [9] - & vec [3] == 6 jest prawdą.

— Lucretiel,

9

Jestem całkiem pewien, że ten wektor nie kurczy się automatycznie, ale od C ++ 11 możesz wywołać shrink_to_fit.

— Dino

Jestem całkowicie zdezorientowany terminem tablica statyczna i nie jestem pewien, jaka jest właściwa terminologia. Masz na myśli tablicę rozmiarów statycznych, a nie tablicę zmiennych statycznych (wykorzystującą pamięć statyczną). stackoverflow.com/questions/2672085/... . Jaka jest prawidłowa terminologia? Czy tablica statyczna to niechlujny termin na tablicę o stałym rozmiarze?

— Z bozonem

3

@Zboson: zdecydowanie nie tylko ty, static to dość nadużywany termin; samo staticsłowo kluczowe w C ++ ma trzy różne niepowiązane znaczenia, a termin ten jest również często używany do mówienia o rzeczach, które są ustalane w czasie kompilacji. Mam nadzieję, że „rozmiar statyczny” jest nieco bardziej wyraźny.

— Matteo Italia

3

Należy zwrócić uwagę na jedną rzecz: w przypadku programowania w czasie rzeczywistym (gdzie po uruchomieniu nie powinno się wykonywać żadnych dynamicznych alokacji / dezalokacji) prawdopodobnie std :: tablica byłaby prawdopodobnie lepsza niż std :: vector.

— TED

17

Korzystanie z std::vector<T>klasy:

... działa tak samo szybko, jak przy użyciu wbudowanych tablic, zakładając, że robisz tylko te rzeczy, na które pozwalają wbudowane tablice (odczytywanie i zapisywanie na istniejących elementach).
... automatycznie zmienia rozmiar po wstawieniu nowych elementów.
... pozwala wstawiać nowe elementy na początku lub w środku wektora, automatycznie „przesuwając” pozostałe elementy „w górę” (czy to ma sens?). Pozwala również usuwać elementy w dowolnym miejscu std::vector, automatycznie przesuwając pozostałe elementy w dół.
... umożliwia wykonanie odczytu z kontrolą zakresu za pomocą at()metody (zawsze możesz użyć indeksatorów, []jeśli nie chcesz, aby ta kontrola była wykonywana).

Istnieją ~~dwa~~ trzy główne zastrzeżenia std::vector<T>:

Nie masz niezawodnego dostępu do podstawowego wskaźnika, co może być problemem, jeśli masz do czynienia z funkcjami innych firm, które wymagają adresu tablicy.
std::vector<bool>Klasa jest głupie. Jest zaimplementowany jako skondensowane pole bitowe, a nie jako tablica. Unikaj go, jeśli chcesz tablicę bools!
Podczas użytkowania std::vector<T>s będą nieco większe niż tablica C ++ z taką samą liczbą elementów. Wynika to z faktu, że muszą śledzić niewielką ilość innych informacji, takich jak ich bieżący rozmiar, oraz ponieważ przy każdej std::vector<T>zmianie rozmiaru rezerwują więcej miejsca, niż potrzebują. Zapobiega to zmianie rozmiaru przy każdym wstawianiu nowego elementu. To zachowanie można zmienić, podając zwyczaj allocator, ale nigdy nie czułem takiej potrzeby!

Edycja: Po przeczytaniu odpowiedzi Zuda na pytanie poczułem, że powinienem dodać:

std::array<T>Klasa nie jest taka sama jak C ++ tablicy. std::array<T>jest bardzo cienkim opakowaniem wokół tablic C ++, którego głównym celem jest ukrycie wskaźnika przed użytkownikiem klasy (w C ++ tablice są domyślnie rzutowane jako wskaźniki, często w celu zniechęcenia). std::array<T>Klasa przechowuje również jego wielkość (długość), które mogą być bardzo przydatne.

— Zamknięcie Cowboy
źródło

5

Jest „tak samo szybki” jak przy użyciu dynamicznie przydzielanej wbudowanej tablicy. Z drugiej strony, użycie automatycznej tablicy może mieć znacznie różną wydajność (i nie tylko podczas alokacji, ze względu na efekty lokalizacji).

— Ben Voigt

4

W przypadku wektorów innych niż bool w C ++ 11 i nowszych można wywołać data()a, std::vector<T>aby uzyskać podstawowy wskaźnik. Możesz także wziąć adres elementu 0 (gwarantowane działanie z C ++ 11, prawdopodobnie będzie działać z wcześniejszymi wersjami).

— Matt

16

Aby podkreślić punkt wskazany przez @ MatteoItalia, różnica wydajności polega na tym, gdzie przechowywane są dane. Pamięć sterty (wymagana w przypadku vector) wymaga połączenia z systemem w celu przydzielenia pamięci, co może być kosztowne, jeśli liczysz cykle. Pamięć stosu (możliwa array) jest praktycznie „zerowa narzut” pod względem czasu, ponieważ pamięć jest przydzielana przez dostosowanie wskaźnika stosu i jest wykonywana tylko raz po wejściu do funkcji. Stos pozwala także uniknąć fragmentacji pamięci. Oczywiście, std::arraynie zawsze będzie na stosie; zależy to od tego, gdzie je przydzielisz, ale nadal będzie wymagało o jeden mniej alokacji pamięci ze sterty w porównaniu do wektora. Jeśli masz

mała „tablica” (powiedzmy poniżej 100 elementów) - (typowy stos ma około 8 MB, więc nie przydzielaj więcej niż kilku KB na stos lub mniej, jeśli kod jest rekurencyjny)
rozmiar zostanie ustalony
czas życia jest w zakresie funkcji (lub jest wartością elementu o tym samym czasie życia co klasa nadrzędna)
liczysz cykle,

zdecydowanie użyj std::arrayponad wektora. Jeśli którykolwiek z tych wymagań nie jest spełniony, użyj std::vector.

— Mark Lakata
źródło

3

Niezła odpowiedź. „Dla pewności, std :: tablica nie zawsze będzie na stosie; zależy to od tego, gdzie ją przydzielisz.” Jak więc mógłbym stworzyć tablicę std :: nie na stosie z dużą liczbą elementów?

— Trilarion

4

@Trilarion użyj new std::arraylub uczyń go członkiem klasy, do przydzielania której używasz „nowego”.

— Mark Lakata

Czyli oznacza to, że new std::arraynadal spodziewa się znać jego rozmiar w czasie kompilacji i nie może zmienić swojego rozmiaru, ale nadal żyje na stosie?

— Trilarion

Tak. Korzystanie z new std::arrayvs nie ma znaczącej przewagi new std::vector.

— Mark Lakata

12

Jeśli zastanawiasz się nad użyciem tablic wielowymiarowych, istnieje jeszcze jedna dodatkowa różnica między std :: array i std :: vector. Wielowymiarowa tablica std :: będzie miała elementy zapakowane w pamięci we wszystkich wymiarach, podobnie jak tablica w stylu ac. Wielowymiarowy std :: vector nie będzie pakowany we wszystkich wymiarach.

Biorąc pod uwagę następujące deklaracje:

int cConc[3][5];
std::array<std::array<int, 5>, 3> aConc;
int **ptrConc;      // initialized to [3][5] via new and destructed via delete
std::vector<std::vector<int>> vConc;    // initialized to [3][5]

Wskaźnik do pierwszego elementu w tablicy typu c (cConc) lub std :: array (aConc) można iterować przez całą tablicę, dodając 1 do każdego poprzedniego elementu. Są ciasno zapakowane.

Wskaźnik do pierwszego elementu w tablicy wektorowej (vConc) lub tablicy wskaźników (ptrConc) może być iterowany tylko przez pierwsze 5 (w tym przypadku) elementów, a następnie jest 12 bajtów (w moim systemie) narzutu dla następny wektor.

Oznacza to, że tablica std :: vector> zainicjowana jako tablica [3] [1000] będzie znacznie mniejsza w pamięci niż tablica zainicjowana jako tablica [1000] [3], i obie będą większe w pamięci niż std: tablica przydzielona w obu kierunkach.

Oznacza to również, że nie można po prostu przekazać wielowymiarowej tablicy wektorowej (lub wskaźnika) do, powiedzmy, openGL bez uwzględnienia narzutu pamięci, ale można naiwnie przekazać wielowymiarową tablicę std :: tablicę do openGL i sprawić, aby się sprawdziła.

— psimpson
źródło

-17

Wektor jest klasą kontenera, a tablica jest pamięcią przydzieloną.

— Saif al Harthi
źródło

23

Twoja odpowiedź wydaje się dotyczyć std::vector<T>kontra T[], ale pytanie dotyczy std::vector<T>kontra std::array<T>.

— Keith Pinson

std :: vector kontra std :: array w C ++