How to update an existing element of std::set?

Question

I have a std::set<Foo>, and I'd like to update some value of an existing element therein. Note that the value I'm updating does not change the order in the set:

#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;
}

Is there any concise way to do this? Or do I have to check if the element is already there, and if so, remove it, add the value and re-insert?

Answer 1

Since val is not involved in comparison, it could be declared 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;
  }
};

This implies that the value of val may change in a logically-const Foo, which means that it shouldn't affect other comparison operators etc.

Or you could just remove and insert, that takes O(1) additional time (compared to accessing and modifying) if insertion uses the position just before just after the old one as the hint.

Something like:

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

Don't try to solve this problem by working around the const-ness of items in a set. Instead, why not use map, which already expresses the key-value relationship you are modeling and provides easy ways to update existing elements.

Answer 3

Make val mutable as:

mutable int val;

Now you can change/modify/mutate val even if foo is const:

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

By the way, from your code, you seem to think that if p.second is true, then the value already existed in the set, and therefore you update the associated value. I think, you got it wrong. It is in fact other way round. The doc at cpluscplus says,

The pair::second element in the pair is set to true if a new element was inserted or false if an element with the same value existed.

which is correct, in my opinion.

---

However, if you use std::map, your solution would be straightforward:

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

What does this code do? m[value.first] creates a new entry if the key doesn't exist in the map, and value of the new entry is default value of int which is zero. So it adds value.second to zero. Or else if the key exists, then it simply adds value.second to it. That is, the above code is equivalent to this:

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
    }
}

But this is too much, isn't it? It's performance is not good. The earlier one is more concise and very performant.

Answer 4

If you know what you're doing (the set elements are not const per se and you're not changing members involved in comparison), then you can just cast away const-ness:

void update(Set& s, Foo f) {
  std::pair<Set::iterator, bool> p = s.insert(f);
  bool alreadyThere = !p.second;
  if (alreadyThere)
  {
    Foo & item = const_cast<Foo&>(*p.first);
    item.val += f.val;
  }
}

Answer 5

Instead of separate hint, use the erase's return value for the next iterator position

bool alreadyThere = !p.second; 
if (alreadyThere)
{
    auto nit = s.erase(p.first);
    s.insert(nit, f);
}

Answer 6

you can use MAP witch has very fast access to your element if you have KEY . in this case i think using MAP would be better way to achieve fastest speed . STD::MAP