MAPA V C++ STANDARD TEMPLATE LIBRARY (STL)

Mapy sú asociatívne kontajnery ktoré ukladajú prvky zmapovaným spôsobom. Každý prvok má hodnotu kľúča a priradenú hodnotu. Žiadne dve namapované hodnoty nemôžu mať rovnaké kľúčové hodnoty.

std::map je šablóna triedy pre kontajnery máp a je definovaná v hlavičkovom súbore.

Základné členské funkcie std::map

Niektoré základné funkcie spojené s std::map sú:

začať() – Vráti iterátor na prvý prvok na mape.
koniec() – Vráti iterátor teoretického prvku, ktorý nasleduje za posledným prvkom na mape.
veľkosť () – Vráti počet prvkov na mape.
max_size() – Vráti maximálny počet prvkov, ktoré mapa pojme.
prázdne () – Vráti, či je mapa prázdna.
vloženie páru (hodnota kľúča, hodnota mapy) – Pridá na mapu nový prvok.
vymazať (pozícia iterátora) – Odstráni prvok v pozícii, na ktorú ukazuje iterátor.
vymazať (konšt. g) – Odstráni z mapy pár kľúč – hodnota „g“.
jasný() – Odstráni všetky prvky z mapy.

Príklady std::map

Nasledujúce príklady ukazujú, ako vykonávať základné operácie na mapových kontajneroch.

Príklad 1: Funkcia begin() a end().

C++

// C++ program to illustrate the begin and end iterator> #include> #include> #include> using> namespace> std;> int> main()> {> > // Create a map of strings to integers> >

mapint>t.t.  // Vložte do mapy nejaké hodnoty mp['one'] = 1;  mp['dva'] = 2;  mp['tri'] = 3;  // Získanie iterátora ukazujúceho na prvý prvok v // mape mapint>::iterator it = mp.begin();  // Iterujte mapu a vytlačte prvky while (it != mp.end()) { cout < < 'Key: '    < < ', Value: '   ++it;  }  return 0; }>

Výkon

Key: one, Value: 1 Key: three, Value: 3 Key: two, Value: 2

Zložitosť vyššie uvedenej metódy:

Časová zložitosť: O(n) kde n je veľkosť mapy.

Pomocný priestor: O(n)

Príklad 2: funkcia size().

C++

// C++ program to illustrate the size() function> #include> #include> #include> using> namespace> std;> int> main()> {> > // Create a map of strings to integers> >

mapint>mapa;  // Vložte nejaké hodnoty do mapy mapy['one'] = 1;  mapa['dva'] = 2;  mapa['tri'] = 3;  // Vytlačí veľkosť mapy cout < < 'Size of map: '  < < map.size()  < < endl;  return 0; }>

Výkon

Size of map: 3

Zložitosť vyššie uvedenej metódy:

Časová zložitosť: O(1).

Príklad 3: Implementácia mapy

CPP

// CPP Program to demonstrate the implementation in Map> // divyansh mishra -->divyanshmishra101010> #include> #include> #include> using> namespace> std;> int> main()> {> > // empty map container> > map <> int> ,> int> >gquiz1;> > // insert elements in random order> > gquiz1.insert(pair <> int> ,> int> >(1, 40));> > gquiz1.insert(pair <> int> ,> int> >(2, 30));> > gquiz1.insert(pair <> int> ,> int> >(3, 60));> > gquiz1.insert(pair <> int> ,> int> >(4, 20));> > gquiz1.insert(pair <> int> ,> int> >(5, 50));> > gquiz1.insert(pair <> int> ,> int> >(6, 50));> > // another way of inserting a value in a map> > gquiz1[7] = 10;> > // printing map gquiz1> > map <> int> ,> int> >::iterator itr;> > cout < <>

'
The map gquiz1 is : 
'>

;> > cout < <>

'	KEY	ELEMENT
'>

