如何更新std :: set的现有元素？

Question

我有一个std::set<Foo>,我想更新其中现有元素的一些值.请注意,我正在更新的值不会更改集合中的顺序:

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

有没有简洁的方法来做到这一点？或者我是否必须检查元素是否已存在,如果是,请将其删除,添加值并重新插入？

Answer 1

由于val没有参与比较,可以宣布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;
  }
};

这意味着值val可以在逻辑const Foo中改变,这意味着它不应该影响其他比较运算符等.

或者您可以删除和插入,如果插入使用刚好在旧提示之前的位置作为提示,则需要额外的O(1)时间(与访问和修改相比).

就像是:

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

不要试图通过解决一个项目的常量来解决这个问题set.相反,为什么不使用map,它已经表达了您正在建模的键值关系,并提供了更新现有元素的简便方法.

Answer 3

使val可变为:

mutable int val;

现在你可以改变/修改/变异,val即使foo是const:

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

顺便说一下,从您的代码中,您似乎认为如果p.second为true,那么该值已经存在于集合中,因此您更新了关联的值.我想,你弄错了.实际上它是其他方式.cpluscplus 的文档说,

如果插入新元素,则对中的pair :: second元素设置为true;如果存在具有相同值的元素,则设置为false.

在我看来,这是正确的.

但是,如果您使用std::map,您的解决方案将是直截了当的:

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

这段代码有什么作用？m[value.first]如果映射中不存在该键,则创建新条目,并且新条目的值的默认值int为零.所以它增加value.second了zero.否则,如果密钥存在,那么它只是添加value.second它.也就是说,上面的代码相当于:

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

但这太过分了,不是吗？它的表现并不好.较早的一个更简洁,非常高效.