I had a similar problem and I was confused too. All the sources I looked at indicated that std::unordered_set::find
can return a non-const iterator that dereferences to value_type&
, which is non-const
. On the other hand, all the above answers that state that changing field values within the instance changes its hash and therefore the way it is stored seem to make that impossible. It seems uncharacteristically "sloppy" for the spec to provide an interface that cannot be used, so there has to be a way to do something like what the questioner wants, and there is. You just have to give the compiler enough information to KNOW it's safe to provide you the non-const iterator. To further simplify the original question, we consider the following:
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
}
If you just use the default std::hash<student>
, it folds in all the data from the struct to create the hash - perhaps some combo of std::hash<std::string>(name)
and std::hash<double>(gpa)
. Regardless of how it uses all this data, the compiler behaves as if it incorporates all the data and that's the problem to which the other answers allude, namely that changing any part of record hashed changes its table index. The unordered_set
definition from the original question specifies "MeinHash", but we are not shown what it is, and if it factors in things that might be changed via an iterator, we're back to the problem described by the above answers. Typically though, not all the data in record is used to uniquely id an instance within a set. Let's say "name" is enough to disambiguate the student and gpa is just associated data that we may update. The constructor above strongly implies that, making the call to find
above dangerous. It will create a temp, using the constructor, assign a name and a gpa of 2.0, and then look up the student using BOTH pieces of information. If "edgar" was added to the set with a gpa of 3.0, his record will never be found, let alone updated by the operation on the iterator (which won't even compile). The compiler takes into account the whole lifespan of an iterator when inferring which override of find
to use, so if you use a naive hash function that includes all the fields of the struct, and the compiler sees you changing one of those fields, it "helps" you by failing at compile time. So the first thing you need to do is identify the fields that are truly intrinsic, and required for a hash, and which are not. Then you supply a hash function that uses only these fields - something like the following -
struct student_hash {
std::size_t operator()(const student& hashed_student) {
return std::hash<std::string>()(hashed_student.name);
}
};
For me (using clang), this was not quite enough - necessary, but not sufficient, but at least the compiler now knows that changing "gpa" will have no effect on the index of a record within hash table. I then had to use the mutable
keyword with the declaration of "gpa" to explicitly say to the compiler that this field can change without changing what we writer considers the state of this data. Typically, it's used for refcounts or master pointers and other kinds of meta-data not intrinsic to the state of the struct instance, but it applies here as well. So now we have -
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
}