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>::iterator beg = asc.begin(); // [*]
set<int,Des>::iterator end = asc.end(); // [*]
copy(beg, end, ostream_iterator<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

 

[Greg]

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>::iterator beg = asc.begin(); // [*]
set<int,Des>::iterator end = asc.end(); // [*]
copy(beg, end, ostream_iterator<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

This code is fine. std::copy does not require that the two iterators be
of the same type. In fact, they need not even belong to containers that
hold identical types - as long as the type being copied is convertible
to the output iterator's type.

So in this example, you could copy a set<int> to a set<long> or even a
set<double> and still be OK.

Greg

 

[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>::iterator beg = asc.begin(); // [*]
set<int,Des>::iterator end = asc.end(); // [*]
copy(beg, end, ostream_iterator<int>(cout, "")); // prints 123
return 0;
}

This code is fine. std::copy does not require that the two iterators be
of the same type. In fact, they need not even belong to containers that
hold identical types - as long as the type being copied is convertible
to the output iterator's type.

So in this example, you could copy a set<int> to a set<long> or even a
set<double> and still be OK.

the question is not about copy(), it's about [*] (the copy() is just there
to make the program meaningful). the problem with [*] is that the program
assigns an object of the type: set<int,Asc>::iterator
to an object of the type : set<int,Dec>::iterator

thanks,
--dan

 

[red floyd]

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>::iterator beg = asc.begin(); // [*]
set<int,Des>::iterator end = asc.end(); // [*]
copy(beg, end, ostream_iterator<int>(cout, "")); // prints 123
return 0;
}

Note 1: You Asc and Des functors have identical behavior.

Note 2: operator() in Asc and Des should be const methods, and
Asc and Desc should probably inherit from std::binary_function<>.

e.g.:

#include <functional>

struct Asc: public std::binary_function<int,int,bool>
{
bool operator()(int a, int b) const { return a < b; }
}

struct Des: public std::binary_function<int,int,bool>
{
// assumes you didn't want identical behavior for
// Asc and Des
bool operator()(int a, int b) const { return a > b; }
}

 

[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>::iterator beg = asc.begin(); // [*]
set<int,Des>::iterator end = asc.end(); // [*]
copy(beg, end, ostream_iterator<int>(cout, "")); // prints 123
return 0;
}

Note 1: You Asc and Des functors have identical behavior.

right you are (my mistake). nevertheless, they are different types.
regardless the question is about [*] in which the program assigns an
object of the type : set<int,Asc>::iterator

Note 2: operator() in Asc and Des should be const methods, and
Asc and Desc should probably inherit from std::binary_function<>.

e.g.:

#include <functional>

struct Asc: public std::binary_function<int,int,bool>
{
bool operator()(int a, int b) const { return a < b; }
}

struct Des: public std::binary_function<int,int,bool>
{
// assumes you didn't want identical behavior for
// Asc and Des
bool operator()(int a, int b) const { return a > b; }
}

unfortunately, this too is not related to my original question

--dan

 

[Greg]

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>::iterator beg = asc.begin(); // [*]
set<int,Des>::iterator end = asc.end(); // [*]
copy(beg, end, ostream_iterator<int>(cout, "")); // prints 123
return 0;
}

Note 1: You Asc and Des functors have identical behavior.

right you are (my mistake). nevertheless, they are different types.
regardless the question is about [*] in which the program assigns an
object of the type : set<int,Asc>::iterator

Note 2: operator() in Asc and Des should be const methods, and
Asc and Desc should probably inherit from std::binary_function<>.

e.g.:

#include <functional>

struct Asc: public std::binary_function<int,int,bool>
{
bool operator()(int a, int b) const { return a < b; }
}

struct Des: public std::binary_function<int,int,bool>
{
// assumes you didn't want identical behavior for
// Asc and Des
bool operator()(int a, int b) const { return a > b; }
}

unfortunately, this too is not related to my original question

I believe the answer is implementation-dependent depending on how
set<>::iterator is declared. If the code compiles - then the iterators
would have to be of the same type (usually declared in a red-black tree
class). Therefore since the code compiles for you, the assignments are
OK. I would just not expect them to be portable however.

Greg

 

[TIT]

