[MultIndex] Iterator/Range validity when modify entries.
Hi guys, While trying to implementing a new feature, I came across a question concerning iterator/range validity of boost::multi_index. To understand the question, here is my setup: <code> // Database entry. struct Entry { int key1; int key2; }; // Access-keys. struct Index1{}; struct Index2{}; using namespace boost::multi_index; using namespace boost; // The multi_index database. using Database = multi_index_container< Entry, indexed_by< hashed_non_unique< tag<Index1>, member<Entry, int, &Entry::key1> >, hashed_non_unique< tag<Index2>, member<Entry, int, &Entry::key2> >
;
Database db; /* ... Here db is getting filled. ... */ </code> I obtain a range of entries from that database with the same value for key1 through the first index and want to modify each single entry of that range. However, I will only modify key2 (which is only used as key in the other index)! My main question is now: Does modifying an entry invalidate my range although I do not modify the member that was used as key for obtaining the range? The code in question would possibly look like this: <code> auto& index1 = db.get<Index1>(); auto range = index1.equal_range(42); for (auto it = range.first; it != range.second; ++it) { index1.modify(it, [](Entry& entry) { entry.key2 = 123; // <---- Does this invalidate my range? // entry.key1 is not getting modified! }); } </code> My follow-up question is then: If the range is indeed invalidated, what would be a working solution for that problem? Incrementing the loop-iterator by hand before modifying the entry (and not letting the loop do it)? So, would the following be a valid solution? <code> auto& index1 = db.get<Index1>(); auto range = index1.equal_range(42); if (range.first != range.second) { auto it = range.first; auto end = --range.second; do { index1.modify(it++, [](Entry& entry) { entry.key2 = 123; // <---- Does this invalidate my range? // entry.key1 is not getting modified! }); while (it != end); } </code> Of course, neither do I want to iterate over an entry twice (and thereby modify it twice) nor do I want miss an entry. And one last question: Does this problem or its solution apply to all index-types or just to hashed indexes? Thanks for the clarification. Deniz PS: Oh and by the way: Boost.MultiIndex is a really cool library. :-)
El 08/09/2016 a las 18:22, Deniz Bahadir escribió:
Hi guys,
[...]
My main question is now: Does modifying an entry invalidate my range although I do not modify the member that was used as key for obtaining the range?
The code in question would possibly look like this:
<code>
auto& index1 = db.get<Index1>(); auto range = index1.equal_range(42);
for (auto it = range.first; it != range.second; ++it) { index1.modify(it, [](Entry& entry) { entry.key2 = 123; // <---- Does this invalidate my range? // entry.key1 is not getting modified! }); }
</code>
Hi, You got lucky :-) if key1 is not modified, then the element maintains its position in Index1 and you can safely continue iterating. The reference guarantees that much: http://www.boost.org/libs/multi_index/doc/reference/hash_indices.html#modify "Postconditions: Validity of position is preserved if the operation succeeds. If the key of the modified value is equivalent to that of the original value, the position of the element does not change." The only potential problem would be if modify fails (i.e. it returns false) in which case the element is erased and the iterator is no longer valid: in your code this can't happen as Index2 (the index whose key you're changing) is non-unique.
My follow-up question is then: If the range is indeed invalidated, what would be a working solution for that problem?
This can only happen, as said above, when there is a collision (the index is unique and you've duplicated the key).
Incrementing the loop-iterator by hand before modifying the entry (and not letting the loop do it)? So, would the following be a valid solution?
<code>
auto& index1 = db.get<Index1>(); auto range = index1.equal_range(42);
if (range.first != range.second) { auto it = range.first; auto end = --range.second; do { index1.modify(it++, [](Entry& entry) { entry.key2 = 123; // <---- Does this invalidate my range? // entry.key1 is not getting modified! }); while (it != end); }
</code>
Yep, that'd do, but you don't really need to take this precaution here as already explained.
[...]
And one last question: Does this problem or its solution apply to all index-types or just to hashed indexes?
All index types provide the same guarantees wrt modify.
PS: Oh and by the way: Boost.MultiIndex is a really cool library. :-)
Thank you! Joaquín M López Muñoz
Am 08.09.2016 um 18:39 schrieb Joaquin M López Muñoz:
El 08/09/2016 a las 18:22, Deniz Bahadir escribió:
Hi Joaquín, [...]
You got lucky :-) if key1 is not modified, then the element maintains its position in Index1 and you can safely continue iterating. The reference guarantees that much:
http://www.boost.org/libs/multi_index/doc/reference/hash_indices.html#modify
Looking at the analog section of "replace", I assume I still would be lucky if the replaced entry would have the same value for key1. :-) [...]
The only potential problem would be if modify fails (i.e. it returns false) in which case the element is erased and the iterator is no longer valid: in your code this can't happen as Index2 (the index whose key you're changing) is non-unique.
My follow-up question is then: If the range is indeed invalidated, what would be a working solution for that problem?
This can only happen, as said above, when there is a collision (the index is unique and you've duplicated the key).
[...]
<code>
auto& index1 = db.get<Index1>(); auto range = index1.equal_range(42);
if (range.first != range.second) { auto it = range.first; auto end = --range.second; do { index1.modify(it++, [](Entry& entry) { entry.key2 = 123; // <---- Does this invalidate my range? // entry.key1 is not getting modified! }); while (it != end); }
</code>
Yep, that'd do, but you don't really need to take this precaution here as already explained.
So, just to make sure: This second solution would even work if Index2 is unique and I have a collision with key2 (as my example code would definitively have)? However, the side effect would be, that I end up erasing all elements of my range except for the first? (Or even erasing that first element, too, if the database already contains another element outside my range with that same value for key2.)
[...]
And one last question: Does this problem or its solution apply to all index-types or just to hashed indexes?
All index types provide the same guarantees wrt modify.
PS: Oh and by the way: Boost.MultiIndex is a really cool library. :-)
Thank you!
Joaquín M López Muñoz
Thank you very much, that was a really fast and satisfying answer. :-) Deniz
El 08/09/2016 a las 19:17, Deniz Bahadir escribió:
Am 08.09.2016 um 18:39 schrieb Joaquin M López Muñoz:
El 08/09/2016 a las 18:22, Deniz Bahadir escribió: So, just to make sure: This second solution would even work if Index2 is unique and I have a
collision with key2 (as my example code would definitively have)?
Correct. The only thing you have to be careful about is not to touch key1, as the element would be repositioned (according to the order of Index1) and your iterator would end up somewhere else within/outside the range.
However, the side effect would be, that I end up erasing all elements of my range except for the first? (Or even erasing that first element, too, if the database already contains another element outside my range with that same value for key2.)
Yes, if your changing the key produces a collision, the element is erased. Depending on your use case, you might want to consider other approaches: - replace() is passed a new element rather than let you change the existing one: if a collision would ensue, replace() does not change the original element. - There is a rollback-equipped version of modify() where you can undo collision-producing changes. Joaquín M López Muñoz
Am 08.09.2016 um 21:06 schrieb Joaquin M López Muñoz:
El 08/09/2016 a las 19:17, Deniz Bahadir escribió:
Am 08.09.2016 um 18:39 schrieb Joaquin M López Muñoz:
El 08/09/2016 a las 18:22, Deniz Bahadir escribió: So, just to make sure: This second solution would even work if Index2 is unique and I have a
collision with key2 (as my example code would definitively have)?
Correct. The only thing you have to be careful about is not to touch key1, as the element would be repositioned (according to the order of Index1) and your iterator would end up somewhere else within/outside the range.
However, the side effect would be, that I end up erasing all elements of my range except for the first? (Or even erasing that first element, too, if the database already contains another element outside my range with that same value for key2.)
Yes, if your changing the key produces a collision, the element is erased. Depending on your use case, you might want to consider other approaches:
- replace() is passed a new element rather than let you change the existing one: if a collision would ensue, replace() does not change the original element. - There is a rollback-equipped version of modify() where you can undo collision-producing changes.
Joaquín M López Muñoz
Thank you very much, Joaquín. This helps a lot. Deniz
participants (1)
-
Deniz Bahadir -
Deniz Bahadir -
Joaquin M López Muñoz