C++ custom template LinkedList crashes adding std::string

Question

For academic purposes, I'm trying to develop a little "textual adventure game". I have to implement all data structures by my own. Now, I have some problems with the implementation of a generic (template) LinkedList.

In the specific, this data structure works with everything (primitive data types and custom objects) BUT strings! (standard library strings).

When I try to add strings to a list, the application crashes with the following error (in console):

"terminate called after throwing an instance of 'std::logic_error' what(): basic_string::_S_constructor null not valid"

The list is implemented as a "double linked list" using the head-node as first-last node

Here the code ("Abstract" List interface):

#ifndef LIST_H_
#define LIST_H_

template <class T>
class List
{
public:
 virtual ~List() {}
 virtual T get(int position) = 0;
 virtual List* add(T item) = 0;
 virtual List* insert(T item, int position) = 0;
 virtual List* remove(int position) = 0;
 virtual int size() const = 0;
 virtual bool isEmpty() const = 0;

protected:

private:

};

#endif /* LIST_H_ */

This is the LinkedList implementation (the "node" class):

#include "List.h"
#include <stdlib.h>

#ifndef LINKEDLIST_H_
#define LINKEDLIST_H_

template <class T>
class ListNode
{
public:
ListNode(T item)
{
    mItem = item;
    mNext = NULL;
    mPrev = NULL;
}

ListNode(T item, ListNode<T>* next, ListNode<T>* prev)
{
    mItem = item;
    mNext = next;
    mPrev = prev;
}


~ListNode()
{
    delete &mItem;
}


T getItem()
{
    return mItem;
}


ListNode<T>* getNext()
{
    return mNext;
}


ListNode<T>* getPrev()
{
    return mPrev;
}


void setItem(T item)
{
    mItem = item;
}


void setNext(ListNode<T>* next)
{
    mNext = next;
}


void setPrev(ListNode<T>* prev)
{
    mPrev = prev;
}

protected:
private:
T mItem;
ListNode<T> *mNext, *mPrev;
};

The LinkedList class:

template <class K>
class LinkedList : public List<K>
{
public:
LinkedList()
{
    mSize = 0;
    mFirstNode = NULL;
}

~LinkedList()
{
    // implementazione distruttore tramite ciclo sui nodi
}

K get(int position)
{
    K item = NULL;

    ListNode<K>* targetNode = getNodeAtPosition(position);
    if (targetNode != NULL) item = targetNode->getItem();

    return item;
}

List<K>* add(K item)
{
    if (mFirstNode == NULL)
    {
        mFirstNode = new ListNode<K>(item);
        mFirstNode->setNext(mFirstNode);
        mFirstNode->setPrev(mFirstNode);
    }
    else
    {
        ListNode<K>* newNode = new ListNode<K>(item, mFirstNode, mFirstNode->getPrev());
        mFirstNode->getPrev()->setNext(newNode);
        mFirstNode->setPrev(newNode);
    }

    mSize++;
    return this;
}

List<K>* insert(K item, int position)
{
    ListNode<K>* targetNode = getNodeAtPosition(position);

    if (targetNode != NULL)
    {
        ListNode<K>* newNode = new ListNode<K>(targetNode->getItem(), targetNode->getNext(), targetNode);
        targetNode->setItem(item);
        targetNode->setNext(newNode);

        mSize++;
    }

    return this;
}

List<K>* remove(int position)
{
    ListNode<K>* targetNode = getNodeAtPosition(position);
    if (targetNode != NULL)
    {
        targetNode->setItem(targetNode->getNext()->getItem());
        targetNode->setNext(targetNode->getNext()->getNext());

        //delete targetNode->getNext();
        mSize--;
    }

    return this;
}

int size() const
{
    return mSize;
}

bool isEmpty() const
{
    return (mFirstNode == NULL) ? true : false;
}

protected:
ListNode<K>* getNodeAtPosition(int position)
{
    ListNode<K>* current = NULL;

    if (mFirstNode != NULL && position < mSize)
    {
        current = mFirstNode;

        for (int i = 0; i < position; i++)
        {
            current = current->getNext();
        }
    }

    return current;
}

private:
     int mSize;
     ListNode<K>* mFirstNode;
};

 #endif /* LINKEDLIST_H_ */

Suggestions?

You have to implement your own data structures but are allowed to use `std::string`? If you can use `std::string`, why can't you use `std::list`? — Zac Howland, Aug 20 '13 at 19:34
consider using references to the contained object in your method calls. You are making a lot of extra copies of the string. This does not address your question, hence it's just a comment. — Dale Wilson, Aug 20 '13 at 19:38
Just an observation, on the destructor you are deleting an object which is not dinamically allocated. — LarryPel, Aug 20 '13 at 19:40
Can you show us exactly how you are using these classes and show us which line it breaks when you try to add a string? While I agree that calling `delete` on a variable that isn't dynamically allocated is a problem, if your program is crashing when you add a string to your template list, then that isn't the cause of the error that you are seeing. — Doug, Aug 20 '13 at 19:52

Zac Howland · Answer 1 · 2013-08-20T19:44:56.177

5

Part of your problem is here:

ListNode(T item)
{
    mItem = item; // for a std::string, this will be a class member, non-pointer
    mNext = NULL;
    mPrev = NULL;
}

ListNode(T item, ListNode<T>* next, ListNode<T>* prev)
{
    mItem = item; // same here
    mNext = next;
    mPrev = prev;
}


~ListNode()
{
    delete &mItem; // you are attempting to delete an item you never created
}

You should either change your constructors to create a T* object on the heap (which will then be deleted in your destructor), or remove the delete line from your destructor.

This problem will be evident with far more than just std::string, by the way.

edited Aug 20 '13 at 19:44

answered Aug 20 '13 at 19:38

Zac Howland

15,777
1
26
42

Could you describe your answer with a piece of code, please? By the way, it's strange it does not work only with strings: when I instantiate a list of custom objects I don't receive any error. With std::string I receive the following console warning after a "List list = new LinkedList()": "warning: FTH: (4344): *** Fault tolerant heap shim applied to current process. This is usually due to previous crashes. *** warning: RTTI symbol not found for class 'LinkedList' warning: RTTI symbol not found for class 'LinkedList' " – Imhotep Aug 20 '13 at 22:38
The error you are getting is another, unrelated, problem, that user2093113 describes below. This error is one you will see with all types once you've fixed your that issue. – Zac Howland Aug 21 '13 at 13:12

score 3 · Answer 2 · answered Aug 20 '13 at 19:37

Somewhere in your program you are doing this:

std::string s(nullptr);

Calling std::string's constructor with a null pointer is causing it to throw a std::logic_error exception.

From the standard:

§ 21.4.2

basic_string(const charT* s, size_type n, const Allocator& a = Allocator());

Requires: s shall not be a null pointer and n < npos.

score 0 · Answer 3 · edited May 23 '17 at 10:25

0

It seems it's not possible to pass std::string as template argument...

Strings as Template Arguments

Now I use an "old" - char const* - to achieve the expected result, even if I have to implement my personal "utils" methods to work with those pointers now...

edited May 23 '17 at 10:25

Community

1
1

answered Aug 21 '13 at 17:33

Imhotep

41
1
4

C++ custom template LinkedList crashes adding std::string

3 Answers3