need help with stl lists

[Christian Christmann]

Hi,

in the past I always appreciated your help and hope that you also can help
me this time. I've spent many many hours but still can't solve the
problem by myself and you are my last hope.

I've a program which is using self-written double-linked lists as a data
structure. The template list consists of list elements and the list itself
linking the list elements.

Here is the header file list.h:

template <class ELEMENT>
class ListElem
{
friend class List<ELEMENT>;
ELEMENT* content;
ListElem<ELEMENT>* nextelem, *prevelem; ListElem(ELEMENT* c);
};

template <class ELEMENT>
class List
{
ListElem<ELEMENT>* firstelem;
ListElem<ELEMENT>* lastelem;
ListElem<ELEMENT>* forward; // Internal forward iterator one //
element beyond
ListElem<ELEMENT>* backward; // Internal backward
//iterator one element beyond

int length;
ListElem<ELEMENT>*> *keymap; void createKeymap();
public:
List();
void Delete(ELEMENT* x);
ELEMENTTYPE* First();
void Append(ELEMENTTYPE* x);
ELEMENTTYPE* Succ(ELEMENTTYPE* x);
};


And the source file:

#include <stdio.h>
#include <stdlib.h>
#include <iostream>
#include "list.h"

using namespace std;

#define ISEMPTY ((bool)!firstelem)

template <class ELEMENT>
ListElem<ELEMENT>::ListElem(ELEMENT* c) {
content = c;
nextelem = prevelem = NULL;
}

template <class ELEMENT>List<ELEMENT>::List()
:keymap(NULL)
{
firstelem = NULL;
lastelem = NULL;
forward = NULL;
backward = NULL;
length = 0;
}


template <class ELEMENT>
void List<ELEMENT>:elete(ELEMENT* x) {
if (!keymap)
{
if (!firstelem) return;

if (firstelem->content==x)
{
ListElem<ELEMENT> *n=firstelem->nextelem;

if (n) n->prevelem=NULL;
else lastelem=NULL;

deleteElem(firstelem);
firstelem=n;
return;
}
if (lastelem->content==x)
{
ListElem<ELEMENT> *p=lastelem->prevelem; p->nextelem=NULL;

deleteElem(lastelem);
lastelem=p;

return;
}

// Otherwise create mapping and search for the requested element:
createKeymap();
}
typename multimap<ELEMENTTYPE*, ListElem<ELEMENTTYPE>*>::iterator
it(keymap->find(x));

if (it!=keymap->end())
{
ListElem<ELEMENT> *e=(*it).second;

if (e->nextelem) e->nextelem->prevelem=e->prevelem; else
lastelem=e->prevelem;

if (e->prevelem) e->prevelem->nextelem=e->nextelem; else
firstelem=e->nextelem;

deleteElem(e);
keymap->erase(it);

if (!length)
{
delete keymap;
keymap=NULL;
}
}
}

template <class ELEMENT>
ELEMENT* List<ELEMENT>::First()
{
if (ISEMPTY) return NULL;

forward=firstelem->nextelem;
return firstelem->content;
}

template <class ELEMENT>
ELEMENT* List<ELEMENT>::Succ(ELEMENT* x) {
if (ISEMPTY) return NULL;

if (!keymap) createKeymap();

typename multimap<ELEMENT*, ListElem<ELEMENT>*>::iterator
it(keymap->find(x));

if (it!=keymap->end())
{
ListElem<ELEMENT> *e=(*it).second;

if (e->nextelem)
{
forward=e->nextelem->nextelem;
return e->nextelem->content;
}
}
forward=NULL;

return NULL;
}

#define APPEND(e) { \
if (ISEMPTY) \
{ firstelem = e; \
lastelem = e; \
} \
else \
{ lastelem->nextelem = e; \
e->prevelem=lastelem;\
lastelem = e; \
} \
length++; }

template <class ELEMENT>
void List<ELEMENT>::Append(ELEMENT* x) {
ListElem<ELEMENT> *e=new ListElem<ELEMENT>(x); APPEND(e); if (keymap)
keymap->insert(pair<ELEMENT* const,
ListElem<ELEMENT>*>(x, e));
}

------------------

The code is probably not good style and it's quite a hassle to handle all
the pointers.
My idea was to replace the self-written class by an STL class. First, I
wanted to keep the pointers and not replace it by references since I
didn't want to change all the programs using this list. I also wanted to
keep the function names in ordner not to change the other programs. When
the lists are running I slowly wanted to remove the list class and use
direct STL statements in the code. However, my wrapper class with an STL
list which should replace the self-written class doesn't work properly. A
test program using my new list is telling me that the information stored
in the list is not what it should be. (The test program is using "diff"
with some known correct results...)

