C++ std::set 更新很乏味：我无法就地更改元素

Question

我发现 std::set 上的更新操作很乏味，因为 cppreference。所以我目前所做的事情是这样的：

//find element in set by iterator
Element copy = *iterator;
... // update member value on copy, varies
Set.erase(iterator);
Set.insert(copy);

基本上 Set 返回的迭代器是一个 const_iterator 并且你不能直接改变它的值。

有更好的方法吗？或者也许我应该通过创建自己的（我不知道它到底是如何工作的..）来覆盖 std::set

Answer 1

我在 C++11 中遇到了同样的问题，其中 ::std::set::iterator 确实是常量，因此不允许更改其内容，即使我们知道变换不会影响 < 不变量。您可以通过将 ::std::set 包装成 mutable_set 类型或为内容编写一个包装器来解决这个问题：

  template <typename T>
  struct MutableWrapper {
    mutable T data;
    MutableWrapper(T const& data) : data(data) {}
    MutableWrapper(T&& data) : data(data) {}
    MutableWrapper const& operator=(T const& data) { this->data = data; }
    operator T&() const { return data; }
    T* operator->() const { return &data; }
    friend bool operator<(MutableWrapper const& a, MutableWrapper const& b) {
      return a.data < b.data;
    }   
    friend bool operator==(MutableWrapper const& a, MutableWrapper const& b) {
      return a.data == b.data;
    }   
    friend bool operator!=(MutableWrapper const& a, MutableWrapper const& b) {
      return a.data != b.data;
    }   
  };

我发现这更简单，并且它可以在 90% 的情况下工作在这种情况下，用户甚至没有注意到集合和实际类型之间存在某些东西。

Answer 2

在某些情况下，这会更快：

std::pair<std::set<int>::iterator, bool> result = Set.insert(value);
if (!result.second) {
  Set.erase(result.first);
  Set.insert(value);
}

如果该值通常不在 std::set 中，那么这可以具有更好的性能。

Answer 3

set 返回 const_iterators （标准规定 set::iterator 是 const，并且 set::const_iterator 和 set::iterator 实际上可能是相同的类型 - 请参阅 23.2.4/6 n3000.pdf），因为它是一个有序的容器。如果它返回常规迭代器，您将被允许从容器下更改项目值，这可能会改变顺序。

您的解决方案是更改 set 中的项目的惯用方法。

Answer 4

C++17 引入了 extract，请参阅 Barry 的回答。

---

如果您坚持使用旧版本，有两种方法可以做到这一点，在简单的情况下：

• 您可以在不属于键的变量上使用 mutable
• 您可以将您的类拆分为一个 Key Value 对（并使用 std::map）

现在，问题是针对棘手的情况：更新实际时会发生什么修改对象的key部分？你的方法很有效，尽管我承认这很乏味。

Answer 5

在 C++17 中，您可以使用 extract()，感谢 P0083：

// remove element from the set, but without needing
// to copy it or deallocate it
auto node = Set.extract(iterator);
// make changes to the value in place
node.value() = 42;
// reinsert it into the set, but again without needing 
// to copy or allocate
Set.insert(std::move(node));

这将避免您的类型的额外副本和额外的分配/解除分配， 和也适用于仅移动类型。

您还可以通过按键提取。如果键不存在，这将返回一个空节点：

auto node = Set.extract(key);
if (node) // alternatively, !node.empty()
{
    node.value() = 42;
    Set.insert(std::move(node));
}

Answer 6

更新：尽管目前以下情况正确，但该行为被视为缺陷并将在即将发布的标准版本中进行更改。多么悲伤啊。

---

有几点使您的问题相当令人困惑。

1. 函数可以返回值，而类则不能。 std::set 是一个类，因此不能返回任何内容。
2. 如果您可以调用 s.erase(iter)，那么 iter 就不是 const_iterator。 erase 需要一个非常量迭代器。
3. 只要集合也是非常量，所有返回迭代器的 std::set 成员函数都会返回非常量迭代器。

只要更新不改变元素的顺序，您就可以更改集合中元素的值。下面的代码编译并运行得很好。

#include <set>

int main()
{
    std::set<int> s;
    s.insert(10);
    s.insert(20);

    std::set<int>::iterator iter = s.find(20);

    // OK
    *iter = 30;

    // error, the following changes the order of elements
    // *iter = 0;
}

如果您的更新更改了元素的顺序，则必须擦除并重新插入。

Answer 7

您可能想使用 std::map 来代替。使用 Element 中影响键排序的部分，并将所有 Element 作为值。将会有一些小的数据重复，但您将获得更容易（并且可能更快）的更新。