De ce contează?
Imagineaza-ti un raft de biblioteca care se lungeste singur. Pui o carte la capat — incape. Mai pui una — raftul se intinde cat trebuie. Nu trebuie sa stii dinainte cate carti vei avea: cumperi un raft de un metru si, cand se umple, el devine pe loc mai lung. Cam asta e std::vector fata de tabloul clasic int v[100], unde lungimea o fixezi din start si nu o mai poti schimba.
Ce este
Un std::vector este un tablou dinamic: o secventa de elemente de acelasi tip, asezate unul dupa altul in memorie, a carei lungime se poate schimba in timpul rularii. Spre deosebire de int v[100], nu fixezi dimensiunea la compilare — adaugi elemente cat ai nevoie, iar vectorul isi gestioneaza singur memoria.
Faci push_back ca sa adaugi la capat, citesti orice element cu v[i] ca la un tablou obisnuit, si afli cate elemente ai cu v.size(). Pentru ca e cea mai simpla structura secventiala care „creste cu tine”, in concurs e alegerea implicita ori de cate ori nu stii dinainte cate valori vor veni.
Cum poate fi push_back rapid, daca uneori trebuie sa mute tot vectorul intr-un loc nou mai mare? Trucul: vectorul nu se mareste cu un element odata, ci isi dubleaza capacitatea cand se umple. Dublarile devin tot mai rare (la 1, 2, 4, 8, 16... elemente), asa ca, mediat pe toate adaugarile, costul pe operatie ramane constant. Asta numim O(1) amortizat.