C++ std::set de actualización es tedioso: yo no puedo cambiar de un elemento en su lugar

Me parece que la operación de actualización en std::set tedioso ya que no hay una API en cppreference. Así que lo que en la actualidad hacer es algo como esto:

//find element in set by iterator
Element copy = *iterator;
... //update member value on copy, varies
Set.erase(iterator);
Set.insert(copy);

Básicamente el iterador de retorno por Set es un const_iterator y no se puede cambiar su valor directamente.

Hay una manera mejor de hacer esto? O tal vez debería reemplazar std::set mediante la creación de mi propia (que no sé exactamente cómo funciona..)

  • Hacer una función en línea si usted encuentra el uso de 2 declaraciones ya es tedioso.
  • KennyTM golpear el clavo en la cabeza. No hay desventajas performancewise a hacer esto, así que simplemente hágalo ya! 😛
  • Si escribes una función de actualización, puede que desee modelo de la misma manera como Impulso.MultiIndex: boost.org/doc/libs/release/libs/multi_index/doc/tutorial/…
  • cplusplus.com es un número de referencia. Encontrar aspectos de la lengua «tedioso», debido a que parece… raro.
  • Creo que la desventaja de este enfoque es tomar un Bloqueo de Lectura y Escritura en el caso de procesamiento concurrente.
InformationsquelleAutor Figo | 2010-02-07

