454,440 Members | 1,436 Online Need help? Post your question and get tips & solutions from a community of 454,440 IT Pros & Developers. It's quick & easy.

# sets with different comparators have same iterator type; standard?

 P: n/a 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 asc(arr, arr+3); set::iterator beg = asc.begin(); //[*] set::iterator end = asc.end(); //[*] copy(beg, end, ostream_iterator(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 Oct 27 '05 #1
13 Replies

 P: n/a Dan Tsafrir wrote: 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 asc(arr, arr+3); set::iterator beg = asc.begin(); //[*] set::iterator end = asc.end(); //[*] copy(beg, end, ostream_iterator(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 to a set or even a set and still be OK. Greg Oct 27 '05 #2

 P: n/a Dan Tsafrir wrote: 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 asc(arr, arr+3); set::iterator beg = asc.begin(); //[*] set::iterator end = asc.end(); //[*] copy(beg, end, ostream_iterator(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 struct Asc: public std::binary_function { bool operator()(int a, int b) const { return a < b; } } struct Des: public std::binary_function { // assumes you didn't want identical behavior for // Asc and Des bool operator()(int a, int b) const { return a > b; } } Oct 27 '05 #3

 P: n/a Greg wrote: Dan Tsafrir wrote: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 asc(arr, arr+3); set::iterator beg = asc.begin(); //[*] set::iterator end = asc.end(); //[*] copy(beg, end, ostream_iterator(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 to a set or even a set 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::iterator to an object of the type : set::iterator thanks, --dan Oct 27 '05 #4

 P: n/a red floyd wrote: Dan Tsafrir wrote: 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 asc(arr, arr+3); set::iterator beg = asc.begin(); //[*] set::iterator end = asc.end(); //[*] copy(beg, end, ostream_iterator(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::iterator to an object of the type: set::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 struct Asc: public std::binary_function { bool operator()(int a, int b) const { return a < b; } } struct Des: public std::binary_function { // 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 Oct 27 '05 #5

 P: n/a Dan Tsafrir wrote: red floyd wrote: Dan Tsafrir wrote: 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 asc(arr, arr+3); set::iterator beg = asc.begin(); //[*] set::iterator end = asc.end(); //[*] copy(beg, end, ostream_iterator(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::iterator to an object of the type: set::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 struct Asc: public std::binary_function { bool operator()(int a, int b) const { return a < b; } } struct Des: public std::binary_function { // 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 Oct 27 '05 #6

 P: n/a 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 asc(arr, arr+3); set::iterator beg = asc.begin(); //[*] set::iterator end = asc.end(); //[*] copy(beg, end, ostream_iterator(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 __rb_tree { class iterator : public __it {}; }; but with STLport the class iterator is not nested within their underlying tree class: template struct _Rb_tree_iterator : public _Rb_tree_base_iterator { }; template class _Rb_tree : public _Rb_tree_base<_Value, _Alloc> { typedef _Rb_tree_iterator > iterator; }; And _Compare is not used with the iterator template so your code will compile using this implementation. TIT Oct 27 '05 #7

 P: n/a TIT wrote: 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 asc(arr, arr+3); set::iterator beg = asc.begin(); //[*] set::iterator end = asc.end(); //[*] copy(beg, end, ostream_iterator(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 __rb_tree { class iterator : public __it {}; }; but with STLport the class iterator is not nested within their underlying tree class: template struct _Rb_tree_iterator : public _Rb_tree_base_iterator { }; template class _Rb_tree : public _Rb_tree_base<_Value, _Alloc> { typedef _Rb_tree_iterator > 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 s1; // holds N jobs set 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::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::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 Oct 27 '05 #8

 P: n/a Dan Tsafrir wrote: TIT wrote: 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 asc(arr, arr+3); set::iterator beg = asc.begin(); //[*] set::iterator end = asc.end(); //[*] copy(beg, end, ostream_iterator(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 __rb_tree { class iterator : public __it {}; }; but with STLport the class iterator is not nested within their underlying tree class: template struct _Rb_tree_iterator : public _Rb_tree_base_iterator { }; template class _Rb_tree : public _Rb_tree_base<_Value, _Alloc> { typedef _Rb_tree_iterator > 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 s1; // holds N jobs set 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::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::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 Oct 27 '05 #9

 P: n/a "Dan Tsafrir" wrote in message news:43**************@cs.huji.ac.il... TIT wrote: 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 asc(arr, arr+3); set::iterator beg = asc.begin(); //[*] set::iterator end = asc.end(); //[*] copy(beg, end, ostream_iterator(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 s1; // holds N jobs set 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 Jobs; Jobs jobs; typedef set S1; typedef set 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::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::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 Oct 27 '05 #10

 P: n/a 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 s1; // holds N jobs ('int' = Job handle) set s2; // holds the same N jobs ... // etc. set::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::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::iterator ] = type[ set::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 Oct 30 '05 #11

 P: n/a 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 Oct 30 '05 #12

 P: n/a 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 s1; // holds N jobs set 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::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::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 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 Oct 30 '05 #13

 P: n/a Kai-Uwe Bux wrote: what about something like this: #include 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 Oct 30 '05 #14

### This discussion thread is closed

Replies have been disabled for this discussion. 