How to check if T (in template class) overloads '<' ?

[atrosh]

Hello.

I have searched a lot of forums/tutorials but cannot seem to find an answer to my question. I am writing a custom vector class: template <typename T> Vector. I know there is a STL version but I'm supposed to write it for an assignment. One of the things that this vector class is supposed to be able to do, is to sort itself (Vector::sort()).

I've finished writing the whole class, and we have an automated testing system for our assignments (we basically send in the source, and then it is tested in a number of ways). In the problem description regarding the sort method, it is
stated that ".. [sort] sorts the vector .. / Observe that swapping two elements require an assignment operator, and all data types which are to be compared have to define operator<. "

I have no idea how to check if 'T' overloads a certain operator. I cannot compile the code in the testing system, because one of the classes in the test case doesn't define operator< (which obviously is needed in the sorting algorithm). So basically, when the compiler tries to compile Vector<Problematic> (Problematic being a class in the test case) it fails, since Problematic doesn't overload operator<.

My question then is, how do I solve this? I would assume that the way to solve it is basically to check if T overloads > or not, and if it doesn't, don't compile the sort() method..?

Thank you for reading through this, I hope someone can answer my question! I have looked everywhere...

Regards,

[Disch]

There currently is no solution to check whether or not T has an appropriate < operator from a template.

The only solutions here are:

1) Give Problematic a < operator
or
2) Don't try to sort a Vector<Problematic>


Vector<Problematic> will still work just fine as long as you don't try to sort it. Calling sort will produce all kinds of weird compiler errors.

I wouldn't worry about it, as the assigment clearly states the following:

and all data types which are to be compared have to define operator<

So as long as your Vector properly sorts classes which overload the < operator, you've fulfilled the assignment. Classes which don't have a < operator are expected not to work.

[atrosh]

Thank you for your response.

I cannot change the test-class (Problematic). Thanks to your answer, I'm beginning to suspect that something in my code is trying to "force" the compilation of the sort() method. _Basically, it only states that we should have a sort method, but it doesn't state which sort method, so I chose the quicksort algorithm, which needs two methods (public: sort() and private: partition()).

As far as I can tell, Problematic never calls the sort method, because I tried writing this:

	/*
	 * Sort the vector (quicksort algorithm)
	 */
	void sort(size_t top, size_t bottom, bool ascending)
	{
		bool test = (vector[top] < vector[bottom]); 
        }

instead of the original sort method, and it compiled. Maybe having a call to "partition" inside sort forces the compiler to compile both of the methods?

Original sort method:

	/*
	 * Sort the vector (quicksort algorithm)
	 */
	void sort(size_t top, size_t bottom, bool ascending)
	{
                // top = subscript of beginning of array
		// bottom = subscript of end of array
		size_t middle;
		if (top < bottom)
		{
                      middle = partition(top, bottom, ascending);
                      sort(top, middle, ascending);   // sort first section
                      sort(middle+1, bottom, ascending);    // sort second section
		}
		return;
	}

I am referring to the line "middle = partition(top,bottom,ascending)". Could this be forcing the compiler to try to compile "partition" even if sort is never called? In that case, I'll simply have to use another sorting algorithm...

Thanks again for your time.
Regards,

[helios]

AFAIK, the standard doesn't define whether a method should be compiled in any particular situation. Code should assume that it's always compiled, otherwise it's just a compiler-specific hack.
Are you sure sort() has to be a member function? If it's a global function, it will only be compiled if it's ever used.

[atrosh]

I should have added that the assignment states that everything has to be written in one file, "vector.h". Doesn't that mean it only compiles what it needs? I'm not sure.

I really can't get to the bottom of this... For some reason, as I explained above, having sort just output for instance

void sort(bool ascending=true){
    std::cout << (vector[0] > vector[1]) << std::endl
}

compiles fine (even though I do a compare!). But whenever I try to do it with a sorting algorithm, it starts complaining again?
For instance, the above code compiles fine, but this bubble sort (sorry for unformatted code) doesn't?:

	void sort(bool ascending = true){
		//sort(0,vSize-1, ascending);
		#pragma warning(disable:4018)
      bool swapped = true;
      size_t j = 0;
      T tmp;
      while (swapped) {
            swapped = false;
            j++;
            for (int i = 0; i < vSize - j; i++) {
                  if (vector[i] > vector[i + 1]) {
                        tmp = vector[i];
                        vector[i] = vector[i + 1];
                        vector[i + 1] = tmp;
                        swapped = true;
				  }
			}
	  }
	}

