binary_function and bind1st

[Greg Lilley]

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_fun ction<vector<in t>,int,void>
{
void
operator() (vector<int> & cardsAvailable, int cardToRemove )const
{
vector<int>::it erator iter;
iter = lower_bound(car dsAvailable.beg in(),cardsAvail able.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_b ack(10);
ourCards.push_b ack(20);

vector<int> cardsAvailable;
vector<int>::it erator 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(removeC ard(),cardsAvai lable) ); // 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\includ e\functional(27 9) :
error C2664: 'void removeCard::ope rator ()(std::vector< _Ty> &,int)
const' :
cannot convert parameter 1 from 'const
std::binary_fun ction<_Arg1,_Ar g2,
_Result>::first _argument_type' to 'std::vector<_T y> &'
with
[
_Ty=int
]
and
[
_Arg1=std::vect or<int>,
_Arg2=int,
_Result=void
]
and
[
_Ty=int
]
Conversion loses qualifiers
C:\Program Files\Microsoft Visual Studio .NET
2003\Vc7\includ e\functional(27 8) :
while compiling class-template member function
'std::binder1st <_Fn2>::result_ type
std::binder1st< _Fn2>::operator ()(std::binder1 st<_Fn2>::argum ent_type
&) const'
with
[
_Fn2=removeCard
]
RemoveCard.cpp( 52) : see reference to class template instantiation
'std::binder1st <_Fn2>' being compiled
with
[
_Fn2=removeCard
]

*/

[Victor Bazarov]

Re: binary_function and bind1st

Greg Lilley wrote:[color=blue]
> 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_fun ction<vector<in t>,int,void>
> {
> void
> operator() (vector<int> & cardsAvailable, int cardToRemove )const
> {
> vector<int>::it erator iter;
> iter = lower_bound(car dsAvailable.beg in(),cardsAvail able.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_b ack(10);
> ourCards.push_b ack(20);
>
> vector<int> cardsAvailable;
> vector<int>::it erator 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(removeC ard(),cardsAvai lable) ); // 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\includ e\functional(27 9) :
> error C2664: 'void removeCard::ope rator ()(std::vector< _Ty> &,int)
> const' :
> cannot convert parameter 1 from 'const
> std::binary_fun ction<_Arg1,_Ar g2,
> _Result>::first _argument_type' to 'std::vector<_T y> &'
> with
> [
> _Ty=int
> ]
> and
> [
> _Arg1=std::vect or<int>,
> _Arg2=int,
> _Result=void
> ]
> and
> [
> _Ty=int
> ]
> Conversion loses qualifiers
> C:\Program Files\Microsoft Visual Studio .NET
> 2003\Vc7\includ e\functional(27 8) :
> while compiling class-template member function
> 'std::binder1st <_Fn2>::result_ type
> std::binder1st< _Fn2>::operator ()(std::binder1 st<_Fn2>::argum ent_type
> &) const'
> with
> [
> _Fn2=removeCard
> ]
> RemoveCard.cpp( 52) : see reference to class template instantiation
> 'std::binder1st <_Fn2>' being compiled
> with
> [
> _Fn2=removeCard
> ]
>
> */[/color]

'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

[Denis Remezov]

Re: binary_function and bind1st

Greg Lilley wrote:[color=blue]
>
> 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_fun ction<vector<in t>,int,void>
> {
> void
> operator() (vector<int> & cardsAvailable, int cardToRemove )const
> {
> vector<int>::it erator iter;
> iter = lower_bound(car dsAvailable.beg in(),cardsAvail able.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_b ack(10);
> ourCards.push_b ack(20);
>
> vector<int> cardsAvailable;
> vector<int>::it erator 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(removeC ard(),cardsAvai lable) ); // operation
>
> // display all of the remaining cards in the deck
> for_each( cardsAvailable. begin(), cardsAvailable. end(), print );
>
> return 0;
> }
>[/color]
[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_fun ction<vector<in t>*, int, void> {
void operator() (vector<int>* p_cardsAvailabl e, int cardToRemove) const {
vector<int>::it erator iter;
iter = lower_bound(p_c ardsAvailable->begin(), p_cardsAvailabl e->end(),
cardToRemove);

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

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

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


Denis

[Siemel Naran]

Re: binary_function and bind1st

greg.lilley@dcj s.virginia.gov (Greg Lilley) wrote in message
[color=blue]
> 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.[/color]

[color=blue]
> struct removeCard : public std::binary_fun ction<vector<in t>,int,void>[/color]

The first_argument_ type is not vector<int> but rather vector<int>&.
[color=blue]
> {
> void
> operator() (vector<int> & cardsAvailable, int cardToRemove )const
> {
> vector<int>::it erator iter;
> iter = lower_bound(car dsAvailable.beg in(),cardsAvail able.end(),
> cardToRemove);
>
> if ( iter != cardsAvailable. end()) cardsAvailable. erase(iter);
> }
> };[/color]
[color=blue]
> for_each( ourCards.begin( ), ourCards.end(), // range
> bind1st(removeC ard(),cardsAvai lable) ); // operation[/color]

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(removeC ard(),&cardsAva ilable) ); // operation

[color=blue]
> struct removeCard : public std::binary_fun ction<vector<in t>,int,void>[/color]

should be changed to

struct removeCard : public
std::binary_fun ction<vector<in t>*,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::rem oveCard(std::ve ctor<int>&);

In this design you don't need binders.


[color=blue]
> iter = lower_bound(car dsAvailable.beg in(),cardsAvail able.end(),
> cardToRemove);[/color]

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_inser ter(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).

[Greg Lilley]

Re: binary_function and bind1st

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.
[color=blue]
> An alternative design is to make removeCard store a reference (or
> pointer) to cardsAvailable. It would have a constructor
>
> explicit removeCard::rem oveCard(std::ve ctor<int>&);
>
> In this design you don't need binders.
>
>
>[color=green]
> > iter = lower_bound(car dsAvailable.beg in(),cardsAvail able.end(),
> > cardToRemove);[/color][/color]

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

[color=blue]
>
> 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.[/color]

I had thought of that, but like you, I didn't know how to do it with
binders.
[color=blue]
>
> 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_inser ter(c).[/color]


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.
[color=blue]
> Finally, removing an element from a vector is an O(N) operation, but
> removing from a list is O(1).[/color]

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

- Greg Lilley

[Siemel Naran]

Re: binary_function and bind1st

greg.lilley@dcj s.virginia.gov (Greg Lilley) wrote in message
[color=blue][color=green]
> > Finally, removing an element from a vector is an O(N) operation, but
> > removing from a list is O(1).[/color]
>
> Thanks. Speed is pretty important to me, so I'm going to think about
> the list idea as well.[/color]

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

[P.J. Plauger]

Re: binary_function and bind1st

"Siemel Naran" <namespace@exci te.com> wrote in message
news:3de02e22.0 405202151.aa1b7 63@posting.goog le.com...
[color=blue]
> greg.lilley@dcj s.virginia.gov (Greg Lilley) wrote in message
>[color=green][color=darkred]
> > > Finally, removing an element from a vector is an O(N) operation, but
> > > removing from a list is O(1).[/color]
> >
> > Thanks. Speed is pretty important to me, so I'm going to think about
> > the list idea as well.[/color]
>
> std::deque also has removing an element as O(1)[/color]

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

P.J. Plauger
Dinkumware, Ltd.

http://www.dinkumware.com