binary_function and bind1st

Discussion in 'C++' started by Denis Remezov, May 19, 2004.

  1. Greg Lilley wrote:
    >
    > I have an application where I want to remove all of the items that are
    > in one vector from a second vector. In the following short program, my
    > objective is to remove all of ourCards from cardsAvailable without
    > writing a loop.
    >
    > I have tried a number of different variations using the for_each
    > algorithm without success, and am currently getting a C2664 error that
    > the compiler cannot convert parameter 1. I am new to STL and not all
    > that adept with C++ either, so I'm sure there is something basic that
    > I am missing. Anyway, I have created the following short program to
    > demonstrate my problem. Any assistance will be greatly appreciated.
    >
    > // Remove Card test using STL
    >
    > #include <iostream> // for cout
    > #include <vector> // for vector
    > #include <algorithm> // for lower_bound, for_each
    > #include <functional> // for binary_function
    > using namespace std;
    >
    > //STL support functions or objects
    >
    > struct removeCard : public std::binary_function<vector<int>,int,void>
    > {
    > void
    > operator() (vector<int> & cardsAvailable, int cardToRemove )const
    > {
    > vector<int>::iterator iter;
    > iter = lower_bound(cardsAvailable.begin(),cardsAvailable.end(),
    > cardToRemove);
    >
    > if ( iter != cardsAvailable.end()) cardsAvailable.erase(iter);
    > }
    > };
    >
    > // To display contents of a container - For testing only
    > void print ( int element )
    > {
    > cout << element << ' ';
    > }
    >
    > int main()
    > {
    > vector<int> ourCards;
    >
    > // add two cards to ourCards vector
    > ourCards.push_back(10);
    > ourCards.push_back(20);
    >
    > vector<int> cardsAvailable;
    > vector<int>::iterator iter;
    >
    > // initialize cardsAvailable with all 52 cards
    > for ( int i = 0; i < 52; ++i) cardsAvailable.push_back(i);
    >
    > // remove all of our cards from the deck
    > for_each( ourCards.begin(), ourCards.end(), // range
    > bind1st(removeCard(),cardsAvailable) ); // operation
    >
    > // display all of the remaining cards in the deck
    > for_each( cardsAvailable.begin(), cardsAvailable.end(), print );
    >
    > return 0;
    > }
    >

    [snip]

    As Victor said, you can't use a non-const reference with bind1st.
    You could do otherwise, but as a dirty cheap fix (I'm curious if anyone
    thinks it's a stylistic kludge) I'd change to binding a pointer to a vector:

    struct removeCard : public std::binary_function<vector<int>*, int, void> {
    void operator() (vector<int>* p_cardsAvailable, int cardToRemove) const {
    vector<int>::iterator iter;
    iter = lower_bound(p_cardsAvailable->begin(), p_cardsAvailable->end(),
    cardToRemove);

    if ( iter != p_cardsAvailable->end()) p_cardsAvailable->erase(iter);
    }
    };

    .... and the usage in main() is:

    for_each( ourCards.begin(), ourCards.end(), // range
    bind1st(removeCard(), &cardsAvailable) ); // operation


    Denis
     
    Denis Remezov, May 19, 2004
    #1
    1. Advertising

  2. Denis Remezov

    Greg Lilley Guest

    I have an application where I want to remove all of the items that are
    in one vector from a second vector. In the following short program, my
    objective is to remove all of ourCards from cardsAvailable without
    writing a loop.

    I have tried a number of different variations using the for_each
    algorithm without success, and am currently getting a C2664 error that
    the compiler cannot convert parameter 1. I am new to STL and not all
    that adept with C++ either, so I'm sure there is something basic that
    I am missing. Anyway, I have created the following short program to
    demonstrate my problem. Any assistance will be greatly appreciated.

    // Remove Card test using STL

    #include <iostream> // for cout
    #include <vector> // for vector
    #include <algorithm> // for lower_bound, for_each
    #include <functional> // for binary_function
    using namespace std;


    //STL support functions or objects

    struct removeCard : public std::binary_function<vector<int>,int,void>
    {
    void
    operator() (vector<int> & cardsAvailable, int cardToRemove )const
    {
    vector<int>::iterator iter;
    iter = lower_bound(cardsAvailable.begin(),cardsAvailable.end(),
    cardToRemove);

    if ( iter != cardsAvailable.end()) cardsAvailable.erase(iter);
    }
    };

    // To display contents of a container - For testing only
    void print ( int element )
    {
    cout << element << ' ';
    }

    int main()
    {
    vector<int> ourCards;

    // add two cards to ourCards vector
    ourCards.push_back(10);
    ourCards.push_back(20);

    vector<int> cardsAvailable;
    vector<int>::iterator iter;

    // initialize cardsAvailable with all 52 cards
    for ( int i = 0; i < 52; ++i) cardsAvailable.push_back(i);

    // remove all of our cards from the deck
    for_each( ourCards.begin(), ourCards.end(), // range
    bind1st(removeCard(),cardsAvailable) ); // operation

    // display all of the remaining cards in the deck
    for_each( cardsAvailable.begin(), cardsAvailable.end(), print );

    return 0;
    }

    // Error message from compiler follows

    /*

    Compiling...
    RemoveCard.cpp
    C:\Program Files\Microsoft Visual Studio .NET
    2003\Vc7\include\functional(279) :
    error C2664: 'void removeCard::eek:perator ()(std::vector<_Ty> &,int)
    const' :
    cannot convert parameter 1 from 'const
    std::binary_function<_Arg1,_Arg2,
    _Result>::first_argument_type' to 'std::vector<_Ty> &'
    with
    [
    _Ty=int
    ]
    and
    [
    _Arg1=std::vector<int>,
    _Arg2=int,
    _Result=void
    ]
    and
    [
    _Ty=int
    ]
    Conversion loses qualifiers
    C:\Program Files\Microsoft Visual Studio .NET
    2003\Vc7\include\functional(278) :
    while compiling class-template member function
    'std::binder1st<_Fn2>::result_type
    std::binder1st<_Fn2>::eek:perator ()(std::binder1st<_Fn2>::argument_type
    &) const'
    with
    [
    _Fn2=removeCard
    ]
    RemoveCard.cpp(52) : see reference to class template instantiation
    'std::binder1st<_Fn2>' being compiled
    with
    [
    _Fn2=removeCard
    ]

    */
     
    Greg Lilley, May 19, 2004
    #2
    1. Advertising

  3. Greg Lilley wrote:
    > I have an application where I want to remove all of the items that are
    > in one vector from a second vector. In the following short program, my
    > objective is to remove all of ourCards from cardsAvailable without
    > writing a loop.
    >
    > I have tried a number of different variations using the for_each
    > algorithm without success, and am currently getting a C2664 error that
    > the compiler cannot convert parameter 1. I am new to STL and not all
    > that adept with C++ either, so I'm sure there is something basic that
    > I am missing. Anyway, I have created the following short program to
    > demonstrate my problem. Any assistance will be greatly appreciated.
    >
    > // Remove Card test using STL
    >
    > #include <iostream> // for cout
    > #include <vector> // for vector
    > #include <algorithm> // for lower_bound, for_each
    > #include <functional> // for binary_function
    > using namespace std;
    >
    >
    > //STL support functions or objects
    >
    > struct removeCard : public std::binary_function<vector<int>,int,void>
    > {
    > void
    > operator() (vector<int> & cardsAvailable, int cardToRemove )const
    > {
    > vector<int>::iterator iter;
    > iter = lower_bound(cardsAvailable.begin(),cardsAvailable.end(),
    > cardToRemove);
    >
    > if ( iter != cardsAvailable.end()) cardsAvailable.erase(iter);
    > }
    > };
    >
    > // To display contents of a container - For testing only
    > void print ( int element )
    > {
    > cout << element << ' ';
    > }
    >
    > int main()
    > {
    > vector<int> ourCards;
    >
    > // add two cards to ourCards vector
    > ourCards.push_back(10);
    > ourCards.push_back(20);
    >
    > vector<int> cardsAvailable;
    > vector<int>::iterator iter;
    >
    > // initialize cardsAvailable with all 52 cards
    > for ( int i = 0; i < 52; ++i) cardsAvailable.push_back(i);
    >
    > // remove all of our cards from the deck
    > for_each( ourCards.begin(), ourCards.end(), // range
    > bind1st(removeCard(),cardsAvailable) ); // operation
    >
    > // display all of the remaining cards in the deck
    > for_each( cardsAvailable.begin(), cardsAvailable.end(), print );
    >
    > return 0;
    > }
    >
    > // Error message from compiler follows
    >
    > /*
    >
    > Compiling...
    > RemoveCard.cpp
    > C:\Program Files\Microsoft Visual Studio .NET
    > 2003\Vc7\include\functional(279) :
    > error C2664: 'void removeCard::eek:perator ()(std::vector<_Ty> &,int)
    > const' :
    > cannot convert parameter 1 from 'const
    > std::binary_function<_Arg1,_Arg2,
    > _Result>::first_argument_type' to 'std::vector<_Ty> &'
    > with
    > [
    > _Ty=int
    > ]
    > and
    > [
    > _Arg1=std::vector<int>,
    > _Arg2=int,
    > _Result=void
    > ]
    > and
    > [
    > _Ty=int
    > ]
    > Conversion loses qualifiers
    > C:\Program Files\Microsoft Visual Studio .NET
    > 2003\Vc7\include\functional(278) :
    > while compiling class-template member function
    > 'std::binder1st<_Fn2>::result_type
    > std::binder1st<_Fn2>::eek:perator ()(std::binder1st<_Fn2>::argument_type
    > &) const'
    > with
    > [
    > _Fn2=removeCard
    > ]
    > RemoveCard.cpp(52) : see reference to class template instantiation
    > 'std::binder1st<_Fn2>' being compiled
    > with
    > [
    > _Fn2=removeCard
    > ]
    >
    > */


    'binder1st' class requires its argument to be a _const_ reference. It
    might be the reason why it can't convert what it tries to convert.

    Victor
     
    Victor Bazarov, May 19, 2004
    #3
  4. Denis Remezov

    Siemel Naran Guest

    (Greg Lilley) wrote in message

    > I have an application where I want to remove all of the items that are
    > in one vector from a second vector. In the following short program, my
    > objective is to remove all of ourCards from cardsAvailable without
    > writing a loop.



    > struct removeCard : public std::binary_function<vector<int>,int,void>


    The first_argument_type is not vector<int> but rather vector<int>&.

    > {
    > void
    > operator() (vector<int> & cardsAvailable, int cardToRemove )const
    > {
    > vector<int>::iterator iter;
    > iter = lower_bound(cardsAvailable.begin(),cardsAvailable.end(),
    > cardToRemove);
    >
    > if ( iter != cardsAvailable.end()) cardsAvailable.erase(iter);
    > }
    > };


    > for_each( ourCards.begin(), ourCards.end(), // range
    > bind1st(removeCard(),cardsAvailable) ); // operation


    After changing the first_argument_type as above, I believe you'll run
    into the reference to reference problem. There may be a fix to the
    ANSI standard to fix this by making a reference to a reference be a
    reference.

    Please be aware that bind1st creates a copy of cardsAvailable, and it
    is this copy that changes. The simple fix is to use pointers. It
    should also fix your original problem.

    for_each( ourCards.begin(), ourCards.end(), // range
    bind1st(removeCard(),&cardsAvailable) ); // operation


    > struct removeCard : public std::binary_function<vector<int>,int,void>


    should be changed to

    struct removeCard : public
    std::binary_function<vector<int>*,int,void>

    Change operator() as appropriate.



    An alternative design is to make removeCard store a reference (or
    pointer) to cardsAvailable. It would have a constructor

    explicit removeCard::removeCard(std::vector<int>&);

    In this design you don't need binders.



    > iter = lower_bound(cardsAvailable.begin(),cardsAvailable.end(),
    > cardToRemove);


    As a minor optimization, if ourCards is sorted, then instead of
    cardsAvailable.begin() you could use the previous value of iter.
    Example: for 10, 20; once you find card 10 in cardsAvailable, to find
    card 20 you need only start searching cardsAvailable from card 10, not
    from the beginning. Don't know how you would do this with binders
    though.

    Have you considered using set functions like set_difference? As far
    as I know, they do employ extra storage. In other words, in

    set_difference(a.begin(), a.end(), b.begin(), b.end(), c.begin());

    'c' must be different from 'a'. Normally one might use
    std::back_inserter(c).

    Have you thought about exception safety? What if you are to remove 2
    cards 10 and 20 and you removed 10 and removing 20 throws an
    exception. What then? It is not necessary to fix this scenario right
    now, but at least be aware of it.

    Finally, removing an element from a vector is an O(N) operation, but
    removing from a list is O(1).
     
    Siemel Naran, May 20, 2004
    #4
  5. Denis Remezov

    Greg Lilley Guest

    Thanks very much to all of you for your responses. I've been wrestling
    with this problem for a long time and your comments were a big help.

    > An alternative design is to make removeCard store a reference (or
    > pointer) to cardsAvailable. It would have a constructor
    >
    > explicit removeCard::removeCard(std::vector<int>&);
    >
    > In this design you don't need binders.
    >
    >
    >
    > > iter = lower_bound(cardsAvailable.begin(),cardsAvailable.end(),
    > > cardToRemove);


    Thanks again. I was thinking there were probably some other approaches
    that were superior to what I was trying to do.


    >
    > As a minor optimization, if ourCards is sorted, then instead of
    > cardsAvailable.begin() you could use the previous value of iter.
    > Example: for 10, 20; once you find card 10 in cardsAvailable, to find
    > card 20 you need only start searching cardsAvailable from card 10, not
    > from the beginning. Don't know how you would do this with binders
    > though.


    I had thought of that, but like you, I didn't know how to do it with
    binders.

    >
    > Have you considered using set functions like set_difference? As far
    > as I know, they do employ extra storage. In other words, in
    >
    > set_difference(a.begin(), a.end(), b.begin(), b.end(), c.begin());
    >
    > 'c' must be different from 'a'. Normally one might use
    > std::back_inserter(c).



    No, I hadn't. I've never used set_difference before, and it hadn't
    occurred to me, but it sounds like its worth trying.

    > Finally, removing an element from a vector is an O(N) operation, but
    > removing from a list is O(1).


    Thanks. Speed is pretty important to me, so I'm going to think about
    the list idea as well.

    - Greg Lilley
     
    Greg Lilley, May 20, 2004
    #5
  6. Denis Remezov

    Siemel Naran Guest

    (Greg Lilley) wrote in message

    > > Finally, removing an element from a vector is an O(N) operation, but
    > > removing from a list is O(1).

    >
    > Thanks. Speed is pretty important to me, so I'm going to think about
    > the list idea as well.


    std::deque also has removing an element as O(1)
     
    Siemel Naran, May 21, 2004
    #6
  7. Denis Remezov

    P.J. Plauger Guest

    "Siemel Naran" <> wrote in message
    news:...

    > (Greg Lilley) wrote in message
    >
    > > > Finally, removing an element from a vector is an O(N) operation, but
    > > > removing from a list is O(1).

    > >
    > > Thanks. Speed is pretty important to me, so I'm going to think about
    > > the list idea as well.

    >
    > std::deque also has removing an element as O(1)


    Only if you remove from either end. Otherwise, it's no better than
    vector.

    P.J. Plauger
    Dinkumware, Ltd.
    http://www.dinkumware.com
     
    P.J. Plauger, May 21, 2004
    #7
    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. Marc
    Replies:
    6
    Views:
    693
    Denis Remezov
    Jul 6, 2004
  2. Alberto
    Replies:
    1
    Views:
    1,313
    Clark S. Cox III
    Feb 7, 2005
  3. news.online.no
    Replies:
    2
    Views:
    508
    Daniel T.
    Jan 30, 2006
  4. Dilip
    Replies:
    6
    Views:
    1,171
    Daniel T.
    May 27, 2006
  5. Christopher
    Replies:
    4
    Views:
    618
    James Kanze
    Nov 29, 2007
Loading...

Share This Page