473,883 Members | 1,744 Online
Bytes | Software Development & Data Engineering Community
+ Post

Home Posts Topics Members FAQ

Tricky pointer problem?

Hello,

I'm having some trouble with implementing a hashtable (hashmap) for a
class at school.
The map's constructor is called with a hash function and the number of
possible keys the function returns. The get and set methods do work
well, only the []-operator does not work. When trying to do something
like map['D'] = "December", it seems like the = has no effect. At
least, if the value for the same key is read after assigning it, it
will be null.
I guess I got some pointer wrong or similar but I just cannot find the
mistake. I'd appreciate any help you can give.

So here's the code for the hashmap:

// ---
template<class KeyType, class DataType> class myhash {
public:
typedef unsigned int (*hashFunctionT ype)(const KeyType &);
typedef pair<KeyType, DataType> pairType;
typedef typename list<pairType>: :iterator listIterator;
private:
list<pairType> **data;
hashFunctionTyp e hashFunction;

inline pairType *findEntry(cons t unsigned int k, const KeyType &key)
const
{
for(listIterato r z = data[k]->begin(); z != data[k]->end(); z++)
if(z->first == key)
return &(*z);
return NULL;
}
public:
void set(const KeyType &key, const DataType &value)
{
unsigned int k = hashFunction(ke y);
if(data[k] == NULL)
{
data[k] = new list<pairType>( );
data[k]->push_back(*n ew pairType(key, value));
}
else
{
pairType *p = findEntry(k, key);
if(p == NULL) data[k]->push_back(*n ew pairType(key, value));
else p->second = value;
}
}
void get(const KeyType &key, DataType &value)
{
unsigned int k = hashFunction(ke y);
if(data[k] == NULL) throw new notfound_error( );
pairType *p = findEntry(k, key);
if(p == NULL) throw new notfound_error( );
value = p->second;
}
DataType &operator[] (const KeyType &key)
{
unsigned int k = hashFunction(ke y);
pairType *p;
if(data[k] == NULL) data[k] = new list<pairType>( ); // create new
list
else
{
p = findEntry(k, key);
if(p != NULL) return p->second;
nCollisions++;
}
DataType *d = new DataType(); // create new data type in case write
access is coming next to that element
p = new pairType(key, *d); // create key-value pair
data[k]->push_back(*p );
return *d; // return reference to data element
}
};
// ---

I left out the definition of the constructor and destructor as they
don't do interesting things.

Now in this test program the myhash template gets specialised with a
char as KeyType and a wrapper class around a const char * as DataType:

// ---
unsigned int hashfunc(const char &c) {
unsigned int i = c - 'A';
return (i*i)%100;
}

class constcharpointe r {
const char *_ptr;
public:
constcharpointe r(const char *ptr) { _ptr = ptr; }
constcharpointe r() { _ptr = 0; }
operator const char* () { return _ptr; }
};

int main() {
using namespace std;
myhash<char,con stcharpointer> h(hashfunc,100) ;
h['D'] = "Dezember";
cerr << "h['D']: " << h['D'] << endl; // this one triggers a
segmentation fault (null pointer returned)
cerr << "strcmp: " << strcmp(h['D'], "Dezember") << endl;
return 0;
}
// ---

The constcharpointe r class was written by the author of the programming
task and thus I guess should be working fine.

Regards,
Denis

Nov 25 '05 #1
6 2019
da********@gmai l.com wrote:
Hello,

I'm having some trouble with implementing a hashtable (hashmap) for a
class at school.
The map's constructor is called with a hash function and the number of
possible keys the function returns. The get and set methods do work
well, only the []-operator does not work. When trying to do something
like map['D'] = "December", it seems like the = has no effect. At
least, if the value for the same key is read after assigning it, it
will be null.
I guess I got some pointer wrong or similar but I just cannot find the
mistake. I'd appreciate any help you can give.

There's lots of problems with references and copying. You're confused
about when to use a pointer and when to use a value. Basically you are
allocating memory unecessarily (and never freeing it). I'll try and fix
them below
So here's the code for the hashmap:

