Cómo garantizar una mejor eficiencia volver a insertar en juegos en C++

Question

tengo que modificar un objeto que ya se ha insertado en un conjunto. Esto no es trivial porque el iterador en el par devuelto por una inserción de un solo objeto es un constante iterativo y no permite modificaciones. Por lo tanto, mi plan era que si una inserción no pude copiar ese objeto en una variable temporal, la borra del conjunto, modificar localmente y luego insertar mi versión modificada.

insertResult = mySet.insert(newPep); 
    if(insertResult.second == false) 
     modifySet(insertResult.first, newPep); 

void modifySet(set<Peptide>::iterator someIter, Peptide::Peptide newPep) { 
    Peptide tempPep = (*someIter); 
    someSet.erase(someIter); 
    // Modify tempPep - this does not modify the key 
    someSet.insert(tempPep);    

}

Esto funciona, pero yo quiero hacer mi inserción más eficiente. Intenté hacer otro iterador y configurarlo igual a someIter en modifySet. Luego, después de eliminar algo más, todavía tendría un iterador en esa ubicación del conjunto y podría usarlo como la ubicación de inserción.

void modifySet(set<Peptide>::iterator someIter, Peptide::Peptide newPep) { 
    Peptide tempPep = (*someIter); 
    anotherIter = someIter; 
    someSet.erase(someIter); 
    // Modify tempPep - this does not modify the key 
    someSet.insert(anotherIter, tempPep);    

}

Sin embargo, esto resulta en una falla seg. Espero que alguien me pueda decir por qué esta inserción falla o sugerir otra forma de modificar un objeto que ya se ha insertado en un conjunto.

El código fuente completo se puede ver en github.

Answer 1

espero que no es una mala forma de responder a mi propia pregunta, pero me gustaría que fuera aquí en caso de que alguien más ha este problema. La respuesta de por qué mi intento falló fue dado mi robot académico, pero aquí está la solución para hacer que esto funcione con un conjunto. Mientras que hago apreciar las otras respuestas y un plan para aprender acerca de los mapas, esta pregunta fue re-insertar sobre eficientemente en un establecido.

void modifySet(set<Peptide>::iterator someIter, Peptide::Peptide newPep) { 
    if(someIter == someSet.begin()) { 
     Peptide tempPep = (*someIter); 
     someSet.erase(someIter); 
     // Modify tempPep - this does not modify the key 
     someSet.insert(tempPep); 
    } 
    else { 
     Peptide tempPep = (*someIter); 
     anotherIter = someIter; 
     --anotherIter; 
     someSet.erase(someIter); 
     // Modify tempPep - this does not modify the key 
     someSet.insert(anotherIter, tempPep); 
    } 
} 

En mi programa, este cambio redujo mi tiempo de ejecución en aproximadamente un 15%, de 32 segundos a 27 segundos. Mi conjunto de datos más grande se está ejecutando actualmente y tengo mis dedos cruzados que las escalas de mejora del 15%.

Answer 2

std :: set :: insert devuelve un par < iterador, bool > por lo que yo sé. En cualquier caso, modificar directamente un elemento en cualquier clase de conjunto es arriesgado. ¿Qué sucede si su modificación hace que el artículo se compare igual a otro elemento existente? ¿Qué pasa si cambia la posición del artículo en el orden total de los elementos en el conjunto? Dependiendo de la implementación, esto causará un comportamiento indefinido.

Si la clave del tema sigue siendo el mismo y sólo cambiar sus propiedades, entonces creo que lo que realmente quiere es un mapa o un unordered_map en lugar de un conjunto.

Answer 3

Estoy de acuerdo con Pedro que un mapa es probablemente un modelo mejor de lo que está haciendo, específicamente algo así como map<pep_key, Peptide::Peptide>, le permiten hacer algo como:

insertResult = myMap.insert(std::make_pair(newPep.keyField(), newPep)); 
if(insertResult.second == false) 
    insertResult.first->second = newPep; 

Para responder a su pregunta, las violaciones de segmento de inserción PORQUE borrar invalida un iterador, por lo que insertarlo (o una copia) es análogo a desreferenciar un puntero no válido. La única manera que veo para hacer lo que quiere es un const_cast

insertResult = mySet.insert(newPep); 
if(insertResult.second == false) 
    const_cast<Peptide::Peptide&>(*(insertResult.first)) = newPep; 

el enfoque const_cast parece que va a trabajar para lo que está haciendo, pero en general es una mala idea.

Answer 4

Como se dio cuenta set es un poco complicado de manejar porque no tiene forma de indicar qué parte del objeto se debe considerar para la clave y qué parte se puede modificar de forma segura.

La respuesta habitual es utilizar un map o un unordered_map (si tiene acceso a C++ 0x) y cortar el objeto en dos mitades: la clave y los datos del satélite.

Tenga cuidado con la respuesta típica: std::map<key_type, Peptide>, si bien parece fácil, significa que necesita garantizar que la parte clave del objeto Peptide coincida siempre con la clave a la que está asociada, el compilador no ayudará.

Así que tienes 2 alternativas:

1. Cut Peptide en dos: Peptide::Key y Peptide::Data, entonces usted puede utilizar el map segura.
2. No proporcione ningún método para modificar la parte de Peptide que define la clave, luego puede usar la respuesta típica.

Finalmente, tenga en cuenta que hay dos maneras de insertar en un objeto similar a map.

• insert: inserte pero falla si el valor ya existe
• operator[]: insertar o actualizar (lo que requiere la creación de un objeto vacío)

Por lo tanto, una solución sería:

class Peptide 
{ 
public: 
    Peptide(int const id): mId(id) {} 

    int GetId() const; 

    void setWeight(float w); 
    void setLength(float l); 

private: 
    int const mId; 
    float mWeight; 
    float mLength; 
}; 

typedef std::unordered_map<int, Peptide> peptide_map; 

Tenga en cuenta que en caso de actualización, significa crear un nuevo objeto (constructor predeterminado) y luego asignarlo. Esto no es posible aquí, porque la asignación significa potencialmente cambiar la parte clave del objeto.

Answer 5

std :: map hará su vida mucho más fácil y no me sorprendería si supera std :: set para este caso en particular. El almacenamiento de la clave puede parecer redundante, pero puede ser trivialmente barato (por ejemplo, un puntero a datos inmutables en Péptido con su propio predicado de comparación para comparar correctamente la punta). Con eso no tienes que preocuparte por la consistencia del valor asociado con una tecla.

Si puede cambiar la implementación de Peptide, puede evitar la redundancia completamente haciendo que Peptide se divida en dos clases separadas: una para la parte clave y otra para el valor asociado con la tecla.