Thynex Academy
Ծրագրավորման ուսումնական գործիքներ
Գործիքների ցանկ

STL Sequence Containers

vector, list, deque — տեսողականորեն դիտեք ինչպես են աշխատում STL-ի հիմնական հաջորդական կոնտեյներները։

vector — դինամիկ զանգված
Հիշողության մեջ անընդհատ (contiguous) բլոկ։ Ավտոմատ ընդլայնվում է capacity-ի կրկնապատկումով։
  • ✓ Արագ O(1) մուտք ըստ ինդեքսի
  • ✓ Արագ push_back (ամորտիզացված O(1))
  • ✗ Insert/erase միջանկյալ դիրքում՝ O(n)
list — երկկապ ցուցակ
Ցանկացած երկու հարևան հանգույցներ կապված են prev և next ցուցիչներով։ Հիշողությունը ֆրագմենտացված է։
  • ✓ O(1) insert/erase տրված հանգույցի մոտ
  • ✓ Հաստատ iterator-ներ (չեն կոտրվում)
  • ✗ Ինդեքսով մուտք չկա — միայն հաջորդականորեն
deque — երկկողմ հերթ
Բլոկների զանգված (chunks)։ push_front/push_back երկուսն էլ O(1)։ Հիշողությունը հատված-հատված անընդհատ է։
  • ✓ O(1) push/pop երկու ծայրից
  • ✓ O(1) մուտք ըստ ինդեքսի (արագ, թեև ոչ այնքան՝ որքան vector)
  • ✗ Insert/erase միջանկյալ դիրքում՝ O(n)
Operation
Best
Avg
Worst
push_back
O(1)
O(1)*
O(n)
pop_back
O(1)
O(1)
O(1)
insert_at
O(1)
O(n)
O(n)
erase_at
O(1)
O(n)
O(n)
find
O(1)
O(n)
O(n)
at
O(1)
O(1)
O(1)