Generic indirection adaptor

[Matthias Kaeppler]

Hi,

as a result of my last posting about an adaption class template for
invoking algorithms on a container of iterators or pointers to elements
in another container, I have come up with this code:

#include <vector>
#include <functional>
#include <algorithm>
#include <iostream>

template< typename It, typename Pred >
class indirect_binary: public std::binary_function<It,It,bool>
{
public:
bool operator() (It lhs, It rhs) const {
return Pred() (*lhs, *rhs);
}
};

int main()
{
typedef std::vector<int> IntVec;
typedef IntVec::iterator IntVecIt;

std::vector<int> v1;
v1.push_back(5);
v1.push_back(2);

std::vector<int*> v2;
v2.push_back( &v1[0] );
v2.push_back( &v1[1] );

indirect_binary< int*, std::less<int> > fctor; // note the int*!
std::sort( v2.begin(), v2.end(), fctor );

std::vector<int*>::iterator it = v2.begin();
for( ; it != v2.end(); ++it )
{
std::cout << **it << std::endl;
}
}

Well, it works, output is: 2, 5.
However, you may have noticed that I instantiated the adaptor with int*
instead of IntVecIt. If I do the latter, I get tons of error messages:

deref.cpp: In function `int main()':
deref.cpp:25: error: no matching function for call to `

:ush_back(

int*)'
/usr/include/c++/3.3/bits/stl_vector.h:596: error: candidates are: void
std::vector<_Tp, _Alloc>:ush_back(const _Tp&) [with _Tp =
main()::IntVecIt, _Alloc = std::allocator<main()::IntVecIt>]
deref.cpp:26: error: no matching function for call to `

:ush_back(

int*)'
/usr/include/c++/3.3/bits/stl_vector.h:596: error: candidates are: void
std::vector<_Tp, _Alloc>:ush_back(const _Tp&) [with _Tp =
main()::IntVecIt, _Alloc = std::allocator<main()::IntVecIt>]
deref.cpp:31: error: conversion from `
__gnu_cxx::__normal_iterator<main()::IntVecIt*,
std::vector<main()::IntVecIt, std::allocator<main()::IntVecIt> > >' to
non-scalar type `__gnu_cxx::__normal_iterator<int**, std::vector<int*,
std::allocator<int*> > >' requested
deref.cpp:32: error: no match for 'operator!=' in 'it != std::vector<_Tp,
_Alloc>::end() [with _Tp = main()::IntVecIt, _Alloc =
std::allocator<main()::IntVecIt>]()'

And another question: Why do I have to take lhs and rhs by value in
operator() ? If I declare it taking const references, it won't compile
either.

I'd be glad for all your input, because I intend to use this template
class pretty often once it is finished, so I want it to be as robust as
possible.

 

[Chris Jefferson]

Hi,

as a result of my last posting about an adaption class template for
invoking algorithms on a container of iterators or pointers to elements
in another container, I have come up with this code:

#include <vector>
#include <functional>
#include <algorithm>
#include <iostream>

template< typename It, typename Pred >
class indirect_binary: public std::binary_function<It,It,bool>
{
public:
bool operator() (It lhs, It rhs) const {
return Pred() (*lhs, *rhs);
}
};

int main()
{
typedef std::vector<int> IntVec;
typedef IntVec::iterator IntVecIt;

std::vector<int> v1;
v1.push_back(5);
v1.push_back(2);

std::vector<int*> v2;
v2.push_back( &v1[0] );
v2.push_back( &v1[1] );

indirect_binary< int*, std::less<int> > fctor; // note the int*!
std::sort( v2.begin(), v2.end(), fctor );

std::vector<int*>::iterator it = v2.begin();
for( ; it != v2.end(); ++it )
{
std::cout << **it << std::endl;
}
}

Well, it works, output is: 2, 5.
However, you may have noticed that I instantiated the adaptor with int*
instead of IntVecIt. If I do the latter, I get tons of error messages:

Your comparison operators gets passed already-dereferenced iterators,
not the iterators themselves.

And another question: Why do I have to take lhs and rhs by value in
operator() ? If I declare it taking const references, it won't compile
either.

Strange, I changed your comparison function to:

bool operator() (const It& lhs, const It& rhs) const {

and it worked fine...

Did you mean something else?

Chris

 

[Matthias Kaeppler]

Your comparison operators gets passed already-dereferenced iterators,
not the iterators themselves.

What do you mean? Isn't IntVecIt in most cases just a typedef for int*
anyway? At least it is on my implementation. So:

bool operator() (It lhs, It rhs) {
return Pred() (*lhs, *rhs);
}

translates to:

bool operator() (int* lhs, int* rhs) {
return Pred() (*lhs, *rhs);
}

I can't see what's wrong with that.

 

[Chris Jefferson]

What do you mean? Isn't IntVecIt in most cases just a typedef for int*
anyway? At least it is on my implementation. So:

It isn't on my implementation (gcc 3.3.3). Assuming that it is is a big
no-no!

You can however given an iterator into a vector<int> do &*it and get an
int*. I'm not positive this is guaranteed by the standard, I remember
seeing a defect report about it and can't remember if it got accepted.
I've never seen an implementation where it didn't work.

Chris

 

[Matthias Kaeppler]

It isn't on my implementation (gcc 3.3.3). Assuming that it is is a big
no-no!

You can however given an iterator into a vector<int> do &*it and get an
int*. I'm not positive this is guaranteed by the standard, I remember
seeing a defect report about it and can't remember if it got accepted.
I've never seen an implementation where it didn't work.

Chris

Oh, okay. But is the design of the adaptor okay?

 

[Chris Jefferson]

Oh, okay. But is the design of the adaptor okay?

Yes, it's good

Chris

 

[Matthias Kaeppler]

Oh, one more question:
I want it to work with both functors and functions. However,
"overloading" a template doesn't seem to work (I tried to replace the
second template argument with a pointer to function returning bool and
taking two It::value_typeS).
This however, results in a redefinition error. Okay, so I renamed the
template and tried it this way:

template< typename It >
class indirect_binary_fn: public std::binary_function<It,It,bool>
{
bool (*pred)(It::value_type, It::value_type);
public:
indirect_binary_fn( bool (*f)(It::value_type, It::value_type) )
: pred(f) {}
bool operator() (const It& lhs, const It& rhs) const {
return pred(*lhs, *rhs);
}
};

Error:
deref.cpp:17: error: variable declaration is not allowed here
deref.cpp:19: error: variable declaration is not allowed here
deref.cpp: In constructor `indirect_binary_fn<It>::indirect_binary_fn()':
deref.cpp:19: error: class `indirect_binary_fn<It>' does not have any
field named `pred'

