C++

Forum

 
Insert in tree problem.

Dlazyguy (36)
So I'm trying to insert an object into a tree, the object contains a string that I will be using to search for nodes in the tree and do comparisons for and a vector string. I keep getting errors in the insert function for my tree and I feel like it's my operator overloading gone wrong. Here are the snippets to the code.
here is my class for the object I'm trying to insert in tree
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
 
#ifndef SEQUENCE_MAP
#define SEQUENCE_MAP
#include <iostream>
#include <vector>
#include <string>

class SequenceMap{
public:
       string rec;
       vector<string>acro;
       SequenceMap(string &x, vector<string> &y);
       void Merge(SequenceMap &x, SequenceMap &y);
       bool operator<(const SequenceMap& other);
};

SequenceMap::SequenceMap(string &x, vector<string> &y)
{
  acro=y;
  rec=x;
}
void Merge(SequenceMap &x, SequenceMap &y)
{
   for(int i=0; i<y.acro.size(); i++)
      {
          x.acro.push_back(y.acro[i]);
       }

}

bool operator<(const SequenceMap& other, const SequenceMap& others)
{
   if(other.rec<others.rec)
   return true;
  
}
#endif


here is the insert function from tree
1
2
3
4
5
6
7
8
9
10
11
 
void insert( Comparable && x, AvlNode * & t )
    {
        if( t == nullptr )
            t = new AvlNode{ std::move( x ), nullptr, nullptr };
        else if( x < t->element )
            insert( std::move( x ), t->left );
        else if( t->element < x )
            insert( std::move( x ), t->right );
        
        balance( t );
    }


1
2
3
4
5
6
7
8
9
10
11
 
using namespace std;
int main( )
{
string x= "dog";
vector<string> lol;
lol.push_back("dog");
LazyAvlTree<SequenceMap> t;
SequenceMap test(x, lol);
t.insert(test);
return 0;
}

and that last one is my main.
Any help would be greatly appreciated.
Last edited on
kbw (9488)
I keep getting errors ...
You haven't posted the errors and you haven't posted the tree definitions. How are we to tell what's going on?
Dlazyguy (36)
The error happens when the insert function (2nd snippet above) is used during the "<" the "<" is supposed to compare the string from each object. The error is too long and can't be posted but the common error I see are bunch of substitution failed and ot derived errors. 
1
2
3
4
5
 
template argument deduction/substitution failed:
In file included from LazyAVLTree.cpp:2:0:
LazyAvlTree.h:178:20: note:   mismatched types ‘const _CharT*’ and ‘SequenceMap’
         else if( x < t->element )


1
2
3
 
LazyAvlTree.h:178:20: note:   ‘const SequenceMap’ is not derived from ‘const std::basic_string<_CharT, _Traits, _Alloc>’
         else if( x < t->element )

Here are the definitions 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
 
struct AvlNode
    {
        Comparable element;
        AvlNode   *left;
        AvlNode   *right;
        int       height;
        bool deleted;

        AvlNode( const Comparable & ele, AvlNode *lt, AvlNode *rt, int h = 0 )
          : element{ ele }, left{ lt }, right{ rt }, height{ h } { }
        
        AvlNode( Comparable && ele, AvlNode *lt, AvlNode *rt, int h = 0 )
          : element{ std::move( ele ) }, left{ lt }, right{ rt }, height{ h } { }
    };
Last edited on
kbw (9488)
I don't understand what's going on. I don't see where SequenceMap connects up with anything. Comparable things should define operator==, but I don't see that in your code.
http://en.cppreference.com/w/cpp/concept/EqualityComparable

This:
 
 
bool operator<(const SequenceMap& other);
should be:
 
 
bool operator<(const SequenceMap& other) const;


Dlazyguy (36)
hmm I think a better question to ask is how would I be able to insert an object into the tree with the comparison being the string of the object such as if one object has string "dog" other object has string "elephant" the object node with dog will be < elephant and will be placed accordingly.

LazyAVLTree<SequenceMap> tree; is a tree with objects of that class.
SequenceMap t;
t.SetString(some string);
tree.insert(t); where t holds the string and it compares it's placement with t.getString();
the header file:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
 
#ifndef SEQUENCE_MAP
#define SEQUENCE_MAP
#include <iostream>
#include <vector>
#include <string>

class SequenceMap{
public: 
     string recognition_;
      vector<string>sequence;
      void SetString(string x);
      string GetString();
      bool operator<(const SequenceMap &other) const;

};

#endif
#include "SequenceMap.cpp"

cpp file:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
 
void SequenceMap::SetString(string x)
{
   recognition_=x;
}

string SequenceMap::GetString()
{
  return recognition_;
}

bool SequenceMap::operator<(const SequenceMap &other)const
{
  return recognition_<other.GetString();
}

functions in my binary tree
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
 
#ifndef BINARY_SEARCH_TREE_H
#define BINARY_SEARCH_TREE_H

#include "dsexceptions.h"
#include <algorithm>

using namespace std;       

// BinarySearchTree class
//
// CONSTRUCTION: zero parameter
//
// ******************PUBLIC OPERATIONS*********************
// void insert( x )       --> Insert x
// void remove( x )       --> Remove x
// bool contains( x )     --> Return true if x is present
// Comparable findMin( )  --> Return smallest item
// Comparable findMax( )  --> Return largest item
// boolean isEmpty( )     --> Return true if empty; else false
// void makeEmpty( )      --> Remove all items
// void printTree( )      --> Print tree in sorted order
// ******************ERRORS********************************
// Throws UnderflowException as warranted


problem is the insert function in 1st post. in the "<" part always points to it as error i know i need an operater overload for the class just not sure how to properly implement it.
error message
1
2
3
4
 
SequenceMap.cpp: In member function ‘bool SequenceMap::operator<(const SequenceMap&) const’:
SequenceMap.cpp:18:39: error: no matching function for call to ‘SequenceMap::GetString() const’
   return recognition_<other.GetString();
Last edited on
kbw (9488)
 
 
string GetString();
should be
 
 
string GetString() const;

const operator< is trying to call non-const GetString which violates the const thing.

The idea of const is the implement a logical read-only interface on your object. You get const versions of things all the time. For example, passing a parameter as const ref generates a const version of your object. So you need to understand it.
dhayden (5795)
hmm I think a better question to ask is how would I be able to insert an object into the tree with the comparison being the string of the object such as if one object has string "dog" other object has string "elephant" the object node with dog will be < elephant and will be placed accordingly.

Look at your less-than operator:
1
2
3
4
5
6
 
bool operator<(const SequenceMap& other, const SequenceMap& others)
{
   if(other.rec<others.rec)
   return true;
  
}

What does this return if other.rec >= others.rec?

If the comparison operator is not reliable then the whole collection will be messed up.
Topic archived. No new replies allowed.