container - set string c++

¿Cómo actualizar un elemento existente de std:: set?

Question

Tengo un std::set<Foo> , y me gustaría actualizar algún valor de un elemento existente en el mismo. Tenga en cuenta que el valor que estoy actualizando no cambia el orden en el conjunto:

#include <iostream>
#include <set>
#include <utility>

struct Foo {
  Foo(int i, int j) : id(i), val(j) {}
  int id;
  int val;
  bool operator<(const Foo& other) const {
    return id < other.id;
  }
};

typedef std::set<Foo> Set;

void update(Set& s, Foo f) {
  std::pair<Set::iterator, bool> p = s.insert(f);
  bool alreadyThere = p.second;
  if (alreadyThere)
    p.first->val += f.val; // error: assignment of data-member
                           // ‘Foo::val’ in read-only structure
}

int main(int argc, char** argv){
  Set s;
  update(s, Foo(1, 10));
  update(s, Foo(1, 5));
  // Now there should be one Foo object with val==15 in the set.                                                                
  return 0;
}

¿Hay alguna forma concisa de hacer esto? ¿O debo verificar si el elemento ya está allí y, de ser así, eliminarlo, agregar el valor y volver a insertarlo?

Answer 1

Como val no está involucrado en comparación, podría declararse mutable

struct Foo {
  Foo(int i, int j) : id(i), val(j) {}
  int id;
  mutable int val;
  bool operator<(const Foo& other) const {
    return id < other.id;
  }
};

Esto implica que el valor de val puede cambiar en un Foo lógicamente const, lo que significa que no debe afectar a otros operadores de comparación, etc.

O puede simplemente eliminar e insertar, que toma O (1) tiempo adicional (en comparación con acceder y modificar) si la inserción usa la posición justo antes del anterior como la sugerencia.

Algo como:

bool alreadyThere = !p.second; // you forgot the !
if (alreadyThere)
{
    Set::iterator hint = p.first;
    hint++;
    s.erase(p.first);
    s.insert(hint, f);
}

Answer 2

Hacer val mutable como:

mutable int val;

Ahora puedes cambiar / modificar / mutar val incluso si foo es const:

void f(const Foo & foo)
{
     foo.val = 10;  //ok
     foo.id  = 11;  //compilation error - id is not mutable.
}

Por cierto, desde su código, parece pensar que si p.second es verdadero, entonces el valor ya existía en el conjunto y, por lo tanto, actualiza el valor asociado. Creo que lo entendiste mal De hecho, es de otra manera. El doc en cpluscplus dice:

El par :: segundo elemento del par se establece en verdadero si se insertó un nuevo elemento o es falso si existió un elemento con el mismo valor.

que es correcto, en mi opinión.

Sin embargo, si usa std::map , su solución sería sencilla:

void update(std::map<int,int> & m, std::pair<int,int> value) 
{
    m[value.first] += value.second;
}

¿Qué hace este código? m[value.first] crea una nueva entrada si la clave no existe en el mapa, y el valor de la nueva entrada es el valor predeterminado de int que es cero. Entonces agrega value.second . value.second a zero . O bien, si la clave existe, entonces simplemente agrega value.second a ella. Es decir, el código anterior es equivalente a esto:

void update(std::map<int,int> & m, std::pair<int,int> value) 
{
    std::map<int,int>::iterator it = m.find(value);
    if ( it != m.end()) //found or not?
           it.second += value; //add if found
    else
    {
           m.insert(value); //insert if not found
    }
}

Pero esto es demasiado, ¿no? Su rendimiento no es bueno. El anterior es más conciso y muy eficiente.

Answer 3

No intente resolver este problema trabajando alrededor de la const-ness de elementos en un set . En su lugar, ¿por qué no usar map , que ya expresa la relación clave-valor que está modelando y proporciona formas sencillas de actualizar los elementos existentes?

Answer 4

puedes usar MAP que tiene acceso muy rápido a tu elemento si tienes KEY. en este caso, creo que usar MAP sería una mejor manera de lograr la velocidad más rápida. STD :: MAP