如何更新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;
}

有没有简洁的方法来做这个？还是我必须检查元素是否已经存在，如果存在，则删除它，添加值并重新插入？

- Frank

---

https://dev59.com/yXE95IYBdhLWcg3wp_kg - Ciro Santilli OurBigBook.com

可能是[C++ STL set更新很繁琐：我无法就地更改元素]的重复问题(https://dev59.com/yXE95IYBdhLWcg3wp_kg)。 - underscore_d

一个有点偏题的纠正：insert() 返回的 pair 的第二个成员具有相反的含义。当插入实际发生时，它是 true，而当元素已经存在时，它是 false。 - Alex Che

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

这意味着在逻辑上为const的Foo中val的值可能会改变，这意味着它不应该影响其他比较运算符等。

或者您可以只是删除和插入，如果插入使用位置旧位置之前的旧位置之后作为提示，则需要额外的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);
}

- Cubbi

---

有趣的是，在我对C++03和C++11标准的草案中发现，hint的含义在这两个版本之间发生了变化：在C++03中，表达式a.insert(p,t)（其中a是一个关联式容器，p是一个hint迭代器，t是要插入的值）必须具有一般情况下的对数复杂度，但如果t紧跟在p之后插入，则为平摊常数复杂度。这句话在C++11中进行了修改，现在规定复杂度应该是如果t紧跟在p之前插入，则为平摊常数复杂度（参见表69（C++03）和表102（C++11））。 - Luc Touraille

我刚刚发现这些评论，非常好地解释了为什么之前的版本是一个错误。 - Luc Touraille

@LucTouraille 这是否意味着，根据代码是否编译为C++11，将会有不同的行为？这是否正确？ - user362515

@LucTouraille 我指的是内部行为。答案应该更新，加入你提供的信息。谢谢！ - user362515

如果你看到像 std< { k; mutable v; } > 这样的模式，你一定要使用 map< k, v >。mutable 是一个不干净的解决方法。 - Tomilov Anatoliy

Answer 2

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

- Mark B

---

选择正确的容器解决正确的问题。 - austingae

偶尔我会遇到这些设计问题，但仍然没有找到一个好的解决方案。如果我的对象很简单，那么我可以使用 map 来管理它们。比如说，如果我的对象使用了 5 个属性进行排序，我可能需要将它们复制到一个元组中作为键。在某些情况下，可变策略是非常糟糕的。如果有人有好的想法，请在这里发帖。 - Kemin Zhou

@KeminZhou 可以使用 Boost.MultiIndex，它可以提供类似于 std::set 的容器并进行修改。 - Slava

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` 为真，则该值已存在于集合中，因此你更新关联值。我认为你理解错了。实际上是相反的。在 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
    }
}

但是这太多了，不是吗？它的性能不好。前面那个更加简洁而且非常高效。

- Nawaz

Answer 4

如果你知道你在做什么（集合元素本身并不是常量，并且你没有更改涉及比较的成员），那么你可以取消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;
  }
}

- Alex Che

Answer 5

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

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

- U J

Answer 6

如果你有键，你可以使用具有非常快速访问元素的MAP。在这种情况下，我认为使用MAP是实现最快速度的更好方式。STD :: MAP

- sam