Tengo un estándar :: conjunto de std :: cadena. Necesito el "índice" o "posición" de cada cadena en el conjunto, ¿es este un concepto significativo en el contexto?índice o posición en std :: conjunto
Supongo que find() devolverá un iterador a la cadena, por lo que mi pregunta podría redactarse mejor como: "¿Cómo convierto un iterador a un número?".
std::distance es lo que necesita. Usted querrá, supongo std::distance(set.begin(), find_result)
Observación: 'std :: distance' es O (n) ya que los iteradores' set' son modelos de 'BidirectionalIterator' y no' RandomAccessIterator' –
std :: distance es O (N) ¿Hay algún forma de obtener las estadísticas de la orden en O (log (n))? –
No hay una buena manera.Cálculo de la distancia se puede lograr en O (logN) para cualquier estructura decente con contabilidad adecuada, pero no es requerido por el estándar, y ninguna biblioteca de STL sé que lo hace. Necesitas otfind o escribir una estructura a medida. – RichardPlunkett
No creo que tenga sentido, los conjuntos se 'autocatenan' y se ordenan así el 'índice' se invalidará cuando se modifique el conjunto.
Por supuesto, depende de cómo pretenda usar el índice y si el conjunto es esencialmente estático (digamos un diccionario).
Creo que mientras se ordena un contenedor, la posición de sus elementos tiene un significado semántico. En particular, la posición real puede ser importante, dependiendo de lo que esté haciendo (por ejemplo, la marca de tiempo). Si el conjunto cambia, naturalmente también lo hace la posición de algunos elementos. – laura
A pesar de lo que otros han escrito aquí, no creo que el "índice" o "posición" tenga significado con respecto a un conjunto. En términos matemáticos, un conjunto expone solo a sus miembros y tal vez su cardinalidad. Las únicas operaciones significativas implican probar si un elemento es miembro del conjunto y combinar o restar conjuntos para producir conjuntos nuevos.
Algunas personas hablan de los conjuntos como estructuras de datos en términos más flexibles, por facetas de ser "ordenados" o "desordenados", y si permiten duplicados o imponen la exclusividad. La primera faceta distingue una matriz con O (n) protector de inserción, donde un intento de insertar un elemento primero explora los miembros existentes para ver si el nuevo elemento existe y, si no, inserta el nuevo elemento al final, y una tabla hash, que podría mantener dicho orden solo dentro de la cadena de un cubo. Un árbol como el Árbol Rojo-Negro utilizado por std::set está en algún punto intermedio; su orden transversal es determinista con respecto al strict weak order impuesto por el predicado del comparador, pero, a diferencia de la matriz esbozada arriba, no retiene orden de inserción.
La otra faceta, ya sea que el conjunto permita la duplicación de elementos, no tiene sentido en matemáticas, y se describe con más precisión como una bolsa . Tal estructura reconoce la diferencia entre la identidad y la "igualdad" basada en el valor.
Su problema puede implicar preocuparse por alguna posición; no está claro qué significa esa posición, pero espero que necesite una estructura de datos separada de std::set para modelar esto correctamente. Tal vez un mapeo std::map de su conjunto de elementos a cada posición sería suficiente. Eso no garantizaría que las posiciones sean únicas.
También puede ayudar a aclarar el problema para pensar cómo lo modeló como relaciones , como en una base de datos relacional. ¿Qué incluye la llave? ¿Qué partes de las entidades pueden variar de forma independiente?
Estoy construyendo un "conjunto" de cadenas únicas desde una base de datos, luego esas cadenas deben representarse como números. La función de distancia() es suficiente. Es posible (¿probable?) Que el conjunto no sea una buena opción, lo hice porque parecía una forma eficiente de garantizar la unicidad de las cadenas. El STL es un nuevo territorio para mí. –
Si ha encontrado un diseño que resuelva su problema, todo está bien. Si se siente cómodo con los conceptos de STL, puede disfrutar del libro * Elements of Programming * de Stepanov and McJones (http://www.elementsofprogramming.com/). – seh
http://stackoverflow.com/questions/1796503/index-or-position-in-stdset/1810416#1810416 @seh si vemos semánticamente, lo que usted ha dicho es correcto, pero los conjuntos están ordenados. Por lo general, se implementan utilizando algún tipo de árboles equilibrados como el árbol negro rojo, y usan órdenes débiles estrictas para ordenar los elementos en el conjunto. No sé si el estándar exige este orden o no. Pero así es como es –