出于测试目的,我创建了一个小的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迭代器之间有什么不同?
使用Visual Studio 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();
你可能会得到类似的东西:
Bucketnummer:0
一个空桶
Bucketnummer:1
Matrikelnummer:5
姓名:威尔玛
Bucketnummer:2
一个空桶
Bucketnummer:3
一个空桶
Bucketnummer:4
Matrikelnummer:5
姓名:弗雷德
Bucketnummer:5
一个空桶
Bucketnummer:6
Matrikelnummer:5
姓名:巴尼
Bucketnummer:7
一个空桶
//不想要的输出;-)
Matrikelnummer:-842150451
name:
set
和unordered_set
都有只读键。很容易理解为什么会出现这种情况 - 如果关键值发生变化,数据结构会将其归档到错误的位置,您将无法再找到它。
根据您的示例,假设您的哈希函数只返回matrNr
字段。当哈希值更改时,对1234
的任何查找都将失败,因为该哈希桶中没有任何内容存储。
有可能更改未用于制作散列键的对象的某些部分,但这可能导致难以追踪错误。标准委员会决定通过制作整个密钥const来消除这种可能性。
围绕这种限制有两种方法。第一种是从值中拆分键,然后使用map
或unordered_map
。第二种是从集合中删除项目,并在修改后重新插入。
他们重视set<K>
的类型是const K
,而对于map<K, T>
它是pair<const K, T>
;对于无序版本同样如此。
迭代器使您可以访问value_type &
,以及const value_type &
的常量迭代器。如您所见,迭代器类型都不能“撤消”键的常量。
密钥不可变的原因是它构成了底层数据结构的组成部分;更改密钥将需要一个非平凡的内部重新排列,这将导致各种问题(例如,非零计算复杂性(对于元素访问!),以及混淆迭代器排序)。
unordered_set是一种数据结构,您无法在不更改其位置的情况下修改项目。
非const迭代器在这里是const'因为STL确实可以保护你免受这种明显的错误。
如果要修改unordered_set的项目,则必须将其删除并重新添加。
我有类似的问题,我也很困惑。我查看的所有资源都表明std::unordered_set::find
可以返回一个非常量迭代器,它解释为value_type&
,这是非const
。另一方面,所有上述答案都表明实例中的变化字段值会改变其散列,因此存储它的方式似乎使得这种情况变得不可能。对于规范来说,提供一个无法使用的界面似乎非常“草率”,所以必须有一种方法来做一些像提问者想要的东西,并且有。您只需向编译器提供足够的信息即可知道为非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”,但我们没有显示它是什么,如果它因可能通过迭代器改变的事物因素,我们回到上述答案描述的问题。通常,并非记录中的所有数据都用于唯一地标识集合中的实例。假设“name”足以消除学生的歧义,而gpa只是我们可能更新的关联数据。上面的构造函数强烈暗示,使对find
的调用变得危险。它将创建一个temp,使用构造函数,指定一个名称和2.0的gpa,然后使用两条信息查找学生。如果将“edgar”添加到具有3.0的gpa的集合中,则永远不会找到他的记录,更不用说通过迭代器上的操作更新(甚至不会编译)。在推断使用哪个find
覆盖时,编译器会考虑迭代器的整个生命周期,所以如果你使用包含结构的所有字段的朴素哈希函数,并且编译器看到你改变其中一个字段,它“帮助你“在编译时失败。因此,您需要做的第一件事是确定真正内在的字段,以及散列所需的字段,哪些不是。然后你提供一个只使用这些字段的哈希函数 - 如下所示 -
struct student_hash {
std::size_t operator()(const student& hashed_student) {
return std::hash<std::string>()(hashed_student.name);
}
};
对我来说(使用clang),这还不够 - 必要,但还不够,但至少编译器现在知道改变“gpa”对哈希表中记录的索引没有影响。然后我不得不使用mutable
关键字和“gpa”的声明来明确地告诉编译器这个字段可以改变而不改变我们作者认为这个数据的状态。通常,它用于refcounts或主指针以及结构实例状态不固有的其他类型的元数据,但它也适用于此处。所以现在我们有 -
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
}