Задача этой книги дать краткое и четкое изложение языка С++ в соответствии со стандар том iso/iec 14882. Она предназначена для студентов, изучающих язык «с нуля»

ГЛАВА 12

Контейнерные классы
Êîíòåéíåðíûå êëaññû — ýòî êëaññû, ïðåäíaçía÷åííûå äëя õðaíåíèя äaííûõ, îð- ãaíèçîâaííûõ îïðåäåëåííûì îáðaçîì. Ïðèìåðaìè êîíòåéíåðîâ ìîãóò ñëóæèòü ìaññèâû, ëèíåéíûå ñïèñêè èëè ñòåêè. Äëя êaæäîãî òèïa êîíòåéíåða îïðåäåëåíû ìåòîäû äëя ðaáîòû ñ åãî ýëåìåíòaìè, íå çaâèñяùèå îò êîíêðåòíîãî òèïa äaííûõ, êîòîðûå õðaíяòñя â êîíòåéíåðå, ïîýòîìó îäèí è òîò æå âèä êîíòåéíåða ìîæíî èñïîëüçîâaòü äëя õðaíåíèя äaííûõ ðaçëè÷íûõ òèïîâ. Ýòa âîçìîæíîñòü ðåaëèçî- âaía ñ ïîìîùüþ øaáëîíîâ êëaññîâ, ïîýòîìó ÷añòü áèáëèîòåêè C++, â êîòîðóþ âõîäяò êîíòåéíåðíûå êëaññû, a òaêæå aëãîðèòìû è èòåðaòîðû, î êîòîðûõ áóäåò ðaññêaçaíî â ñëåäóþùèõ ðaçäåëaõ, íaçûâaþò ñòaíäaðòíîñ áèáëèîòånîñ øaáëîíîâ (STL — Standard Template Library).
Èñïîëüçîâaíèå êîíòåéíåðîâ ïîçâîëяåò çía÷èòåëüíî ïîâûñèòü íaäåæíîñòü ïðî- ãðaìì, èõ ïåðåíîñèìîñòü è óíèâåðñaëüíîñòü, a òaêæå óìåíüøèòü ñðîêè èõ ðaçða- áîòêè.
Åñòåñòâåííî, ýòè ïðåèìóùåñòâa íå äaþòñя äaðîì: óíèâåðñaëüíîñòü è áåçîïañ- íîñòü èñïîëüçîâaíèя êîíòåéíåðíûõ êëaññîâ íå ìîãóò íå îòðaæaòüñя ía áûñòðî- äåéñòâèè ïðîãðaììû. Cíèæåíèå áûñòðîäåéñòâèя â çaâèñèìîñòè îò ðåaëèçaöèè êîìïèëяòîða ìîæåò áûòü âåñüìa çía÷èòåëüíûì. Êðîìå òîãî, äëя ýôôåêòèâíîãî èñïîëüçîâaíèя êîíòåéíåðîâ òðåáóåòñя çaòðaòèòü óñèëèя ía âäóì÷èâîå îñâîåíèå áèáëèîòåêè.
STL ñîäåðæèò êîíòåéíåðû, ðåaëèçóþùèå îñíîâíûå ñòðóêòóðû äaííûõ, èñïîëü- çóåìûå ïðè íaïèñaíèè ïðîãðaìì — âånòîðû, äâóñòîðîííèå î÷åðåäè, ñïèñnè è èõ ðaçíîâèäíîñòè, ñëîâaðè è ìíîxåñòâa. Êîíòåéíåðû ìîæíî ðaçäåëèòü ía äâa òèïa: ïîñëåäîâaòåëüíûå è aññîöèaòèâíûå.
Ïîñëåäîâaòåëüíûå nîíòåñíåðû îáåñïå÷èâaþò õðaíåíèå êîíå÷íîãî êîëè÷åñòâa îä- íîòèïíûõ âåëè÷èí â âèäå íåïðåðûâíîé ïîñëåäîâaòåëüíîñòè. Ê íèì îòíîñяòñя âåêòîðû (veCtOr), äâóñòîðîííèå î÷åðåäè (deque) è ñïèñêè (list), a òaêæå òaê ía- çûâaåìûå aäaïòåðû, òî åñòü âaðèaíòû, êîíòåéíåðîâ — ñòåêè (staCk), î÷åðåäè (queue) è î÷åðåäè ñ ïðèîðèòåòaìè (priOrity_queue).
Êaæäûé âèä êîíòåéíåða îáåñïå÷èâaåò ñâîé íaáîð äåéñòâèé íaä äaííûìè. Âûáîð âèäa êîíòåéíåða çaâèñèò îò òîãî, ÷òî òðåáóåòñя äåëaòü ñ äaííûìè â ïðîãðaììå.

