Почему 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. Но дело в том, что я должен иметь возможность получить неконстантную ссылку для использования внутри цикла, поскольку сам набор не является константным. Я получаю ту же ошибку, если создаю функцию установки и использую ее в цикле.

Answer 1

Набор похож на карту без значений, только ключи. Поскольку эти ключи используются для дерева, которое ускоряет операции на множестве, они не могут измениться. Таким образом, все элементы должны быть постоянными, чтобы не нарушать ограничения базового дерева.

Answer 2

std::set использует содержащиеся в нем значения для формирования быстрой структуры данных (обычно красно-черного дерева). Изменение значения означает, что вся структура должна быть изменена. Итак, принуждая constНесс, std::set не позволяет вам перевести его в неиспользуемое состояние.

Answer 3

Из ссылки на cpp:

В наборе значение элемента также идентифицирует его (само значение является ключом типа T), и каждое значение должно быть уникальным. Значение элементов в наборе нельзя изменить один раз в контейнере (элементы всегда постоянны), но их можно вставить или удалить из контейнера.

Answer 4

Поведение - это дизайн.

Предоставление вам неконстантного итератора может вдохновить вас на изменение элемента в наборе; последующее итеративное поведение будет тогда неопределенным.

Обратите внимание, что стандарт C++ говорит, что set<T>::iterator является const так что старомодный путь до C++11 все равно не сработает.

Answer 5

Добавление ответа Нейта :

Набор похож на карту без значений, только ключи. Поскольку эти ключи используются для дерева, которое ускоряет операции над набором, они не могут изменяться. Таким образом, все элементы должны быть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.