Czy std :: vector :: wstawić rezerwę z definicji?

Question

Podczas wywoływania funkcji składowej insert na std::vector, czy będzie ona reserve przed "przesunięciem" nowych elementów? Mam na myśli czy standardowa gwarancja jest taka, czy nie?

Innymi słowy, należy zrobić to tak:

std::vector<int> a{1,2,3,4,5}; 
std::vector<int> b{6,7,8,9,10}; 
a.insert(a.end(),b.begin(),b.end()); 

lub tak:

std::vector<int> a{1,2,3,4,5}; 
std::vector<int> b{6,7,8,9,10}; 
a.reserve(a.size()+b.size()); 
a.insert(a.end(),b.begin(),b.end()); 

lub innym lepszym rozwiązaniem?

Answer 1

odniesieniu do złożoności funkcji [link]:

liniowy od liczby elementów wstawianych (budowa kopii/posuwu) plus liczba elementów po położeniu (w ruchu).

Dodatkowo, jeśli InputIterator we wkładce zakres (3) nie jest przynajmniej z kategorii naprzód iteratora (czyli po prostu iterator wejściowy) nowa pojemność nie może być ustalona wcześniej i wkładanie ponosi w dodatkową złożoność logarytmiczną w rozmiarach (ponowne przydziały).

Stąd jest dwa przypadki:

• Nowa pojemność może być ustalone, dlatego nie trzeba będzie zadzwonić zarezerwować
• Nowa pojemność nie może być określony, a więc wezwanie do reserve powinny być przydatne.

Answer 2

Z documentation, wydaje się, że:

Powoduje realokacji jeśli nowy rozmiar() jest większy niż stary pojemności().

Należy pamiętać, że w takim przypadku wszystkie iteratory i odwołania są unieważniane.

Oczywiste jest zatem, że realokacjach są odpowiedzialne za insert i, jeśli spojrzeć na te operacje jednej chwili, to tak konsekwentna rezerwa-size-plus-jeden operacja wykonana jest na każdym kroku.
Można argumentować, że wywołanie reserve u góry wstawki przyspieszyłoby wszystko w tych przypadkach, gdy ma miejsce więcej niż jedna realokacja ... Cóż, prawda, może to pomóc, ale w większości zależy to od rzeczywistego problemu.

Answer 3

Czy std::vector::insert jest zarezerwowany z definicji?

Tak, nie; zależy od aktualnej pojemności.

z projektu N4567, §23.3.6.5/1 ([]): vector.modifiers

Powoduje realokacji jeśli nowa wielkość jest większa niż stary pojemności.

Jeżeli przydzielona pamięć w vector jest wystarczająco duży, aby zawierać nowe elementy, nie są potrzebne żadne dodatkowe przydziały dla vector. Więc nie, to nie zarezerwuje pamięci.

Jeśli pojemność vector nie jest wystarczająco duża, przydzielany jest nowy blok, bieżąca zawartość jest przenoszona/kopiowana i wstawiane są nowe elementy. Dokładny algorytm alokacji nie jest określony, ale zazwyczaj byłby używany w metodzie reserve().

... czy inne lepsze podejście?

Jeśli jesteś zaniepokojony zbyt wielu przydziałów przy jednoczesnym wstawianie elementów do vector, a następnie wywołanie metody reserve z wielkością liczby oczekiwanych elementów dodawanych ma zminimalizować przydziały.

Czy vector dzwoni reserve przed/dowolnymi wstawkami? To znaczy. czy przydziela wystarczającą przepustowość w ramach jednej alokacji?

Brak gwarancji. Skąd miałby wiedzieć odległość między wejściowymi iteratorami? Biorąc pod uwagę, że metoda insert może zająć InputIterator (tj. Iterator z pojedynczym przejściem), nie ma powodu do obliczenia oczekiwanego rozmiaru. Czy metoda może obliczyć rozmiar, jeśli iteratory zawierają coś innego (np. Wskaźniki lub RandomAccessIterator)? Tak, może. Czy byłby to? Zależy od implementacji i dokonanych optymalizacji.