Re: [Boost-users] [MultiIndex] Iterator validity when modifying equal_range keys

Subject: Re: [Boost-users] [MultiIndex] Iterator validity when modifying equal_range keys
From: Joaquin M Lopez Munoz (joaquin_at_[hidden])
Date: 2011-09-02 15:25:33

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#composite_key_result

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