map with custom comparison function?

[xaq]

I would like to write a custom comparison function object that I can pass to a map container. In my hands, a function object works fine when passed to an algorithm like sort, but I can't figure out how to use it in a container template. The compiler protests that I can't pass it a non-constant type, ie I can't use a constructor in the map declaration (line 35).

#include <vector>
#include <algorithm>
#include <map>

using namespace std;

class compare_1 { // simple comparison function
   public:
      bool operator()(const int x,const int y) { return (x-y)>0; } // returns x>y
};

class compare_2 { // a more complicated comparison function which varies according to specified parameter s
   public:
      compare_2(int s_) : s(s_) {};		
      bool operator()(const int x,const int y) { return s*(x-y)>0; } // returns x>y if s>0, else x<y
   private:
      int s;
};


int main()
{
   vector<int> v;	
			
   sort(v.begin(), v.end(), compare_1()); // ok
   sort(v.begin(), v.end(), compare_2(-1)); // ok
	
   map<int,int,compare_1> mymap1; // ok
   map<int,int,compare_2(-1)> mymap2; // error: a call to a constructor cannot appear in a constant-expression
	
   return 0;
}

Possibly I can find a workaround using function pointers but I suspect that will ultimately get ugly (bad style and safety).

Does anyone have a good solution for this? Many many thanks for any suggestions.

pax,
xaq

[jsmith]

I don't have a compiler on my Windows box to test this, but looking at

http://www.cplusplus.com/reference/stl/map/map.html

I think this is what you want:

  map<int,int,compare_2> mymap2( compare_2(-1) );

[xaq]

That's great, works perfectly. Makes sense, too, in retrospect. Thanks so much for reading the post and taking the time to answer.

[xaq]

A follow-up question:
When I go to use a map created this way, I run into problems if I pass the comparison constructor a variable ('s', line 26) rather than a constant parameter (-1, line 25). What's going on? Maybe this is some subtle error concerning constructors, because I get a similar error when I use a map declared with an explicit argument-free comparison object (line 24). For another possible clue to the problem: I get a warning on the declaration of 's' (line 21) that the variable is unused, even though I've clearly used it in passing it to my map (line 26).

#include <vector>
#include <algorithm>
#include <map>

using namespace std;

class compare {
	public:
		bool operator()(const int x,const int y) const { return (x-y)>0; }
};

class compare_val { // comparison object with an argument passed by value
	public:
		compare_val(int s_) : s(s_) {};				
		bool operator()(const int x,const int y) const { return s*(x-y)>0; } // returns x>y if s>0, else x<y
		int s;
};

int main()
{
	int s=-1; // warning: unused variable 's'
			
	map<int,int,compare> mymap1;
	map<int,int,compare> mymap2(compare());
	map<int,int,compare_val> mymap3(compare_val(-1));
	map<int,int,compare_val> mymap4(compare_val(s));

	mymap1.size();	// ok
	mymap2.size();	// error: request for member 'size' in 'mymap2',
			//    which is of non-class type 'map<int,int,compare,allocator...>()(compare(*)())
	mymap3.size();	// ok
	mymap4.size();	// error: request for member 'size' in 'mymap4',
			//    which is of non-class type 'map<int,int,compare,allocator...>()(compare_val)
	
	return 0;
}

Any clues? Once again, grateful for the help.

[exception]

You are the victim of of a very very nasty problem inherited from the C grammar, which states something like "Anything that *might be* a declaration *is* a declaration".
In line 26 for example, you do in fact declare a function (surprise!) with the name mymap4 which returns a map<int,int,compare_val> and takes a compare_val with a formal parameter name of 's' as argument. (Yes, 'void foo(int x)' is equivalent to 'void foo(int(x))')
In line 24 the same problem exists, this time you declare a function named mymap2 which returns a map<int,int,compare> and takes as parameter a pointer to a function which returns a 'compare'-object and takes no parameters.

This ambiguity doesn't exist in the other two cases. The first one is clear. In the second one, the formal parameter named 's' would be named '-1', which wouldn't be legal. Thus the otherwise same statement cannot be a declaration, thus it must be an 'expression-statement' as defined in ISO 14882, i.e. the instantiation of the variable mymap3 of type map<int,int,compare_val> and a function pointer object of type compare_val constucted with the parameter -1, just like you expected.

On a sidenote: the second problem wouldn't have occured if you hadn't circumvented the languages intended use of the namespace mechanism and had qualified the names with "std::" instead of using the 'using' keyword, because formal parameter names cannot include the qualifier operator '::'.

And yes, C++ indeed is a language you have to love. Otherwise you won't get along with it. These subtleties keep you busy learning for a lifetime...

[jsmith]

I'm using GCC 3.3.3 and I get the same errors as you when using the -Wall option.

I don't have immediate access to a newer version of GCC to try it out, but I will
in about 2.5 hours.

I think this is a compiler bug, because the following code compiles cleanly for me:

int main()
{      
	int s=-1; 
        compare c2; 
        compare_val c3( -1 );
        compare_val c4( s );
			
	map<int,int,compare> mymap1;
	map<int,int,compare> mymap2( c2 );
	map<int,int,compare_val> mymap3( c3 );
	map<int,int,compare_val> mymap4( c4 );

	mymap1.size();
	mymap2.size();	
	mymap3.size();
	mymap4.size();	
	return 0;
}

Looking at map's constructor, it takes the comparator as a const reference, which
means you should be able to pass a temporary (my first thought), which means the
change I made above should have made no effect.

But, the error that GCC spit out was totally wrong anyway...

So I'm thinking compiler bug. That would make about 6 or so compiler bugs I've
encountered with GCC 3.3.

[exception]

Nope, the compiler does exactly what it is told - it declares a function and is done with it. This behavior is 100% standard conforming.

Edit.
I just realized that I talked and talked, but didn't provide a solution ;-)
Just remove the abiguity!
Instead of
map<int,int,compare_val> mymap4(compare_val(s));
you have to write

compare_val c(s);
map<int,int,compare_val> mymap4(c);

This can't be a declaration (except c is a type in your context), so everything is fine.

[jsmith]

Yes -- "C++'s most vexing parse" as it is called, and is explained here:

http://episteme.arstechnica.com/eve/forums/a/tpc/f/6330927813/m/5650981735

Realized this after GCC 3.3, GCC 4.0, and Comeau compilers all failed with
similar errors (two different compiler code bases).

Comeau compiler is on-line at:

http://www.comeaucomputing.com/tryitout/

[xaq]

Oh, the horror, the horror. That's incredible. Thank you folks for the generous explanations and experiments on my behalf. Now I can interpret that bizarre-seeming error message, and hopefully I'll recognize this most vexing parse in the future...

[exception]

Guideline:
(a) avoid calling constructors in function calls
(b) never call a constructor in the parameter list of another constructor (your problem)

Then this and other problems won't occur (except for the class C {...}; C c(); case, but that error is easy to spot).