Help needed to overload function template. [C++]

Prev: Warning: Can't find linker symbol
Next: Recursive friendship

From: mg on 25 Sep 2009 13:39

Hi,

I want to have two template functions erase_if, one for regular
containers and another for associative containers.

If I leave the code as below the compiler will complain about
ambiguity.
I tried to use template template parameters but could not figure it
out in a proper way.
Any suggestions ?

template <class Container, class Predicate>
Container& erase_if (Container& c, Predicate& p)
{
c.erase (std::remove_if (c.begin (), c.end (), p), c.end ());
return c;
}

template<class MapClass, class Predicate>
void erase_if (MapClass& map, Predicate& p)
{
typedef typename MapClass::iterator iterator;
iterator it = map.begin ();
const iterator end = map.end ();
while (it != end);
{
iterator tmp=it++;
if (p (*tmp))map.erase (tmp);
}
}

I managed to get this to compile (but not the code to use it):
template<typename Key, typename T, template <typename _Key = Key,
typename _T = T, typename Compare = std::less<Key>,
typename Alloc = std::allocator<std::pair<const Key, T> >
> class MapClass,
class Predicate>
void erase_if (MapClass<>& map, Predicate& p)
{
typedef typename MapClass<>::iterator iterator;
iterator it = map.begin ();
const iterator end = map.end ();
while (it != end);
{
iterator tmp=it++;
if (p (*tmp))map.erase (tmp);
}
}

It is very ugly and I was not even able to use it, the code below
resulted in no match for function erase_if:
#include <boost/test/unit_test.hpp>

#include "algorithm_util.h"
#include <map>
#include <string>

typedef std::pair<int, std::string> MapEntry;
struct IsDigit : public std::unary_function<MapEntry, bool>
{
bool operator() (MapEntry p) {return isdigit (p.first);}
};

typedef std::map<int, std::string> Map;

BOOST_AUTO_TEST_SUITE(algorithm_util_suite)

BOOST_AUTO_TEST_CASE(erase_if_map)
{
Map map;
map[0] = "a";
map[1] = "1";
map[2] = "c";

cpplib::erase_if<int, std::string, Map, IsDigit> (map, IsDigit());
// I would like to be able to call it this way: erase_if<Map,
IsDigit>(map, IsDigit());
// Or preferebly erase_if (map, IsDigit()); Hoping the compiler
would be smart enough to figure it out.
BOOST_CHECK_EQUAL ("a", map[0]);
BOOST_CHECK_EQUAL ("c", map[1]);
}

BOOST_AUTO_TEST_SUITE_END ()

Thank you in advance for your attention !

--
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]

From: Paul Bibbings on 26 Sep 2009 02:59

mg wrote:
<snip>
>
> template <class Container, class Predicate>
> Container& erase_if (Container& c, Predicate& p)
> {
// ...
> }
>
> template<class MapClass, class Predicate>
> void erase_if (MapClass& map, Predicate& p)
> {
> // ...
> }

For your first attempt, your call is ambiguous since template argument
deduction succeeds for both equally. typenames in a template parameter
are just placeholders in a sense, and the second above might just as
well have been written:

