Wat is de asymptotische complexiteit van bewerkingen met de std::vector-klasse in C++?

Asymptotische complexiteit voor de hoofdoperaties met std::vector:

Operatie	Gemiddelde tijd	Slechtste tijd
Toegang tot element ([], at)	O(1)	O(1)
Toevoegen/verwijderen aan het einde	O(1)	O(N)
Toevoegen/verwijderen in het begin/midden	O(N)	O(N)
Grootte ophalen (size)	O(1)	O(1)
Grootte aanpassen (resize)	O(N)	O(N)

Uitleg:

• O(1) (constante tijd): De operatie wordt in een vast aantal stappen uitgevoerd, ongeacht de grootte van de vector.
• O(N) (lineaire tijd): De uitvoeringstijd van de operatie is recht evenredig met het aantal elementen in de vector (N).

Daarnaast:

• Toevoegen/verwijderen aan het einde kan in het slechtste geval O(N) vereisen vanwege geheugenherallocatie, wanneer de huidige capaciteit niet voldoende is. Bij herallocatie wordt een nieuwe, grotere buffer gemaakt en worden alle bestaande elementen gekopieerd. Dankzij de geheugenstrategie (meestal, verdubbeling van capaciteit) is de gemiddelde tijd voor toevoegen/verwijderen aan het einde O(1).
• Toevoegen/verwijderen in het midden vereist het verschuiven van alle volgende elementen, wat O(N) tijd kost.

Voorbeeld van herallocatie bij push_back:

// Stel dat de vector een capaciteit van 4 heeft en vol is
std::vector<int> vec = {1, 2, 3, 4}; // Capaciteit = 4, Grootte = 4

// Het toevoegen van een nieuw element vereist herallocatie
vec.push_back(5); // Mogelijk wordt de capaciteit 8, en alle elementen worden gekopieerd

// De `push_back` operatie in dit geval kostte O(N) tijd,
// waarbij N het aantal elementen vóór de herallocatie is.