Quick Question - functors via structs

[Doug Mika]

I have the following short ReverseSort algorithm implemented in a structs operator() method:

template<typename KeyType>
struct ReverseSort{
bool operator()(const KeyType& key1, const KeyType& key2){
return (key1 > key2);
}
};

My Question is why, when declaring a map I write

map<int, string, ReverseSort<int> > someOtherMap (someOtherMap.cbegin(), someOtherMap.cend());

and NOT

map<int, string, ReverseSort<int>() > someOtherMap (someOtherMap.cbegin(), someOtherMap.cend());

[Note the brackets () in ReverseSort<int>()]
Afterall the decleration of map states that it takes a binary predicate, then why isn't it an object of a functor (ReverseSort<int>()) instead of just a type (ReverseSort<int>)??

[Doug Mika]

With a follow up question to the above... why does the following not work

#include <string>
#include <map>

using namespace std;

template<typename KeyType>
bool ReverseSort(const KeyType& key1, const KeyType& key2){
return (key1 > key2);
}



int main(int argc, char** argv) {

// Prints arguments...
std::cout<<"Command Parameters: "<<std::endl;
if (argc > 1) {
std::cout << std::endl << "Arguments:" << std::endl;
for (int i = 1; i < argc; i++) {
std::cout << i << ": " << argv[i] << std::endl;
}
}

//The Program
map<int, string> mapIntToString1;

map<int, string, ReverseSort<int> > mapIntToString2 (mapIntToString1.cbegin(), mapIntToString1.cend());
}

The problem is with my template function ReverseSort<int>, but why can't I include it as the binary predicate in map?

[Paavo Helde]

Doug Mika <doug...@gmail.com> wrote in
news:086aadf5-87b2-400b...@googlegroups.com:

Because templates are instantiated with a type (or a compile-time
integral constant, but this does not apply here). An object is not a
type. Type is a compile-time concept and object is a run-time concept,
and template instantiation happens at compile time only.

Maybe you are confusing the template parameter with the map constructor
parameter. The map constructor indeed has a comp parameter for taking the
comparator object. By default it uses a default-constructed object of the
relevant type, but you can pass it also explicitly:

map<int, string, ReverseSort<int> > myMap
(someOtherMap.cbegin(), someOtherMap.cend(), ReverseSort<int>());

Note the parens near the end.

hth
Paavo

[Victor Bazarov]

What does your compiler say? Can you not take a hint from its error
message?

ReverseSort<int> is not a type, you can't use it as the third argument
to the 'std::map' template.

V
--
I do not respond to top-posted replies, please don't ask

[Doug Mika]

So let me see if I understand this correctly. Template Classes are instantiated with a type, not an object...that makes sense. So I just have to remember that when instantiating a template, I have to use the type NOT an object...and Paavo's explenation made sense.

Now however, let's say that as my binary predicate for the map decleration I would like to use a template FUNCTION (not a template CLASS). That is, as my predicate I would like to use the following function:

template<typename KeyType>
bool ReverseSort(const KeyType& key1, const KeyType& key2){
return (key1 > key2);
}

Since this is a template function not a template object, how would I declare a map to use this function as it's binary predicate?

None of the ones below work? Why?
map<int, string, ReverseSort> mapIntToString (someOtherMap.cbegin(), someOtherMap.cend());

map<int, string> mapIntToString3 (mapIntToString1.cbegin(), mapIntToString1.cend(),ReverseSort<int>);

map<int, string> mapIntToString3 (mapIntToString1.cbegin(), mapIntToString1.cend(),ReverseSort);

[Richard]

[Please do not mail me a copy of your followup]

Doug Mika <doug...@gmail.com> spake the secret code
<086aadf5-87b2-400b...@googlegroups.com> thusly:

>My Question is why, when declaring a map I write
>
>map<int, string, ReverseSort<int> > someOtherMap (someOtherMap.cbegin(),
>someOtherMap.cend());
>
>and NOT
>
>map<int, string, ReverseSort<int>() > someOtherMap
>(someOtherMap.cbegin(), someOtherMap.cend());

Templates arguments can be types or an integral or enumeration type
value.[1]

std::map takes four template parameters:
- class Key
- class T
- class Compare = std::less<Key>
- class Allocator = std::allocator<std::pair<const Key, T>>

ReverseSort is defined as:

template<typename KeyType>
struct ReverseSort{
bool operator()(const KeyType& key1, const KeyType& key2){
return (key1 > key2);
}
};

ReverseSort<int> is a type, an instantiation of the template struct
ReverseSort with a template argument of int.

