C++
std :: set y std :: multiset
Buscar..
Introducción
set es un tipo de contenedor cuyos elementos están ordenados y son únicos. multiset es similar, pero, en el caso de multiset , múltiples elementos pueden tener el mismo valor.
Observaciones
Se han usado diferentes estilos de C ++ en esos ejemplos. Tenga cuidado de que si está utilizando un compilador C ++ 98; Es posible que parte de este código no sea utilizable.
Insertando valores en un conjunto
Se pueden utilizar tres métodos diferentes de inserción con conjuntos.
- Primero, una simple inserción del valor. Este método devuelve un par que permite a la persona que llama verificar si realmente se produjo la inserción.
- Segundo, una inserción dando una pista de donde se insertará el valor. El objetivo es optimizar el tiempo de inserción en tal caso, pero saber dónde debe insertarse un valor no es el caso común. Ten cuidado en ese caso; La forma de dar una pista difiere con las versiones del compilador .
- Finalmente, puede insertar un rango de valores dando un puntero inicial y uno final. El inicio se incluirá en la inserción, el final se excluye.
#include <iostream>
#include <set>
int main ()
{
std::set<int> sut;
std::set<int>::iterator it;
std::pair<std::set<int>::iterator,bool> ret;
// Basic insert
sut.insert(7);
sut.insert(5);
sut.insert(12);
ret = sut.insert(23);
if (ret.second==true)
std::cout << "# 23 has been inserted!" << std::endl;
ret = sut.insert(23); // since it's a set and 23 is already present in it, this insert should fail
if (ret.second==false)
std::cout << "# 23 already present in set!" << std::endl;
// Insert with hint for optimization
it = sut.end();
// This case is optimized for C++11 and above
// For earlier version, point to the element preceding your insertion
sut.insert(it, 30);
// inserting a range of values
std::set<int> sut2;
sut2.insert(20);
sut2.insert(30);
sut2.insert(45);
std::set<int>::iterator itStart = sut2.begin();
std::set<int>::iterator itEnd = sut2.end();
sut.insert (itStart, itEnd); // second iterator is excluded from insertion
std::cout << std::endl << "Set under test contains:" << std::endl;
for (it = sut.begin(); it != sut.end(); ++it)
{
std::cout << *it << std::endl;
}
return 0;
}
La salida será:
# 23 has been inserted!
# 23 already present in set!
Set under test contains:
5
7
12
20
23
30
45
Insertar valores en un multiset
Todos los métodos de inserción de conjuntos también se aplican a multisets. Sin embargo, existe otra posibilidad, que es proporcionar una initial__list:
auto il = { 7, 5, 12 };
std::multiset<int> msut;
msut.insert(il);
Cambiar el tipo predeterminado de un conjunto
set y multiset tienen métodos de comparación predeterminados, pero en algunos casos es posible que deba sobrecargarlos.
Imaginemos que estamos almacenando valores de cadena en un conjunto, pero sabemos que esas cadenas contienen solo valores numéricos. Por defecto, la clasificación será una comparación de cadena lexicográfica, por lo que el orden no coincidirá con la clasificación numérica. Si desea aplicar una clasificación equivalente a la que tendría con los valores int , necesita un functor para sobrecargar el método de comparación:
#include <iostream>
#include <set>
#include <stdlib.h>
struct custom_compare final
{
bool operator() (const std::string& left, const std::string& right) const
{
int nLeft = atoi(left.c_str());
int nRight = atoi(right.c_str());
return nLeft < nRight;
}
};
int main ()
{
std::set<std::string> sut({"1", "2", "5", "23", "6", "290"});
std::cout << "### Default sort on std::set<std::string> :" << std::endl;
for (auto &&data: sut)
std::cout << data << std::endl;
std::set<std::string, custom_compare> sut_custom({"1", "2", "5", "23", "6", "290"},
custom_compare{}); //< Compare object optional as its default constructible.
std::cout << std::endl << "### Custom sort on set :" << std::endl;
for (auto &&data : sut_custom)
std::cout << data << std::endl;
auto compare_via_lambda = [](auto &&lhs, auto &&rhs){ return lhs > rhs; };
using set_via_lambda = std::set<std::string, decltype(compare_via_lambda)>;
set_via_lambda sut_reverse_via_lambda({"1", "2", "5", "23", "6", "290"},
compare_via_lambda);
std::cout << std::endl << "### Lambda sort on set :" << std::endl;
for (auto &&data : sut_reverse_via_lambda)
std::cout << data << std::endl;
return 0;
}
La salida será:
### Default sort on std::set<std::string> :
1
2
23
290
5
6
### Custom sort on set :
1
2
5
6
23
290
### Lambda sort on set :
6
5
290
23
2
1
En el ejemplo anterior, uno puede encontrar 3 formas diferentes de agregar operaciones de comparación al std::set , cada una de ellas es útil en su propio contexto.
Orden predeterminado
Esto usará el operador de comparación de la clave (primer argumento de la plantilla). A menudo, la clave ya proporcionará un buen valor predeterminado para la función std::less<T> . A menos que esta función sea especializada, utiliza el operator< del objeto. Esto es especialmente útil cuando otro código también intenta usar algunos pedidos, ya que esto permite la coherencia en toda la base del código.
Escribir el código de esta manera reducirá el esfuerzo de actualizar su código cuando la clave cambie en API, como: una clase que contiene 2 miembros que cambia a una clase que contiene 3 miembros. Al actualizar el operator< en la clase, todas las ocurrencias se actualizarán.
Como es de esperar, el uso de la ordenación predeterminada es un valor predeterminado razonable.
Orden personalizado
La adición de una ordenación personalizada a través de un objeto con un operador de comparación se usa a menudo cuando la comparación predeterminada no cumple. En el ejemplo anterior, esto se debe a que las cadenas se refieren a números enteros. En otros casos, a menudo se usa cuando se desean comparar (inteligentes) los punteros en función del objeto al que hacen referencia o porque se necesitan diferentes restricciones para comparar (ejemplo: comparar std::pair por el valor de first ).
Al crear un operador de comparación, esto debería ser una clasificación estable. Si el resultado del operador de comparación cambia después de la inserción, tendrá un comportamiento indefinido. Como buena práctica, su operador de comparación solo debe usar los datos constantes (miembros const, funciones const ...).
Como en el ejemplo anterior, a menudo encontrará clases sin miembros como operadores de comparación. Esto da como resultado constructores por defecto y constructores de copia. El constructor predeterminado le permite omitir la instancia en el momento de la construcción y se requiere el constructor de copia ya que el conjunto toma una copia del operador de comparación.
Tipo lambda
Las Lambdas son una forma más corta de escribir objetos de función. Esto permite escribir el operador de comparación en menos líneas, lo que hace que el código general sea más legible.
La desventaja del uso de lambdas es que cada lambda obtiene un tipo específico en el momento de la compilación, por lo que decltype(lambda) será diferente para cada compilación de la misma unidad de compilación (archivo cpp) que sobre varias unidades de compilación (cuando se incluye a través del archivo de cabecera ). Por esta razón, se recomienda usar objetos de función como operador de comparación cuando se usa dentro de los archivos de encabezado.
Esta construcción se encuentra a menudo cuando se usa un std::set dentro del alcance local de una función, mientras que el objeto de la función se prefiere cuando se usa como argumentos de la función o miembros de la clase.
Otras opciones de clasificación
Como el operador de comparación de std::set es un argumento de plantilla, todos los objetos que se pueden llamar se pueden usar como operador de comparación y los ejemplos anteriores son solo casos específicos. Las únicas restricciones que tienen estos objetos invocables son:
- Deben ser copiables construibles.
- Deben ser invocables con 2 argumentos del tipo de la clave. (las conversiones implícitas están permitidas, aunque no se recomiendan ya que pueden afectar el rendimiento)
Buscando valores en set y multiset
Hay varias formas de buscar un valor dado en std::set o en std::multiset :
Para obtener el iterador de la primera aparición de una clave, se puede usar la función find() . Devuelve end() si la clave no existe.
std::set<int> sut;
sut.insert(10);
sut.insert(15);
sut.insert(22);
sut.insert(3); // contains 3, 10, 15, 22
auto itS = sut.find(10); // the value is found, so *itS == 10
itS = sut.find(555); // the value is not found, so itS == sut.end()
std::multiset<int> msut;
sut.insert(10);
sut.insert(15);
sut.insert(22);
sut.insert(15);
sut.insert(3); // contains 3, 10, 15, 15, 22
auto itMS = msut.find(10);
Otra forma es usar la función count() , que cuenta cuántos valores correspondientes se han encontrado en el set / set multiset (en el caso de un set , el valor de retorno puede ser solo 0 o 1). Usando los mismos valores que arriba, tendremos:
int result = sut.count(10); // result == 1
result = sut.count(555); // result == 0
result = msut.count(10); // result == 1
result = msut.count(15); // result == 2
En el caso de std::multiset , puede haber varios elementos que tengan el mismo valor. Para obtener este rango, se puede usar la función equal_range() . Devuelve std::pair con iterador límite inferior (inclusivo) y límite superior (exclusivo) respectivamente. Si la clave no existe, ambos iteradores apuntarían al valor superior más cercano (basado en el método de comparación usado para ordenar el multiset dado).
auto eqr = msut.equal_range(15);
auto st = eqr.first; // point to first element '15'
auto en = eqr.second; // point to element '22'
eqr = msut.equal_range(9); // both eqr.first and eqr.second point to element '10'
Eliminar valores de un conjunto
El método más obvio, si solo desea restablecer su conjunto / conjunto múltiple a uno vacío, es usar clear :
std::set<int> sut;
sut.insert(10);
sut.insert(15);
sut.insert(22);
sut.insert(3);
sut.clear(); //size of sut is 0
Luego se puede utilizar el método de erase . Ofrece algunas posibilidades que parecen un tanto equivalentes a la inserción:
std::set<int> sut;
std::set<int>::iterator it;
sut.insert(10);
sut.insert(15);
sut.insert(22);
sut.insert(3);
sut.insert(30);
sut.insert(33);
sut.insert(45);
// Basic deletion
sut.erase(3);
// Using iterator
it = sut.find(22);
sut.erase(it);
// Deleting a range of values
it = sut.find(33);
sut.erase(it, sut.end());
std::cout << std::endl << "Set under test contains:" << std::endl;
for (it = sut.begin(); it != sut.end(); ++it)
{
std::cout << *it << std::endl;
}
La salida será:
Set under test contains:
10
15
30
Todos esos métodos también se aplican a multiset . Tenga en cuenta que si solicita eliminar un elemento de un multiset y está presente varias veces, se eliminarán todos los valores equivalentes .