Dynamically allocated list in C++

Question

I made a cute generic (i.e. template) List class to handle lists in C++. The reason for that is that I found the std::list class terribly ugly for everyday use and since I constantly use lists, I needed a new one. The major improvement is that with my class, I can use [] to get items from it. Also, still to be implemented is an IComparer system to sort things.

I'm using this List class in OBJLoader, my class that loads Wavefront .obj files and converts them to meshes. OBJLoader contains lists of pointers to the following "types": 3D positions, 3D normals, uv texture coordinates, vertices, faces and meshes. The vertices list has objects that must be linked to some objects in all of the 3D positions, 3D normals and uv texture coordinates lists. Faces link to vertices and meshes link to faces. So they are all inter-connected.

For the sake of simplicity, let's consider that, in some context, there are just two lists of pointers: List<Person*> and List<Place*>. Person class contains, among others, the field List<Place*> placesVisited and the Place class contains the field List<Person*> peopleThatVisited. So we have the structure:

class Person
{
    ...
  public:
    Place* placeVisited;
    ...
};

class Place
{
    ...
  public:
    List<People*> peopleThatVisited;
};

Now we have the following code:

Person* psn1 = new Person();
Person* psn2 = new Person();

Place* plc1 = new Place();
Place* plc2 = new Place();
Place* plc2 = new Place();


// make some links between them here:
psn1->placesVisited.Add(plc1, plc2);
psn2->placesVisited.Add(plc2, plc3);

// add the links to the places as well
plc1->peopleThatVisited.Add(psn1);
plc2->peopleThatVisited.Add(psn1, psn2);
plc3->peopleThatVisited.Add(plc3);

// to make things worse:

List<Person*> allThePeopleAvailable;

allThePeopleAvailable.Add(psn1);
allThePeopleAvailable.Add(psn2);

List<Place*> allThePlacesAvailable;

allThePlacesAvailable.Add(plc1);
allThePlacesAvailable.Add(plc2);
allThePlacesAvailable.Add(plc3);

All done. What happens when we reach }? All the dtors are called and the program crashes because it tries to delete things two or more times.

The dtor of my list looks like this:

~List(void)
{
    cursor = begin;
    cursorPos = 0;

    while(cursorPos < capacity - 1)
    {
        cursor = cursor->next;
        cursorPos++;
        delete cursor->prev;
    }

    delete cursor;
}

where Elem is:

struct Elem
{
  public:
    Elem* prev;
    T value;
    Elem* next;
};

and T is the generic List type.

Which brings us back to the question: What ways are there to safely delete my List classes? The elements inside may or may not be pointers and, if they are pointers, I would like to be able, when I delete my List, to specify whether I want to delete the elements inside or just the Elem wrappers around them.

Smart pointers could be an answer, but that would mean that I can't have a List<bubuType*>, but just List<smart_pointer_to_bubuType>. This could be ok, but again: declaring a List<bubuType*> would cause no error or warning and in some cases the smart pointers would cause some problems in the implementation: for example, I might want to declare a List<PSTR> for some WinAPI returns. I think getting those PSTR inside smart pointers would be an ugly job. Thus, the solution I'm looking for I think should be somehow related to the deallocation system of the List template.

Any ideas?

Answer 1

Without even looking at your code, I say: scrap it!

C++ has a list class template that's about as efficient as it gets, well-known to all C++ programmers, and comes bug-free with your compiler.

Learn to use the STL.¹ Coming from other OO languages, the STL might seem strange, but there's an underlying reason for its strangeness, an alien beauty combining abstraction and performance - something considered impossible before Stepanov came and thought up the STL.
Rest assured that you are not the only one struggling with understanding the STL. When it came upon us, we all struggled to grasp its concepts, to learn its particularities, to understand how it ticks. The STL is a strange beast, but then it manages to combine two goals everybody thought could never be combined, so it's allowed to seem unfamiliar at first.

I bet writing your own linked list class used to be the second most popular indoor sport of C++ programmers - right after writing your own string class. Those of us who had been programming C++ 15 years ago nowadays enjoy ripping out those bug-ridden, inefficient, strange, and unknown string, list, and dictionary classes rotting in old code, and replacing it with something that is very efficient, well-known, and bug-free. Starting your own list class (other than for educational purposes) has to be one of the worst heresies.

If you program in C++, get used to one of the mightiest tools in its box as soon as possible.

¹_{Note that the term "STL" names that part of the C++ standard library that stems from Stepanov's library (plus things like std::string which got an STL interface attached as an afterthought), not the whole standard library.}