ReverseSort<int>() is an (anonymous) instance of the type
ReverseSort<int>.

Templates cannot take instances of objects as template arguments, only
types or integral values.

[1] This is slightly simplified, see 14.3.2 Template non-type
arguments in the standard for details.
--
"The Direct3D Graphics Pipeline" free book <http://tinyurl.com/d3d-pipeline>
The Computer Graphics Museum <http://computergraphicsmuseum.org>
The Terminals Wiki <http://terminals.classiccmp.org>
Legalize Adulthood! (my blog) <http://legalizeadulthood.wordpress.com>

[Doug Mika]

Yes, so how would I instantiate a map object if I wanted to use the following template FUNCTION as my sort predicate:

template<typename KeyType>
bool ReverseSort(const KeyType& key1, const KeyType& key2){
return (key1 > key2);
}

???

[Victor Bazarov]

On 5/5/2015 11:06 AM, Doug Mika wrote:
> So let me see if I understand this correctly. Template Classes are
instantiated with a type, not an object...that makes sense. So I just
have to remember that when instantiating a template, I have to use the
type NOT an object...and Paavo's explenation made sense.
>
> Now however, let's say that as my binary predicate for the map
decleration I would like to use a template FUNCTION (not a template
CLASS). That is, as my predicate I would like to use the following function:
>
> template<typename KeyType>
> bool ReverseSort(const KeyType& key1, const KeyType& key2){
> return (key1 > key2);
> }

That's not a *function*. It's a *function template*. You can't *use*
this one, you can only instantiate it and use an instantiation.

>
> Since this is a template function not a template object, how would I
declare a map to use this function as it's binary predicate?
>
> None of the ones below work? Why?
> map<int, string, ReverseSort> mapIntToString (someOtherMap.cbegin(), someOtherMap.cend());
>
> map<int, string> mapIntToString3 (mapIntToString1.cbegin(), mapIntToString1.cend(),ReverseSort<int>);
>
> map<int, string> mapIntToString3 (mapIntToString1.cbegin(), mapIntToString1.cend(),ReverseSort);
>

All class templates that use comparators are implemented in such a way
that a function cannot be use do instantiate those templates. You need
either a lambda or a functor.

[Victor Bazarov]

I keep forgetting about 'function' template...

See if this works for you:

#include <string>
#include <map>
#include <functional>
#include <iostream>

using namespace std;

template<typename KeyType>
bool ReverseSort(const KeyType& key1, const KeyType& key2){
return (key1 > key2);
}

