Type Mismatch?

[coolbeanbob]

This is a lot of code, but most can be ignored. I am just having a problem with using templates/types.

main.cpp(48) : error C2664: 'HashTable<Entry>::insert' : cannot convert parameter 1 from 'int' to 'int &'

There is basically a type mismatch between line 48 of main (int) and the HashTable::insert function.

What am I doing wrong?

main.cpp

#include "utility.h"
#include "Key.h"
#include "HashTable.h"

using namespace std;

int main() 
{
    const int num_files = 2;						
	const string fileNames[num_files] = {"Lab8a.txt", "Lab8b.txt"};
	int temp_array300[300];
	int temp_array750[750];

	// Fill up temporary arrays
	for (int j = 0; j < num_files; j++)	
	{	
		ifstream fin(fileNames[j].c_str());
		if (!fin.is_open())
		{
			cout << endl << "Unable to open input file" << fileNames[j]	<< endl;
			return 1;
		}
		
		int i = 0;
		if (j == 0)
		{
			for (i = 0; i < 300; i++)
			{
				fin >> temp_array300[i];
				//cout << i << ": " << temp_array300[i] << endl;
			}
		}
		else
		{
			for (i = 0; i < 750; i++)
			{
				fin >> temp_array750[i];
				//cout << i << ": " << temp_array750[i] << endl;
			}
		}
	}





	HashTable<int> hTable1;
	hTable1.insert(3241);





	
	cout << "hello world" << endl;




}

HashTable.h

#ifndef HASHTABLE_H
#define HASHTABLE_H

#include "utility.h"
#include "Key.h"
#include <list>

using namespace std;

template <class Entry>
class HashTable
{
public:
    HashTable(); //constructor

	Key hash_function(Entry &x);
	void insert(Entry &k);
	std::vector<list<Key>> my_vec[97];
};

template <class Entry>
HashTable<Entry>::HashTable()
{


}

template <class Entry>
Key HashTable<Entry>::hash_function(Entry &x)
{

	int remainder[4];

	int data = x;
	int hashed_data = 0;
	cout << "Number is " << data << endl;

	for(int i = 0; i < 4; i++)
	{
		remainder[i] = data % 10;	
		data = data/10;
		
		cout << "Remainder: " << remainder[i] << endl;
		cout << "x: " << data << endl;	
	}

	hashed_data = remainder[3]*10 + remainder[2] + remainder[1]*1000 + remainder[0]*100;
	
	cout << "Hash is " << hashed_data % 97 << endl;
	return (hashed_data % 97);

}

template <class Entry>
void HashTable<Entry>::insert(Entry &k)
{
	int index = hash_function(k);
	my_vec[index] = k;
	cout << "my_vec(index) = " << my_vec[index] << endl;



}



#endif //HASHTABLE_H

Key.cpp

#include "key.h"

double Key::comparisons = 0;

Key::Key(int v ) 
{
    //ctor
	key = v;
}

int Key::the_key() const
{
	return key;
}

// Operator overload for ==  to compare the integer key 
// member variables between two Key objects, also increments comparisons
bool operator ==(const Key &x, const Key &y) 
{
	++Key::comparisons;
    return x.the_key() == y.the_key();
}

// Operator overload for > to compare the integer key 
// member variables between two Key objects, also increments comparisons
bool operator>(const Key &x, const Key &y) 
{
	++Key::comparisons;
    return x.the_key() > y.the_key();
}

// Operator overload for < to compare the integer key 
// member variables between two Key objects, also increments comparisons
bool operator<(const Key &x, const Key &y) 
{
	++Key::comparisons;
    return x.the_key() < y.the_key();
}

// Operator overload for >=  to compare the integer key 
// member variables between two Key objects, also increments comparisons
bool operator >=(const Key &x, const Key &y) 
{
	++Key::comparisons;
    return x.the_key() >= y.the_key();
}

// Operator overload for <=  to compare the integer key 
// member variables between two Key objects, also increments comparisons
bool operator <=(const Key &x, const Key &y) 
{
	++Key::comparisons;
    return x.the_key() <= y.the_key();
}

// Operator overload for !=  to compare the integer key 
// member variables between two Key objects, also increments comparisons
bool operator !=(const Key &x, const Key &y) 
{
	++Key::comparisons;
    return x.the_key() != y.the_key();
}

Key.h

#ifndef KEY_H
#define KEY_H

//header file for class Key.  Keys are
//just integers with overloaded comparison
//operators to count compares.

class Key
{
public:
	//static variable to count the number of
	//times a comparison is made against a Key object
	static double comparisons;
	
	Key (int x = 0);
	//constructor 
	//default is to set the integer value key to 0

	int the_key() const;
	//accessor function - to inspect key value

private:
	int key;
};

//overload relational operators for type Key
//each also increments the comparisons counter variable
bool operator ==(const Key &x, const Key &y);
bool operator > (const Key &x, const Key &y);
bool operator < (const Key &x, const Key &y);
bool operator >=(const Key &x, const Key &y);
bool operator <=(const Key &x, const Key &y);
bool operator !=(const Key &x, const Key &y);