;> > for> (itr = gquiz1.begin(); itr != gquiz1.end(); ++itr) {> > cout < <> ' '>

'	'    < < '
';  }  cout  < < endl;  // assigning the elements from gquiz1 to gquiz2  map gquiz2(gquiz1.begin(), gquiz1.end());  // vytlačí všetky prvky mapy gquiz2 cout < < '
The map gquiz2 after'   < < ' assign from gquiz1 is : 
';  cout  < < '	KEY	ELEMENT
';  for (itr = gquiz2.begin(); itr != gquiz2.end(); ++itr) {  cout  < < '	' '	'    < < '
';  }  cout  < < endl;  // remove all elements up to  // element with key=3 in gquiz2  cout  < < '
gquiz2 after removal of'  ' elements less than key=3 : 
';  cout  < < '	KEY	ELEMENT
';  gquiz2.erase(gquiz2.begin(), gquiz2.find(3));  for (itr = gquiz2.begin(); itr != gquiz2.end(); ++itr) {  cout  < < '	' '	'    < < '
';  }  // remove all elements with key = 4  int num;  num = gquiz2.erase(4);  cout  < < '
gquiz2.erase(4) : ';  cout  < < num  < < ' removed 
';  cout  < < '	KEY	ELEMENT
';  for (itr = gquiz2.begin(); itr != gquiz2.end(); ++itr) {  cout  < < '	' '	'    < < '
';  }  cout  < < endl;  // lower bound and upper bound for map gquiz1 key = 5  cout  < < 'gquiz1.lower_bound(5) : '   < < '	KEY = ';  cout '	';  cout  < < '	ELEMENT = '    < < endl;  cout  < < 'gquiz1.upper_bound(5) : '   < < '	KEY = ';  cout '	';  cout  < < '	ELEMENT = '    < < endl;  return 0; }>

Výkon

The map gquiz1 is : KEY ELEMENT 1 40 2 30 3 60 4 20 5 50 6 50 7 10 The map gquiz2 after assign from gquiz1 is : KEY ELEMENT 1 40 2 30 3 60 4 20 5 50 6 50 7 10 gquiz2 after remov...

Zložitosť vyššie uvedenej metódy:

Časová zložitosť: O(n log(n)), keďže n je veľkosť mapy
Pomocný priestor: O(n)

Príklad 4: Implementácia mapy celých čísel

C++

// C++ program to implement map container> #include> #include> #include> using> namespace> std;> int> main()> {> > // Create a map of strings to integers> >

mapint>mapa;  // Vložte nejaké hodnoty do mapy mapy['one'] = 1;  mapa['dva'] = 2;  mapa['tri'] = 3;  // Vytlačí hodnoty v mape cout < < 'Key: one, Value: '  < < map['one']  < < endl;  cout  < < 'Key: two, Value: '  < < map['two']  < < endl;  cout  < < 'Key: three, Value: '  < < map['three']  < < endl;  // Check if a key is in the map  if (map.count('four')>0) { cout < < 'Key 'four' is in the map'  < < endl;  }  else {  cout  < < 'Key 'four' is not in the map'  < < endl;  }  return 0; }>

Výkon

Key: one, Value: 1 Key: two, Value: 2 Key: three, Value: 3 Key 'four' is not in the map

Zoznam všetkých funkcií std::map

Nasledujúca tabuľka obsahuje všetky funkcie definované v triede std::map.

Funkcia	Definícia
mapa::vložiť()	Vložte prvky s konkrétnym kľúčom do kontajnera mapy –> O(log n)
mapa:: pocet()	Vráti počet zhôd s prvkom s párom kľúč – hodnota „g“ na mape. –> O(log n)
map equal_range()	Vráti iterátor párov. Dvojica sa týka hraníc rozsahu, ktorý zahŕňa všetky prvky v kontajneri, ktoré majú kľúč ekvivalentný k.
vymazanie mapy ()	Používa sa na vymazanie prvkov z kontajnera –> O(log n)
map Rend()	Vráti spätný iterátor ukazujúci na teoretický prvok tesne pred prvým párom kľúč – hodnota na mape (ktorý sa považuje za jeho opačný koniec).
mapa rbegin()	Vráti spätný iterátor, ktorý ukazuje na posledný prvok mapy.
nájsť mapu ()	Vráti iterátor prvku s párom kľúč – hodnota „g“ na mape, ak sa nájde, inak vráti iterátor na koniec.
map crbegin() a crend()	crbegin() vracia konštantný reverzný iterátor odkazujúci na posledný prvok v kontajneri mapy. crend() vracia konštantný reverzný iterátor ukazujúci na teoretický prvok pred prvým prvkom na mape.
map cbegin() a cend()	cbegin() vracia konštantný iterátor odkazujúci na prvý prvok v kontajneri mapy. cend() vracia konštantný iterátor ukazujúci na teoretický prvok, ktorý nasleduje za posledným prvkom v multimape.
mapa emplace()	Vloží kľúč a jeho prvok do kontajnera mapy.
mapa max_size()	Vráti maximálny počet prvkov, ktoré môže kontajner mapy obsahovať –> O(1)
horná_medza mapy ()	Vráti iterátor k prvému prvku, ktorý je ekvivalentný namapovanej hodnote s párom kľúč – hodnota „g“, alebo bude určite nasledovať po prvku s párom kľúč – hodnota „g“ na mape
operátor mapy=	Priradí obsah kontajnera inému kontajneru a nahradí jeho aktuálny obsah.
map lower_bound()	Vráti iterátor k prvému prvku, ktorý je ekvivalentný namapovanej hodnote s párom kľúč – hodnota „g“ alebo určite neprejde pred prvok s párom kľúč – hodnota „g“ na mape –> O(log n)
mapa emplace_hint()	Vloží kľúč a jeho prvok do kontajnera mapy s danou nápovedou.
map value_comp()	Vráti objekt, ktorý určuje, ako sú prvky na mape usporiadané (predvolene ‘ <‘).
mapa key_comp()	Vráti objekt, ktorý určuje, ako sú prvky na mape usporiadané (predvolene ‘ <‘).
mapa::veľkosť()	Vráti počet prvkov na mape.
mapa::prázdna()	Vráti, či je mapa prázdna
map::begin() a end()	begin() vracia iterátor k prvému prvku na mape. end() vracia iterátor teoretického prvku, ktorý nasleduje za posledným prvkom na mape
mapa::operátor[]	Tento operátor sa používa na odkazovanie na prvok prítomný na pozícii uvedenej vo vnútri operátora.
mapa::jasná()	Odstráni všetky prvky z mapy.
map::at() a mapa::swap()	Funkcia at() sa používa na vrátenie odkazu na prvok spojený s kľúčom k. Funkcia swap() sa používa na výmenu obsahu dvoch máp, ale mapy musia byť rovnakého typu, aj keď veľkosti sa môžu líšiť.