Por lo general, el propósito principal de usar el contenedor de mapa stl es para operaciones de búsqueda eficientes y recuperación de orden ordenado . Como el mapa almacena el par clave-valor, todas las operaciones de búsqueda toman un tiempo “ O(log(n)) ” (n es el tamaño del mapa). Existen diferentes tipos de funciones de búsqueda en el lenguaje C++, cada una con funciones diferentes. En el contexto de la programación competitiva, esto resulta útil cuando se requieren operaciones de búsqueda y funciona mejor que otros contenedores. Algunas operaciones de búsqueda se describen a continuación.
estándar::mapa::buscar()
find() se usa para buscar el par clave-valor y acepta la «clave» en su argumento para encontrarlo. Esta función devuelve el puntero al elemento si se encuentra el elemento, de lo contrario, devuelve el puntero que apunta a la última posición del mapa, es decir, » map.end() «.
// C++ code to demonstrate the working of find()
#include<iostream>
#include<map> // for map operations
using namespace std;
int main()
{
// declaring map
// of char and int
map< char, int > mp;
// declaring iterators
map<char, int>::iterator it ;
map<char, int>::iterator it1 ;
// inserting values
mp['a']=5;
mp['b']=10;
mp['c']=15;
mp['d']=20;
mp['e']=30;
// using find() to search for 'b'
// key found
// "it" has address of key value pair.
it = mp.find('b');
if(it == mp.end())
cout << "Key-value pair not present in map" ;
else
cout << "Key-value pair present : "
<< it->first << "->" << it->second ;
cout << endl ;
// using find() to search for 'm'
// key not found
// "it1" has address of end of map.
it1 = mp.find('m');
if(it1 == mp.end())
cout << "Key-value pair not present in map" ;
else
cout << "Key-value pair present : "
<< it1->first << "->" << it1->second ;
}
Producción:
Key-value pair present : b->10 Key-value pair not present in map
std::map::lower_bound()
lower_bound() también se usa para la operación de búsqueda, pero a veces también devuelve un par clave-valor válido incluso si no está presente en el mapa. lower_bound() devuelve la dirección del par de valores clave, si uno está presente en el mapa, de lo contrario, devuelve la dirección a la clave más pequeña mayor que la clave mencionada en sus argumentos. Si todas las claves son más pequeñas que la clave que se va a encontrar, apunta a “map.end()” .
// C++ code to demonstrate the working of lower_bound()
#include<iostream>
#include<map> // for map operations
using namespace std;
int main()
{
// declaring map
// of char and int
map< char, int > mp;
// declaring iterators
map<char, int>::iterator it ;
map<char, int>::iterator it1 ;
map<char, int>::iterator it2 ;
// inserting values
mp['a']=5;
mp['b']=10;
mp['c']=15;
mp['h']=20;
mp['k']=30;
// using lower_bound() to search for 'b'
// key found
// "it" has address of key value pair.
it = mp.lower_bound('b');
if(it == mp.end())
cout << "Key-value pair not present in map" ;
else
cout << "Key-value pair returned : "
<< it->first << "->" << it->second ;
cout << endl ;
// using lower_bound() to search for 'd'
// key not found
// "it1" has address of next greater key.
// key - 'h'
it1 = mp.lower_bound('d');
if(it1 == mp.end())
cout << "Key-value pair not present in map" ;
else
cout << "Key-value pair returned : "
<< it1->first << "->" << it1->second ;
cout << endl;
// using lower_bound() to search for 'p'
// key not found
// "it2" has address of next greater key.
// all keys are smaller, hence returns mp.end()
it2 = mp.lower_bound('p');
if(it2 == mp.end())
cout << "Key-value pair not present in map" ;
else
cout << "Key-value pair returned : "
<< it2->first << "->" << it2->second ;
}
Producción:
Key-value pair returned : b->10 Key-value pair returned : h->20 Key-value pair not present in map
std::mapa::superior_enlace()
upper_bound() también se usa para la operación de búsqueda y nunca devuelve el par clave-valor buscado . upper_bound() devuelve la dirección del par de valores clave que se encuentra exactamente al lado de la clave buscada, si hay una presente en el mapa. Si todas las claves son más pequeñas que la clave que se va a encontrar, apunta a “map.end()”
// C++ code to demonstrate the working of upper_bound()
#include<iostream>
#include<map> // for map operations
using namespace std;
int main()
{
// declaring map
// of char and int
map< char, int > mp;
// declaring iterators
map<char, int>::iterator it ;
map<char, int>::iterator it1 ;
map<char, int>::iterator it2 ;
// inserting values
mp['a']=5;
mp['b']=10;
mp['c']=15;
mp['h']=20;
mp['k']=30;
// using upper_bound() to search for 'b'
// key found
// "it" has address of key value pair next to 'b' i.e 'c'.
it = mp.upper_bound('b');
if(it == mp.end())
cout << "Key-value pair not present in map" ;
else
cout << "Key-value pair returned : "
<< it->first << "->" << it->second ;
cout << endl ;
// using upper_bound() to search for 'd'
// key not found
// "it1" has address of next greater key.
// key - 'h'
it1 = mp.upper_bound('d');
if(it1 == mp.end())
cout << "Key-value pair not present in map" ;
else
cout << "Key-value pair returned : "
<< it1->first << "->" << it1->second ;
cout << endl;
// using upper_bound() to search for 'p'
// key not found
// "it2" has address of next greater key.
// all keys are smaller, hence returns mp.end()
it2 = mp.upper_bound('p');
if(it2 == mp.end())
cout << "Key-value pair not present in map" ;
else
cout << "Key-value pair returned : "
<< it2->first << "->" << it2->second ;
}
Producción:
Key-value pair returned : c->15 Key-value pair returned : h->20 Key-value pair not present in map
std::map::igual-rango
Otra función más para buscar en el mapa, devuelve el rango que contiene la clave buscada . Como el mapa contiene elementos únicos, el rango devuelto contiene como máximo 1 elemento. Esta función devuelve un iterador de par, cuyo primer elemento apunta a lower_bound() del par de claves buscado, y el segundo elemento apunta a upper_bound() de la clave buscada. Si la clave no está presente, tanto el primer elemento como el segundo apuntan al siguiente elemento mayor.
// C++ code to demonstrate the working of equal_range()
#include<iostream>
#include<map> // for map operations
using namespace std;
int main()
{
// declaring map
// of char and int
map< char, int > mp;
// declaring iterators
pair<map<char, int>::iterator, map<char, int>::iterator> it;
// inserting values
mp['a']=5;
mp['b']=10;
mp['c']=15;
mp['h']=20;
mp['k']=30;
// using equal_range() to search for 'b'
// key found
// 1st element of "it" has the address to lower_bound (b)
// 2nd element of "it" has the address to upper_bound (c)
it = mp.equal_range('b');
cout << "The lower_bound of key is : "
<< it.first -> first << "->" << it.first -> second;
cout << endl;
cout << "The upper_bound of key is : "
<< it.second -> first << "->" << it.second -> second;
cout << endl << endl ;
// using equal_range() to search for 'd'
// key not found
// Both elements of it point to next greater key
// key - 'h'
it = mp.equal_range('d');
cout << "The lower_bound of key is : "
<< it.first -> first << "->" << it.first -> second;
cout << endl;
cout << "The upper_bound of key is : "
<< it.second -> first << "->" << it.second -> second;
}
Producción:
The lower_bound of key is : b->10 The upper_bound of key is : c->15 The lower_bound of key is : h->20 The upper_bound of key is : h->20
Este artículo es una contribución de Manjeet Singh . Si le gusta GeeksforGeeks y le gustaría contribuir, también puede escribir un artículo usando contribuya.geeksforgeeks.org o envíe su artículo por correo a contribuya@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA