C++ Issue: "undefined reference"

Esoteric · 05-29-2008, 07:28 AM

Hey guys, I am working on a project for a class, I am a little stuck though as to why I am getting this error.

I am required to use this code, as a baseline and expand from it to make it work.

When I try and use the Dictionary class in main I get the error "undefined reference to `Dictionary<char, char>:ictionary()'"

Any help would be appreciated.

-Erik

Code:

#include <iostream>
using namespace std;


// == Class HashTable
template <typename HashedObj>
class HashTable
{
public:
	explicit HashTable( int size = 101 );
	
	bool contains ( const HashedObj & x ) const;
	
	void makeEmpty();
	void insert( const HashedObj & x );
	void remove( const HashedObj & x );
	
private:
	int currentSize;
	
	void rehash();
	int myhash( const HashedObj & x ) const;
};



// == Class Pair ==
template <typename HashedObj, typename Object>
class Pair
{
	HashedObj key;
	Object def;

};

// == Dictionary Class ==
template <typename HashedObj, typename Object>
class Dictionary
{
public:
	Dictionary( );
	
	void insert( const HashedObj & key, const Object & definition );
	const Object & lookup( const HashedObj & key ) const;
	bool isEmpty() const;
	void makeEmpty();

private:
	HashTable<Pair<HashedObj,Object> > items;

};


// == MAIN ==
int main ()
{
	Dictionary <char,char> my_dictionary;
	
	return 0;
}

Nylex · 05-29-2008, 07:51 AM

How are you compiling your code? Are your definitions for your class constructors and member functions in another file? They must be if they're not in the file you've shown. You need to include this file when you're compiling. For example, say the file containing your main() function is called "main.cpp" and the file containing your definitions for member functions and constructors is called "definitions.cpp", you should be able to compile with

g++ main.cpp definitions.cpp -o main,

assuming of course you're using g++.

Edit: you'll also need your class declaration present in your definitions file. Of course, the better way to do it would be to put your class declarations in header files and include those in both your main file and the file containing the definitions for your constructors and member functions. Edited again: Or, you just put everything in one file..

Esoteric · 05-29-2008, 08:00 AM

I am not following you, unfortunately I haven't programmed in C++ in 5-6 years and I wasn't a big C++ programmer back then, but this class is required and I am trying to do my best.

I am using g++ as my compiler.

Quote:

Are your definitions for your class constructors and member functions in another file? They must be if they're not in the file you've shown. You need to include this file when you're compiling.

My understanding is that I have defined everything so far. I do realize I didn't have a constructor or deconstructor for the Pair class so I have fixed this.

If you are willing, I would appreciate any explanation or help.

I am trying to find a good resource for relearning class and class templating right now.

Thanks.
-Erik

Nylex · 05-29-2008, 08:13 AM

I shall stop using the terms "declaration" and "definition", because I always get them the wrong way round.

Basically, you've only provided information about the member functions and constructions that exist, but you haven't specified what happens when those constructors/member functions are called.

You can put the code that runs when the constructors/member functions are called in the same file, for example

Code:

// A.h
class A
{
  public:
    A() { x = 0; }
    int get_x() { return x; }
  private:
    int x;
};

Code:

// main.cpp - example program
#include <iostream>
#include "A.h"
using namespace std;

int main()
{
  A myA;
  cout << A.get_x() << endl;
  return 0;
}

Obviously, you can put the whole lot in a single file (i.e. just merge the files above and then you just remove the "#include A.h" line).

You can also put the interface to the class - i.e. the code that says which members and constructors exist (but says nothing about what they do) in one file and the code for those in a separate file:

Code:

// A.h
class A
{
  public:
    A();
    int get_x();
  private:
    int x;
};

Code:

// A.cpp - definitions for constructor and member function
#include "A.h"

A::A() { x = 0; }

int A::get_x() { return x; }

The main program will be identical to that given above, but when you compile, you'll need to include the A.cpp file:

g++ main.cpp A.cpp -o main

Does this help at all?

Esoteric · 05-29-2008, 08:25 AM

