Re: [Boost-users] multi index sidx.relocate(sidx.end(), si) performance, legality

From: Joaquín Mª López Muñoz (joaquin_at_[hidden])
Date: 2006-04-03 09:28:02

Hello Bert,

bert hubert ha escrito:

> Hi People,
>
> Does anybody know if the code below, which relocates an interator to the
> end() of an index, is legal? I tried delving into the multi_index code but
> it is over my head.
>
> I ask this because begin() is typically valid as an iterator, but end()
> never is. The code does appear to work.

sidx.relocate(sidx.end(), si); // does this work?

This is perfectly legal and works as you expect. The confusion arises
with your claim that end() is not a valid iterator. I'm adopting the
following standard terminology:

1. Dereferenceable iterators are those for which *it has defined behavior.
2. Valid iterators are dereferenceable AND past-the-end iterators.

So, end() yields a valid iterator, though not a dereferenceable one. If
you look at the reference entry for relocate, it carefully states that:

  "void relocate(iterator position,iterator i);
  Requires: position is a valid iterator of the index. i is a valid
  dereferenceable iterator of the index."

So, you can use end() as "position", but not as the "i" argument.

[Digression:

I'd like to refer you to a place in the standard where the definition of
"valid iterator" is given, but alas there's no such a place, and iterator
validity is thus a concept without a definition. This is IMHO a defect in
the standard. You have a concise definition of iterator validty in SGI
docs, though:

http://www.sgi.com/tech/stl/InputIterator.html (section "Definitions")

As for the standard, there is a definition of "singularity" in 24.1/5 and
"valid iterator" can be interpreted as meaning "non-singular iterator";
except that a DR resolution of 2000 seems to break this implicit
understanding:

http://std.dkuug.dk/jtc1/sc22/wg21/docs/lwg-defects.html#208

and adds more confussion to the issue. See also http://tinyurl.com/ocvqn

End of digression]

> Also, would it be expensive? I think relocating in a sequenced index is
> about as expensive as swapping pointers, but I'm not sure.

This is extremely cheap as it only involves pointer swapping, no elements
are copied, assigned or swapped in the process.

HTH,

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