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

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.

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,

Odpowiedzi:

318

std::vectorto klasa szablonów, która obudowuje tablicę dynamiczną 1 , 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 .


  1. 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>:

  1. 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.

  2. std::vector<bool>Klasa jest głupie. Jest zaimplementowany jako skondensowane pole bitowe, a nie jako tablica. Unikaj go, jeśli chcesz tablicę bools!

  3. 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