Yeah I get where you are going, let me try something first and get back to you. I am just trying to get it to compile without actually "working", like compile without functionality at this point, as I am working on getting the functionality created.

Nylex · 05-29-2008, 08:27 AM

You can of course just put empty member functions and constructors in, e.g.

Code:

class A
{
  public:
    A() {}
    int get_x() {}
  private:
    int x;
};

Esoteric · 05-29-2008, 08:53 AM

Wow, such a simple fix, I am not sure why I didn't see that, I just made all of them empty member functions. I need to wake up apparently.

Okay, I will press on, hopefully I can get this working, if not I will be back, thanks for your hepl so far Nylex I appreciate it.

Esoteric · 05-29-2008, 09:04 AM

Okay now I am here...

Error .... at line "items[ key ] = definition;"

Code:

no match for ‘operator[]’ in ‘((Dictionary<std::basic_string<char, 
 std::char_traits<char>, std::allocator<char> >, 
 std::basic_string<char, std::char_traits<char>, 
 std::allocator<char> > >*)this)-
 >Dictionary<std::basic_string<char, std::char_traits<char>, 
 std::allocator<char> >, std::basic_string<char, 
 std::char_traits<char>, std::allocator<char> > >::items[key]’

Code ....

Code:

#include <iostream>
#include <string>

using namespace std;

// == HashTable Members ==
template <typename HashedObj>
class HashTable
{
public:
	explicit HashTable( int size = 101 ) {}
	
	bool contains ( const HashedObj & x ) const { return 0; }
	
	void makeEmpty() { }
	void insert( const HashedObj & x ) {}
	void remove( const HashedObj & x ) {}
	
	
private:
	int currentSize;
	
	void rehash() {}
	int myhash( const HashedObj & x ) const { return 0; }
	int myhash( int key ) { return 0; }
};
// == END HashTable Members ==


// == Class Pair ==
template <typename HashedObj, typename Object>
class Pair
{
	HashedObj key;
	Object def;

public:
	Pair() {}
	~Pair() {}
};

// == Dictionary Class ==
template <typename HashedObj, typename Object>
class Dictionary
{
public:
	Dictionary( void ) {}
	~Dictionary() {}

	void insert( const HashedObj & key, const Object & definition )
	{
		cout << key << " : " << definition << "\n";
		items[ key ] = definition;
	}
	const Object & lookup( const HashedObj & key ) const {}
	bool isEmpty() const { return true; }
	void makeEmpty() {}

private:
	HashTable<Pair<HashedObj,Object> > items;

};


// == MAIN ==
int main ()
{
	Dictionary <std::string, std::string> my_dictionary;
	
	my_dictionary.insert("hot", "not cold");
	
	return 0;
}

ntubski · 05-29-2008, 11:59 AM

You need to define the operator[] function for HashTable. The way you're using it, you need this signature:

Code:

//note this would have to be the HashedObj of Dictionary, not of HashTable
Object& operator[](const HashedObj & key);

Except that as you have written things, HashTable doesn't know anything about the objects it stores, so you won't be able to do this. If you don't want to change HashTable you could write Dictionary::insert as

Code:

        void insert( const HashedObj & key, const Object & definition )
	{
		cout << key << " : " << definition << "\n";

                Pair<HashedObj, Object> p(key, definition); //you have to add this constructor
		items.insert(p);
	}

Also see std::pair

Esoteric · 05-29-2008, 12:28 PM

Well I am limited to what I can change due to the restrictions of the text. I have been working on this a bit and this is what I have come up with.

Thanks for the operator[] code, I just have to figure out what to put in it now.

Error:

Code:

