10

出于测试目的，我创建了一个小 unordered_set 并尝试迭代该集合。该集合包含一个自己的类：

class Student {
private:
    int matrNr;
    string name;
public:
    Student( const int& matrNr = 0, const string& name = "" )
        : matrNr( matrNr ), name( name ) {}
    void setNr( const int& matrNr ) {
        this->matrNr = matrNr;
    }
...
};

我插入了一些元素并尝试在迭代期间更改对象：

unordered_set<Student, meinHash> meineHashTable;
meineHashTable.emplace( 12, "Fred" );
meineHashTable.emplace( 22, "Barney" );
meineHashTable.emplace( 33, "Wilma" );

for (int i = 0; i < meineHashTable.bucket_count(); i++) {
    cout << "Bucketnummer: " << i << endl;
    unordered_set<Student, meinHash>::local_iterator iter;  // not constant?!?

    if (meineHashTable.bucket_size( i ) > 0) {
        for (iter = meineHashTable.begin( i ); iter != meineHashTable.end( i ); iter++) {
            //const_cast<Student&>(*iter).setNr( 1234 );  //This does work
            iter->setNr( 1234 );  //This does not work
        }

    }
    else {
        cout << "An empty Bucket" << endl;
    }

}

我使用了 local_iterator（而不是 const_local_iterator），但我仍然无法更改对象。由于某些原因，迭代器仍然指向一个常量对象。

我现在的问题是：为什么会这样？如果普通迭代器引用一个 const 对象，那么 const 和非 const 迭代器有什么区别？

使用 VisualStudio 2013 和 minGW 测试。

提前感谢您的帮助:-)

编辑：哈希函子：

struct meinHash {
    size_t operator()( const Student& s ) {
        return s.getNr();
    }
};

对于将来有相同问题的该主题的发现者，如果您将 matrNr 更改为暴力，以下是一些示例输出：

const_cast<Student&>(*iter).setNr( 5 );

并尝试显示它：

unordered_set<Student, meinHash>::local_iterator iter = meineHashTable.find( 5 );
iter->display();

你可能会得到类似的东西：

桶号：0

一个空桶

桶数：1

Matrikelnummer: 5

姓名：威尔玛

桶数：2

一个空桶

桶数：3

一个空桶

桶数：4

Matrikelnummer: 5

姓名：弗雷德

桶数：5

一个空桶

桶数：6

Matrikelnummer: 5

姓名：巴尼

桶数：7

一个空桶

//不想要的输出;-)

Matrikel 号码：-842150451

姓名：

4

5 回答 5

19

两者都set具有unordered_set只读键。很容易看出为什么会这样 - 如果键值发生变化，数据结构会将其归档在错误的位置，您将无法再找到它。

根据您的示例，假设您的哈希函数仅返回该matrNr字段。当哈希值发生变化时，任何查找1234都将失败，因为该哈希桶中没有存储任何内容。

可以更改未用于制作哈希键的对象的某些部分，但这可能会导致难以追踪错误。标准委员会决定通过将整个密钥设置为 const. 来消除这种可能性。

有两种方法可以绕过这个限制。第一种是将键从值中分离出来，然后使用maporunordered_map代替。第二种是从集合中移除项目并在修改后重新插入。

于 2013-09-09T18:43:32.530 回答
7

他们重视 a set<K>is的类型const K，而对于 a map<K, T>it is pair<const K, T>; 无序版本同上。

迭代器使您可以访问value_type &，并且 const-iterator 可以访问const value_type &. 如您所见，两种迭代器类型都不能“撤消”键的常量。

密钥不可变的原因是它构成了底层数据结构的一个组成部分；更改密钥将需要不平凡的内部重新排列，这将导致各种问题（例如，非零计算复杂度（用于元素访问！），以及混淆的迭代器排序）。

于 2013-09-09T18:06:05.547 回答
1

unordered_set 是一种数据结构，您无法在不更改其位置的情况下修改项目。