#endif //KEY_H

[vijayan121]

Make the code const-correct.
http://www.parashift.com/c++-faq-lite/const-correctness.html

template <class Entry>
class HashTable
{
public:
    HashTable(); //constructor

	Key hash_function( const Entry &x ) const ;
	void insert( const Entry &k );
	std::vector<list<Key>> my_vec[97];
};

// also in the definitions

[coolbeanbob]

Make the code const-correct.
http://www.parashift.com/c++-faq-lite/const-correctness.html

template <class Entry>
class HashTable
{
public:
    HashTable(); //constructor

	Key hash_function( const Entry &x ) const ;
	void insert( const Entry &k );
	std::vector<list<Key>> my_vec[97];
};

// also in the definitions

I'm getting the same error. The link you provided did not work. Any other ideas?

[raptr_dflo]

Did you make your implementation match the method-declaration in the class? We don't need 1,000 lines of code, the original error message told you exactly what the problem was: you originally declared your insert() method to take type Entry & which allows the argument to be altered within the method, replacing the original passed-in value; you can't pass a numeric constant to that, since it can't be altered. You must either declare an int variable, and pass the variable (whose value -can- be altered), or (since your implementation isn't changing the value being passed) declare the argument as const Entry & , meaning you're still passing by reference but guaranteeing that the value won't be changed, so that passing a constant is OK.