Why am I not allowed to declare that variable?

 

[Kurt Stutsman]

Oh, one more question:
I want it to work with both functors and functions. However,
"overloading" a template doesn't seem to work (I tried to replace the
second template argument with a pointer to function returning bool and
taking two It::value_typeS).
This however, results in a redefinition error. Okay, so I renamed the
template and tried it this way:

template< typename It >
class indirect_binary_fn: public std::binary_function<It,It,bool>
{
bool (*pred)(It::value_type, It::value_type);

This should be:
// to make life easier, use a typedef
typedef bool (*pred_fn)(typename It::value_type,
typename It::value_type);

pred_fn pred;

public:
indirect_binary_fn( bool (*f)(It::value_type, It::value_type) )
: pred(f) {}

Also:
indirect_binary_fn(pred_fn f) : pred(f) {}

bool operator() (const It& lhs, const It& rhs) const {
return pred(*lhs, *rhs);
}
};

There is a much better solution though, to allow for both functors and
functions to be called if you use the boost library:

template<class BinaryPredicate>
class indirect_binary_fn : public std::binary_function<typename
boost::binary_traits<BinaryPredicate>::first_argument_type,
typename
boost::binary_traits<BinaryPredicate>::second_argument_type,
bool> {
private:
typedef typename boost::binary_traits<BinaryPredicate> It;

BinaryPredicate pred;

public:
indirect_binary_fn(BinaryPredicate f) : pred(f) {}
bool operator() (const It& lhs, const It& rhs)const
{ return pred(*lhs, *rhs); }
};

typename boost::binary_traits<BinaryPredicate>::first_argument_type and
its brother second_argument_type allow you to get the argument types for
either a function pointer or an AdaptableBinaryPredicate (which you can
get by deriving your functors from std::binary_function). The
definintion is a little spammy I know, but in the end you have a much
more useful indirection functor here.

 

[Matthias Kaeppler]

This should be:
// to make life easier, use a typedef
typedef bool (*pred_fn)(typename It::value_type,
typename It::value_type);

pred_fn pred;


Also:
indirect_binary_fn(pred_fn f) : pred(f) {}


There is a much better solution though, to allow for both functors and
functions to be called if you use the boost library:

