I suggest that an alternate overload for many STL algorithms be
added with an new "iterator context" parameter.  For example:

template <class ran_iter_context, class cmp>
void sort(
  ran_iter_context &ic,
  typename ran_iter_context::rel_iterator begin,
  typename ran_inter_context::rel_iterator end,
  cmp c)
  { ... }

The usage for "ran_iter_context" would be:

ran_iter_context::rel_iterator -- relative iterator type
ran_iter_context::abs_iterator -- absolute iterator type
ran_iter_context::const_abs_iterator -- read-only
  absolute iterator type
ran_iter_context ic;
rel_iterator ri, ri2(ri);
ri = ri2;
abs_iterator ai(ic.abs(ri));
const_abs_iterator cai(ic.const_abs(ri));
. -- the usage of abs_iterator and const_abs_iterator and
  their instances would correspond to the current usage of
  read/write and read-only iterators (respectively).

To see why this might be useful, consider a dynamically-
sized random access container implemented as a static
array of pointers to dynamically allocated (but statically
sized) arrays of elements.  Suppose the size of the array
of pointers and the arrays of elements were both 64.
T & operator [] (size_t i) for this container would index
into the array of pointers using the index i >> 6 to
get the address of the array of elements.  It would index
into the array of elements using the index i & 0x3f .

A "context-free" or absolute iterator for this container
would need both the address of the container and
the index of the (current) element.  This iterator is
somewhat "fat", compared to the iterators of the
STL-defined containers, whose only data member is
a single pointer.  Algorithms like sort create a fair
number of iterator instances, so there is a potential
impact.

For the example container, a simple index 0 - 4095
could be used as the relative iterator, and the
address of the container could occur only (once) in
the iterator context.  If, in the algorithm implementation,
absolute iterators were instantiated only as short-
lived temporaries, memory and potentially
(iterator-copying-)time could be saved.  (Note that,
as an added advantage, pushing and poping
will not invalidate relative iterators for this
container.)

The current versions of the algorithms could
be defined in terms of the context-using versions
something like this:

template <
  class abs_iter, class const_abs_iter = abs_iter>
struct trival_abs_iterator
  {
    typedef abs_iter rel_iterator, abs_iterator;
    typedef const_abs_iter const _abs_iterator;
    static abs_iterator abs(rel_iterator ri)
      { return(ri); }
    static const_abs_iterator abs(rel_iterator ri)
      { return(ri); }
  };

.

template <class ran_iter, class cmp>
void sort(ran_iter begin, ran_iter end, cmp c)
  {
    trivial_abs_iterator<ran_iter> ic;
    sort<trivial_abs_iterator<ran_iter>, cmp>(
      ic, begin, end, c);
  }

Another relevant example might be a binary-search-
tree-based ordered associate container where each
tree node does not have a parent pointer (unlike
normal implementation of map and set).  For these
containers, the iterators would have to store pointers
to the nodes in the path from the current node to the
root.  The relative iterators could, in this case, be
pointers to the absolute iterators allocated by "new".

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.comeaucomputing.com/csc/faq.html                      ]