C2678: error on insertion of Binary search tree c++

Question

Using visual studios 2015 for C++ implementation I am receiving a compilation error in my insertHelper().

Insert Helper is a recursive function listed below.

    template < typename DataType, typename KeyType >
    void BSTree<DataType, KeyType>::insertHelper(BSTreeNode *&p,
    const DataType &newDataItem)

    // Recursive helper function for insert. Inserts newDataItem in
    // the subtree pointed to by p.

{
    if (p == NULL) {
        p->dataItem = newDataItem;
        p->left = NULL;
        p->right = NULL;
    }
    else {
        if (p->dataItem < newDataItem) { // <- error triggers here
            insertHelper(p->left, newDataItem);
        }
        else {
            insertHelper(p->right, newDataItem);
        }
    }
}

Insert Helper is called by insert here:

 template < typename DataType, typename KeyType >
    void BSTree<DataType, KeyType>::insert(const DataType &newDataItem)

// Inserts newDataItem into a tree. If an data item with the same key
// as newDataItem already exists in the tree, then updates that
// data item's data with newDataItem's data.

{
    insertHelper(root, newDataItem);
}

And a simplified version of my trees header file is here.

#ifndef BSTREE_H
#define BSTREE_H
#include <stdexcept>
#include <iostream>
using namespace std;

template < typename DataType, class KeyType >    // DataType : tree data item
class BSTree                                     // KeyType : key field
{
public:

    // Constructor
    BSTree();                         // Default constructor
    // Binary search tree manipulation operations
    void insert(const DataType& newDataItem);  // Insert data item
protected:
    class BSTreeNode                  // Inner class: facilitator for the BSTree class
    {
    public:

        // Constructor
        BSTreeNode(const DataType &nodeDataItem, BSTreeNode *leftPtr, BSTreeNode *rightPtr);

        // Data members
        DataType dataItem;         // Binary search tree data item
        BSTreeNode *left,    // Pointer to the left child
            *right;   // Pointer to the right child
    };

    // Recursive helpers for the public member functions -- insert
    // prototypes of these functions here.
    void insertHelper(BSTreeNode *&p, const DataType &newDataItem);

    // Data member
    BSTreeNode *root;   // Pointer to the root node
};

#endif  // define BSTREE_H

Test Data and initialization :

class TestData
{
  public:

    void setKey ( int newKey )
        { keyField = newKey; }   // Set the key

    int getKey () const
        { return keyField; }     // Returns the key

  private:

    int keyField;                // Key for the data item
};

int main()
{
    BSTree<TestData,int> testTree;   // Test binary search tree
    TestData testData;               // Binary search tree data item
}

I don't understand why I can't use if (p->dataItem < newDataItem){}. I've tried if (p.dataItem < newDataItem){} and even just if (dataItem < newDataItem){}. And I am getting nowhere fast with this bug. Any help would be appreciated.

The error reads:

C2678 : binary '<': no operator found which takes a left-hand BST operand of type 'TestData' (or there is no acceptable conversion).

What's the error message, and what's `DataType` when you call `insert`? — songyuanyao, Jul 20 '16 at 02:02
What is `TestData`, and how have you defined its `operator<`? — aschepler, Jul 20 '16 at 02:06
`DataType` is just the typename of whatever the input is. In this case `int`. — Callat, Jul 20 '16 at 02:06
@aschepler no. Do I need to overload it to use it in this case? — Callat, Jul 20 '16 at 02:07
It seems you specify `TestData` as the template argument `DataType`, which doesn't have `operator<`, so `p->dataItem < newDataItem` failed. — songyuanyao, Jul 20 '16 at 02:07
@songyuanyao but `dataItem` in `p->dataItem` and `newDataItem` are both of type `DataType` — Callat, Jul 20 '16 at 02:14
`class X {}; X a, b; if (a < b) {}` this will also fail to compile with the same error. Just because they're the same type doesn't mean that `operator<` is defined. — Sam Varshavchik, Jul 20 '16 at 02:15
@KazRodgers Yes, they're `DataType`, which is `TestData`, which doesn't have `operator<`, isn't it? You don't show all the code, I guess you write sth like `BSTree b; b.insert(some_TestData);`. — songyuanyao, Jul 20 '16 at 02:16
@gsamaras According to what I've read in the help segment this is minimal as it is the function that I am having a problem with along with all defining information. The only thing I did not include here is main which is unneeded because the code does not even compile. Main is never even looked at. — Callat, Jul 20 '16 at 02:17
@songyuanyao thanks I kind of figured since these are templates that overloading for comparisons was unneeded but I suppose your right after all nothing I've tried has worked — Callat, Jul 20 '16 at 02:21
@KazRodgers There're 2 things at least you should show us. The declaration of `TestData` mensioned in the error message, and how you instantiate `BSTree`, it's important for class template. [MCVE](http://stackoverflow.com/help/mcve) means sample code we can run it directly to reproduce the error. — songyuanyao, Jul 20 '16 at 02:24
@KazRodgers So what makes a `TestData` less than another `TestData`? That is what your template expands to, which is why you get the error. No one knows, not anyone here (except maybe yourself), and neither does the compiler. — PaulMcKenzie, Jul 20 '16 at 02:30
@KazRodgers It's clear now, the reason is just as my previous comments said. You might need to provide `operator<` for `TestData`. — songyuanyao, Jul 20 '16 at 02:32

score 1 · Accepted Answer · answered Jul 20 '16 at 05:48

if (p->dataItem < newDataItem) { // <- error triggers here

base on

BSTree<TestData,int> testTree;

we know that p->dataItem and newDataItem are of type TestData.

So the comparison above expands to

if (p->dataItem.operator<(newDataItem))

Now lets look at the error message again:

binary '<': no operator found which takes a left-hand BST operand of type 'TestData' (or there is no acceptable conversion).

It was looking for a binary '<' operator. You haven't provided one, so the language can't implement your requested < comparison.

class TestData
{
  public:

    void setKey ( int newKey )
        { keyField = newKey; }   // Set the key

    int getKey () const
        { return keyField; }     // Returns the key

    bool operator < (const TestData& rhs) const
        { return keyField < rhs.keyField; }

  private:

    int keyField;                // Key for the data item
};

or

class TestData
{
  public:

    void setKey ( int newKey )
        { keyField = newKey; }   // Set the key

    int getKey () const
        { return keyField; }     // Returns the key

    friend bool operator < (const TestData&, const TestData&);

  private:

    int keyField;                // Key for the data item
};

bool operator < (const TestData& lhs, const TestData& rhs)
{
    return lhs.keyField < rhs.keyField;
}

Live demo: http://ideone.com/Y7JGCD

Can confirm this fixed my problem. Thank you. And I have a follow up question based off the need to overload the `operator<`. I can see that I'm going to need to also overload operator=`. Should my return type be `int` because of keyField? or `TestData` because of the class name? — Callat, Jul 20 '16 at 15:56
@KazRodgers DataType::operator= (single =) has to return DataType&, e.g. `DataType& operator=(int value) { keyField = value; return *this; }`. See also http://stackoverflow.com/questions/4421706/operator-overloading — kfsone, Jul 20 '16 at 18:31

C2678: error on insertion of Binary search tree c++

1 Answers1