Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > C++ > sets with different comparators have same iterator type; standard?

Reply
Thread Tools

sets with different comparators have same iterator type; standard?

 
 
Dan Tsafrir
Guest
Posts: n/a
 
      10-30-2005
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_runtime> s1; // holds N jobs ('int' = Job handle)
set<int,cmp_arrival> s2; // holds the same N jobs
... // etc.

set<int>::iterator 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>::iterator 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
>

 
Reply With Quote
 
 
 
 
Dan Tsafrir
Guest
Posts: n/a
 
      10-30-2005
Ali Çehreli wrote:
> How about:
>
> if (p == RUNTIME)
> {
> for_each(s1.begin(), /* ... */);
> }
> else if (/* ... */)
> {
> for_each(s2.begin(), /* ... */);
> }
> // 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 "polymorphic", whereas your alternative is not.

thanks,
--dan

 
Reply With Quote
 
 
 
 
Kai-Uwe Bux
Guest
Posts: n/a
 
      10-30-2005
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_runtime> s1; // holds N jobs
> set<Job,cmp_arrival> 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>::const_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_iterator 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

 
Reply With Quote
 
Dan Tsafrir
Guest
Posts: n/a
 
      10-30-2005
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_iterator 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
 
Reply With Quote
 
 
 
Reply

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
toward null-safe cookie cutter Comparators Roedy Green Java 40 12-12-2011 11:42 AM
Weird issue, same code, same browser, two different apache servers,very different css bluebaron HTML 3 11-04-2009 07:13 PM
running same script on same data on two different machines -->different result Christopher Brewster Python 5 11-14-2008 08:19 PM
same code produces different decimal symbol on different computers with same settings ASP General 2 12-29-2003 02:29 PM
Re: Cranking out Comparators Tim Robinson Java 3 08-06-2003 03:25 AM



Advertisments