非 const 迭代器在这里是 const，因为 STL 确实可以保护您免受如此明显的错误的影响。

如果您想修改 unordered_set 的项目，您必须将其删除并重新添加。

于 2013-09-09T18:04:38.350 回答
1

我有类似的问题，我也很困惑。我查看的所有来源都表明std::unordered_set::find可以返回一个取消引用的非常量迭代器value_type&，它是非const. 另一方面，上述所有答案都表明更改实例中的字段值会更改其哈希值，因此它的存储方式似乎使这成为不可能。规范提供一个无法使用的接口似乎一反常态地“草率”，所以必须有一种方法来做一些提问者想要的事情，而且确实存在。您只需向编译器提供足够的信息，就知道为您提供非常量迭代器是安全的。为了进一步简化原始问题，我们考虑以下内容：

struct student {
  std::string name;
  double gpa;

  // necessary for a decent member of a hash table. Compares all fields by default
  bool operator==(const student& other) const = default;

  student(const char* _name)
    : name(_name)
    , gpa(2.0) {}
};

std::unordered_set<student> student_set;

auto found = student_set.find("edgar"); // danger!! See note below
if (found != student_set.end()) {
  found->gpa = 4.0;  // <- compile failure here. "found" is of type const_iterator
}

如果您只使用默认值std::hash<student>，它会将结构中的所有数据折叠起来以创建散列 - 可能是std::hash<std::string>(name)和的一些组合std::hash<double>(gpa)。无论它如何使用所有这些数据，编译器的行为都好像它合并了所有数据，这就是其他答案所暗示的问题，即更改记录散列的任何部分都会更改其表索引。这unordered_set原始问题的定义指定了“MeinHash”，但我们没有看到它是什么，如果它考虑到可能通过迭代器改变的事情，我们就会回到上述答案所描述的问题。但是，通常情况下，并非记录中的所有数据都用于唯一标识集合中的实例。假设“姓名”足以消除学生的歧义，而 gpa 只是我们可能更新的关联数据。上面的构造函数强烈暗示，调用find以上危险。它将使用构造函数创建一个临时，分配一个名称和 2.0 的 gpa，然后使用这两条信息查找学生。如果将“edgar”添加到 gpa 为 3.0 的集合中，将永远找不到他的记录，更不用说由迭代器上的操作更新（甚至不会编译）。编译器在推断要使用哪个覆盖时会考虑迭代器的整个生命周期find，因此如果您使用包含结构的所有字段的简单哈希函数，并且编译器看到您更改了其中一个字段，它会“帮助“你在编译时失败了。因此，您需要做的第一件事是识别真正内在的、散列所需的字段，哪些不是。

struct student_hash {
   std::size_t operator()(const student& hashed_student) {
     return std::hash<std::string>()(hashed_student.name);
  }
};

对我（使用 clang）来说，这还不够——必要，但还不够，但至少编译器现在知道更改“gpa”不会影响哈希表中记录的索引。然后我不得不使用mutable带有“gpa”声明的关键字来明确告诉编译器这个字段可以改变而不改变我们认为这个数据的状态。通常，它用于引用计数或主指针以及其他类型的元数据，这些元数据不是结构实例状态所固有的，但它也适用于这里。所以现在我们有 -

struct student {
  std::string name;
  mutable double gpa;

  // indicates that a matching name means a hit
  bool operator==(const student& other) const {
    return name.compare(other.name) == 0;
  }

  student(const char* _name)
    : name(_name)
    , gpa(2.0) {}
};

std::unordered_set<student, student_hash> student_set;

auto found = student_set.find("edgar"); // will find "edgar" regardless of gpa
if (found != student_set.end()) {
  found->gpa = 4.0;  // <- no longer fails here. "found" is of type iterator
}
于 2019-04-03T02:19:54.710 回答
0

您可以将 const 类型转换为非常量类型。通过这个你'告诉编译器'你知道你在做什么，所以你确实应该知道你在做什么。

于 2020-09-07T09:48:26.673 回答