// ---
template<class KeyType, class DataType> class myhash {
public:
typedef unsigned int (*hashFunctionT ype)(const KeyType &);
typedef pair<KeyType, DataType> pairType;
typedef typename list<pairType>: :iterator listIterator;
private:
list<pairType> **data;
hashFunctionTyp e hashFunction;

inline pairType *findEntry(cons t unsigned int k, const KeyType &key)
const
{
for(listIterato r z = data[k]->begin(); z != data[k]->end(); z++)
if(z->first == key)
return &(*z);
return NULL;
}
public:
void set(const KeyType &key, const DataType &value)
{
unsigned int k = hashFunction(ke y);
if(data[k] == NULL)
{
data[k] = new list<pairType>( );
data[k]->push_back(*n ew pairType(key, value));
Should be

data[k]->push_back(pair Type(key, value));

You don't need to allocate memory, just create the pairType directly.
}
else
{
pairType *p = findEntry(k, key);
if(p == NULL) data[k]->push_back(*n ew pairType(key, value));
Again should be

if(p == NULL) data[k]->push_back(pair Type(key, value));
else p->second = value;
}
}
void get(const KeyType &key, DataType &value)
{
unsigned int k = hashFunction(ke y);
if(data[k] == NULL) throw new notfound_error( );
pairType *p = findEntry(k, key);
if(p == NULL) throw new notfound_error( );
value = p->second;
}
DataType &operator[] (const KeyType &key)
{
unsigned int k = hashFunction(ke y);
pairType *p;
if(data[k] == NULL) data[k] = new list<pairType>( ); // create new
list
else
{
p = findEntry(k, key);
if(p != NULL) return p->second;
nCollisions++;
}
DataType *d = new DataType(); // create new data type in case write
access is coming next to that element
p = new pairType(key, *d); // create key-value pair
data[k]->push_back(*p );
return *d; // return reference to data element
Same error twice, neither memory allocation is necessary (both leak
memory) and then to make it worse you return a reference to the
allocated memory, which is not the object that is in the hash_map. This
is why it seems to have no effect.

Here's how you could do it

data[k]->push_back(pair Type(key, DataType()));
return data[k].last().second;

Note there is no need for memory allocation, no need for the d or p
variables, just create values with constructors. Also note how the
return statement returns a reference to the item you just added to the list.
}


You are using too many pointers, in all the wrong places. Remember
pointers are the work of the devil.

john
Nov 25 '05 #2
>
data[k]->push_back(pair Type(key, DataType()));
return data[k].last().second;


Typo, should be

return data[k]->last().secon d;

But there probably not good reason to use pointers to lists, it just
means you have to allocate them and then remember to free them, which is
tedious and error prone. Why not declare data like this

list<pairType> *data;

or even better like this

vector< list<pairType> > data;

then your lists will be created *automatically* you won't have to
allocate them, or free them.

You're flirting with the dark side, cease using pointers!

john
Nov 25 '05 #3
>
Typo, should be

return data[k]->last().secon d;


Sorry another typo

return data[k]->back().secon d;

john
Nov 25 '05 #4
Great, I'll try that and give feedback whether that solved my problems!

I'm sorry for all those pointers... I'm more familiar with Java
programming and in C++ I always feel like I have to use those evil
pointers :-)

Nov 27 '05 #5
Thank you very much, that solved my problems. Now the program is
working correctly!

But I have some questions about the changes, because I don't see why
this solution is working:

To create a pair, I use now:

data[k]->push_back(pair Type(key, DataType()));

just as you suggested. But why does that work? Doesn't that create a
new pairType on the current method's local stack and so should be
invalid as soon as the method returns? That's why I made had a call to
'new' there.

Nov 28 '05 #6
da********@gmai l.com wrote:
Thank you very much, that solved my problems. Now the program is
working correctly!

But I have some questions about the changes, because I don't see why
this solution is working:

To create a pair, I use now:

data[k]->push_back(pair Type(key, DataType()));

just as you suggested. But why does that work? Doesn't that create a
new pairType on the current method's local stack and so should be
invalid as soon as the method returns? That's why I made had a call to
'new' there.


No, because what goes into the the hash map is a copy of the object. The
original is destroyed but the copy lives on in your hash map.

Exactly the same thing happens when you called new, except that way the
copy goes into the hash map and the original lives on as a memory leak.

This is a fundanental difference between java and C++, in java all class
objects are references, when you copy then you are in effect copying a
pointer an object. But in C++ when you copy an object you now have two
objects, not two pointers to the same object. If you want to use the
buzz words you say that Java has 'reference sementics' but C++ has
'value semantics'.

For instance this would also be a perfectly correct way to code your program

DataType x;
pairType y(key, x);
data[k]->push_back(y) ;

The variable x and y are local, they do get destroyed, but it doesn't
matter, by the time they are destroyed copies of there values are safely
in your hash map.

john
Nov 28 '05 #7

This thread has been closed and replies have been disabled. Please start a new discussion.

Similar topics

