更新 C + + std: : set 很乏味: 我不能在适当的位置更改元素

我发现在 std::set上的更新操作很乏味，因为在 首选上没有这样的 API。所以我现在做的是这样的:

//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，创建我自己的(我不知道它到底是如何工作的。.)

29666 次浏览
小开
最佳答案

set返回 const_iterators(标准说 set<T>::iterator是 const，而且 set<T>::const_iterator和 set<T>::iterator实际上可能是相同的类型——见 n3000.pdf 中的23.2.4/6) ，因为它是一个有序的容器。如果它返回一个常规的 iterator，您将被允许从容器下面更改项值，这可能会改变订单。

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

小开

您可能需要使用 std::map代替。使用影响键排序的 Element部分，并将所有 Element作为值。将会有一些小的数据重复，但是您将会有更容易(可能更快)的更新。

小开

更新: 虽然到目前为止下面的内容是正确的，但是这种行为被认为是 背叛，并且将在即将发布的标准版本中进行更改。真可怜。

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

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

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

小开

C + + 17介绍了 extract，参见 巴里的回答。

如果你坚持使用旧版本，有两种简单的方法可以做到:

  • 可以对不属于键的变量使用 mutable
  • 您可以将类拆分为 Key Value对(并使用 std::map)

现在的问题是这种棘手的情况: 当更新实际上修改了对象的 key部分时会发生什么？你的方法很有效，虽然我承认很无聊。

小开

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

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

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

小开

我在 C + + 11中遇到了同样的问题，在 C + + 11中，实际上 ::std::set<T>::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% 的情况下工作，甚至没有用户注意到之间的设置和实际类型的东西。

小开

在 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));

这将避免类型的额外副本和额外的分配/释放，并且还可以使用仅移动类型。

也可以按键返回 extract。如果没有键，则返回一个空节点:

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

提交答案