Перегрузка операторов шаблонами внутри BST - PullRequest
Новая
       10

Перегрузка операторов шаблонами внутри BST

0 голосов
/ 23 февраля 2011

В настоящее время у меня есть настройка бинарного дерева поиска, использующая шаблоны, которые позволяют мне легко изменять тип данных в бинарном дереве поиска. В данный момент у меня возникают проблемы с перегрузкой класса studentRecord, которая содержит данные, которые будут храниться в дереве. Мне нужно перегрузить операторы сравнения в этом классе, чтобы мой BST мог правильно сравнивать два объекта на основе одного из их содержимого (в данном случае, идентификатора студента). Однако, несмотря на перегрузку операторов в studentRecord, правильное сравнение по-прежнему не выполняется.

Подробности ниже:

На данный момент создан объект bst studentTree типа 

bst<studentRecord *> studentTree;

studentRecord - это следующий класс: 

// studentRecord class
class studentRecord{
public:
    // standard constructors and destructors
    studentRecord(int studentID, string lastName, string firstName, string academicYear){ // constructor
        this->studentID=studentID;
        this->lastName=lastName;
        this->firstName=firstName;
        this->academicYear=academicYear;
    }

    friend bool operator > (studentRecord &record1, studentRecord &record2){
        if (record1.studentID > record2.studentID)
            cout << "Greater!" << endl;
        else
            cout << "Less then!" << endl;
        return (record1.studentID > record2.studentID);
    }

private:
    // student information
    string studentID;
    string lastName;
    string firstName;
    string academicYear;
};

Всякий раз, когда новые элементы добавляются в мой BST, они должны сравниваться друг с другом. Следовательно, я хотел перегрузить класс studentRecord, чтобы при выполнении этого процесса сравнения идентификаторы studentID сравнивались (иначе будет выполнено недопустимое сравнение).

Однако моя функция вставки никогда не использует мои перегруженные функции сравнения. Вместо этого он, кажется, сравнивает два объекта другим способом, что приводит к неправильной сортировке в BST. Ниже приведена часть моей функции вставки - важно отметить, что и toInsert, и данные nodePtr-> должны иметь тип studentRecord из-за происходящего процесса шаблонирования. 

// insert (private recursive function)
template<typename bstType>
void bst<bstType>::insert(bstType & toInsert, bstNodePtr & nodePtr){
    // check to see if the nodePtr is null, if it is, we've found our insertion point (base case)
    if (nodePtr == NULL){
        nodePtr = new bst<bstType>::bstNode(toInsert);
    }

    // else, we are going to need to keep searching (recursive case)
    // we perform this operation recursively, to allow for rotations (if AVL tree support is enabled)
    // check for left
    else if (toInsert < (nodePtr->data)){ // go to the left (item is smaller)
        // perform recursive insert
        insert(toInsert,nodePtr->left);

        // AVL tree sorting
        if(getNodeHeight(nodePtr->left) - getNodeHeight(nodePtr->right) == 2 && AVLEnabled)
            if (toInsert < nodePtr->left->data)
                rotateWithLeftChild(nodePtr);
            else
                doubleRotateWithLeftChild(nodePtr);
    }

Кроме того, вот часть определения класса BST 

// BST class w/ templates
template <typename bstType>
class bst{

private: // private data members

    // BST node structure (inline class)
    class bstNode{
    public: // public components in bstNode

        // data members
        bstType data;
        bstNode* left;
        bstNode* right;

        // balancing information
        int height;

        // constructor
        bstNode(bstType item){
            left = NULL;
            right = NULL;
            data = item;
            height = 0;
        }

        // destructor
        // no special destructor is required for bstNode     
    };

    // BST node pointer
    typedef bstNode* bstNodePtr;

public: // public functions.....

Есть идеи, что может быть причиной этого? Я перегружаю неправильный класс или неправильную функцию? Любая помощь приветствуется - я, кажется, теряюсь, потому что происходит так много разных вещей одновременно.

Ответы [ 2 ]

2 голосов
/ 23 февраля 2011

Вы создаете экземпляр своего шаблона таким образом: 

bst<studentRecord *> studentTree;

Итак bstType == studentRecord *

Вставка выглядит следующим образом: 

template<studentRecord*>
void bst<studentRecord*>::insert(studentRecord*& toInsert, bst<studentRecord*>::bstNodePtr & nodePtr);

так что вы делаете сравнение указателей, и именно поэтому ваш оператор не называется, как уже указывал Аша.

Более того, вы перегружаете только оператор «больше» (>), но при вставке вы используете оператор «меньше» (<). Если вы действительно сравниваете два объекта типа studentRecord при вставке, код даже не должен компилироваться и должен жаловаться, что не может найти подходящий оператор меньше. </p>

Более того, я могу указать на несколько проблем в вашем коде:

  1. studentRecord.studentID имеет тип string? Однако вы пытаетесь присвоить ему целое число в конструкторе. Это просто преобразует целое число в тип char и назначает символ в строку - так что, вполне вероятно, не то, что вы хотели.
  2. Вам не хватает оператора меньше.

Ниже приведен код и некоторый код, демонстрирующий, что оператор вызывается при сравнении двух экземпляров типа studentRecord. Вы также можете увидеть, каковы будут последствия пропущенного оператора меньше, комментируя определение оператора в классе studentRecord (-> ошибка компиляции). 

class studentRecord
{
public:

    studentRecord(int studentID) : studentID(studentID)
    { 
    }

    bool operator > (studentRecord &record)
    {
        return (studentID > record.studentID);
    }

    /* Uncomment to get rid of the compile error!
    bool operator < (studentRecord &record)
    {
        return studentID < record.studentID;
    }
    */

private:
    // student information
    int studentID;
};

int main()
{
    studentRecord r1(10);
    studentRecord r2(5);

    if ( r1 < r2 )
    {
        cout << "It works! " << "r1 less than r2" << endl;
    }
    else
    {
        cout << "It works! " << "r1 greater than r2" << endl;
    }

    if ( r1 > r2 )
    {
        cout << "It works! " << "r1 greater than r2" << endl;
    }
    else
    {
        cout << "It works! " << "r1 less than r2" << endl;
    }
}

В качестве заключительного комментария, вероятно, было бы неплохо указать и другие операторы сравнения (> =, <=, == и! =. </p>

1 голос
/ 23 февраля 2011

Ваше дерево - это дерево указателей .Поэтому, когда вы пытаетесь вставить элемент в дерево, значения указателей сравниваются.Так что ваш перегруженный оператор не называется.Если вы хотите использовать перегруженный оператор, вы должны создать bst<studentrecord>

...