Here is my wrapper class which should replace the above posted list:
template <class ELEMENT>
class List
{

list<ELEMENT*>* mylist;
public:
List();
void Delete(ELEMENT* x);
ELEMENT* First();
ELEMENT* Succ(ELEMENT* x);
void Append(ELEMENT* x);
};

And the source code:
#include <cstdio>
#include <cstdlib>
#include <list>
#include <algorithm>
#include <iostream>

#include "graph.h"

using namespace std;

template <class ELEMENT>
List<ELEMENT>::List()
{
mylist = new list<ELEMENT*>;
}

template <class ELEMENT>
void List<ELEMENT>:elete(ELEMENT* x) {
typename list<ELEMENT*>::iterator it = find(mylist->begin(),
mylist->end(), x);
if (it != mylist->end())
mylist->erase(it);
}

template <class ELEMENT>
ELEMENT* Liste<ELEMENT>::First()
{
if (mylist->empty()) return NULL;
return *(mylist->begin());
}


template <class ELEMENT>
ELEMENT* Liste<ELEMENT>::Succ(ELEMENT* x)
{
if (mylist->empty()) return NULL;

typename list<ELEMENTTYPE2*>::iterator it = find(mylist->begin(),
mylist->end(), x);
if (it != mylist->end())
{
return *(++(it));
}
else
{
current = NULL;
return NULL;
}
}

void Liste<ELEMENT>::Append(ELEMENT* x)
{
mylist->push_back(x);
}


I would really appreciate your help. I spent days with this class
but can't find the error. Maybe you can find why there's a
difference with the stored values in the self-written list and my
STL list.
Sorry, for so many lines of code, but I'm really stuck and this
prevents me of going one with my work.

I also appreciate any comments on how to improve my code.


PLEASE HELP ME

Thank you very much.

Chris

 

[Andre Kostur]

Hi,

in the past I always appreciated your help and hope that you also can
help me this time. I've spent many many hours but still can't solve
the problem by myself and you are my last hope.

I've a program which is using self-written double-linked lists as a
data structure. The template list consists of list elements and the
list itself linking the list elements.

[snip large code dump]

The code is probably not good style and it's quite a hassle to handle
all the pointers.
My idea was to replace the self-written class by an STL class. First,
I wanted to keep the pointers and not replace it by references since I
didn't want to change all the programs using this list. I also wanted
to keep the function names in ordner not to change the other programs.
When the lists are running I slowly wanted to remove the list class
and use direct STL statements in the code. However, my wrapper class
with an STL list which should replace the self-written class doesn't
work properly. A test program using my new list is telling me that the
information stored in the list is not what it should be. (The test
program is using "diff" with some known correct results...)

Where's the test program? What's the output of the original, and your
modified version?

[snip more code]

I would really appreciate your help. I spent days with this class
but can't find the error. Maybe you can find why there's a
difference with the stored values in the self-written list and my
STL list.
Sorry, for so many lines of code, but I'm really stuck and this
prevents me of going one with my work.

I also appreciate any comments on how to improve my code.


PLEASE HELP ME

Help us help you. Post the smallest compiliable version of the code that
exhibits the problem.

 

[Chris Theis]

Hi,

in the past I always appreciated your help and hope that you also can help
me this time. I've spent many many hours but still can't solve the
problem by myself and you are my last hope.

[SNIP]

As Andre already suggested we'd need some more information. Anyway, there is
something which strikes me odd at first glance. Why do you have a pointer to
a standard template lib list in your list class? It would be sufficient to
have something like this:

template<typename T>
class CMyList {
....
protected:
list<T> m_InternalList;
};

If you are using a pointer to a list you should be aware that you need a
destructor, which is at least missing in the code that you posted, and in
the due course you should consider the rule of 3 (ctor, dtor and copy
ctor!).

HTH
Chris

 

[Christian Christmann]

As Andre already suggested we'd need some more information. Anyway, there
is something which strikes me odd at first glance. Why do you have a
pointer to a standard template lib list in your list class? It would be
sufficient to have something like this:

template<typename T>
class CMyList {
....
protected:
list<T> m_InternalList;
};

Thank you for your advice.
I've changed the pointer to the list to a normal value as suggested.

Chris

 

[Christian Christmann]

Where's the test program? What's the output of the original, and your
modified version?

The test program is pretty complex. It's using perl and diff and some
other classes. So, it would be to much code to post here.

I've written some debug information in the code to see the values
stored in the lists.

