QMap/QHash operator[] returned reference validity

Question

I was wondering for how long the reference to a value inside a Qt container, especially a QHash or a QMap is valid. By valid I mean if it is guaranteed to still point to the correct location inside the map/hash after inserting or removing other elements.

Let's the following code:

QHash<char,int> dict; // or QMap<char,int> dict;
dict.insert('a', 1);
int& val(dict['a']);

dict.insert('b', 2);

val = 3;             // < will this work or lead to a segfault

Will setting the value at the last line correctly update the value associated with a to 3 or will it lead to a segfault or will it be undefined (so work sometimes, segfault other times, depending on whether the data structure had to be reorganized internally, like resizing of the hash-table array). Is the behavior the same for QMap and QHash, or will one work and the other not?

Dyspeptic

Answer 1

This is fully covered in the documentation — you must have missed it!

Iterators of both types are invalidated when the data in the container is modified or detached from implicitly shared copies due to a call to a non-const member function.

So, although I would expect iterators/references to remain valid in practice in the scenario you described above, you shall not rely on this. Using them in this way shall invoke Undefined Behaviour.

This holds for QHashIterator and QMutableHashIterator, as well as bare references. Beware of non-authoritative references claiming the opposite, relying on implementation details that may change at any time.

Wholesale

I did indeed miss that, as it talks about iterators and not references. Hence it could be that references stay valid, despite the iterators not being valid anymore, however this seems admitably unlikely. – Dyspeptic

@inflagranti: Iterator invalidation rules are universally applied to refs-to-elements also. This is because iterators dereference to references, and if you can no longer dereference your iterator to obtain a reference, then it stands to reason that any reference obtained from that iterator previously is no longer valid either. – Wholesale

@TomalakGeret'kal are you really sure about that? E.g., if the hash or map nodes indeed allocated the values on heap and reference those with a pointer, a reorganization of the hash would obviously render iterators (basically pointers to the nodes) invalid, however the referenced values could still be completely untouched. Actually, that would make a lot of sense w.r.t. omitting copying data around. So, I am not so sure about the iterator -> refernce generalization. There is just no statement about that. – Emanuele

@Tilman: If a pointer to something is invalidated, that's because the object it points to no longer exists. A reference to such an object would also be invalidated, by just the same token. References do not magically follow objects around. – Wholesale

@TomalakGeret'kal: Absolutely, but it doesn't refer to the question. You were previously generalizing the statement "the iterator gets invalidated" to "the pointer to the object stored at the iterator get invalidated". And I think, this generalization is not valid in general. Referring to the link in webclectic's answer, you'll see an example in QList<> where for big objects, the objects are indeed allocated on the heap and referenced from a pointer list. The pointers may move inside the pointer list, thus rendering iterators which point there invalid. However, the pointers stay fixed. – Emanuele

@TomalakGeret'kal continued: I.e. &*oldIt == &*newIt if oldIt and newIt refer to the same element before and after an iterator invalidating operation (e.g. insert at or before oldIt in a QList<>). – Emanuele

@Tilman: I agree, but in the absence of any documentation stating otherwise, I'm going to suggest that it's safest to presume that iterator -> pointer is a valid substitution in this case, going from high-level to low-level detail. I certainly wouldn't write code that presumes the opposite. – Wholesale

@TomalakGeret'kal: Ok, so we kind of agree. I still think, that strictly speaking any statement about whether iterators are preserved or not, doesn't say anything about the pointers to elments, because even if iterators stay valid, there could theoretically be the case that the iterator is updated behind the scenes or that the value storage gets reordered (garbage collected?) and thus pointers to elements get dangling. I just wished they put a guarantee on pointers into the interface because it seems to be technically there (for large elements) and is very useful in some cases. – Emanuele

Answer 2

There is nothing wrong with using references at QMap/QHash elements unless you delete the node you are referencing to. The elements of qt containers do not get reallocated every time a new elements is inserted. However I cannot see any good reason for using references to container elements.

For more details check this excellent article about qt containers internal implementation

Gloria

The reason to use references is that then there is no need to do a lockup in the dictionary again to change the value (which is especially useful if the value is a struct). – Dyspeptic

Thanks for the link! However, please note that the reference/pointer stability is indeed intricate: e.g. with QList<>, the implementation details make QList<BigClass> behave such that the pointers to elements are actually stable. However, pointers to elements in QList<SmallClass> or QList<SomeClass *> are /not/ stable because they are stored in the master list itself and not allocated on the heap. In essence, there is no statement/guarantee in the interfaces. – Emanuele