4
1915
by: Bung | last post by:
Hi, I have a tricky sql statment I have to write (tricky for me) and I am stuck. I'm having trouble with the following problem. Table1 (Column a, Column b, Column c) Table2 (Column a, Column b, Column c) Table3 (Column a, Column b, Column c) Table1 contains a row of value (1, 2, 3)
8
2742
by: david wolf | last post by:
I have a function called void f(){ char * tmp = "abc"; static * tmp1 = "abcd"; } Can anyone tell me 1)whether pointer tmp is stored in stack or heap? 2)whether string "abc" of length 4 bytes is stored in stack or help? 3)whether pointer tmp1 is stored in stack or heap?
3
2466
by: Adam Toline | last post by:
In reference to the following: http://www.bellecose.com/form.htm At the top of each column there is a box for "All". When one is checked I need to check all of (and only) those boxes underneath. Now, the rub here is that every checkbox on the page (except the "All"s)
5
1641
by: Danny | last post by:
Hi there I need help with a tricky problem. I have a 2 dimensional array with qualities such as ball size, ball color, ball weight. Now I have to print out all the possible combinations of this. assume I have it stored as such i have two dimensional array ball:
21
364
by: Ike Naar | last post by:
Consider the following code: #include <stdlib.h> struct s { /* ... */ struct s * next; };
27
2322
by: onkar | last post by:
#include<stdio.h> int main(void){ char a="abcde"; char *p=a; p++; p++; p='z'; printf("%s\n",p); return 0; }
15
2186
by: fungus | last post by:
I'm moving some code from VC++ 6 to VC++ 2005 and I've run into a nasty problem because iterators are no longer pointers. In the program I'm moving, there's a std::vector of items hidden inside a class and users of the class get to iterate it via a const_iterator. eg.
11
2413
by: onkar | last post by:
Program 1: #include<stdio.h> int main(void){ int *p; p=(int *)malloc(sizeof(int)); *p=12; printf("%d %p\n",*p,p); return 0; }
10
1573
by: goacross | last post by:
i found something tricky this morning. char *p="abc"; 1. char m=1;// m='b' 2. char n=sizeof('h'); // n=1; I guess the reason of 1is,
0
9791
by: Hystou | last post by:
Most computers default to English, but sometimes we require a different language, especially when relocating. Forgot to request a specific language before your computer shipped? No problem! You can effortlessly switch the default language on Windows 10 without reinstalling. I'll walk you through it. First, let's disable language synchronization. With a Microsoft account, language settings sync across devices. To prevent any complications,...
0
11140
Oralloy
by: Oralloy | last post by:
Hello folks, I am unable to find appropriate documentation on the type promotion of bit-fields when using the generalised comparison operator "<=>". The problem is that using the GNU compilers, it seems that the internal comparison operator "<=>" tries to promote arguments from unsigned to signed. This is as boiled down as I can make it. Here is my compilation command: g++-12 -std=c++20 -Wnarrowing bit_field.cpp Here is the code in...
1
10847
by: Hystou | last post by:
Overview: Windows 11 and 10 have less user interface control over operating system update behaviour than previous versions of Windows. In Windows 11 and 10, there is no way to turn off the Windows Update option using the Control Panel or Settings app; it automatically checks for updates and installs any it finds, whether you like it or not. For most users, this new feature is actually very convenient. If you want to control the update process,...
0
9572
agi2029
by: agi2029 | last post by:
Let's talk about the concept of autonomous AI software engineers and no-code agents. These AIs are designed to manage the entire lifecycle of a software development project—planning, coding, testing, and deployment—without human intervention. Imagine an AI that can take a project description, break it down, write the code, debug it, and then launch it, all on its own.... Now, this would greatly impact the work of software developers. The idea...
0
7125
by: conductexam | last post by:
I have .net C# application in which I am extracting data from word file and save it in database particularly. To store word all data as it is I am converting the whole word file firstly in HTML and then checking html paragraph one by one. At the time of converting from word file to html my equations which are in the word document file was convert into image. Globals.ThisAddIn.Application.ActiveDocument.Select();...
0
5797
by: TSSRALBI | last post by:
Hello I'm a network technician in training and I need your help. I am currently learning how to create and manage the different types of VPNs and I have a question about LAN-to-LAN VPNs. The last exercise I practiced was to create a LAN-to-LAN VPN between two Pfsense firewalls, by using IPSEC protocols. I succeeded, with both firewalls in the same network. But I'm wondering if it's possible to do the same thing, with 2 Pfsense firewalls...
1
4611
by: 6302768590 | last post by:
Hai team i want code for transfer the data from one system to another through IP address by using C# our system has to for every 5mins then we have to update the data what the data is updated we have to send another system
2
4218
muto222
by: muto222 | last post by:
How can i add a mobile payment intergratation into php mysql website.
3
3232
bsmnconsultancy
by: bsmnconsultancy | last post by:
In today's digital era, a well-designed website is crucial for businesses looking to succeed. Whether you're a small business owner or a large corporation in Toronto, having a strong online presence can significantly impact your brand's success. BSMN Consultancy, a leader in Website Development in Toronto offers valuable insights into creating effective websites that not only look great but also perform exceptionally well. In this comprehensive...

By using Bytes.com and it's services, you agree to our Privacy Policy and Terms of Use.

To disable or enable advertisements and analytics tracking please visit the manage ads & tracking page.