My Succ function with the debug information reads:
template <class ELEMENT>
ELEMENT* List<ELEMENT>::Succ(ELEMENT* x)
{
cout << "\nList before call Succ:\n";
PrintList();
cout << "Successor(parameter) of ELEMENT* x: " << x << endl;
if (mylist.empty()) return NULL;

typename list<ELEMENT*>::iterator it = find(mylist.begin(),
mylist.end(), x);
if (it != mylist.end())
{
ELEMENT *x = *(++(it));
cout << "\nSuccessor2(return value) is: " << x << endl;
return x;
}
else
{
return NULL;
}
}

with function PrintList() be:
template <class ELEMENT>
void List<ELEMENT>:rintList() const
{
if (mylist.empty())
cout << "List is empty\n" ;
else
{
typename list<ELEMENT*>::const_iterator it;
for (it = mylist.begin();
it != mylist.end(); ++it)
cout << (*it) << " ";
}
cout << endl;
}


Running the test program with the debug information I
get the output:

List before call Succ:
0x8186b80 0x8185c50 0x8185cb0 0x8185ce0
Successor2(parameter) of ELEMENT* x: 0x8186b80

Successor2(return value) is: 0x8185c50

Adding the same debug information to the old list I get an
output:

List before call Succ:
0x8186768 0x8185360 0x81853c0 0x8185400
Successor(parameter) of ELEMENT* x: 0x8186290

Successor(return value) is: 0x8185350

I hope this information can help you little bit. If not, let
me know or please make a suggestion how you would
test the equality of the information stored in both lists.

Thank you very much.


Chris

 

[Karl Heinz Buchegger]

I hope this information can help you little bit. If not, let
me know or please make a suggestion how you would
test the equality of the information stored in both lists.

Problems like that are really hard to solve when all we have
is a source code dump.

All would be much easier, if you could provide us with a stripped
down version of your program, which contains only what is absolutely
needed to run and reproduce that problem. Then we can take this code
into our debuggers and step through it and see life where you did
go wrong.

Yes, that means work for you. Write a test program which contains
only a simple main function and inserts a few items in the list
(or whatever you need to do to reproduce that problem) and the code
for insertion and dumping (if that is enough to reproduce the problem).

Then post this program and somebody will be able to help.

One doesn't need an entire Space Shuttle to track down problems in the
Shuttles main computer cooling fan. But you do need the real fan to
track down why the blade wheel stops turning sometimes. A description
of the fan or some drawings are simply not enough.

 

[Christian Christmann]

I hope this information can help you little bit. If not, let me know or

Problems like that are really hard to solve when all we have is a source
code dump.

All would be much easier, if you could provide us with a stripped down
version of your program, which contains only what is absolutely needed to
run and reproduce that problem. Then we can take this code into our
debuggers and step through it and see life where you did go wrong.

Yes, that means work for you. Write a test program which contains only a
simple main function and inserts a few items in the list (or whatever you
need to do to reproduce that problem) and the code for insertion and
dumping (if that is enough to reproduce the problem).

Then post this program and somebody will be able to help.

One doesn't need an entire Space Shuttle to track down problems in the
Shuttles main computer cooling fan. But you do need the real fan to track
down why the blade wheel stops turning sometimes. A description of the fan
or some drawings are simply not enough.

Thank you for all your help. Finally, I could solve my problem. It was the
Succ function which had an iterator which in some cases was incremented
to the end() of the list and thus generated wrong results.

Chris

 

[santosh]

Hello,
I have two doubts on C/C++.
1. float i=1.1;
double d=1.1;
if(i==d)
printf("equal\n");
else
printf("not-equal\n");
what is the output?
I am getting "not-equal" as output.
Why it is so?
Regards,
Santosh.

 

[Billy Patton]

Hello,
I have two doubts on C/C++.
1. float i=1.1;
double d=1.1;
if(i==d)
printf("equal\n");
else
printf("not-equal\n");
what is the output?
I am getting "not-equal" as output.
Why it is so?
Regards,
Santosh.

Your compiler should have given you a warning that you were comparing 2 items
of different lengths.
If you using g++ add -Wall to your CPPFLAGS.

 

[Tim Slattery]

Hello,
I have two doubts on C/C++.
1. float i=1.1;
double d=1.1;
if(i==d)
printf("equal\n");
else
printf("not-equal\n");
what is the output?
I am getting "not-equal" as output.

That's because floating point numbers - and "double" is a floating
point number, just longer and therefore having more significant digits
- are approximations. They *cannot* be relied on to yield absolutely
precise results. In particular comparisons, like what you have done,
are pretty well guaranteed to fail.

Check here http://www.cs.utah.edu/~zachary/isp/applets/FP/FP.html for
an explanation of floating point numbers.