为什么 std::set 似乎强制使用 const_iterator？

Question

考虑下面的简单程序，它尝试使用对集合中元素的非常量引用来迭代集合的值：

#include <set>
#include <iostream>

class Int
{
public:
   Int(int value) : value_(value) {}
   int value() const { return value_; }
   bool operator<(const Int& other) const { return value_ < other.value(); }
private:
   int value_;
};

int
main(int argc, char** argv) {
   std::set<Int> ints;
   ints.insert(10);
   for (Int& i : ints) {
      std::cout << i.value() << std::endl;
   }
   return 0;
}

编译时，我从 gcc 收到错误：

test.c: In function ‘int main(int, char**)’:
test.c:18:18: error: invalid initialization of reference of type ‘Int&’ from expression of type ‘const Int’  
for (Int& i : ints) {  
              ^  

是的，我知道我实际上并没有尝试修改 for 循环中的元素。但重点是我应该能够获得一个非常量引用在循环内使用，因为集合本身不是 const 限定的。如果我创建一个 setter 函数并在循环中使用它，我会得到同样的错误。

Answer 1

集合就像一张地图，没有值，只有键。由于这些键用于加速集合操作的树，因此它们无法更改。因此，所有元素都必须是 const 以防止底层树的约束被破坏。

Answer 2

std::set

使用包含的值形成快速数据结构（通常是红黑树）。改变一个值意味着整个结构需要改变。因此，强制

const

ness，

std::set

可以防止您将其推入不可用状态。

Answer 3

来自cpp参考：

在集合中，元素的值也标识了它（值为 本身就是 T 类型的键，并且每个值必须是唯一的。价值 集合中的元素一旦进入容器就无法修改（ 元素始终是const），但可以插入或删除它们 容器。

Answer 4

给你一个非常量迭代器可以激发你改变集合中的元素；随后的迭代行为将是未定义的。

请注意，C++ 标准规定

set<T>::iterator

是

const

，因此老式的 C++11 之前的方法仍然行不通。

Answer 5

nate的答案

：

集合就像一张地图，没有值，只有键。由于这些键用于加速集合操作的树，因此它们无法更改。因此，所有元素都必须是

const

，以防止底层树的约束被破坏。

C++17 中有新的

extract

 成员函数，因此 

const_cast 的替代方案可以是：

#include <iostream>
#include <string_view>
#include <set>

struct S
{
  int used_for_sorting;
  bool not_used_for_sorting;

  bool operator<(const S &rhs) const
  { return used_for_sorting < rhs.used_for_sorting; }
};

void print(std::string_view comment, const std::set<S> &data)
{
  std::cout << comment;
  for (auto datum : data)
    std::cout << " {" << datum.used_for_sorting
              << ',' << datum.not_used_for_sorting
              << '}';

  std::cout << '\n';
}

int main()
{
  std::set<S> cont = {{1, false}, {2, true}, {3, false}};

  print("Start:", cont);

  // Extract node handle and change key
  auto nh = cont.extract({1, false});
  nh.value().not_used_for_sorting = true;

  print("After extract and before insert:", cont);

  // Insert node handle back
  cont.insert(std::move(nh));

  print("End:", cont);
}

作为热修复可能很有用。一般来说，很难看出比

std::map

有什么优势。