sets with different comparators have same iterator type; standard?

Discussion in 'C++' started by Dan Tsafrir, Oct 27, 2005.

  1. Dan Tsafrir

    Dan Tsafrir Guest

    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
     
    Dan Tsafrir, Oct 27, 2005
    #1
    1. Advertising

  2. Dan Tsafrir

    Greg Guest

    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<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
     
    Greg, Oct 27, 2005
    #2
    1. Advertising

  3. Dan Tsafrir

    Dan Tsafrir Guest

    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<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
     
    Dan Tsafrir, Oct 27, 2005
    #3
  4. Dan Tsafrir

    red floyd Guest

    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<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; }
    }
     
    red floyd, Oct 27, 2005
    #4
  5. Dan Tsafrir

    Dan Tsafrir Guest

    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<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
    to an object of the type: set<int,Dec>::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
     
    Dan Tsafrir, Oct 27, 2005
    #5
  6. Dan Tsafrir

    Greg Guest

    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<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
    > to an object of the type: set<int,Dec>::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
     
    Greg, Oct 27, 2005
    #6
  7. Dan Tsafrir

    TIT Guest

    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
     
    TIT, Oct 27, 2005
    #7
  8. Dan Tsafrir

    Dan Tsafrir Guest

    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<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
     
    Dan Tsafrir, Oct 27, 2005
    #8
  9. Dan Tsafrir

    Greg Guest

    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<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
     
    Greg, Oct 27, 2005
    #9
  10. "Dan Tsafrir" <> wrote in message
    news:...
    > 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<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
     
    =?iso-8859-1?Q?Ali_=C7ehreli?=, Oct 27, 2005
    #10
  11. Dan Tsafrir

    Dan Tsafrir Guest

    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
    >
     
    Dan Tsafrir, Oct 30, 2005
    #11
  12. Dan Tsafrir

    Dan Tsafrir Guest

    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
     
    Dan Tsafrir, Oct 30, 2005
    #12
  13. Dan Tsafrir

    Kai-Uwe Bux Guest

    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
     
    Kai-Uwe Bux, Oct 30, 2005
    #13
  14. Dan Tsafrir

    Dan Tsafrir Guest

    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
     
    Dan Tsafrir, Oct 30, 2005
    #14
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Tim Robinson

    Re: Cranking out Comparators

    Tim Robinson, Aug 4, 2003, in forum: Java
    Replies:
    3
    Views:
    489
    Roedy Green
    Aug 6, 2003
  2. Christopher Brewster
    Replies:
    5
    Views:
    357
    John Machin
    Nov 14, 2008
  3. bluebaron
    Replies:
    3
    Views:
    767
    Jonathan N. Little
    Nov 4, 2009
  4. Guest
    Replies:
    2
    Views:
    186
    Foo Man Chew
    Dec 29, 2003
  5. Roedy Green
    Replies:
    40
    Views:
    1,138
    Arved Sandstrom
    Dec 12, 2011
Loading...

Share This Page