Íaïðèìåð, ïðè íåîáõîäèìîñòè ÷añòî âñòaâëяòü è óäaëяòü ýëåìåíòû èç ñåðåäèíû ïîñëåäîâaòåëüíîñòè ñëåäóåò èñïîëüçîâaòü ñïèñîê, a åñëè âêëþ÷åíèå ýëåìåíòîâ âûïîëíяåòñя ãëaâíûì îáðaçîì â êîíåö èëè ía÷aëî — äâóñòîðîííþþ î÷åðåäü.

Àññîöèaòèâíûå nîíòåñíåðû îáåñïå÷èâaþò áûñòðûé äîñòóï ê äaííûì ïî êëþ÷ó. Ýòè êîíòåéíåðû ïîñòðîåíû ía îñíîâå ñáaëaíñèðîâaííûõ äåðåâüåâ. Cóùåñòâóåò ïяòü òèïîâ aññîöèaòèâíûõ êîíòåéíåðîâ: ñëîâaðè (map), ñëîâaðè ñ äóáëèêaòaìè (multimap), ìíîæåñòâa (set), ìíîæåñòâa ñ äóáëèêaòaìè (multiset) è áèòîâûå ìíî- æåñòâa (bitset).
Ïðîãðaììèñò ìîæåò ñîçäaâaòü ñîáñòâåííûå êîíòåéíåðíûå êëaññû ía îñíîâå èìåþùèõñя â ñòaíäaðòíîé áèáëèîòåêå.
Öåíòðaëüíûì ïîíяòèåì STL яâëяåòñя øaáëîí, ïîýòîìó ïåðåä òåì, êaê ïðèñòó- ïèòü ê èçó÷åíèþ ìaòåðèaëa ýòîé ãëaâû, ðåêîìåíäóåòñя óáåäèòüñя, ÷òî ýòî ïî- íяòèå íå ïðåäñòaâëяåò äëя ÷èòaòåëя çaãaäêó (ñì. «Øaáëîíû ôóíêöèé», ñ. 85, è «Øaáëîíû êëaññîâ», ñ. 211). Òaêæå íåîáõîäèìî çíaòü, ÷òî òaêîå ïðîñòðaíñòâa èìåí (ñ. 99), ïåðåãðóçêa ôóíêöèé (ñ. 83) è ïåðåãðóçêa îïåðaöèé (ñ. 189).
Êîíòåéíåðíûå êëaññû îáåñïå÷èâaþò ñòaíäaðòèçîâaííûé èíòåðôåéñ ïðè èõ èñ- ïîëüçîâaíèè. Cìûñë îäíîèìåííûõ îïåðaöèé äëя ðaçëè÷íûõ êîíòåéíåðîâ îäèía- êîâ, îñíîâíûå îïåðaöèè ïðèìåíèìû êî âñåì òèïaì êîíòåéíåðîâ. Còaíäaðò îïðå- äåëяåò òîëüêî èíòåðôåéñ êîíòåéíåðîâ, ïîýòîìó ðaçíûå ðåaëèçaöèè ìîãóò ñèëüíî îòëè÷aòüñя ïî ýôôåêòèâíîñòè.
Ïðaêòè÷åñêè â ëþáîì êîíòåéíåðíîì êëaññå îïðåäåëåíû ïîëя ïåðå÷èñëåííûõ íèæå òèïîâ: