Strings with Templates not working?

[Obnoxious User]

Hello,

I'm using a template to simulate a LinkedList from Java.It works without
problems, but when I want to use strings in main.cpp instead of char*, I
get the following error message:

$ ./Main
terminate called after throwing an instance of 'std::logic_error'
what(): basic_string::_S_construct NULL not valid

I tried to import <string> both in main.cpp and listT.h, but the
errormsg was the same.

The classes look like this:
[snip]
template <class T>
T ListT<T>::get(int i) {
TKnoten *iterator = new TKnoten();
T daten = 0;

!---->>^^^^^^^^^^^

T daten = "";

 

[Markus Pitha]

Hello,

I'm using a template to simulate a LinkedList from Java.It works without
problems, but when I want to use strings in main.cpp instead of char*, I
get the following error message:

$ ./Main
terminate called after throwing an instance of 'std::logic_error'
what(): basic_string::_S_construct NULL not valid

I tried to import <string> both in main.cpp and listT.h, but the
errormsg was the same.

The classes look like this:

MAIN.CPP------------------------------------------
#include "ListT.h"
#include <iostream>

using namespace std;

int main(void) {

ListT<string> *testList = new ListT<string>();
testList->add("Test1");
testList->add("Test2");
testList->add("Test3");
cout << testList->get(0) <<endl;
cout << testList->get(1) <<endl;
cout << testList->get(2) <<endl;
delete testList;

return 0;
}
------------------------------------------------

LISTT.H-----------------------------------------

template <class T> class ListT {

private:
struct TKnoten {
T daten;
int index;
TKnoten *next;
};
int counter;
TKnoten *kopf;

public:
ListT();
virtual ~ListT();
void add(T element);
//void remove(T element);
T get(int i);
};

template <class T>
ListT<T>::ListT() {
counter = 0;
kopf = new TKnoten();
kopf->next = 0;
}

template <class T>
ListT<T>::~ListT() {
while (kopf->next != 0) {
TKnoten *previous = new TKnoten();
previous = kopf;
kopf = kopf->next;
delete previous;
}
delete kopf;
}

template <class T>
void ListT<T>::add(T element) {
TKnoten *newKnoten = new TKnoten();

newKnoten->next = kopf;
kopf = newKnoten;
kopf->daten = element;
kopf->index = counter;
counter++;
}

template <class T>
T ListT<T>::get(int i) {
TKnoten *iterator = new TKnoten();
T daten = 0;
iterator = kopf;
while (iterator->next != 0) {
if (iterator->index == i) {
daten = iterator->daten;
}
iterator = iterator->next;
}
delete iterator;
return daten;
}

What's wrong with string as type? I'm using Linux with gcc (g++),


Thanks for your answers,

Markus

 

[Obnoxious User]

Hello,

I'm using a template to simulate a LinkedList from Java.It works without
problems, but when I want to use strings in main.cpp instead of char*, I
get the following error message:

$ ./Main
terminate called after throwing an instance of 'std::logic_error'
what(): basic_string::_S_construct NULL not valid

I tried to import <string> both in main.cpp and listT.h, but the
errormsg was the same.

The classes look like this:
[snip]
template <class T>
T ListT<T>::get(int i) {
TKnoten *iterator = new TKnoten();
T daten = 0;

!---->>^^^^^^^^^^^

T daten = "";

Or better yet, so it works with any type.

T daten;

 

[Zachary Turner]

template <class T>
T ListT<T>::get(int i) {
TKnoten *iterator = new TKnoten();
T daten = 0;

Pretty sure this is your problem. You're assigning NULL to a string
object.

I know this isn't your question, but you know that C++ already comes
with a linked list right? And also, it may have been better style to
declare your list on the stack instead of as a pointer and then using
new / delete. You may be aware of this already, but from your post it
sounds like you come from a Java background, where everything is just
new new new allocated on the heap.

 

[Victor Bazarov]

Hello,

I'm using a template to simulate a LinkedList from Java.It works
without problems, but when I want to use strings in main.cpp instead
of char*, I get the following error message:

$ ./Main
terminate called after throwing an instance of 'std::logic_error'
what(): basic_string::_S_construct NULL not valid

I tried to import <string> both in main.cpp and listT.h, but the
errormsg was the same.

You have some logical errors in your code. See below.

The classes look like this:

MAIN.CPP------------------------------------------
#include "ListT.h"
#include <iostream>

using namespace std;

int main(void) {

ListT<string> *testList = new ListT<string>();
testList->add("Test1");
testList->add("Test2");
testList->add("Test3");
cout << testList->get(0) <<endl;
cout << testList->get(1) <<endl;
cout << testList->get(2) <<endl;
delete testList;

return 0;
}
------------------------------------------------

LISTT.H-----------------------------------------

template <class T> class ListT {

private:
struct TKnoten {
T daten;
int index;
TKnoten *next;

The 'TKnoten' struct is not a POD, which means that upon its
default-initialisation both 'index' and 'next' contain garbage.
You should write a default c-tor which will initialise 'index'
to something specific, like -1, and 'next' to NULL.

};
int counter;
TKnoten *kopf;

public:
ListT();
virtual ~ListT();
void add(T element);
//void remove(T element);
T get(int i);
};

template <class T>
ListT<T>::ListT() {
counter = 0;
kopf = new TKnoten();
kopf->next = 0;
}

template <class T>
ListT<T>::~ListT() {
while (kopf->next != 0) {
TKnoten *previous = new TKnoten();
previous = kopf;

Take a close look at the previous two statements. You create
a new 'TKnoten' object, obtain a pointer to it and IMMEDIATELY
lose it by overriding the value in 'previous'. Do you really
need to create a new 'TKnoten' here while deleting your list?

kopf = kopf->next;
delete previous;
}
delete kopf;
}

template <class T>
void ListT<T>::add(T element) {
TKnoten *newKnoten = new TKnoten();

newKnoten->next = kopf;
kopf = newKnoten;
kopf->daten = element;
kopf->index = counter;
counter++;
}

template <class T>
T ListT<T>::get(int i) {
TKnoten *iterator = new TKnoten();

HUH? Why are you creating another 'TKnoten' here?

T daten = 0;
iterator = kopf;

Again, you're immediately losing the value of 'iterator' that you
just obtained from 'new'...

while (iterator->next != 0) {
if (iterator->index == i) {
daten = iterator->daten;
}
iterator = iterator->next;
}
delete iterator;

Are you sure you need to 'delete' it here?

return daten;
}

What's wrong with string as type? I'm using Linux with gcc (g++),

Nothing is wrong with string as type. Several things are wrong with
your program, however. The main thing I'd look closely into would
be the 'delete iterator' in the 'get' member function.

V

 

[Markus Pitha]

Hello,

!---->>^^^^^^^^^^^

Ah, I see. That's it.
By the way, why do I have to include <string> for using NULL?
At first, I thought I have to define NULL like this #define NULL (void*)
0 but I got some error about redefining null.
By coincidence, I found out that NULL is in string.

Markus

 

[Obnoxious User]

Where can I find this linked list? In the internet, I only find
tutorials how to create a linked list.

#include <list>
#include <iostream>


int main() {
std::list<int> list;
list.push_back(0);
list.push_back(1);
list.push_back(2);

std::cout<<"front: "<<list.front()<<std::endl;
std::cout<<"back: "<<list.back()<<std::endl;
std::cout<<"complete: ";
std::list<int>::iterator ii = list.begin();
while(true) {
std::cout<<*ii;
if(++ii == list.end()) break;
std::cout<<",";
}
std::endl(std::cout);
return 0;
}

 

[Markus Pitha]

I know this isn't your question, but you know that C++ already comes
with a linked list right? And also, it may have been better style to
declare your list on the stack instead of as a pointer and then using
new / delete.

Where can I find this linked list? In the internet, I only find
tutorials how to create a linked list.
Which benefits does it have to create it on the stack?
I thought that dynamically allocated space would be better.

 

[Markus Pitha]

You have some logical errors in your code. See below.


The 'TKnoten' struct is not a POD, which means that upon its
default-initialisation both 'index' and 'next' contain garbage.
You should write a default c-tor which will initialise 'index'
to something specific, like -1, and 'next' to NULL.
Ok.
Take a close look at the previous two statements. You create
a new 'TKnoten' object, obtain a pointer to it and IMMEDIATELY
lose it by overriding the value in 'previous'. Do you really
need to create a new 'TKnoten' here while deleting your list?

I have an old C book. They write the following in this book:

free(head);
head = head->next;

I thought this can not work, because how can I free the "head" of the
list _at first_ without losing the whole list?

HUH? Why are you creating another 'TKnoten' here?

How can I iterate over the whole list then without an extra object?

Again, you're immediately losing the value of 'iterator' that you
just obtained from 'new'...


Are you sure you need to 'delete' it here?

I thought that I have to delete everything I allocated with "new"?

Markus

 

[Zachary Turner]

Where can I find this linked list? In the internet, I only find
tutorials how to create a linked list.
Which benefits does it have to create it on the stack?
I thought that dynamically allocated space would be better.

#include <list>
using namespace std;

int main()
{
list<int> mylist;
mylist.push_back(1);
mylist.push_back(2);
mylist.push_back(3);
}

If you take this approach, there is a bit of a learning curve you will
have to overcome. Some keywords you can use to search for related
topics are:

STL (Standard Template Library) - a collection of generic containers
and algorithms provided with C++)
std::list - One of the generic collections in the STL. It's a doubly
linked list, and supports any time
iterator - The STL paradigm for iterating over any and all collections
in the STL.




Regarding memory allocation, stack based and heap based memory
allocation is totally separate.

Heap based - You specify exactly when it is created (with new), NULL
value is possible, and you specify exactly when it is deleted (with
delete)

Stack based - It is created the instant it is declared, NULL is not
possible, it is deleted immediately when it goes out of scope.
Consider this code:

if (true)
{
list<int>* pList = new list<int>();

pList->push_back(1);

delete pList;
}

Here you create a new instance of list immediately when you declare
it. You never make use of the null value, and you delete it
immediately before it goes out of scope. This is equivalent to what
stack based allocation provides. Therefore, the code is equivalent
to:

if (true)
{
list<int> list;
list.push_back(1);
}

 

[Victor Bazarov]

[..]
template <class T>
T ListT<T>::get(int i) {
TKnoten *iterator = new TKnoten();

HUH? Why are you creating another 'TKnoten' here?

How can I iterate over the whole list then without an extra object?

That's a strange question. When you need to look for something in
your desk drawers, do you go out an buy another drawer? When you
need to look for something in some text files on your hard drive,
do you first create another file? No, you just open them, look in
them, and move on.

To iterate over objects that exist in your list, all you need is
a pointer where you will store the address of the existing objects.
There is no need to create another object to immediately lose its
address because you assign 'kopf' to 'iterator' two lines down.

I thought that I have to delete everything I allocated with "new"?

Yes, but *what* are you deleting? It would seem to me that you
are actually deleting the last element of the list...

You should undoubtedly attempt to write your own linked list at some
point in your studies. But you need to pay attention to what you're
doing.

V

 

[Thomas J. Gritzan]

Where can I find this linked list? In the internet, I only find
tutorials how to create a linked list.
Which benefits does it have to create it on the stack?
I thought that dynamically allocated space would be better.

In your favorite C++ programming book. Or google for "c++ standard library"
(also known as "standard template library").

#include <iostream>
#include <string>
#include <list>

int main()
{
using std::list;
using std::string;

list<string> mylist;

mylist.push_back("One");
mylist.push_back("Two");

for (list<string>::iterator itor = mylist.begin(); itor != mylist.end();
itor++)
std::cout << *itor << std::endl;
}

In C++, it is generally better to use objects with automatic storage
duration (generally created on the stack), and use dynamic allocation only
when necessary. The problem with dynamically allocated objects is that you
have to handle the deletion manually.

 

[Zachary Turner]

I thought that I have to delete everything I allocated with "new"?

I think the real issue is that you should never have 'new'd anything
in the first place. All the memory required for this operation has
already been allocated. This is just a get function. The object
already exists, you just want to get it. A more correct get()
function would look like this:

template <class T>
T ListT<T>::get(int i) {
TKnoten *iterator = kopf;

while (iterator->next != NULL) {
if (iterator->index == i) {
return iterator->daten;
}
}
return ??; //Need to decide what to return here that means "not
found". Probably a design issue though.
}

 

[Markus Pitha]

Thanks again for all your tips.
I'll take it to heart.

Markus

 

[Markus Pitha]

Markus Pitha wrote:
[..]
template <class T>
T ListT<T>::get(int i) {
TKnoten *iterator = new TKnoten();
HUH? Why are you creating another 'TKnoten' here?

How can I iterate over the whole list then without an extra object?

That's a strange question. When you need to look for something in
your desk drawers, do you go out an buy another drawer? When you
need to look for something in some text files on your hard drive,
do you first create another file? No, you just open them, look in
them, and move on.

When I don't instance a new object, I get memory access errors while
executing the file.

 

[Andre Kostur]

Hello,



Ah, I see. That's it.
By the way, why do I have to include <string> for using NULL?
At first, I thought I have to define NULL like this #define NULL (void*)
0 but I got some error about redefining null.
By coincidence, I found out that NULL is in string.

IIRC: NULL is properly defined in <cstddef>. And if you must define NULL
yourself, it should be:

#define NULL 0

Or, Stroustrup suggests:

const int NULL = 0;


You don't want the (void *) in there.

 

[Victor Bazarov]

Victor Bazarov schrieb:
Markus Pitha wrote:
[..]
template <class T>
T ListT<T>::get(int i) {
TKnoten *iterator = new TKnoten();
HUH? Why are you creating another 'TKnoten' here?
How can I iterate over the whole list then without an extra object?

That's a strange question. When you need to look for something in
your desk drawers, do you go out an buy another drawer? When you
need to look for something in some text files on your hard drive,
do you first create another file? No, you just open them, look in
them, and move on.

When I don't instance a new object, I get memory access errors while
executing the file.

I am not sure I understand. How did you arrive at the conclusion that
you need to allocate another object to fix the memore access errors?
And I bet you the memore access errors are actually due to the 'delete'
you have there without merit.

V

 

[Markus Pitha]

I am not sure I understand. How did you arrive at the conclusion that
you need to allocate another object to fix the memore access errors?
And I bet you the memore access errors are actually due to the 'delete'
you have there without merit.

Yes, u were right. I only need to instance a new object while creating a
new node in my list.
But I still don't understand why this works:

template <class T>
ListT<T>::~ListT() {
while (kopf->next != NULL) {
delete kopf;
kopf = kopf->next;
}
delete kopf;
}

For testing, I wrote an int to stdout as often as the while loop runs. I
get 3 outputs (as much as I have(had) elements).
For me that means, that the list is not lost, but why does that work?

Markus

 

[Zachary Turner]

When I don't instance a new object, I get memory access errors while
executing the file.

Imagine this were a different language like Java. Would you write the
following code?

int get()
{
TKnoten iterator = new TKnoten();

while ((iterator = list->next()) != null)
{
//do something with iterator
}
}

certainly not. You would do this:

int get()
{
TKnoten iterator = null;

while ((iterator = list->next()) != null)
{
//do something with iterator
}
}



My personal advice is to study the basics of pointers and dynamic/
static memory allocation some more. The problem you are trying to
solve, while not terribly difficult, combines a lot of concepts that
it seems you're trying to jump into without first having a fundamental
understanding of pointers and memory.

 

[Markus Pitha]

IIRC: NULL is properly defined in <cstddef>. And if you must define NULL
yourself, it should be:

#define NULL 0

Or, Stroustrup suggests:

const int NULL = 0;

You don't want the (void *) in there.

You were right. It works with cstddef.
But I don't understand yet why NULL is frowned upon in C++.
I already found similar information about what you said, but I didn't
find a logical explanation about the disadvantages with using NULL
instead of 0.
By the way. Is there some standard library collection about c++ like the
Java Doc in Java? I found a good collection on
http://www.cplusplus.com/. I guess that these libraries there are the
standard libraries.

Markus