Re: [Boost-users] [multiindex] hashed index, modify() and traversal

From: Joaquín Mª López Muñoz (joaquin_at_[hidden])
Date: 2006-10-27 03:31:57

Hi Francesco,

Francesco Biscani ha escrito:

> Hello,
>
> I'm modifying the elements of a multiindex container by accessing them through
> an hashed index (I suppose that this is faster than accessing them through
> the other index, which is ordered). I would like to know if I can keep going
> ++ on the hashed iterator as the elements of the container get changed,
> without modifying the same elements more than once or reaching the end()
> prematurely.

No, you can't.

> In other words, does the re-hash change the relative positions
> of the elements or are they unaltered as the elements are modified?

As soon as you modify() an element, this gets repositioned accordingly:
in ordered indices, to keep the ascending order; in hashed indices,
where the new hash code indicates. So, you can't rely on the traversal
order being preserved during a modify and traversal operation, except for
sequenced and random access indices.

Now, if you don't have a sequenced or random access index to base
your traversal on, you still can safely modify a range of elements
[first,last) as follows:

1. If you traverse an ordered index and the modifications on [first,last)
are *stable* in the following sense:

  given it0 in [first, last) and it1=++it0, after modifying *it0 the modified
  element is repositioned *outside* [it1,last),

then you can safely modify the range as you proposed originally. A
common case of stable modifier is one that changes the
associated key to a lower value, since modified elements will be
repositioned before the current iterator, for instance:

  for(it=first;it!=last;){
    // subtract 2 from current value
    m.modify(it++,boost::lambda::_1-=2);
  }

2. If you don't have an ordered index, only hashed indices, and/or your
modifying operation is not stable in the sense defined above, you can
prestore the original traversal order in an auxiliary external structure
and use that to make sure you visit all the elements exactly once, for
instance:

  typedef std::vector<iterator> buffer_type;
  buffer_type v;
  while(first!=last)v.push_back(first++);

  for(buffer_type::iterator it=v.begin();it!=v.end;){
    // add 2 to current value (not stable)
    i.modify(*it++,boost::lambda::_1-=2);
  }

This question was already discussed some months ago, please
take a look at

http://lists.boost.org/boost-users/2006/03/18048.php

where some working code is also provided (look for the attached
file jeff.cpp)

> Thanks  very much,
>
>   Francesco
>

HTH, please report back,

Joaquín M López Muñoz
Telefónica, Investigación y Desarrollo