../src/cs270_a3.cpp: In member function ‘bool HashTable<HashedObj>::insert(const HashedObj&) [with HashedObj = Pair<std::basic_string<char, std::char_traits<char>, std::allocator<char> >, std::basic_string<char, std::char_traits<char>, std::allocator<char> > >]’:
../src/cs270_a3.cpp:233:   instantiated from ‘void Dictionary<HashedObj, Object>::insert(const HashedObj&, const Object&) [with HashedObj = std::basic_string<char, std::char_traits<char>, std::allocator<char> >, Object = std::basic_string<char, std::char_traits<char>, std::allocator<char> >]’
../src/cs270_a3.cpp:263:   instantiated from here
../src/cs270_a3.cpp:91: warning: comparison between signed and unsigned integer expressions
../src/cs270_a3.cpp: In member function ‘int HashTable<HashedObj>::findPos(const HashedObj&) const [with HashedObj = Pair<std::basic_string<char, std::char_traits<char>, std::allocator<char> >, std::basic_string<char, std::char_traits<char>, std::allocator<char> > >]’:
../src/cs270_a3.cpp:85:   instantiated from ‘bool HashTable<HashedObj>::insert(const HashedObj&) [with HashedObj = Pair<std::basic_string<char, std::char_traits<char>, std::allocator<char> >, std::basic_string<char, std::char_traits<char>, std::allocator<char> > >]’
../src/cs270_a3.cpp:233:   instantiated from ‘void Dictionary<HashedObj, Object>::insert(const HashedObj&, const Object&) [with HashedObj = std::basic_string<char, std::char_traits<char>, std::allocator<char> >, Object = std::basic_string<char, std::char_traits<char>, std::allocator<char> >]’
../src/cs270_a3.cpp:263:   instantiated from here
../src/cs270_a3.cpp:142: warning: comparison between signed and unsigned integer expressions
../src/cs270_a3.cpp: In member function ‘void HashTable<HashedObj>::rehash() [with HashedObj = Pair<std::basic_string<char, std::char_traits<char>, std::allocator<char> >, std::basic_string<char, std::char_traits<char>, std::allocator<char> > >]’:
../src/cs270_a3.cpp:92:   instantiated from ‘bool HashTable<HashedObj>::insert(const HashedObj&) [with HashedObj = Pair<std::basic_string<char, std::char_traits<char>, std::allocator<char> >, std::basic_string<char, std::char_traits<char>, std::allocator<char> > >]’
../src/cs270_a3.cpp:233:   instantiated from ‘void Dictionary<HashedObj, Object>::insert(const HashedObj&, const Object&) [with HashedObj = std::basic_string<char, std::char_traits<char>, std::allocator<char> >, Object = std::basic_string<char, std::char_traits<char>, std::allocator<char> >]’
../src/cs270_a3.cpp:263:   instantiated from here
../src/cs270_a3.cpp:154: warning: comparison between signed and unsigned integer expressions
../src/cs270_a3.cpp:158: warning: comparison between signed and unsigned integer expressions

Code:

#include <iostream>
#include <string>
#include <vector>

using namespace std;

// Source: Weiss
static const int ACTIVE  = 0;
static const int EMPTY   = 1;
static const int DELETED = 2;


// ======
bool isPrime( int n )
{
    if( n == 2 || n == 3 )
        return true;

    if( n == 1 || n % 2 == 0 )
        return false;

    for( int i = 3; i * i <= n; i += 2 )
        if( n % i == 0 )
            return false;

    return true;
}

int nextPrime( int n )
{
    if( n % 2 == 0 )
        n++;

    for( ; !isPrime( n ); n += 2 )
        ;

    return n;
}
// ======


// == HashTable Members ==
// Source: Weiss
template <typename HashedObj>
class HashTable
{
public:
	// Source: Weiss
	explicit HashTable( int size = 101 )
	{

	}
	
	/**
	 * Source: Weiss
	 */
	bool contains ( const HashedObj & x ) const
	{
		return isActive( findPos( x ) );
	}
	
	/**
	 * Source: Weiss
	 */
	void makeEmpty()
	{
		currentSize = 0;
		for( int i = 0; i < array.size(); i++ )
			array[ i ].info = EMPTY;
	}

	bool insert( const HashedObj & x ) 
	{
		int currentPos = findPos( x );
		if ( isActive( currentPos ) )
			return false;
		
		array[ currentPos ] = HashEntry( x , ACTIVE );
		
		if ( ++currentPos > array.size() / 2 )
			rehash();
		
		return true;
	}

