Re: [Boost-users] [MultiIndex] Iterator validity when modifying equal_range keys
Ovanes Markarian <om_boost <at> keywallet.com> writes:
Hello *,
reading this page
What page?
states only that iterator validity is preserved for hashed indices. I have a multi-index container with ordered_non_unique entries.
Iterator validity is preserved for all types of indices.
Is it safe to find a matching range and modify the keys there?
In general no, see above.
Here an example:
entry_data& entries = indexed; //get the view to the MI-Container
What is this supposed to do? Usually you get an index view using get(), which you're not using here.
for(iterator_range<entry_data::iterator> r
= entries.equal_range(boost::make_tuple(false)) ; !r.empty() ; r.advance_begin(1) ) { index_data d = r.front();
d.masked = true; entries.replace(r.begin(), d); }
Here updated d.masked field is a first member of the composite key. What happens if I do the update as shown upon?
This fails for two reasons: 1. After entries.replace(...), r.begin() points to a modified element that is out of its original range; hence, r is no longer a proper range (in this particular example, its begin iterator will point beyond its end iterator.) 2. As elements are reordered, some of them can potentially be relocated *before* r.end(), so even if you fix problem #1 you still can end up visiting elements twice.
Would it be more efficient to iterate backwards and do the update, since than all the elements will not be rearranged?
Not really, since other types of similar problems crop up. The following is a possible solution (using iterator pairs rather than ranges since ranges here seem to be more noisy that useful): std::pair<entry_data::iterator,entry_data::iterator> p= entries.equal_range(boost::make_tuple(false)); if(p.first!=p.second){ // non-empty range --(p.second); // solve problem #2 for(;;){ bool end=(p.first==p.second); index_data d=p.first; d.masked=true; entries.replace((p.first)++,d); //++ solves problem #1 if(end)break; } }
Is there also any way to use modify_key with composite index or are composite index key extractors always read-only?
composite_key extractors return an opaque type called composite_key_result that you might esentially trat as read-only: http://www.boost.org/libs/multi_index/doc/reference/key_extraction.html#comp... So the short answer is you can't use modify_key with composite keys. Joaquín M López Muñoz Telefónica, Investigación y Desarrollo
Hello thanks for your answers, please see my comments below.... On Fri, Sep 2, 2011 at 9:25 PM, Joaquin M Lopez Munoz <joaquin@tid.es>wrote:
Ovanes Markarian <om_boost <at> keywallet.com> writes:
Hello *,
reading this page
What page?
Sorry forgot to include the link. I assumed this page applies here: http://www.boost.org/doc/libs/1_46_1/libs/multi_index/doc/tutorial/indices.h...
states only that iterator validity is preserved for hashed indices. I have a multi-index container with ordered_non_unique entries.
Iterator validity is preserved for all types of indices.
Is it safe to find a matching range and modify the keys there?
In general no, see above.
Here an example:
entry_data& entries = indexed; //get the view to the MI-Container
What is this supposed to do? Usually you get an index view using get(), which you're not using here.
I thought I am getting an index view here. Isn't it done implicitly... Why am I suppose to use it than? The upper statement can be seen as: my_index_container_type::index<named_tag>::type& entries = indexed; If I am not suppose to do that this way, why does this code compile? I know the docs state I should use the my_index_container_type::get<...> member, by how is this construct should be different?
for(iterator_range<entry_data::iterator> r
= entries.equal_range(boost::make_tuple(false)) ; !r.empty() ; r.advance_begin(1) ) { index_data d = r.front();
d.masked = true; entries.replace(r.begin(), d); }
Here updated d.masked field is a first member of the composite key. What happens if I do the update as shown upon?
This fails for two reasons:
1. After entries.replace(...), r.begin() points to a modified element that is out of its original range; hence, r is no longer a proper range (in this particular example, its begin iterator will point beyond its end iterator.)
Ok, thanks...
2. As elements are reordered, some of them can potentially be relocated *before* r.end(), so even if you fix problem #1 you still can end up visiting elements twice.
Ok, this was also my doubt ;)
Would it be more efficient to iterate backwards and do the update, since than all the elements will not be rearranged?
Not really, since other types of similar problems crop up. The following is a possible solution (using iterator pairs rather than ranges since ranges here seem to be more noisy that useful):
std::pair<entry_data::iterator,entry_data::iterator> p= entries.equal_range(boost::make_tuple(false)); if(p.first!=p.second){ // non-empty range --(p.second); // solve problem #2 for(;;){ bool end=(p.first==p.second); index_data d=p.first; d.masked=true; entries.replace((p.first)++,d); //++ solves problem #1 if(end)break; } }
Is there also any way to use modify_key with composite index or are composite index key extractors always read-only?
composite_key extractors return an opaque type called composite_key_result that you might esentially trat as read-only:
http://www.boost.org/libs/multi_index/doc/reference/key_extraction.html#comp...
So the short answer is you can't use modify_key with composite keys.
Ok thanks for your help and a great lib! With Kind Regards, Ovanes
participants (2)
-
Joaquin M Lopez Munoz -
Ovanes Markarian