sets with different comparators have same iterator type; standard?

[Dan Tsafrir]

is the following code standard? (cleanly compiles under g++-4.0.2):

struct Asc { bool operator()(int a, int b) {return a < b;} };
struct Des { bool operator()(int a, int b) {return b > a;} };
int main() {
int arr[] = {1, 2, 3};
set<int,Asc> asc(arr, arr+3);
set<int,Des>::i terator beg = asc.begin(); //[*]
set<int,Des>::i terator end = asc.end(); //[*]
copy(beg, end, ostream_iterato r<int>(cout, "")); // prints 123
return 0;
}

note that the types of the _sets_ in both sides of assignment[*] are
different due to their different comparators (Asc/Des). nevertheless,[*] seems to be standard as the template parameters of the iterator
are 'Key' and 'Distance' (not the 'Comparator'), and so the iterator
types are equal, right? [we use user defined template 'Comparator'
parameters (Des/Asc), so they don't have standard specialization,
which means we can be sure the 'Distance' type of the two iterators
is the same; the 'Key' type (int) is also obviously the same].

thanks,
--dan

[Dan Tsafrir]

Greg wrote:

The Comparator is a property of the container and not its iterator. In
other words, the Container arranges the items in a particular order and
uses the Comparator to determine that order. So any iterator that
traverses the container from beginning to end will encounter each
contained item in a just one specific order. Since the items can be
sorted in only one order per container at a time, it would take more
than just a different iterator to traverse the items in a different
order.
this is well understood. indeed, I have a few different set<>s, each
holding N *handles* to *the same* N objects. the set<>s differ only
in their comparators which indeed determine the order of the sets and
effect only the inserting / deleting / searching of elements, and
*in principle*, shouldn't (technically) effect the manner in which
iteration is conducted. that is, the order of the set<> is a
derivative of the manner in which elements were inserted: any
red-black tree (or other O(logN) containers) holding elements of type
T are in principle traversed in a similar manner that is not effected
by the comparator.

the bottom line is that all that stops the following code from being
portable (and thus usable):

set<int,cmp_run time> s1; // holds N jobs ('int' = Job handle)
set<int,cmp_arr ival> s2; // holds the same N jobs
... // etc.

set<int>::itera tor beg, end;
determine_order (&beg, &end); // beg/end set to s1.begin()/s2.end()
// or s2.begin()/s2.end()
// etc. and determine_order () is O(1).

for(set<int>::i terator i=beg; i!=end; ++i)
// do whatever

is the fact that nobody thinks it's appropriate to state the above in
the standard. that is, it seems the standard should explicitly say that
type[ set<int,cmp1>:: iterator ] = type[ set<int,cmp2>:: iterator ]
as there's (seems to be) nothing to loose and a lot to gain.

my current understanding is that we agree that the alternatives (using
a base iterator class and derived iterators, or the one you mentioned
below, which I'm not even sure solves the problem) are much more complex
and pricey in terms of performance. right?
if this is indeed the case, then I'll go ahead and suggest in comp.std.c++
to consider adding the above as a requirement of STL.

thanks,
--dan

Since the iterators of one container can be elements in another
Container, one solution would be to declare, say, a list with the
elements in one order, and then declare another list populated with the
iterators (or elements) of the first list, but sorted in a different
order. There would be some extra management involved in keeping the
sorted lists, but some savings as well gained by essentially sharing
the elements between more than one list.

Greg

[Dan Tsafrir]

Ali Çehreli wrote:

How about:

if (p == RUNTIME)
{
for_each(s1.beg in(), /* ... */);
}
else if (/* ... */)
{
for_each(s2.beg in(), /* ... */);
}
// etc.

Ali

see my response to Greg from a few minutes ago: the above
is an O(k) solution (where k = number of values of p) which
involves a lot of code repetition. in contrast, my suggestion
is O(1) and eliminates all the code repetition.
in other words, to the best of my understanding, my alternative
is "polymorphi c", whereas your alternative is not.

thanks,
--dan

[Kai-Uwe Bux]

Dan Tsafrir wrote:

[snip]

However, wouldn't it be great had such an iterator assignment been
standard? I'm suggesting this because it would have allowed iteration over
a collection of objects sorted according to an arbitrary criterion,
without the overhead of virtual function calls:

For example, assume you have a collection of N "Job" objects sorted
according to various criteria:

set<Job,cmp_run time> s1; // holds N jobs
set<Job,cmp_arr ival> s2; // holds the same N jobs
... // etc.

And you want some loop to iterate through the job collection according
to a criterion which is specified by a user parameter 'p'. Wouldn't being
able to do the following be very beneficial in terms of performance:

set<Job>::const _iterator beg, end;
if( p == RUNTIME ) {
beg = s1.begin();
end = s1.end();
}
else if( p == ARRIVAL ) {
beg = s2.begin();
end = s2.end();
}
else if( ... ) {
// ...
} // ...

for(set<Job>::c onst_iterator i=beg; i!=end; ++i) {
// do whatever...
}

Regrettably, the only alternative I can think of that will obtain the
above, involves inheritance and virtual function calls that turn out
to be very expensive in my application (the above loop is its kernel).

what about something like this:

#include <set>

struct Job {

int runtime;
int arrival;

};
bool cmp_runtime ( Job const & a, Job const & b ) {
return ( a.runtime < b.runtime );
}

bool cmp_arrival ( Job const & a, Job const & b ) {
return ( a.arrival < b.arrival );
}
typedef bool (*cmp_jobs) ( Job const &, Job const & );

typedef std::set< Job, cmp_jobs > JobSet;
typedef JobSet::const_i terator JobSetConstIter ;
int main ( void ) {
JobSet a ( cmp_runtime );
JobSet b ( cmp_arrival );

JobSetConstIter from = ( true ? a.begin() : b.begin() );
JobSetConstIter to = ( true ? a.end() : b.end() );
}
[snip]

Best

Kai-Uwe Bux

[Dan Tsafrir]

Kai-Uwe Bux wrote:

what about something like this:

#include <set>

struct Job {

int runtime;
int arrival;

};
bool cmp_runtime ( Job const & a, Job const & b ) {
return ( a.runtime < b.runtime );
}

bool cmp_arrival ( Job const & a, Job const & b ) {
return ( a.arrival < b.arrival );
}
typedef bool (*cmp_jobs) ( Job const &, Job const & );

typedef std::set< Job, cmp_jobs > JobSet;
typedef JobSet::const_i terator JobSetConstIter ;
int main ( void ) {
JobSet a ( cmp_runtime );
JobSet b ( cmp_arrival );

JobSetConstIter from = ( true ? a.begin() : b.begin() );
JobSetConstIter to = ( true ? a.end() : b.end() );
}

to the best of my understanding, as you use a pointer to the comparison
functor, you prevent the comparator code from being inlined. I think that
this might even be worse than defining and using a base-iterator-class :(

thanks,
--dan