	bool remove( const HashedObj & x )
	{
		int currentPos = findPos( x );
		if ( !isActive( currentPos ) )
			return false;
		
		array[ currentPos ].info = DELETED;
		return true;
	}
	
	bool operator[] ( const HashedObj & key )
	{
		return true;
	}
	
	enum EntryType { ACTIVE, EMPTY, DELETED };
	
private:
	struct HashEntry
	{
		HashedObj element;
		EntryType info;

		HashEntry( const HashedObj & e = HashedObj(), EntryType i = EMPTY )
			: element ( e ), info ( i ) { }
	};
	
	vector<HashEntry> array;
	int currentSize;
	
	bool isActive ( int currentPos ) const
	{
		return array[ currentPos ].info == ACTIVE;
	}

	int findPos( const HashedObj & x ) const
	{
		int offset = 1;
		int currentPos = myhash( x );
		
		while( array[ currentPos ].info != EMPTY &&
				array[ currentPos ].element != x )
		{
			currentPos += offset;
			offset += 2;
			if( currentPos >= array.size() )
				currentPos -= array.size();
		}
		
		return currentPos;
	}

	void rehash()
	{
		vector<HashEntry> oldArray = array;
		
		array.resize( nextPrime( 2 * oldArray.size() ) );
		for( int j = 0; j < array.size(); j++ )
			array[ j ].info = EMPTY;
		
		currentSize = 0;
		for( int i = 0; i < oldArray.size(); i++ )
			if( oldArray[ i ].info == ACTIVE )
				insert( oldArray[ i ].element );
	}

	int myhash( const HashedObj & key ) const
	{
		int hashVal = 0;
		
		hashVal %= array.size();
		if( hashVal < 0 )
			hashVal += array.size();
		
		return hashVal;
	}
};
// == END HashTable Class ==


// == BEGIN Pair Class ==
template <typename HashedObj, typename Object>
class Pair
{

public:
	Pair() { }
	
	void create( string k, string d )
	{
		key = k;
		def = d;
	}

	const string & getKey() const
	{
		return key;
	}

	const string & getDef() const
	{
		return def;
	}

	bool operator==( const Pair & rhs ) const
	{
		return getKey() == rhs.getKey();
	}
	
	bool operator!=( const Pair & rhs ) const
	{
		return !( *this == rhs );
	}
	
private:
	HashedObj key;
	Object def;

};
// == END Pair Class ==


// == Dictionary Class ==
template <typename HashedObj, typename Object>
class Dictionary
{
public:
	Dictionary( )
	{
		
	}

	void insert( const HashedObj & key, const Object & definition )
	{
		Pair<string,string> p;
		p.create(key, definition);
		items.insert(p);
	}

	const Object & lookup( const HashedObj & key ) const
	{
		
	}

	bool isEmpty() const
	{
		return true;
	}
	
	void makeEmpty()
	{
		
	}

private:
	HashTable<Pair<HashedObj,Object> > items;

};
// == END Pair Class ==


// == BEGIN main ==
int main ()
{
	Dictionary <string, string> d;
	
	d.insert("hot", "not cold");
	
	return 0;
}
// == END main ==

Esoteric · 05-29-2008, 12:44 PM

Nevermind, after resolving the comparison issues it resolved the other issues.

Now I just have to figure out how to do the lookup function.

Thanks.
-Erik

landonmkelsey · 05-30-2008, 06:12 PM

#include <iostream>
using namespace std;
template <class T>
bool tooBig(const T& val, const T& lim)
{
return val>lim;
}
template <class T>
class TooBig
{
public:
T cutoff_;
TooBig(const T& cutoff):cutoff_(cutoff) {}
bool operator() (const T& v)
{
return tooBig<T>(v,cutoff_);
}
};
int main()
{
TooBig<int> tb100(100);
int i = 101;
cout<<tb100(i)<<endl;
return 0;
}