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

Download 2 Mb.

bet	182/232
Sana	29.03.2022
Hajmi	2 Mb.
	#516205
Turi	Задача

1 ... 178 179 180 181 182 183 184 185 ... 232

Bog'liq
Т. А. Павловская C C . Программирование на языке высокого уровня

Словари (map)

Â ñëîâaðå (map), â îòëè÷èå îò ñëîâaðя ñ äóáëèêaòaìè (multimap), âñå êëþ÷è äîëæ- íû áûòü óíèêaëüíû. Ýëåìåíòû â ñëîâaðå õðaíяòñя â îòñîðòèðîâaííîì âèäå, ïî- ýòîìó äëя êëþ÷åé äîëæíî áûòü îïðåäåëåíî îòíîøåíèå «ìåíüøå». Øaáëîí ñëî- âaðя ñîäåðæèò òðè ïaðaìåòða: òèï êëþ÷a, òèï ýëåìåíòa è òèï ôóíêöèîíaëüíîãî îáúåêòa, îïðåäåëяþùåãî îòíîøåíèå «ìåíüøå» (ôóíêöèîíaëüíûå îáúåêòû ðañ- ñìaòðèâaëèñü ía ñ. 195):
template > Class map{
publiC:
typedef pair value_type; expliCit map(COnst COmpare& COmp = COmpare()); template

map(InputIter first, InputIter last, COnst COmpare& COmp = COmpare());

map(COnst map & x);
…
};
Êaê âèäíî èç ïðèâåäåííîãî îïèñaíèя (îíî äaíî ñ ñîêðaùåíèяìè), òèï ýëåìåíòîâ ñëîâaðя value_type îïðåäåëяåòñя êaê ïaða ýëåìåíòîâ òèïa Key è T.
Ïåðâûé nîíñòðónòîð ñîçä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ðя îïðåäåëåíû äåñòðónòîð, îïåðaöèя ïðè- ñâaèâaíèя è îïåðaöèè îòíîøåíèя. Èòåðaòîðû ñëîâaðя ïåðå÷èñëåíû â òaáë. 12.
Äëя äîñòóïa ê ýëåìåíòaì ïî êëþ÷ó îïðåäåëåía îïåðaöèя [ ]: T& OperatOr[](COnst Key & x);
C ïîìîùüþ ýòîé îïåðaöèè ìîæíî íå òîëüêî ïîëó÷aòü çía÷åíèя ýëåìåíòîâ, íî è äîáaâëяòü â ñëîâaðü íîâûå. Íå áóäó îòñòóïaòü îò òðaäèöèé è â êa÷åñòâå ïðèìåða ñëîâaðя ïðèâåäó òåëåôîííóþ êíèãó, êëþ÷îì â êîòîðîé ñëóæèò ôaìèëèя, a ýëå- ìåíòîì — íîìåð òåëåôîía:
inClude inClude inClude inClude
using namespaCe std;
typedef map > map_sl; // 1 int main(){
map_sl m1;
ifstream in("phOnebOOk"); string str;
lOng num;
while (in >> num, !in.eOf()){ // ×òåíèå íîìåða in.get(); // Ïðîïóñê ïðîáåëa
getline(in, str); // ×òåíèå ôaìèëèè
m1[str] = num; // Çaíåñåíèå â ñëîâaðü COut << str << " " << num << endl;
}
m1["Petya P."] = 2134622; // Äîïîëíåíèå ñëîâaðя map_sl :: iteratOr i;
COut << "m1:" << endl; // Âûâîä ñëîâaðя fOr (i = m1.begin(); i != m1.end(); i++)
COut << (*i).first << " " << (*i).seCOnd << endl;
i = m1.begin(); i++; // Âûâîä âòîðîãî ýëåìåíòa COut << "Âòîðîé ýëåìåíò: ";
COut << (*i).first << " " << (*i).seCOnd << endl;

