45
Tengo std::set<int>, ¿cuál es la forma correcta de encontrar la int más grande en este conjunto?¿Cómo puedo encontrar el int más grande en un std :: set <int>?
A
Respuesta
75
¿Qué comparador estás utilizando?
Por defecto, ésta funcionará:
if(!myset.empty())
*myset.rbegin();
else
//the set is empty
Esto también habrá tiempo constante en lugar de lineal como la solución max_element.
6
creo que busca std::max_element:
La función devuelve un iterador
max_element()al elemento más grande de la gama [inicio, final).
+14
Este parece ser el camino lento para hacerlo, ya que max_element no puede saber que se ordena el rango. –
+2
Esto es lo que obtengo al responder una pregunta fuera de mi zona de confort :) No sabía que un 'std :: set' estaba ordenado por defecto. Como suponía que no estaba ordenado, un algoritmo O (n) parecía ser la única opción práctica. Ahora que sé lo que sé, sí, esta respuesta no es óptima. –
29
Los juegos se solicitan siempre. Suponiendo que está utilizando la comparación predeterminada (menos), simplemente tome el último elemento en el conjunto. rbegin() podría ser útil.
+0
Garantía de orden estándar de C++ : http://stackoverflow.com/q/8833938/895245 –
6
Dado que el conjunto ordena el elemento en orden ascendente de forma predeterminada, solo selecciona el último elemento del conjunto.
-1
Antes push() en su set<int> guardar el valor en int max en la variable global
+0
por favor explique qué se supone que debe hacer su respuesta, y quizás proporcione un ejemplo de código. Tengo curiosidad por ver lo que se te ocurre – andrewgu
Cuestiones relacionadas
- 1. Encontrar nth bit SET en un int
- 2. C++ ¿Cómo encontrar la clave más grande en un std :: map?
- 3. Cómo iterar std :: set?
- 4. std :: for_each sobre std :: set, C++ 11
- 5. ¿Hay alguna diferencia entre std :: map <int, int> y std :: map <const int, int>?
- 6. Encontrar el palíndromo más grande en la implementación de cadenas
- 7. Borrar el miembro final de std :: set
- 8. Encontrar el valor más grande en un diccionario
- 9. ¿Cómo seleccionar un elemento aleatorio en std :: set?
- 10. distancia entre std :: set begin() y std :: set iterator en O (logn)
- 11. ¿PHP tiene un tipo de datos más grande que int?
- 12. ¿Por qué std :: set :: lower_bound (x) (efectivamente) se define como el número más pequeño> = x en lugar del número más grande <= x?
- 13. std :: back_inserter for a std :: set?
- 14. Encuentra el elemento más grande y el segundo más grande en un rango
- 15. std :: set :: insert, ¿qué tan mal puedo insinuar?
- 16. Cómo contener mi clase con std :: set
- 17. std :: set encargo comparador
- 18. ¿Cómo puedo encontrar el valor más grande en una columna en postgres sql?
- 19. Encontrar la int positiva más grande en una matriz por recursión
- 20. ¿Cómo puedo imprimir el valor de std :: atomic <unsigned int>
- 21. ¿Cómo puedo encontrar el tamaño más grande (en tamaño) de dos enteros?
- 22. ¿Cómo encontrar el número más pequeño y más grande en una matriz?
- 23. BOOST_CHECK_EQUAL con el par <int, int> y el operador personalizado <<
- 24. pasando más datos a std: set Clase de comparación
- 25. ¿Por qué no puedo construir std :: set con una instanciación de un predicado, pero puedo asignar un std :: set construido de esa manera?
- 26. ¿Qué pasa con `std :: set`?
- 27. ¿El ordenamiento std :: pair <int, std :: string> está bien definido?
- 28. conversión no válida del 'const int *' a 'int *', teniendo std :: set dirección del elemento
- 29. La forma más rápida de restablecer cada valor de std :: vector <int> en 0
- 30. ¿Cómo encontrar el paquete UDP más grande que puedo enviar sin fragmentar?
Encontrar el elemento máximo es el tiempo constante, sí, pero llenar el conjunto no es, ya que está ordenando en insertar. Un conjunto no ordenado tiene un inserto de tiempo constante, pero requeriría una búsqueda para el elemento máximo. – crunchdog
Pero dado que la pregunta original comienza con "Tengo un std :: set", podemos suponer que se incurrirá en un tiempo de inserción no constante independientemente de nuestro mecanismo de búsqueda. Como ya pagó el precio, ¿por qué no aprovecharlo utilizando un método de búsqueda constante? – Darryl
@crunchdog: 'unordered_set' solo tiene un promedio de tiempo constante, pero tiene el peor caso de tiempo lineal, que es peor que' set' – user102008