The error I get is:
vector.h(281) : error C2676: binary '>' : '`anonymous-namespace'::Problematic' does not define this operator or a conversion to a type acceptable to the predefined operator
1> d:\k\TVector\vector.h(271) : while compiling class template member function 'void Vector<T>::sort(bool)'
1> with
1> [
1> T=`anonymous-namespace'::Problematic
1> ]


Why does it compile with the first sort method (without complaining that I use a compare <) but not the second?

[atrosh]

I just realized it might have something to do with std::cout, because I just tried

void sort(bool ascending=true){
	bool test = (vector[0] > vector[1]);
		if (test)
			std::cout << "hello" << std::endl;
	}

and that didn't compile either...

In this case, the only thing I can think of is to write a specialized sort method (which does nothing) for when T=Problematic , which I suppose is an ugly hack to pass the test case, but I'm running out of options here. How would I go about writing that?
What I'm looking for is something like

sort<Problematic>(bool ascending=true){
return;
}

but I don't know the proper syntax on how to do it, and I can't find it..

Thank you for your help.

[Galik]

atrosh wrote:

I would assume that the way to solve it is basically to check if T overloads > or not, and if it doesn't, don't compile the sort() method..?

Isn't that the behaviour you are already getting?

I believe that is the solution. However the problem is that it can be difficult to tell from the compiler error messages exactly what went wrong. So there is a technique to make the compilation fail deliberately and provide more information to the programmer as to what went wrong. Straustrup referred to them as 'constraints'.

Consider the following:

template<class T1, class T2 = T1> struct CanCompare
{
	static void constraints(T1 a, T2 b) { a == b; a != b; a < b; }
	CanCompare() { void(*p)(T1, T2) = constraints; }
};

If you try to compile the above for a type T that does not have ==, != or < defined the compiler will generate an error. Importantly the name "CanCompare" will appear in the error message giving you a clue as to what went wrong. The CanCompare 'constraint' was not met at compile time.

You can thus apply this 'constraint' to a template class like this:

template<typename T>
class Vector : public CanCompare<T>
{
    // ... stuff
};

Of course your class is already causing a compiler error, which is a good thing. What this technique does is try to make the generated error message a little clearer.

http://www2.research.att.com/~bs/bs_faq2.html#constraints

[atrosh]

Thank you Galik! That is certainly useful to know.

And I'm sorry to come with this information too late, just after you posted that, but I just found that Problematic DOES in fact overload the < operator:

			bool operator<(const Problematic &rhs) const {
				assert(myself == this);
				return (data & 0xF) < (rhs.data & 0xF);
			}

So why isn't it working?

[Galik]

atrosh wrote:

So why isn't it working?

In your above code your bubble sort algorithm uses a greater than > operator. Is that the problem?

[atrosh]

I think I'm going to start crying now.

Yes, that was the problem. Now I know that if I ever have to overload <, I should also overload >.

I will also shoot my teacher for just overloading < and not > in his test case.

Thanks a LOT. I've been stuck at this for more than a day now, and I can finally keep working on it. I can't believe the solution was that simple, haha.

Thanks again...

Regards,

[Galik]

To be fair to your teacher, its normal to only overload the < operator because you can always write your algorithm to only use <. Just switch the two operands round ;o)

[helios]

Assignment statement wrote:

Observe that swapping two elements require an assignment operator, and all data types which are to be compared have to define operator<.

[jsmith]

I don't understand why you care whether or not T overloads operator<. If T doesn't, then
your sort method won't compile, which is what you want. anyway. All of the above examples
do nothing more than generate a different compile error in a different place.

Note that this is what STL does.

[jsmith]

And, actually, I believe there is a way to test if T overloads operator<, but it requires some
esoteric template machinery that I cannot reproduce off the top of my head. But I recall
a colleague of mine writing a compile time test for ostreamability. (If T did not provide
operator<<, then his code would use a default operator<<.)

[Bazzy]

IMO boost concept_check does everything needed: http://www.boost.org/doc/libs/1_44_0/libs/concept_check/concept_check.htm