Question 1

Ի՞նչ է std::vector-ը?

Accepted Answer

vector-ը դինամիկ զանգված է, որը ավտոմատ աճում է։ push_back-ը ամորտիզացված O(1) է, insert միջնամասում O(n)։ at(i) — O(1) random access։

Question 2

Ո՞րն է տարբերությունը list-ի և vector-ի միջև?

Accepted Answer

std::list-ը double-linked list է՝ insert/erase ցանկացած կետում O(1), բայց random access չկա (միայն sequential)։ std::vector-ը continuous memory, O(1) at(i), բայց insert միջնամասում O(n)։

Question 3

Ե՞րբ օգտագործել std::deque-ը?

Accepted Answer

deque-ն օգտագործվում է, երբ push/pop անհրաժեշտ է երկու ծայրից էլ O(1)-ով։ Իրականացվում է որպես բլոկների շարք՝ random access O(1)-ով։

Question 4

Ի՞նչ է amortized O(1)?

Accepted Answer

Միջինում O(1), թեև առանձին դեպքերում կարող է լինել O(n) (օր. vector resize-ի ժամանակ)։ Մեծ քանակությամբ operations-ի համար միջին արժեքը մնում է O(1)։

STL Sequence Containers