template<class BinaryPredicate>
class indirect_binary_fn : public std::binary_function<typename
boost::binary_traits<BinaryPredicate>::first_argument_type,
typename
boost::binary_traits<BinaryPredicate>::second_argument_type,
bool> {
private:
typedef typename boost::binary_traits<BinaryPredicate> It;

BinaryPredicate pred;

public:
indirect_binary_fn(BinaryPredicate f) : pred(f) {}
bool operator() (const It& lhs, const It& rhs)const
{ return pred(*lhs, *rhs); }
};

typename boost::binary_traits<BinaryPredicate>::first_argument_type and
its brother second_argument_type allow you to get the argument types for
either a function pointer or an AdaptableBinaryPredicate (which you can
get by deriving your functors from std::binary_function). The
definintion is a little spammy I know, but in the end you have a much
more useful indirection functor here.

Nice, thanks for the great advice. I have already lots of boost'ed code
in my program, so I certainly don't mind to add some more.

I'll report back if still something shouldn't work

 

[Kurt Stutsman]

Spotted an error in my code. The above line should be:

 

[Kurt Stutsman]

Found a couple more problems with my code. Decided to just go ahead and write a little program to
verify my code. Here it is. Notice I added a template function that returns an instance of the
class. This is so you don't have to include the type of the function in the declaration of the functor:

#include <boost/functional.hpp>
#include <functional>
#include <iostream>

template<class BinPred>
class indirect_fn_functor : public std::binary_function<typename
boost::binary_traits<BinPred>::first_argument_type,
typename
boost::binary_traits<BinPred>::second_argument_type,
bool> {
private:
typedef typename boost::binary_traits<BinPred>::first_argument_type It;

BinPred pred;

public:
indirect_fn_functor(BinPred f) : pred(f) {}
bool operator() (const It* lhs, const It* rhs)const
{ return pred(*lhs, *rhs); }
};

template<class BinPred>
indirect_fn_functor<BinPred> indirect_fn(BinPred pred)
{
return indirect_fn_functor<BinPred>(pred);
}

bool intLessThan(int lhs, int rhs)
{
return lhs < rhs;
}

bool intGreaterThan(int lhs, int rhs)
{
return lhs > rhs;
}

int main()
{
int a = 1;
int b = 2;

std::cout << "1 < 2: " << indirect_fn(intLessThan)(&a, &b) << "\n";
std::cout << "1 < 2: " << indirect_fn(std::less<int>())(&a, &b) << "\n";

std::cout << "1 > 2: " << indirect_fn(intGreaterThan)(&a, &b) << "\n";
std::cout << "1 > 2: " << indirect_fn(std::greater<int>())(&a, &b) << "\n";
return 0;
}

 

[Matthias Kaeppler]

#include <boost/functional.hpp>
#include <functional>
#include <iostream>

template<class BinPred>
class indirect_fn_functor : public std::binary_function<typename
boost::binary_traits<BinPred>::first_argument_type,
typename
boost::binary_traits<BinPred>::second_argument_type,
bool> {
private:
typedef typename
boost::binary_traits<BinPred>::first_argument_type It;

BinPred pred;

public:
indirect_fn_functor(BinPred f) : pred(f) {}
bool operator() (const It* lhs, const It* rhs)const
{ return pred(*lhs, *rhs); }
};

template<class BinPred>
indirect_fn_functor<BinPred> indirect_fn(BinPred pred)
{
return indirect_fn_functor<BinPred>(pred);
}

bool intLessThan(int lhs, int rhs)
{
return lhs < rhs;
}

bool intGreaterThan(int lhs, int rhs)
{
return lhs > rhs;
}

int main()
{
int a = 1;
int b = 2;

std::cout << "1 < 2: " << indirect_fn(intLessThan)(&a, &b) << "\n";
std::cout << "1 < 2: " << indirect_fn(std::less<int>())(&a, &b)
<< "\n";

std::cout << "1 > 2: " << indirect_fn(intGreaterThan)(&a, &b) <<
"\n";
std::cout << "1 > 2: " << indirect_fn(std::greater<int>())(&a,
&b) << "\n";
return 0;
}

Okay, hm, some questions coming to my mind:

This line:
typedef typename boost::binary_traits<BinPred>::first_argument_type It;

bothers me for example. If BinPred is std::less<int> for example, then
binary_traits<BinPred>::first_argument_type is int, not an iterator
type, or am I missing something? ^^

Furthermore, why are you passing the BinPred's by value? I guess this
ends up in a lot of copying?

 

[Matthias Kaeppler]