7 Kommentare

  1. 72

    set devuelve const_iterators (la norma dice que set<T>::iterator es const, y que set<T>::const_iterator y set<T>::iterator puede ser en realidad el mismo tipo – ver 23.2.4/6 en n3000.pdf) porque es una orden de contenedor. Si se devuelve un regular iterator, usted estaría permitido para cambiar los elementos de valor de debajo del contenedor, potencialmente alterar el orden.

    Su solución es la idiomáticas manera de modificar los elementos de una set.

    • Los miembros de la (no-const) std::set no volver const_iterator y puede modificar sus elementos si tienes cuidado. ¿Por qué es este (incorrecto) responda a tener muchos upvotes? Lo que me estoy perdiendo?
    • Mi respuesta es correcta – la suya está mal. He actualizado mi post con referencias a la norma.
    • Terry, gracias por el debate. He revisado de nuevo: el informe de defecto en efecto, había sido presentado en 1998, pero no fue incorporado en C++03. Será en C++0x. Así, mientras que su respuesta no es correcta hasta la actual carta de la norma se refiere, no es correcta la medida de que la intención va. +1.
    • Gracias por tu comentario y tu debate con Avakar (O Avatar?). Ellos ayudaron un montón.
    • Los elementos son técnicamente mutable pero no podrán alterar ellos. Este es un defecto en la norma.
    • Así que supongo que la manera correcta de hacer mutable partes, asociados a las claves únicas, mientras que aún usando la STL, es el cambio a std::map. Eso es lo que yo hice de todos modos
    • Sí, por supuesto. Ambos set y map necesidad inmutable claves, y si no dispone de clave de campos que desea cambiar, los que deben ser el valor de la parte de un map. (Yo desautorizar opciones como el uso de mutable miembros en set elementos: ¡puaj!)

  2. 24

    Hay 2 maneras de hacer esto, en el caso fácil:

    • Puede utilizar mutable en la variable que no son parte de la clave
    • Puede dividir la clase en un Key Value par (y el uso de un std::map)

    Ahora, la pregunta es para los casos difíciles: ¿qué sucede cuando la actualización modifica la key parte del objeto ? Su enfoque funciona, aunque he de admitir que es tedioso.

    • añadir mutable en un no miembro clave podría estar bien si algunos interna y privada de la clase, pero aún es una sucia hack! Tan pronto como la clase está expuesto a algunos usuarios, id nunca se atreven a utilizar mutable para los miembros que no están destinados a ser mutable! Eso es el mal!
  3. 10

    En C++17 puede hacer mejor con extract(), gracias a P0083:

    //remove element from the set, but without needing
    //to copy it or deallocate it
    auto node = Set.extract(iterator);
    //make changes to the value in place
    node.value() = 42;
    //reinsert it into the set, but again without needing 
    //to copy or allocate
    Set.insert(std::move(node));

    Esto evitará una copia adicional de su tipo y un extra de asignación/desasignación, y también funciona con move-sólo los tipos.

    También puede extract por clave. Si la clave está ausente, esto devolverá un vacío nodo:

    auto node = Set.extract(key);
    if (node) //alternatively, !node.empty()
    {
        node.value() = 42;
        Set.insert(std::move(node));
    }
  4. 8

    Actualización: Aunque el siguiente es verdadero como el de ahora, el comportamiento es considerado como un defecto y será cambiado en la próxima versión de la norma. Cómo muy triste.


    Hay varios puntos que hacen que su pregunta bastante confuso.

    1. Funciones pueden devolver valores, las clases no pueden. std::set es una clase, y por lo tanto no puede devolver nada.
    2. Si se le puede llamar s.erase(iter), entonces iter no es un const_iterator. erase requiere que los no-const iterador.
    3. Todas las funciones miembro de std::set que devuelven un iterador de retorno de un no-const iterador mientras el conjunto es no-const así.

    Te permite cambiar el valor de un elemento de un conjunto tan larga como la actualización no cambia el orden de los elementos. El siguiente código se compila y funciona bien.

    #include <set>
    
    int main()
    {
        std::set<int> s;
        s.insert(10);
        s.insert(20);
    
        std::set<int>::iterator iter = s.find(20);
    
        //OK
        *iter = 30;
    
        //error, the following changes the order of elements
        //*iter = 0;
    }

    Si su actualización cambia el orden de los elementos, entonces usted tiene que borrar y volver a insertarla.

    • Que el código no compila, al menos en VC10 – por las razones que expuse en mi post. Esto puede haber cambiado recientemente (sido una «corrección» a la norma), pensé que era en C++03, pero puedo estar equivocado.
    • Bueno, yo estoy mirando a 23.1.2[lib.asociativa.reqmts] de C++03, tabla 69 y dice: «un.encontrar(k): iterator; const_iterator por una constante».
    • Y acabo de comprobar que el proyecto de C++0x y no hay ningún cambio (lo cual es lógico y romper una gran cantidad de código).
    • No tengo el C++03 pdf práctico (cuesta dinero). Pensé que esto era fijo en C++03, pero podría haber sido un post 03 revisión. En n3000.pdf es 23.2.4/6, que explica que para asociativa contenedores, iterador es un const iterator (y pueden ser del mismo tipo que const_iterator). Qué compilador estás usando? Este comportamiento fue implementado en VC9 así (que fue el seguimiento de C++03), que es la razón por la que yo pensaba que el comportamiento fue una C++03 de corrección del error.
    • No hay que mirar la tabla, busque en el párrafo que explique los requisitos de «iterator» en un contenedor asociativo. Un iterador puede ser «const», sin realmente ser llamado «const_iterator».
    • a la derecha, a pesar de que un cambio de C++03, donde 23.1.2/6 (el equivalente de 23.3.4/6 en C++0x) sólo dice que «iterador de un contenedor asociativo es de la iterador bidireccional categoría». He construido el fragmento con msvc9 sin problemas, así que de hecho la pista C++03.
    • Es en la biblioteca Estándar defecto informes: open-std.org/jtc1/sc22/wg21/docs/lwg-defects.html#103. No compilar con GCC, el cual se hace una mención de DR 103 y typedefs tanto iterador y const_iterator a ser del mismo tipo. – Una propuesta de solución para OP problemas, por CIERTO, son const_cast y mutable de los miembros.
    • ¿se nota que para los mapas, C++03 especifica el tipo de valor es pair<const Key, T>. Basado en esto, se puede cambiar la tecla set parece un descuido que el C++0x comité fijo.
    • lo que sucede en MSVC 9 al hacer *iter = 0;? ¿La operación de tiro? No se permite la operación, pero causa problemas en otros usos del contenedor?
    • sí, he encontrado el DR demasiado. Estoy un poco sorprendido de que no lo hacen en C++03, pero fue incorporado en el proyecto actual. Es más bien un cambio severo desde mi punto de vista como se va a romper de lo contrario, el código correcto.
    • Samuel Klatchko, compile y corra bien, pero lo más probable es romper en algún lugar abajo de la línea.

  5. 8

    Puede que desee utilizar un std::map lugar. Utilice la parte de Element que afecta el orden de la clave, y poner todo de Element como el valor. Habrá algunos menores de duplicación de datos, pero será más fácil (y posiblemente más) actualizaciones.

  6. 2

    Me encontré con el mismo problema en C++11, donde, de hecho, ::std::set<T>::iterator es constante y por lo tanto no permite cambiar su contenido, incluso si sabemos que la transformación no afecta a la < invariante. Usted puede evitar esto mediante un ajuste de ::std::set en un mutable_set escribir en un contenedor para el contenido:

      template <typename T>
      struct MutableWrapper {
        mutable T data;
        MutableWrapper(T const& data) : data(data) {}
        MutableWrapper(T&& data) : data(data) {}
        MutableWrapper const& operator=(T const& data) { this->data = data; }
        operator T&() const { return data; }
        T* operator->() const { return &data; }
        friend bool operator<(MutableWrapper const& a, MutableWrapper const& b) {
          return a.data < b.data;
        }   
        friend bool operator==(MutableWrapper const& a, MutableWrapper const& b) {
          return a.data == b.data;
        }   
        friend bool operator!=(MutableWrapper const& a, MutableWrapper const& b) {
          return a.data != b.data;
        }   
      };

    Esto me parece mucho más simple y funciona en el 90% de los casos sin que el usuario ni siquiera darse cuenta de que hay algo entre el conjunto y el tipo real.

    • Interesante idea, voy a tratar de recordar esto.
    • Sí, pero sólo para estar más seguro, es de señalar, que esta sólo puede ser utilizado si la modificación de los datos almacenados detrás de la iterador es garantizado de no cambiar el orden de la serie. De lo contrario, esto es UB y se break! (Simplemente reiterando esta para estar seguro de que nadie dispara en el pie. Yo no soy lo que implica, en particular, no se dan cuenta de esto.)
    • +1 esto es ideal si desea único ordenado de artículos basados en algunos de los principales (por que es el contenedor adecuado), pero también desea mantener a algunos de los «metadatos» con ellos que puede cambiar
    • Este enfoque no funciona en mi objeto. Especialmente en Puntero-como operador operador «->()» cuando intento llamar a mi método de clase.
  7. 0

    Esto es más rápido en algunos casos:

    std::pair<std::set<int>::iterator, bool> result = Set.insert(value);
    if (!result.second) {
      Set.erase(result.first);
      Set.insert(value);
    }

    Si el valor es generalmente no ya en el std::set, a continuación, esto puede tener un mejor rendimiento.

Kommentieren Sie den Artikel

Bitte geben Sie Ihren Kommentar ein!
Bitte geben Sie hier Ihren Namen ein

Pruebas en línea