Dan Tsafrir sade:

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>::iterator beg = asc.begin(); // [*]
set<int,Des>::iterator end = asc.end(); // [*]
copy(beg, end, ostream_iterator<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

The standard defines the implementation of iterators as implementation
defined. The above code doesn't compile with RW since that
implemenation of the underlying tree class is defined as:

template <class _Key, class _Val, class _KeyOf, class _Comp, class _Alloc>
class __rb_tree {
class iterator : public __it {};
};

but with STLport the class iterator is not nested within their
underlying tree class:

template <class _Value, class _Traits>
struct _Rb_tree_iterator : public _Rb_tree_base_iterator
{ };

template <class _Key, class _Value, class _KeyOfValue, class _Compare,
_STLP_DEFAULT_ALLOCATOR_SELECT(_Value) >
class _Rb_tree : public _Rb_tree_base<_Value, _Alloc> {

typedef _Rb_tree_iterator<value_type, _Nonconst_traits<value_type> >
iterator;

};

And _Compare is not used with the iterator template so your
code will compile using this implementation.

TIT

 

[Dan Tsafrir]

Dan Tsafrir sade:

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>::iterator beg = asc.begin(); // [*]
set<int,Des>::iterator end = asc.end(); // [*]
copy(beg, end, ostream_iterator<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

The standard defines the implementation of iterators as implementation
defined. The above code doesn't compile with RW since that
implemenation of the underlying tree class is defined as:

template <class _Key, class _Val, class _KeyOf, class _Comp, class _Alloc>
class __rb_tree {
class iterator : public __it {};
};

but with STLport the class iterator is not nested within their
underlying tree class:

template <class _Value, class _Traits>
struct _Rb_tree_iterator : public _Rb_tree_base_iterator
{ };

template <class _Key, class _Value, class _KeyOfValue, class _Compare,
_STLP_DEFAULT_ALLOCATOR_SELECT(_Value) >
class _Rb_tree : public _Rb_tree_base<_Value, _Alloc> {

typedef _Rb_tree_iterator<value_type, _Nonconst_traits<value_type> >
iterator;

};

And _Compare is not used with the iterator template so your
code will compile using this implementation.

TIT

Ok, I understand, it's implementation dependent.
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 do you think? I personally can't think of any reason why the above
shouldn't be made possible/standard. Am I missing something? is there
some other simple alternative I am not aware of?

thanks,
--dan

 

[Greg]

Dan Tsafrir sade:

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>::iterator beg = asc.begin(); // [*]
set<int,Des>::iterator end = asc.end(); // [*]
copy(beg, end, ostream_iterator<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

The standard defines the implementation of iterators as implementation
defined. The above code doesn't compile with RW since that
implemenation of the underlying tree class is defined as:

template <class _Key, class _Val, class _KeyOf, class _Comp, class _Alloc>
class __rb_tree {
class iterator : public __it {};
};

but with STLport the class iterator is not nested within their
underlying tree class:

template <class _Value, class _Traits>
struct _Rb_tree_iterator : public _Rb_tree_base_iterator
{ };

template <class _Key, class _Value, class _KeyOfValue, class _Compare,
_STLP_DEFAULT_ALLOCATOR_SELECT(_Value) >
class _Rb_tree : public _Rb_tree_base<_Value, _Alloc> {

typedef _Rb_tree_iterator<value_type, _Nonconst_traits<value_type> >
iterator;

};

And _Compare is not used with the iterator template so your
code will compile using this implementation.

TIT

Ok, I understand, it's implementation dependent.
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 do you think? I personally can't think of any reason why the above
shouldn't be made possible/standard. Am I missing something? is there
some other simple alternative I am not aware of?

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.

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

 

[=?iso-8859-1?Q?Ali_=C7ehreli?=]

Dan Tsafrir sade:

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>::iterator beg = asc.begin(); // [*]
set<int,Des>::iterator end = asc.end(); // [*]
copy(beg, end, ostream_iterator<int>(cout, "")); // prints 123
return 0;
}

[...]
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.

Would keeping the jobs in one place, and having sets of iterators work for
you application?

typedef vector<Job> Jobs;
Jobs jobs;

typedef set<Jobs::iterator, cmp_runtime> S1;
typedef set<Jobs::iterator, cmp_arrival> S2;

Now the iterators stored in S1 and S2 are the same type.

(Of course cmp_runtime and cmp_arrival now take Jobs::iterator types.)

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...
}

How about:

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

Ali

 

[Dan Tsafrir]

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

 

[Dan Tsafrir]

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

 

[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_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

 

[Dan Tsafrir]

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