Początkowa pojemność wektora w C ++

Co to capacity()jest, std::vectorktóry jest tworzony przy użyciu domyślnego konstruktora? Wiem, że to size()jest zero. Czy możemy stwierdzić, że domyślnie skonstruowany wektor nie wywołuje alokacji pamięci sterty?

W ten sposób byłoby możliwe utworzenie tablicy z dowolną rezerwą przy użyciu jednej alokacji, np std::vector<int> iv; iv.reserve(2345);. Powiedzmy, że z jakiegoś powodu nie chcę zaczynać size()na 2345.

Na przykład w systemie Linux (g ++ 4.4.5, kernel 2.6.32 amd64)

#include <iostream>
#include <vector>

int main()
{
  using namespace std;
  cout << vector<int>().capacity() << "," << vector<int>(10).capacity() << endl;
  return 0;
}

drukowane 0,10. Czy jest to reguła, czy też zależy od dostawcy STL?

Standard nie określa, jaka capacitypowinna być inicjał kontenera, więc polegasz na implementacji. Typowa implementacja rozpocznie wydajność od zera, ale nie ma gwarancji. Z drugiej strony nie ma sposobu, aby ulepszyć swoją strategię, std::vector<int> iv; iv.reserve(2345);więc trzymaj się jej.

Implementacje pamięci masowej std :: vector znacznie się różnią, ale wszystkie te, z którymi się spotkałem, zaczynają się od 0.

Poniższy kod:

#include <iostream>
#include <vector>

int main()
{
  using namespace std;

  vector<int> normal;
  cout << normal.capacity() << endl;

  for (unsigned int loop = 0; loop != 10; ++loop)
  {
      normal.push_back(1);
      cout << normal.capacity() << endl;
  }

  cin.get();
  return 0;
}

Daje następujący wynik:

0
1
2
4
4
8
8
8
8
16
16

zgodnie z GCC 5.1 i:

0
1
2
3
4
6
6
9
9
9
13

pod MSVC 2013.

O ile zrozumiałem standard (chociaż właściwie nie mogłem nazwać referencji), instancjacja kontenera i alokacja pamięci zostały celowo rozdzielone nie bez powodu. Dlatego masz różne, oddzielne wezwania

• constructor aby stworzyć sam kontener
• reserve() aby wstępnie przydzielić odpowiednio duży blok pamięci, aby pomieścić co najmniej (!) daną liczbę obiektów

I to ma sens. Jedynym prawem do istnienia reserve()jest danie ci możliwości kodowania wokół potencjalnie kosztownych realokacji podczas wzrostu wektora. Aby być użytecznym, musisz znać liczbę obiektów do przechowywania lub przynajmniej umieć dokonać świadomego przypuszczenia. Jeśli to nie jest podane, lepiej trzymaj się z daleka, reserve()ponieważ po prostu zmienisz realokację na zmarnowaną pamięć.

Więc łącząc to wszystko razem:

• Standard celowo nie określa konstruktora, który pozwala wstępnie zaalokować blok pamięci dla określonej liczby obiektów (co byłoby przynajmniej bardziej pożądane niż przydzielenie konkretnego, ustalonego „czegoś” pod maską).
• Alokacja nie powinna być niejawna. Tak więc, aby wstępnie przydzielić blok, musisz wykonać osobne wywołanie, reserve()a to nie musi znajdować się w tym samym miejscu budowy (może / powinno być oczywiście później, po uzyskaniu informacji o wymaganym rozmiarze do pomieszczenia)
• Tak więc, gdyby wektor zawsze wstępnie przydzielał blok pamięci o zdefiniowanym przez implementację rozmiarze, udaremniłoby to zamierzone zadanie reserve(), prawda?
• Jaka byłaby zaleta wstępnego przydzielania bloku, jeśli STL w naturalny sposób nie może znać zamierzonego celu i oczekiwanego rozmiaru wektora? Będzie to raczej bezsensowne, jeśli nie przyniesie odwrotnych skutków.
• Zamiast tego właściwym rozwiązaniem jest przydzielenie i zaimplementowanie określonego bloku za pomocą pierwszego push_back()- jeśli nie został on wcześniej wyraźnie przydzielony przez reserve().
• W przypadku konieczności ponownej alokacji zwiększenie rozmiaru bloku jest również zależne od implementacji. Implementacje wektorów, o których wiem, zaczynają się od wykładniczego wzrostu rozmiaru, ale ograniczają szybkość przyrostu do pewnego maksimum, aby uniknąć marnowania ogromnej ilości pamięci, a nawet jej przepalenia.

