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

Последовательные контейнеры

Âåêòîðû (veCtOr), äâóñòîðîííèå î÷åðåäè (deque) è ñïèñêè (list) ïîääåðæèâaþò ðaçíûå íaáîðû îïåðaöèé, ñðåäè êîòîðûõ åñòü ñîâïaäaþùèå îïåðaöèè. Îíè ìîãóò áûòü ðåaëèçîâaíû ñ ðaçíîé ýôôåêòèâíîñòüþ:

Операция	Метод	vector	deque	list
Âñòaâêa â ía÷aëî	push_frOnt	–	+	+
Óäaëåíèå èç ía÷aëa	pOp_frOnt	–	+	+
Âñòaâêa â êîíåö	push_baCk	+	+	+

Операция	Метод	vector	deque	list
Óäaëåíèå èç êîíöa	pOp_baCk	+	+	+
Âñòaâêa â ïðîèçâîëüíîå ìåñòî	insert	(+)	(+)	+
Óäaëåíèå èç ïðîèçâîëüíîãî ìåñòa	erase	(+)	(+)	+
Ïðîèçâîëüíûé äîñòóï ê ýëåìåíòó	[ ], at	+	+	–

Çíaê + îçía÷aåò, ÷òî ñîîòâåòñòâóþùaя îïåðaöèя ðåaëèçóåòñя ça ïîñòîяííîå âðå- ìя, íå çaâèñяùåå îò êîëè÷åñòâa n ýëåìåíòîâ â êîíòåéíåðå. Çíaê (+) îçía÷aåò, ÷òî ñîîòâåòñòâóþùaя îïåðaöèя ðåaëèçóåòñя ça âðåìя, ïðîïîðöèîíaëüíîå n. Äëя ìa- ëûõ n âðåìя îïåð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ëåíèå èç êîíöa.
Äâóñòîðîííяя î÷åðåäü ýôôåêòèâíî ðåaëèçóåò ïðîèçâîëüíûé äîñòóï ê ýëåìåíòaì, äîáaâëåíèå â îáa êîíöa è óäaëåíèå èç îáîèõ êîíöîâ.
Cïèñîn ýôôåêòèâíî ðåaëèçóåò âñòaâêó è óäaëåíèå ýëåìåíòîâ â ïðîèçâîëüíîå ìå- ñòî, íî íå èìååò ïðîèçâîëüíîãî äîñòóïa ê ñâîèì ýëåìåíòaì.
Ïðèìåð ðaáîòû ñ âåêòîðîì.  ôaéëå íaõîäèòñя ïðîèçâîëüíîå êîëè÷åñòâî öåëûõ
÷èñåë. Ïðîãðaììa ñ÷èòûâaåò èõ â âåêòîð è âûâîäèò ía ýêðaí â òîì æå ïîðяäêå.
inClude inClude using namespaCe std; int main(){
ifstream in ("inpnum.txt"); veCtOr v;
int x;
while ( in >> x, !in.eOf()) v.push_baCk(x);
fOr (veCtOr::iteratOr i = v.begin(); i != v.end(); ++i) COut << *i << " ";
}
Ïîñêîëüêó ôaéë ñîäåðæèò öåëûå ÷èñëa, èñïîëüçóåòñя ñîîòâåòñòâóþùaя ñïåöèa- ëèçaöèя øaáëîía veCtOr — veCtOr. Äëя ñîçäaíèя âåêòîða v èñïîëüçóåòñя êîí- ñòðóêòîð ïî óìîë÷aíèþ. Îðãaíèçóåòñя öèêë äî êîíöa ôaéëa, â êîòîðîì èç íåãî ñ÷èòûâaåòñя î÷åðåäíîå öåëîå ÷èñëî. C ïîìîùüþ ìåòîäa push_baCk îíî çaíîñèòñя â âåêòîð, ðaçìåð êîòîðîãî óâåëè÷èâaåòñя aâòîìaòè÷åñêè¹.


¹ Ðaçìåð âåêòîða íå èçìåíяåòñя êaæäûé ðaç ïðè äîáaâëåíèè ýëåìåíòa, ýòî áûëî áû íåða- öèîíaëüíî. Îí óâåëè÷èâaåòñя ïî îïðåäåëåííîìó aëãîðèòìó, êîòîðûì ìîæíî óïðaâëяòü (ñì. ñ. 301).

Äëя ïðîõîäa ïî âñåìó âåêòîðó ââîäèòñя ïåðåìåííaя i êaê èòåðaòîð ñîîòâåòñò- âóþùåãî òèïa (íaïîìíþ, ÷òî îïåðaöèя :: îáîçía÷aåò äîñòóï ê îáëañòè âèäèìî- ñòè, òî åñòü çäåñü îáúяâëяåòñя ïåðåìåííaя i òèïa «èòåðaòîð äëя êîíêðåòíîé ñïå- öèaëèçaöèè øaáëîía»). C ïîìîùüþ ýòîãî èòåðaòîða îñóùåñòâëяåòñя äîñòóï êî âñåì ïî ïîðяäêó ýëåìåíòaì êîíòåéíåða, ía÷èíaя ñ ïåðâîãî. Ìåòîä begin() âîçâða- ùaåò óêaçaòåëü ía ïåðâûé ýëåìåíò, ìåòîä end() — ía ýëåìåíò, ñëåäóþùèé ça ïî- ñëåäíèì. Ðåaëèçaöèя ãaðaíòèðóåò, ÷òî ýòîò óêaçaòåëü îïðåäåëåí.

Cðaâíèâaòü òåêóùåå çía÷åíèå ñ ãðaíè÷íûì ñëåäóåò èìåííî ñ ïîìîùüþ îïåðaöèè
!=, òaê êaê îïåðaöèè < èëè <= ìîãóò áûòü äëя äaííîãî òèïa íå îïðåäåëåíû. Îïåða- öèя èíêðåìåíòa ( i++) ðåaëèçîâaía òaê, ÷òîáû ïîñëå íåå èòåðaòîð óêaçûâaë ía ñëåäóþùèé ýëåìåíò êîíòåéíåða â ïîðяäêå îáõîäa. Äîñòóï ê ýëåìåíòó âåêòîða âûïîëíяåòñя ñ ïîìîùüþ îïåðaöèè ðaçaäðåñaöèè, êaê äëя îáû÷íûõ óêaçaòåëåé.
 äaííîì ïðèìåðå âìåñòî âåêòîða ìîæíî áûëî èñïîëüçîâaòü ëþáîé ïîñëåäîâa- òåëüíûé êîíòåéíåð ïóòåì ïðîñòîé çaìåíû ñëîâa veCtOr ía deque èëè list. Ïðè ýòîì èçìåíèëîñü áû âíóòðåííåå ïðåäñòaâëåíèå äaííûõ è íaáîð äîñòóïíûõ îïå- ðaöèé, a â ïîâåäåíèè ïðîãðaììû íèêaêèõ èçìåíåíèé íå ïðîèçîøëî áû.
Îäíaêî åñëè âìåñòî öèêëa fOr âñòaâèòü ôðaãìåíò
fOr (inti= 0; iâ êîòîðîì èñïîëüçîâaía îïåðaöèя äîñòóïa ïî èíäåêñó [ ], ïðîãðaììa íå áóäåò ða- áîòaòü äëя êîíòåéíåða òèïa list, ïîñêîëüêó â íåì ýòa îïåðaöèя íå îïðåäåëåía.