Found a couple more problems with my code. Decided to just go ahead and
write a little program to verify my code. Here it is. Notice I added a
template function that returns an instance of the class. This is so you
don't have to include the type of the function in the declaration of the
functor:

#include <boost/functional.hpp>
#include <functional>
#include <iostream>

template<class BinPred>
class indirect_fn_functor : public std::binary_function<typename
boost::binary_traits<BinPred>::first_argument_type,
typename
boost::binary_traits<BinPred>::second_argument_type,
bool> {
private:
typedef typename
boost::binary_traits<BinPred>::first_argument_type It;

BinPred pred;

public:
indirect_fn_functor(BinPred f) : pred(f) {}
bool operator() (const It* lhs, const It* rhs)const
{ return pred(*lhs, *rhs); }
};

template<class BinPred>
indirect_fn_functor<BinPred> indirect_fn(BinPred pred)
{
return indirect_fn_functor<BinPred>(pred);
}

bool intLessThan(int lhs, int rhs)
{
return lhs < rhs;
}

bool intGreaterThan(int lhs, int rhs)
{
return lhs > rhs;
}

int main()
{
int a = 1;
int b = 2;

std::cout << "1 < 2: " << indirect_fn(intLessThan)(&a, &b) << "\n";
std::cout << "1 < 2: " << indirect_fn(std::less<int>())(&a, &b)
<< "\n";

std::cout << "1 > 2: " << indirect_fn(intGreaterThan)(&a, &b) <<
"\n";
std::cout << "1 > 2: " << indirect_fn(std::greater<int>())(&a,
&b) << "\n";
return 0;
}

Another point is, that it now doesn't work with iterators anymore, since
operator() now explicitly takes pointers. So the indirection on a
container of iterators won't work.

 

[Matthias Kaeppler]

Okay, based on your code, I have come up with this:

template< typename Operation >
class indirecter_binary
: public std::binary_function< typename
boost::binary_traits<Operation>::first_argument_type,
typename boost::binary_traits<Operation>::second_argument_type,
typename boost::binary_traits<Operation>::result_type >
{
typedef typename
boost::binary_traits<Operation>::first_argument_type arg1_type;
typedef typename
boost::binary_traits<Operation>::second_argument_type arg2_type;
typedef typename boost::binary_traits<Operation>::result_type
result_type;
const Operation op;
public:
explicit indirecter_binary( Operation o ): op(o) {}
result_type operator() (arg1_type *lhs, arg2_type *rhs) const {
return op(*lhs, *rhs);
}
};

To make this also work on containers of iterators, I guess it's best to
write a separate class template and separate between e.g.
ptr_indirecter_binary and iter_indirecter_binary?

Or can anyone come up with an idea how to make the adaptor work on both
pointers and iterators? The problem is, I can't do something like
typedef typename arg1_type::iterator ItType;
because that obviously won't work on types which don't define a nested
iterator type.

 

[Matthias Kaeppler]

Okay, based on your code, I have come up with this:

template< typename Operation >
class indirecter_binary
: public std::binary_function< typename
boost::binary_traits<Operation>::first_argument_type,
typename
boost::binary_traits<Operation>::second_argument_type,
typename boost::binary_traits<Operation>::result_type >
{
typedef typename
boost::binary_traits<Operation>::first_argument_type arg1_type;
typedef typename
boost::binary_traits<Operation>::second_argument_type arg2_type;
typedef typename boost::binary_traits<Operation>::result_type
result_type;

correction here:

typedef typename boost::binary_traits<Operation>::function_type
function_type;
function_type op;

public:
explicit indirecter_binary( Operation o ): op(o) {}
result_type operator() (arg1_type *lhs, arg2_type *rhs) const {
return op(*lhs, *rhs);
}
};

Weird that it worked even without using function_type (I just tried it)!
But this should be the correct usage.

 

[Kurt Stutsman]

Okay, hm, some questions coming to my mind:

This line:
typedef typename boost::binary_traits<BinPred>::first_argument_type It;

bothers me for example. If BinPred is std::less<int> for example, then
binary_traits<BinPred>::first_argument_type is int, not an iterator
type, or am I missing something? ^^

Yes it wasn't meant to work on iterators.

Furthermore, why are you passing the BinPred's by value? I guess this
ends up in a lot of copying?

Because functors are typically empty classes with just a operator(). So I think the standard says
you have to at least allocate 1 byte for an empty structure. Either way, it probably will be
optimized into a register. Same with a pointer. This is also how the standard C++ library handles
its algorithms that take functions and functors.