int main()
{
//The Program
map<int, string, function<bool(const int&, const int&)>>
mapIntToString1(ReverseSort<int>);

mapIntToString1[1] = "one";
mapIntToString1[2] = "two";
mapIntToString1[3] = "three";
mapIntToString1[4] = "four";

for (auto m : mapIntToString1)
{ cout << m.first << "," << m.second << endl; }

[Richard]

[Please do not mail me a copy of your followup]

Victor Bazarov <v.ba...@comcast.invalid> spake the secret code
<miapag$5m2$1...@dont-email.me> thusly:

> map<int, string, function<bool(const int&, const int&)>>
> mapIntToString1(ReverseSort<int>);

That works. Details of std::function template class:
<http://en.cppreference.com/w/cpp/utility/functional/function>

[Doug Mika]

Yes that worked nicely, and I'll admit, I haven't yet read about the std::function template but I hope someone could quickly explain the following line:

map<int, string, function<bool(const int&, const int&)>>
mapIntToString1(ReverseSort<int>);

function<bool(const int&, const int&)> - defines type as function that takes two int's and returns a bool. Check

mapIntToString1(ReverseSort<int>) - calls the constructor of map that takes key_compare as argument, in this case a function pointer. Is this correct?

[Victor Bazarov]

'function< blah >' is a class (type), first of all. It can be used to
create an object, and that's the most important thing as far as map and
other containers where a comparator is needed, are concerned. In place
of 'blah' you write the type of the function. Basically, it's the
sequence of tokens as if you declare a function but omit the name, and
the names of the argument.

mapI2S(ReverseSort<int>) declares, defines, and initializes the object
of the type map<int,...>. As the process of the initialization, the
constructor is called and 'ReverseSort<int>' (the argument to the c-tor)
is converted to the 'function<bool...>' object.

[Paavo Helde]

Doug Mika <doug...@gmail.com> wrote in

news:ec79f3e2-788b-4d0d...@googlegroups.com:

> So let me see if I understand this correctly. Template Classes are
> instantiated with a type, not an object...that makes sense. So I just
> have to remember that when instantiating a template, I have to use the
> type NOT an object...and Paavo's explenation made sense.
>
> Now however, let's say that as my binary predicate for the map
> decleration I would like to use a template FUNCTION (not a template
> CLASS). That is, as my predicate I would like to use the following
> function:
>
> template<typename KeyType>
> bool ReverseSort(const KeyType& key1, const KeyType& key2){
> return (key1 > key2);
> }

You are confusing two templates - your function template ReverseSort and
the class template std::map. You need to instantiate both. ReverseSort is
easy, it is instantiated with type int. Std::map needs to be also
instantiated with a type. However, ReverseSort is a template, not a
function, so it is not a type and does not have a type. When
instantiated, it may generate functions of potentially infinite number of
types.

The function type involves its parameter and return types. As I mentioned
before, it is easiest to work with function pointers. A suitable type is
a pointer type, namely a pointer which points to functions taking two
ints and returns bool:

typedef bool (*MyFuncType)(const int&, const int&);

This is the type which you can use for instantiating std::map. Note that
this is not a template (because templates are not types, they just can
generate types; you could use your template to define all kind of types,
but this requires struct or class templates).

This function type is quite generic. How does it know it has to use your
ReverseSort? Well, you have to tell it, by passing the value of the above
type to the std::map constructor. This value is of course just a pointer
to a suitable function, namely to the correct instantiation of your
function template.

The whole program looks like this:

#include <map>
#include <string>

template<typename KeyType>
bool ReverseSort(const KeyType& key1, const KeyType& key2){
return (key1 > key2);
}

typedef bool (*MyFuncType)(const int&, const int&);

int main() {
std::map<int, std::string> someOtherMap;

std::map<int, std::string, MyFuncType>
mapIntToString(
someOtherMap.cbegin(),
someOtherMap.cend(),
&ReverseSort<int>);
}

Here, &ReverseSort<int> gives you a function pointer. A function pointer
is an object and can be passed here easily. Note that this is
conceptually passed at run-time, so the compiler will have much more
trouble optimizing the code and inlining your function (as opposed to the
functor variant).

> Since this is a template function not a template object, how would I
> declare a map to use this function as it's binary predicate?
>
> None of the ones below work? Why?
> map<int, string, ReverseSort> mapIntToString (someOtherMap.cbegin(),
> someOtherMap.cend());

ReverseSort is not a type.

>
> map<int, string> mapIntToString3 (mapIntToString1.cbegin(),
> mapIntToString1.cend(),ReverseSort<int>);

The default comparator type does not match ReverseSort<int>.

> map<int, string> mapIntToString3 (mapIntToString1.cbegin(),
> mapIntToString1.cend(),ReverseSort);
>

ReverseSort is not an object.

[Doug Mika]

One of the constructors of map is defined as follows:

explicit map (const key_compare& comp = key_compare(),
const allocator_type& alloc = allocator_type());

given this, why wouldn't the following map decleration work?

map<int, string> mapIntToString2 (mapIntToString1.cbegin(), mapIntToString1.cend(), ReverseSort<int>);

[Paavo Helde]

Doug Mika <doug...@gmail.com> wrote in

news:87746632-550a-4f8d...@googlegroups.com:

I answered this in another reply just few minutes ago. Here, template
argument for comparator is the default (std::less<int>), but your passed
value is of a different type (a function (reference)). std::less is a
class, not a function type. You need to specify the correct type as the
template argument.

hth
Paavo

[Doug Mika]

Well, I think I'm beginning to understand all of this, but there is one more thing that is peculiar. If in my map object instantiation I specify a type for the sort algorithm, then why don't I have to include the sort functor or sort function pointer in the constructor?

ie. In the following program the map object called "fourth" has in it's type template parameter the type for classcomp, but doesn't include an instance of classcomp in its constructor. Which sort algorithm will fourth use: the one originally provided by std::map or classcomp::operator()?

// constructing maps
#include <iostream>
#include <map>

bool fncomp (char lhs, char rhs) {return lhs<rhs;}

struct classcomp {
bool operator() (const char& lhs, const char& rhs) const
{return lhs<rhs;}
};

int main ()
{
std::map<char,int> first;

first['a']=10;
first['b']=30;
first['c']=50;
first['d']=70;

std::map<char,int> second (first.begin(),first.end());

std::map<char,int> third (second);

std::map<char,int,classcomp> fourth; // class as Compare

bool(*fn_pt)(char,char) = fncomp;
std::map<char,int,bool(*)(char,char)> fifth (fn_pt); // function pointer as Compare

return 0;
}

[Richard]

[Please do not mail me a copy of your followup]

Doug Mika <doug...@gmail.com> spake the secret code

<651a4ae2-f8b5-4a7f...@googlegroups.com> thusly:

>Well, I think I'm beginning to understand all of this, but there is one
>more thing that is peculiar. If in my map object instantiation I
>specify a type for the sort algorithm, then why don't I have to include
>the sort functor or sort function pointer in the constructor?

The answer is obtained by looking at the declarations for the
constructors of std::map:
<http://en.cppreference.com/w/cpp/container/map/map>

Every place where the constructor accepts an instance of the
comparison function, the default value for this argument is Compare(),
a default constructed instance of your comparison type supplied in the
template argument.

[Victor Bazarov]

On 5/6/2015 12:40 PM, Doug Mika wrote:
> Well, I think I'm beginning to understand all of this, but there is
one more thing that is peculiar. If in my map object instantiation I
specify a type for the sort algorithm, then why don't I have to include
the sort functor or sort function pointer in the constructor?

If you don't supply a particular function, what's going to happen?

Case 1: the comparator is a class with operator() defined. If you don't
supply an object, it will be default-constructed from that type. What
does it mean to default-construct an object? If all that type does is
to use its op(), i.e. if the object has no *state*, who cares? It's
still going to be fine, a default-constructed object will be called to
compare your objects (keys), i.e. an empty instance of the class will
work hard [by means of its operator() member function] to successfully
compare what needs to be compared. All is well.

Case 2: the comparator is a function [pointer]. If you don't supply any
specific function, it will be default-constructed from that type (a
pointer to a function). What does it mean to default-construct a
pointer? What value will it have? What *code* will be behind that
pointer? It will be a _null_ pointer, IOW, a non-existent function.
Can *that* be used to compare your objects? Not going to work.

That is why when you specify a class (with an overloaded op() member),
you're pretty much done, unless you need a special state, which you can
give it at the construction time (less frequent). But when you specify
that "my comparator is a function that takes two references to int and
returns a bool", the compiler is not going to invent that function for you.

> ie. In the following program the map object called "fourth" has in it's type template parameter the type for classcomp, but doesn't include an instance of classcomp in its constructor. Which sort algorithm will fourth use: the one originally provided by std::map or classcomp::operator()?
>
> // constructing maps
> #include <iostream>
> #include <map>
>
> bool fncomp (char lhs, char rhs) {return lhs<rhs;}
>
> struct classcomp {
> bool operator() (const char& lhs, const char& rhs) const
> {return lhs<rhs;}
> };
>
> int main ()
> {
> std::map<char,int> first;
>
> first['a']=10;
> first['b']=30;
> first['c']=50;
> first['d']=70;
>
> std::map<char,int> second (first.begin(),first.end());
>
> std::map<char,int> third (second);
>
> std::map<char,int,classcomp> fourth; // class as Compare
>
> bool(*fn_pt)(char,char) = fncomp;
> std::map<char,int,bool(*)(char,char)> fifth (fn_pt); // function pointer as Compare
>
> return 0;
> }
>

[Paavo Helde]

Doug Mika <doug...@gmail.com> wrote in

news:651a4ae2-f8b5-4a7f...@googlegroups.com:

> Well, I think I'm beginning to understand all of this, but there is
> one more thing that is peculiar. If in my map object instantiation I
> specify a type for the sort algorithm, then why don't I have to
> include the sort functor or sort function pointer in the constructor?

The constructor parameter has a default value, namely the default value
of the given comparator type. In the functor variant, this is the
default-constructed functor, which is OK for simple functors which do not
need any extra data. In the function pointer variant, the default value
would be a NULL pointer, which obviously would not be very useful. Thus
you need to pass the pointer explicitly (and in your code actually have
done so).

So, the functor style is more readable, more flexible, more optimizable
and provides some sensible defaults. IOW, it just fits better with the
templated STL code. I guess the function pointer variant is mainly
supported for smoother upgrade path for C programmers used to qsort().

> ie. In the following program the map object called "fourth" has in
> it's type template parameter the type for classcomp, but doesn't
> include an instance of classcomp in its constructor. Which sort
> algorithm will fourth use: the one originally provided by std::map or
> classcomp::operator()?

The latter. There is no algorithm "provided originally" by std::map,
because std::map is a template, not a class, and the default algorithm
(std::less) appears just as the default choice for some template
argument.

The compiler will generate the actual class code from this template,
based on the template arguments. As you have replaced the default
template argument std::less with your classcomp, then the generated class
code for this instantiation has no idea that std::less exists, not to
speak about using or calling it somehow.