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

Question

我有一个 std::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;
}

是否有任何简洁的方法可以做到这一点？或者我是否必须检查该元素是否已经存在，如果是，则将其删除，添加值并重新插入？

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 的值可能会在逻辑常量 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;

现在，即使 foo 是 const，您也可以更改/修改/改变 val：

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

顺便说一句，从您的代码中，您可以似乎认为如果 p.second 为 true，则该值已存在于集合中，因此您更新关联的值。我想，你搞错了。事实上恰恰相反。 cpluscplus 的 doc 说，

如果插入了新元素，则pair::pair 中的第二个元素设置为 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
    }
}

但这太多了，不是吗？它的性能并不好。早期的更加简洁并且性能非常好。

Answer 4

如果您知道自己在做什么（集合元素本身不是 const 并且您没有更改参与比较的成员），那么您可以放弃 const 性：

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

不使用单独的提示，而是使用擦除的返回值作为下一个迭代器位置

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

Answer 6

如果您有 KEY ，您可以使用 MAP 女巫可以非常快速地访问您的元素。在这种情况下，我认为使用 MAP 是实现最快速度的更好方法。标准::地图