Overload comparison operators for a templated class

Question

Hi experts,

I'm having troubles in overloading comparison operators in order to compare two pair struct in such way:

typedef pair<string, unsigned int> INDEX;
bool operator>(INDEX &v1, INDEX &v2)
{
    if(v1.second == v2.second)  //if integer parts are equal
    {
        //string that comes earlier in the dictionary should be larger
        return v1.first < v2.first; 
    }
    return v1.second > v2.second;
}

The actual comparison takes place at this->element(hole/2) < this->element(hole) inside fixUp(CBTNODE hole), a member function of BinaryHeap class, which is a derived class of CompleteBinaryTree. The T will be instantiated as type INDEX, which is typedefed as pair<string, unsigned int>.

In other words, the comparison between two pairs: ("a.txt", 42) > ("b.txt", 42) should return true.

I tried to overload operator> outside the class declaration in two different ways but neither of them worked:

1. bool operator>(INDEX &v1, INDEX &v2);
2. bool operator>(BinaryHeap<T> &v1, BinaryHeap<T> &v2);

Any help will be much appreciated!

Z.Zen

Here is the declarations:

typedef int CBTNODE;

template <typename T>
class CompleteBinaryTree {
public:
  //Initializes an empty binary tree
  CompleteBinaryTree(int initialSize = 10);

  //Destructor
  ~CompleteBinaryTree();

  //Returns the element of the CBT pointed to by node. Behavior is undefined
  //if node does not exist. 
  T element(CBTNODE node);

protected:
  T *data;
  int numElts, maxElts;
};

typedef pair<string, unsigned int> INDEX;

template <typename T>
class BinaryHeap : public CompleteBinaryTree<T>
{
    public:
        //Maintain heap property with bottom up heapify method.
        void fixUp(CBTNODE hole);
};
bool operator>(INDEX &v1, INDEX &v2);

Implementation:

template <typename T>
T CompleteBinaryTree<T>::element(CBTNODE node) {
  assert(node >= 0);
  assert(node < numElts);
  return data[node];
}

template <typename T>
void BinaryHeap<T>::fixUp(CBTNODE hole)
{
    T tmp = this->element(hole);    
    while( hole > 0 && this->element(hole/2) < tmp )
    {
        //do stuff
    }
}

bool operator>(INDEX &v1, INDEX &v2)
{
    if(v1.second == v2.second)  //if two have same relevance
    {
        return v1.first < v2.first;
    }
    return v1.second > v2.second;
}

Answer 1

A temporary, such as the result of element func, cannot be bound to a reference to non-const, such as the formal arguments of your operator>.

Declare it thusly:

bool operator>( INDEX const& v1, INDEX const& v2 )

However, the implementation that you present doesn't seem to be correct for operator>.

And while I'm at it, what you want is really operator< instead, because that's the one required by standard algorithms. Perhaps combined with an operator== (because it's inefficient to synthesize it from operator<). With those two any relationship can be checked for relatively efficiently.

Btw., if you stop using ALL UPPERCASE names for anything else then macros (see the FAQ), then you can avoid inadvertent name collision with macros.

Cheers & hth.,

Answer 2

Don't typedef INDEX, be explicit:

template<class F, class S>
struct Index {
    std::pair<F, S> Value;
    Index(const std::pair<F, S>& pValue)
     : Value(pValue) {}
};

template<class F, class S>
bool operator<(const Index<F, S>& pLeft, const Index<F, S>& pRight) {
    // your implementation...
}