Dan Tsafrir wrote:
> Hello,
>
> While obviously not standard, this email suggests the answer to the question
> appearing in the subject should be "yes". Indeed, the following cleanly compiles
> and runs when using gcc-4.0.1:
>
>         set<int,cmp_runtime>  s1;    // holds N jobs (int = job handle)
>         set<int,cmp_arrival>  s2;    // holds the same N jobs
>         ...                          // s3, s4, s5... etc.
>
>         set<int>::iterator beg, end;
>
>         // beg/end assignment can be O(1) using the "factory" design pattern:
>         if     ( p == RUNTIME ) {  beg = s1.begin(); end = s1.end(); }
>         else if( p == ARRIVAL ) {  beg = s2.begin(); end = s2.end(); }
>         else if( p == ...     ) {  //...                             }
>
>         for(set<int>::iterator i=beg; i!=end; ++i)
>             // do whatever...
>
> Unfortunately, this code is implementation-defined, e.g. because we
> assign an object of the type   :  set<int,cmp_runtime>::iterator
> (as returned from s1.begin())
> into 'beg' which is of the type:  set<int            >::iterator.
> These types are the same for the gcc distribution (and also for
> STLPort), but may not be for other distributions (e.g. when 'iterator'
> is a nested class of 'set').
>
> The above piece of code can be very useful in the common scenario
> where several container<T>-s order the same object collection in
> various ways. To the best of my understanding, the portable
> alternative of the above 'for' mandates defining a "base" iterator
> class to be the type of 'i', and wrapping all the set<int,cmp*>::iterator
> types using an associated sub-class. The price of this alternative
> is of course that the iteration code may no longer be inlined.
> Several alternatives exist but to the best of my knowledge suffer from
> similar or other deficiencies.
>
> Is there an inherent reason why the above shouldn't be made standard?
> (I failed to find previous postings on the subject).
> If so, I suggest considering adding to STL a requirement like:
>     TYPE[ container<T,cmp*1*>::iterator ] =
>     TYPE[ container<T,cmp*2*>::iterator ]
> (as it seems there's nothing to loose and a lot to be gained by adding it).
> I think the same argument may also be applied to other template parameters
> namely allocators.

The idea here as I understand it is to guarantee that two containers of
the same type each holding the same type of object would then also have
to offer iterators of matching types. The benefit by mandating what are
essentially interchangeable iterators, between say:

    std::set<int, std::less<int> >

and a:

    std::set<int, std::greater<int> >

is that a program could then treat each container as the same type for
the purposes of iterating its contents. While generic programming
certainly has value, distinct typing has some value as well. In this
case, the distinct iterator types make it less likely that the program
would ever compare iterators from different containers or - worse - try
to iterate between two such mismatched iterators.

There are really two solutions that readily suggest themselves: the
first is the one proposed: ensure that the iterators are sufficiently
generic. The other approach would be not to require generic iterators
but to call a set of more generic routines. These routines would
operate at the necessary level of abstraction - that is, not at the
iterator level, but at the level of the containers themselves.

Here is the reason that I think that a set of container-based
algorithms would be useful: if one were to survey how iterators are
commonly used today, I think that one pattern would dominate. A great
proportion of the time a program simply calls begin() to the end() in
order to iterate over all of a container's items.

Now wherever a certain programming idiom keeps recurring in source
code, I believe that there is likely to be an opportunity for further
abstraction. I think that iterating the entire contents of a container
is one such case. The idea would be to call a set of generic routines
that operate with containers in much the same way that the routines in
<algorithm> work with iterators. A set of container algorithms would be
able to capture the generic traits that containers share, without being
tripped up by unimportant differences such as differing comparators.

Along these lines it is possible to imagine a Container algorithm to,
say, apply a function to each item in a Container:

    template <class Container, class Function>
    void for_each_item( Container c, Function f)
    {
        std::for_each(c.begin(), c.end(), f);
    }

A great many of the routines in <algorithm> could easily have
Container-accepting equivalents. Perhaps it would be possible to write
a template function that would do so automatically - essentially using
the iterator template functions as parameters to generate a set of
template functions implementing Container-based algorithms. I may have
to think some more on that last idea, it might have potential.

Greg

---
[ 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.jamesd.demon.co.uk/csc/faq.html                       ]

Dan Tsafrir wrote:

> [wants set<T,C1,A1>::iterator to be the same as set<T,C2,A2>::iterator]

A1 != A2 would mean that implementations cannot efficiently support
multiple, simultaneous pointer/reference models (proxy references, for
instance).

C1 != C2 would mean that implementations cannot efficiently change the
underlying structure for different comparisons.  If my implementation
supports partition_traits<C1>::max_size, and that tells me that
set<T,C1> will never have more than eight values, I may use a
specialized structure for small sets which is very different from (and
more efficient than) the RB tree I use for larger sets.

I must admit that I've never taken advantage of either of these, but
there are times that I would have, if they'd been available.

---
[ 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.jamesd.demon.co.uk/csc/faq.html                       ]