Wszystko to w pełni działa i przynosi korzyści tylko wtedy, gdy nie jest zakłócane przez konstruktora alokującego. Masz rozsądne wartości domyślne dla typowych scenariuszy, które można zastąpić na żądanie przez reserve()(i shrink_to_fit()). Tak więc, nawet jeśli standard nie stwierdza tego wprost, jestem całkiem pewien, że założenie, że nowo skonstruowany wektor nie jest wstępnie przydzielony, jest całkiem bezpiecznym zakładem dla wszystkich obecnych implementacji.

Jako niewielki dodatek do innych odpowiedzi stwierdziłem, że podczas uruchamiania w warunkach debugowania w programie Visual Studio domyślny skonstruowany wektor nadal będzie alokowany na stercie, mimo że pojemność zaczyna się od zera.

W szczególności, jeśli _ITERATOR_DEBUG_LEVEL! = 0, wektor przydzieli trochę miejsca, aby pomóc w sprawdzaniu iteratora.

https://docs.microsoft.com/en-gb/cpp/standard-library/iterator-debug-level

Po prostu uznałem to za nieco irytujące, ponieważ używałem wówczas niestandardowego alokatora i nie spodziewałem się dodatkowej alokacji.

To jest stare pytanie i wszystkie odpowiedzi tutaj właściwie wyjaśniają punkt widzenia standardu i sposób, w jaki można uzyskać początkową pojemność w przenośny sposób za pomocą std::vector::reserve;

Jednakże wyjaśnię, dlaczego nie ma sensu, aby żadna implementacja STL przydzielała pamięć podczas konstruowania std::vector<T>obiektu ;

1. std::vector<T> niekompletnych typów;

   Przed C ++ 17 konstruowanie a, std::vector<T>jeśli definicja Tjest nadal nieznana w momencie tworzenia instancji , było niezdefiniowanym zachowaniem . Jednak to ograniczenie zostało złagodzone w C ++ 17 .

   Aby efektywnie przydzielić pamięć dla obiektu, musisz znać jego rozmiar. Począwszy od C ++ 17 i nowszych, Twoi klienci mogą mieć przypadki, w których Twoja std::vector<T>klasa nie zna rozmiaru T. Czy ma sens, aby charakterystyka alokacji pamięci była zależna od kompletności typu?

2. Unwanted Memory allocations

   Jest wiele, wiele razy potrzeba modelowania wykresu w oprogramowaniu. (Drzewo to wykres); Najprawdopodobniej zamierzasz to wymodelować w następujący sposób:

   class Node {
       ....
       std::vector<Node> children; //or std::vector< *some pointer type* > children;
       ....
    };
   

   A teraz pomyśl przez chwilę i wyobraź sobie, że masz dużo węzłów końcowych. Byłbyś bardzo wkurzony, gdyby twoja implementacja STL przydzieliła dodatkową pamięć tylko w oczekiwaniu na obecność obiektów children.

   To tylko jeden przykład, możesz pomyśleć o więcej ...

Standard nie określa wartości początkowej pojemności, ale kontener STL automatycznie rośnie, aby pomieścić tyle danych, ile umieścisz, pod warunkiem, że nie przekroczysz maksymalnego rozmiaru (użyj funkcji składowej max_size, aby wiedzieć). W przypadku wektorów i łańcuchów wzrost jest obsługiwany przez realokację, gdy potrzeba więcej miejsca. Załóżmy, że chcesz utworzyć wektor o wartości 1-1000. Bez użycia rezerwy kod zazwyczaj powoduje od 2 do 18 realokacji podczas następującej pętli:

vector<int> v;
for ( int i = 1; i <= 1000; i++) v.push_back(i);

Modyfikacja kodu w celu użycia rezerwy może spowodować 0 alokacji podczas pętli:

vector<int> v;
v.reserve(1000);

for ( int i = 1; i <= 1000; i++) v.push_back(i);

Z grubsza rzecz biorąc, pojemności wektorów i łańcuchów rosną za każdym razem o współczynnik od 1,5 do 2.