MAPA A LA BIBLIOTECA DE PLANTILLES ESTÀNDARD (STL) DE C++

Els mapes ho són contenidors associatius que emmagatzemen elements de manera mapeada. Cada element té un valor clau i un valor assignat. No hi ha dos valors assignats que tinguin els mateixos valors clau.

std::map és la plantilla de classe per als contenidors de mapes i es defineix dins del fitxer de capçalera.

Funcions bàsiques dels membres std::map

Algunes funcions bàsiques associades a std::map són:

començar () – Retorna un iterador al primer element del mapa.
final() – Retorna un iterador a l'element teòric que segueix l'últim element del mapa.
mida () – Retorna el nombre d'elements del mapa.
mida_màx () – Retorna el nombre màxim d'elements que pot contenir el mapa.
buit() – Retorna si el mapa està buit.
insertar parell (valor clau, valor de mapa) – Afegeix un nou element al mapa.
esborrar (posició de l'iterador) – Elimina l'element a la posició assenyalada per l'iterador.
esborrar (const g) – Elimina el valor-clau 'g' del mapa.
clar () – Elimina tots els elements del mapa.

Exemples de std::map

Els exemples següents mostren com realitzar operacions bàsiques als contenidors de mapes.

Exemple 1: funció begin() i 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>mp;  // Insereix alguns valors al mapa mp['one'] = 1;  mp['dos'] = 2;  mp['tres'] = 3;  // Obteniu un iterador que apunta al primer element del // mapint>::iterator it = mp.begin();  // Itera pel mapa i imprimeix els elements mentre (it != mp.end()) { cout < < 'Key: '    < < ', Value: '   ++it;  }  return 0; }>

Sortida

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

Complexitat del mètode anterior:

Complexitat temporal: O(n) on n és la mida del mapa.

Espai auxiliar: O(n)

Exemple 2: funció 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;  // Insereix alguns valors al mapa del mapa['un'] = 1;  mapa['dos'] = 2;  mapa['tres'] = 3;  // Imprimeix la mida del mapa < < 'Size of map: '  < < map.size()  < < endl;  return 0; }>

Sortida

Size of map: 3

Complexitat del mètode anterior:

Complexitat temporal: O(1).

Exemple 3: Implementació del mapa

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> >::iterador 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());  // imprimeix tots els elements del mapa 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; }>

Sortida

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...

Complexitat del mètode anterior:

Complexitat temporal: O(n log(n)) ja que n és la mida del mapa
Espai auxiliar: O(n)

Exemple 4: Implementació del mapa de nombres enters

C++

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

mapint>mapa;  // Insereix alguns valors al mapa del mapa['un'] = 1;  mapa['dos'] = 2;  mapa['tres'] = 3;  // Imprimeix els valors al mapa 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; }>

Sortida

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

Llista de totes les funcions de std::map

La taula següent conté totes les funcions definides dins de la classe std::map.

Funció	Definició
map::insert()	Insereix elements amb una clau particular al contenidor del mapa -> O(log n)
mapa:: comptar()	Retorna el nombre de coincidències a l'element amb el valor-clau 'g' al mapa. –> O (log n)
mapa equal_range()	Retorna un iterador de parells. La parella fa referència als límits d'un rang que inclou tots els elements del contenidor que tenen una clau equivalent a k.
esborrar mapa ()	S'utilitza per esborrar elements del contenidor -> O (log n)
mapa rend()	Retorna un iterador invers que apunta a l'element teòric just abans del primer parell clau-valor del mapa (que es considera l'extrem invers).
mapa rbegin()	Retorna un iterador invers que apunta a l'últim element del mapa.
cerca del mapa ()	Retorna un iterador a l'element amb el valor-clau 'g' al mapa si es troba, en cas contrari torna l'iterador al final.
map crbegin() i crend()	crbegin() retorna un iterador invers constant que fa referència a l'últim element del contenidor del mapa. crend() retorna un iterador invers constant que apunta a l'element teòric abans del primer element del mapa.
mapa cbegin() i cend()	cbegin() retorna un iterador constant que fa referència al primer element del contenidor del mapa. cend() retorna un iterador constant que apunta a l'element teòric que segueix l'últim element del multimapa.
mapa emplace()	Insereix la clau i el seu element al contenidor del mapa.
mida_màx del mapa()	Retorna el nombre màxim d'elements que pot contenir un contenidor de mapes -> O(1)
mapa upper_bound()	Retorna un iterador al primer element que és equivalent al valor assignat amb el valor-clau 'g' o sens dubte anirà després de l'element amb el valor-clau 'g' al mapa
operador de mapa=	Assigna el contingut d'un contenidor a un contenidor diferent, substituint el seu contingut actual.
mapa low_bound()	Retorna un iterador al primer element que és equivalent al valor assignat amb el valor-clau 'g' o definitivament no anirà abans de l'element amb el valor-clau 'g' al mapa -> O(log n)
mapa emplace_hint()	Insereix la clau i el seu element al contenidor del mapa amb una pista donada.
map value_comp()	Retorna l'objecte que determina com estan ordenats els elements del mapa (' <' per defecte).
mapa key_comp()	Retorna l'objecte que determina com estan ordenats els elements del mapa (' <' per defecte).
mapa::mida()	Retorna el nombre d'elements del mapa.
mapa::buit()	Retorna si el mapa està buit
map::begin() i end()	begin() retorna un iterador al primer element del mapa. end() retorna un iterador a l'element teòric que segueix l'últim element del mapa
mapa::operador[]	Aquest operador s'utilitza per fer referència a l'element present a la posició donada dins de l'operador.
mapa::clear()	Elimina tots els elements del mapa.
map::at() i map::swap()	La funció at() s'utilitza per retornar la referència a l'element associat a la clau k. La funció swap() s'utilitza per intercanviar el contingut de dos mapes, però els mapes han de ser del mateix tipus, encara que les mides poden ser diferents.