template<class Container, class Predicate>
void erase_if (Container& c, Predicate& p)
{ /* ... * }

As you can see the only difference is in the return type, and as
overload resolution does not consider return types, hence the ambiguity.

</snip><snip>

> // I would like to be able to call it this way: erase_if<Map,
> IsDigit>(map, IsDigit());
> // Or preferebly erase_if (map, IsDigit()); Hoping the compiler
> would be smart enough to figure it out.

</snip>

This last is certainly achievable along the lines you have been
attempting. Given the following definitions you should be able to use
the syntax erase_if(map, IsDigit()); and have the arguments deduced
for you, and achieve appropriate overload resolution at the same time.

template< // #1
typename T,
typename Alloc,
template<typename, typename> class Container,
typename Predicate
>
Container<T, Alloc>& erase_if(Container<T, Alloc>& c, Predicate p)
{
// ...
}

template< // #2
typename Key,
typename T,
typename Compare,
typename Alloc,
template<typename, typename, typename, typename> class MapClass,
typename Predicate
>
void erase_if(MapClass<Key, T, Compare, Alloc>& map, Predicate p)
{
// ...
}

This allows uses such as:

std::map<int, std::string> map;

// ...

erase_if(map, IsDigit()); // calls #2

std::vector<int> vec;

// ...

erase_if(vec, std::bind2nd(std::less<int>(), 1)); // calls #1

Regards

Paul Bibbings

--
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]

From: Paul Bibbings on 26 Sep 2009 02:59

From: Paul Bibbings on 26 Sep 2009 03:00

On Sep 26, 5:39 am, mg <mgpen...(a)gmail.com> wrote:
<snip>
>
> template <class Container, class Predicate>
> Container& erase_if (Container& c, Predicate& p)
> {
// ...
> }
>
> template<class MapClass, class Predicate>
> void erase_if (MapClass& map, Predicate& p)
> {
> // ...
> }

For your first attempt, your call is ambiguous since template argument
deduction succeeds for both equally. typenames in a template parameter
are just placeholders in a sense, and the second above might just as
well have been written:

template<class Container, class Predicate>
void erase_if (Container& c, Predicate& p)
{ /* ... * }

As you can see the only difference is in the return type, and as
overload resolution does not consider return types, hence the
ambiguity.

</snip><snip>

> // I would like to be able to call it this way: erase_if<Map,
> IsDigit>(map, IsDigit());
> // Or preferebly erase_if (map, IsDigit()); Hoping the compiler
> would be smart enough to figure it out.

</snip>

This last is certainly achievable along the lines you have been
attempting. Given the following definitions you should be able to use
the syntax erase_if(map, IsDigit()); and have the arguments deduced
for you, and achieve appropriate overload resolution at the same time.

template< // #1
typename T,
typename Alloc,
template<typename, typename> class Container,
typename Predicate
>
Container<T, Alloc>& erase_if(Container<T, Alloc>& c, Predicate p)
{
// ...
}

template< // #2
typename Key,
typename T,
typename Compare,
typename Alloc,
template<typename, typename, typename, typename> class MapClass,
typename Predicate
>
void erase_if(MapClass<Key, T, Compare, Alloc>& map, Predicate p)
{
// ...
}

This allows uses such as:

std::map<int, std::string> map;

// ...

erase_if(map, IsDigit()); // calls #2

std::vector<int> vec;

// ...

erase_if(vec, std::bind2nd(std::less<int>(), 1)); // calls #1

Regards

Paul Bibbings

--
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]

From: mg on 30 Sep 2009 05:50

Hi Paul, I followed your example and defined the functions like showed
below:

Obs.: the code below is in the cpplib namespace.

template<
typename T,
typename Alloc,
template<typename, typename> class Container,
typename Predicate
>
Container<T, Alloc>& erase_if(Container<T, Alloc>& c, Predicate p)
{
c.erase (std::remove_if (c.begin (), c.end (), p), c.end ());
return c;
}

template<
typename Key,
typename T,
typename Compare,
typename Alloc,
template<typename, typename, typename, typename> class
MapClass,
typename Predicate
>
void erase_if(MapClass<Key, T, Compare, Alloc>& map, Predicate p)

{
typedef typename MapClass<Key, T, Compare, Alloc>::iterator
iterator;
iterator it = map.begin ();
const iterator end = map.end ();
while (it != end);
{
iterator tmp=it++;
if (p (*tmp))map.erase (tmp);
}
}

And called it this way:

....
typedef std::pair<int, std::string> MapEntry;
struct IsDigit : public std::unary_function<MapEntry, bool>
{
bool operator() (MapEntry p) {return isdigit (p.first);}
};

typedef std::map<int, std::string> Map;

BOOST_AUTO_TEST_SUITE(algorithm_util_suite)

BOOST_AUTO_TEST_CASE(erase_if_map)
{
Map map;
map[0] = "a";
map[1] = "1";
map[2] = "c";

cpplib::erase_if (map, IsDigit());
....

And the compiler complained saying it is ambiguous with this message:
||=== cpplib, Debug ===|
C:\projects\cpplib\test\algorithm_util_test.cpp||In member function
`void algorithm_util_suite::erase_if_map::test_method()':|
C:\projects\cpplib\test\algorithm_util_test.cpp|30|error: call of
overloaded `erase_if(Map&, IsDigit)' is ambiguous|
c:\projects\cpplib\algorithm_util.h|16|note: candidates are:
Container<T, Alloc>& cpplib::erase_if(Container<T, Alloc>&, Predicate)
[with T = int, Alloc = std::string, Container = std::map, Predicate =
IsDigit]|
c:\projects\cpplib\algorithm_util.h|31|note: void
cpplib::erase_if(MapClass<Key, T, Compare, Alloc>&, Predicate) [with
Key = int, T = std::string, Compare = std::less<int>, Alloc =
std::allocator<std::pair<const int, std::string> >, MapClass =
std::map, Predicate = IsDigit]|
||=== Build finished: 1 errors, 0 warnings ===|

If I try to fully qualify the call this way:
cpplib::erase_if<Map::key_type, Map::value_type, Map::key_compare,
Map::allocator_type, Map, IsDigit> (map, IsDigit());

It still does not find it:
C:\projects\cpplib\test\algorithm_util_test.cpp|30|error: no matching
function for call to `erase_if(Map&, IsDigit)'|

Any suggestions ?

Thank you very much for your help.

Best regards,
Mau.

--
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]

| Next | Last
Pages: 1 2
Prev: Warning: Can't find linker symbol
Next: Recursive friendship