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

From: Joaquin M Lopez Munoz (joaquin_at_[hidden])
Date: 2006-10-27 15:28:42

Francesco Biscani <bluescarni <at> gmail.com> writes:

> 
> Hi Joaquín,
> 
> first of all thanks for your answers. I find your replies always very 
> helpful :)

Thank you :)

> I think I've understood what you mean. Just let me recap to see if I
> got it right.
> 
> 1. There are two ways to make sure a modification with traversal is 
> successful:
> 
> 2. I can traverse an index (hashed or ordered, it does not matter) to
> modify() all the elements of the container if I am sure that the
> modification does not change the representation of the elements with
> respect to the index I'm traversing on.
> 2a. For example, I can use the hashed index for traversing whenever
> I'm sure that the modifications won't change the hash value of the
> elements.
> 2b. Or I can use an ordered index whenever I'm sure that the
> modification does not change the position of the element in the
> binary search tree.

Correct. In the case of ordered indices, I'd phrase this as
"the modification does not change the relative order of the
element", since the binary search tree it's an implementation
detail after all --your statement about the binary search tree
is roughly but not entirely equivalent.

> 3. I can also traverse and modify an ordered index from top to
> bottom if I'm consistently modifying each element to place
> itself _higher_ in the tree than it was before. In the opposite
> way I can traverse bottom to top if I'm consistently modifying
> the element to be _lower_ in the tree.

As in the 2b I'd forget about the internal binary tree; for one,
you don't traverse the index from top to bottom, but from
the leftmost node (which usually is not at the top) to the
rightmost node. Your statement is IMHO correct if you do the
following substitutions:

top --> begin
bottom --> end
higher in the tree --> before
lower in the three --> after

> So, in my case I was using an hashed index traversal while I
> was changing the hash values. It's a no-go. However I also
> have an ordered index already  defined, and the modification I want
> to do does not change the ordering of elements. Hence the use of
> a sorted index for this purpose is safe.
> 
> Does this make sense? :)

Absolutely. If the modifications affect only the hash part and
do not change the ordering of elements, doing the traversal
through the ordered index is the way to go.

> Thanks again,
> 
>   Francesco

Happy mofiy()ing,

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