If doing the latter, just make sure you change the insert() method specification in both places (in the class definition at line 17, and the method implementation at line 55, in HashTable.h). And because insert() then calls hash_function() with the same parameter (which, if you passed a numeric constant, still can't be altered), you need to do the same for that method.

[coolbeanbob]

Thanks, I think I get what you are saying.

I have another question. I need to make an array, which I have done using the ptr variable (line 20). Now I need to load a list into each index of the array. I think I can make the ptr point to each list. Can this be implemented in the for loop (line 34)? Or do I need to specify a unique list name for each index?

I obviously have a problem on line 37. I am trying to figure out how to get the pointer to point to the list.

Am I at least on the right track?

#ifndef HASHTABLE_H
#define HASHTABLE_H
 
#include "utility.h"
#include "Key.h"
 
using namespace std;
 
template <class Entry>
class HashTable
{
public:
    HashTable(const Entry &x); //constructor
 
	int hash_function( const Entry &x) const;
	void insert( const Entry &k);
//	std::vector<list<Key>> my_vec[97];

protected:
	int *ptr;

};
 
template <class Entry>
HashTable<Entry>::HashTable(const Entry &x)
{	
	int size = x;

	ptr = new int [size]; 


	ptr[5] = 4;
	cout << "ptr : " << ptr[5] << endl;
	for(int i = 0; i < size; i++)
	{		
		std::list<int> mylist;
		ptr[i] = mylist;
	}

}

[raptr_dflo]

Hmmmm, a couple of things. First of all, if your HashTable constructor is supposed to take the size of the table (and just store items of type Entry), then you should probably specify its argument as type int instead of const Entry & . Assigning the parameter to an integer at line 27 only works for certain types, and Entry could be almost anything.

Then, you can't assign a std::list<int> to an element of an array-of-integers. If you can use STL containers anyway, you could just have a vector<> of lists, and I think your constructor can be as simple as:

template <class Entry>
HashTable<Entry>::HashTable(int size)
{
    // std::vector<std::list<int>> table;
    table = std::vector<std::list<int>>(size);
}

where std::vector<type>(val) creates a new vector of initial-length val , storing elements of type type .

If you're required to use arrays instead, then something more ugly like the following would work:

template <class Entry>
HashTable<Entry>::HashTable(int size)
{
    // int **table
    table = new int* [size];
    // new" probably default-initializes the int* array members to NULL, but if not:
    // for (int i = 0; i < size; i++)
    //     table[i] = NULL;
}

... keeping in mind that before you can use one of the "lists" in table, you need to allocate an appropriate amount of memory and assign that back to the table-entry.

[coolbeanbob]

... keeping in mind that before you can use one of the "lists" in table, you need to allocate an appropriate amount of memory and assign that back to the table-entry.

So if I were to use your second example, I would need to declare the list somewhere? Then link each pointer to it's appropriate list?

I was trying to do that here. I guess I need to first make p = NULL?

template <class Entry>
HashTable<Entry>::HashTable(const Entry &x)
{	
	int size = x; 
	ptr = new int [size]; 
 
	for(int i = 0; i < size; i++)
	{		
		std::list<int> mylist;
		ptr[i] = mylist;
	}
 
}

[coolbeanbob]

I guess my biggest question is how do I connect an index of the array to a list?

I tried

ptr[i] = mylist.begin(); // fails
ptr[i]->mylist.begin(); // fails

I would think this would work. ptr is a pointer variable, and I believe mylist.begin() is a pointer (first iterator of the list).

[raptr_dflo]

If you want a dynamic array of std::list<> containers, then declare ptr correctly in your class definition:

std::list<int> *ptr;

and allocate it correctly in your constructor:

ptr = new std::list<int> [size];

Then I think the rest of your code will work as intended. (And don't forget to pass the HashTable size in as an integer, not a const Entry &!)

If you mean to use the code as I posted it, yes you would need to allocate the lists somewhere, but until you know how much memory you need, there's no point doing it in the constructor.

The advantage of the STL containers is that they hide all the ugly details of the memory management from you. The disadvantage is that you then don't learn how dynamic memory works. At least, not the way you learn it if you have to implement it yourself, and get it right! :)

Here's a class I've re-written enough times ... I'm doing it from memory, so bear with me if there are compiler errors! It should give you an idea of what's really involved in allocating memory dynamically, and keeping track of where you're at. Now you know why there's a Standard Template Library, especially of already-implemented containers! :)

class GrowableIntBuffer
{
private:
    int currentSize;
    int maxSize;
    int *data;

    void growBuffer();  // called as needed by appendVal()

public:
    GrowableIntBuffer();
    ~GrowableIntBuffer();

    void appendVal(int val);
    void print();
};

GrowableIntBuffer::GrowableIntBuffer() :
    maxSize(0), currentSize(0), data(NULL)
{
    // members will become more useful as items are added
}

GrowableIntBuffer::~GrowableIntBuffer()
{
    // when done with the buffer, we need to give back the memory
    if (data != NULL)
        delete [] data;
}

GrowableIntBuffer::appendVal(int val)
{
    if (current_size == max_size)
        growBuffer();
    data[current_size] = val;
    current_size++;
}

void GrowableIntBuffer::print()
{
    for (int i = 0;  i < current_size;  ++i) {
        std::cout << data[i] << " ";
}

void GrowableIntBuffer::growBuffer()
{
    int new_size;
    if (max_size == 0)
        new_size = 10;
    else
        new_size = max_size * 2;

    int * new_data = new int [new_size];
    if (new_data == NULL) {
        // handle error condition, probably return false,
        // remember to change return type!
    }
    else {
        // copy values into new space
        for (i = 0;  i < current_size;  ++i)
            new_data[i] = data[i];
        // get rid of old space
        delete [] data;
        // update members to reflect new space (note, current_size hasn't changed!)
        data = new_data;
        max_size = new_size;
    }
}

[raptr_dflo]

In response to your question:
ptr is a pointer, but ptr is not, it's been declared to be an int. Even if ptr were a pointer, std::list<int> is not a pointer, its an instance of a class which internally manages a pointer (or several, the point is, you shouldn't need to know how it's implemented in order to use it). std::list<int>.begin() is a pointer to a std::list<int>::iterator object, so now you might be getting close, but any halfway decent compiler is going to issue a warning that a "int *" isn't the same as a "std::list<int>::iterator *", though it will probably still compile at that point.

[coolbeanbob]

Just found out that I can use a static array, so I have re-written my code.

On line 19, should I declare this to be a array of lists, all in one swoop?
Something like...

int hash_array<list<int>>[250]; //does not compile, but is this the right idea?

The whole idea of working with an array of lists is confusing me. I would like to leave the pointers out, which it appears I can by using a static array.

#ifndef HASHTABLE_H
#define HASHTABLE_H 
#include "utility.h" 
using namespace std;
 

class HashTable
{
public:
    HashTable(int x); //constructor
 
	int hash_function(int x) const;
	void insert(int k);
	bool search(int k);


protected:
	//int *ptr;	// compiles
	int hash_array[250];
}; 

HashTable::HashTable(int x)
{	
	int size = x;

	std::list<int> mylist;
	for(int i = 0; i < size; i++)
	{	
		hash_array[i]=mylist;
	}
}


int HashTable::hash_function(int x) const
{ 
	int remainder[4]; 
	int data = x;
	int hashed_data = 0;
	cout << "Number is " << data << endl;
 
	for(int i = 0; i < 4; i++)
	{
		remainder[i] = data % 10;	
		data = data/10;
	}
 
	hashed_data = remainder[3]*10 + remainder[2] + remainder[1]*1000 + remainder[0]*100;
 
	cout << "Hash is " << hashed_data % 97 << endl;
	return (hashed_data % 97);

}
 
void HashTable::insert(int k)
{
	int index = hash_function(k);
	// search() for duplicate, if dup found, don't insert, otherwise insert.
	hash_array[index] = k;
	cout << "hash_array[index] = " << hash_array[index] << endl;

	cout << "ptr(index) = " << hash_array[index] << endl; 
}
  
 
#endif //HASHTABLE_H

[coolbeanbob]

Is this the proper implementation for an array of lists?

list<int> hash_array[250];

[raptr_dflo]

Looks right to me:

SomeType someVariableName[constHowManyToAllocate];
int int_array[10];
char text[256];
const int HASH_SIZE = 250;
std::list<int> hash_array[HASH_SIZE];  // OK: HASH_SIZE is known at compile-time

Does it compile? Does your code appear to be running correctly?