COut << "Vasia: " << m1["Vasia"] << endl; // Âûâîä ýëåìåíòa ïî êëþ÷ó return 0;

}
Äëя óëó÷øåíèя ÷èòaåìîñòè ïðîãðaììû ââåäåíî áîëåå êîðîòêîå îáîçía÷åíèå òèïa ñëîâaðя (îïåðaòîð, ïîìå÷åííûé // 1). Câåäåíèя î êaæäîì ÷åëîâåêå ðañïîëî- æåíû â ôaéëå phOnebOOk ía îäíîé ñòðîêå: ñía÷aëa èäåò íîìåð òåëåôîía, çaòåì ÷å- ðåç ïðîáåë ôaìèëèя:
1001002 Petya K.
3563398 IvanOva N.M.
1180316 VOvOChka
2334476 Vasia
Äëя èòåðaòîðîâ ñëîâaðя äîïóñòèìû îïåðaöèè èíêðåìåíòa è äåêðåìåíòa, íî íå îïåðaöèè + è –. Íèæå ïðèâåäåí ðåçóëüòaò ðaáîòû ïðîãðaììû (îáðaòèòå âíèìa- íèå, ÷òî ñëîâaðü âûâîäèòñя â óïîðяäî÷åííîì âèäå):
Petya K. 1001002
IvanOva N.M. 3563398
VOvOChka 1180316
Vasia 2334476 m1:
IvanOva N.M. 3563398
Petya K. 1001002
Petya P. 2134622
Vasia 2334476
VOvOChka 1180316
Âòîðîé ýëåìåíò: Petya K. 1001002 Vasia: 2334476
Äëя ïîèñna ýëåìåíòîâ â ñëîâaðå îïðåäåëåíû ñëåäóþùèå ôóíêöèè:
iteratOr find(COnst key_type& x); COnst_iteratOr find(COnst key_type& x) COnst; iteratOr lOwer_bOund(COnst key_type& x); COnst_iteratOr lOwer_bOund(COnst key_type& x) COnst; iteratOr upper_bOund(COnst key_type& x); COnst_iteratOr upper_bOund(COnst key_type &x) COnst; size_type COunt(COnst key_type& x) COnst;
Ôóíêöèя find âîçâðaùaåò èòåðaòîð ía íaéäåííûé ýëåìåíò â ñëó÷aå óñïåøíîãî ïîèñêa èëè end() â ïðîòèâíîì ñëó÷aå.
Ôóíêöèя upper_bOund âîçâðaùaåò èòåðaòîð ía ïåðâûé ýëåìåíò, êëþ÷ êîòîðîãî íå ìåíüøå x, èëè end(), åñëè òaêîãî íåò (åñëè ýëåìåíò ñ êëþ÷îì x åñòü â ñëîâaðå, áó- äåò âîçâðaùåí èòåðaòîð ía íåãî).
Ôóíêöèя lOwer_bOund âîçâðaùaåò èòåðaòîð ía ïåðâûé ýëåìåíò, êëþ÷ êîòîðîãî áîëüøå x, èëè end(), åñëè òaêîãî íåò.
Äîáaâèì â ïðèâåäåííûé âûøå ïðèìåð îïåðaòîðû
getline(Cin, str);
if (m1.find(str) != m1.end())

COut << m1 [str]; else{

COut << (*m1.upper_bOund(str)).first << " " ; COut << (*m1.lOwer_bOund(str)).first << " " ;
}
Åñëè ââåñòè ñ êëaâèaòóðû ôaìèëèþ, êîòîðaя åñòü â ñëîâaðå, áóäåò âûâåäåí ñîîò- âåòñòâóþùèé íîìåð òåëåôîía, a èía÷å — äâa ðaça ïîäðяä ïåðâaя èç ôaìèëèé, êî- òîðaя ïî aëôaâèòó ñëåäóåò ça ââåäåííîé, íaïðèìåð:
Petya M. // Ïîä÷åðêèâaíèåì îáîçía÷åí ââîä ïîëüçîâaòåëя Petya P. Petya P.
Ôóíêöèя COunt âîçâðaùaåò êîëè÷åñòâî ýëåìåíòîâ, êëþ÷ êîòîðûõ ðaâåí x (òaêèõ ýëåìåíòîâ ìîæåò áûòü 0 èëè 1).
Äëя âñòaânè è óäaëåíèя ýëåìåíòîâ îïðåäåëåíû ôóíêöèè:
pair insert(COnst value_type& x); iteratOr insert(iteratOr pOsitiOn, COnst value_type& x); template
vOid insert(InputIter first, InputIter last); vOid erase(iteratOr pOsitiOn);
size_type erase(COnst key_type& x);
vOid erase(iteratOr first, iteratOr last); vOid Clear();
Ïåðâaя ôîðìa ôóíêöèè èñïîëüçóåòñя äëя âñòaâêè â ñëîâaðü ïaðû «êëþ÷—çía-
÷åíèå». Ôóíêöèя âîçâðaùaåò ïaðó, ñîñòîяùóþ èç èòåðaòîða, óêaçûâaþùåãî ía âñòaâëåííîå çía÷åíèå, è áóëåâîãî ïðèçíaêa ðåçóëüòaòa îïåðaöèè: true, åñëè çaïè- ñè ñ òaêèì êëþ÷îì â ñëîâaðå íå áûëî (òîëüêî â ýòîì ñëó÷aå ïðîèñõîäèò äîáaâëå- íèå), è false â ïðîòèâíîì ñëó÷aå (èòåðaòîð óêaçûâaåò ía ñóùåñòâóþùóþ çaïèñü). Âðåìя ðaáîòû ôóíêöèè ïðîïîðöèîíaëüíî ëîãaðèôìó êîëè÷åñòâa ýëåìåíòîâ â ñëî- âaðå.
Òaêèì îáðaçîì, ñêîððåêòèðîâaòü ñóùåñòâóþùóþ çaïèñü, èñïîëüçóя ôóíêöèþ âñòaâêè, íåëüçя. Ýòî äåëaåòñя ñ ïîìîùüþ îïåðaöèè äîñòóïa ïî èíäåêñó.
Íèæå ïðèâåäåíî íåñêîëüêî ïðèìåðîâ âñòaâêè â ñëîâaðü, òèï êîòîðîãî îïèñaí â ïðåäûäóùåì ëèñòèíãå:
map_sl m2; // Cîçäaíèå ïóñòîãî ñëîâaðя
m2.insert(map_sl::value_type("Lena", 3157725)); str = "Anna";
num = 5536590;
m2.insert(make_pair(str, num)); num = 5530000;
// Ïîïûòêa âñòaâêè ñóùåñòâóþùåé çaïèñè: m2.insert(make_pair(str, num));
i = m1.begin();
m2.insert(*i); // Âñòaâêa â m2 ïåðâîãî ýëåìåíòa ñëîâaðя m1 m2["Lena"] = 2222222; // Êîððåêòèðîâêa ýëåìåíòa fOr (i = m2.begin(); i != m2.end(); i++) // Âûâîä ñëîâaðя
COut << (*i).first << " " << (*i).seCOnd << endl;

Ðåçóëüòaò ðaáîòû ïðîãðaììû:

Anna 5536590
IvanOva N.M. 3563398
Lena 2222222
Âòîðaя ôîðìa ôóíêöèè insert ïðèìåíяåòñя äëя óñêîðåíèя ïðîöåñña âñòaâêè. C ýòîé öåëüþ åé ïåðåä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âêè яâëяåòñя êîíñòaíòîé):
inClude inClude inClude
using namespaCe std;
typedef map > map_sl; typedef pair pair_sl;
int main(){
pair_sl p[3] = { pair_sl("Anna", 123123),
pair_sl("Maria", 234234),
pair_sl("Teresa", 345345)};
map_sl m1;
map_sl :: iteratOr i = m1.begin(); fOr (intk= 0; k<3; k++)
i = m1.insert(i, p[k]); // siC!
fOr (i = m1.begin(); i != m1.end(); i++)
COut << (*i).first << " " << (*i).seCOnd << endl; return 0;
}
Òðåòüя ôîðìa ôóíêöèè insert èñïîëüçóåòñя äëя âñòaâêè ãðóïïû ýëåìåíòîâ, îïðå- äåëяåìîé äèaïaçîíîì èòåðaòîðîâ. Ôóíêöèè óäaëåíèя ýëåìåíòîâ è î÷èñòêè ñëî- âaðя aíaëîãè÷íû îäíîèìåííûì ôóíêöèяì äðóãèõ êîíòåéíåðîâ: ïåðâaя ôîðìa ôóíêöèè erase óä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ðåé ïðèìåíяåòñя ôóíêöèя swap: template
vOid swap(map& x, map& y);

¹ Åñëè óêaçaííaя ïîçèöèя íaõîäèòñя ïîñëå ìåñòa, â êîòîðîå òðåáóåòñя âñòaâèòü ýëåìåíò, âñòaâêa áóäåò âñå ðaâíî âûïîëíåía âåðíî.

Ôóíêöèя equal_range âîçâðaùaåò ïaðó èòåðaòîðîâ (lOwer_bOund(x), upper_bOund(x)) äëя ïåðåäaííîãî åé çía÷åíèя x:

pair equal_range(COnst key_type& x); pair
equal_range(COnst key_type& x) COnst;
Ïîñëå âûçîâa ôóíêöèè îáa èòåðaòîða áóäóò óêaçûâaòü ía ýëåìåíò ñ çaäaííûì êëþ÷îì, åñëè îí ïðèñóòñòâóåò â ñëîâaðå, èëè ía ïåðâûé ýëåìåíò, áîëüøèé íåãî, â ïðîòèâíîì ñëó÷aå.

Download 2 Mb.

Do'stlaringiz bilan baham:

1 ... 178 179 180 181 182 183 184 185 ... 232