Building a safer linked list for C++

[Josh]

The containers tutorial really makes the dangers of C++ lists obvious:

https://www.leadwerks.com/learn?page=Tutorials_CPP_Containers

 

Iterators are the only way to quickly remove objects from a list, and they are extremely touchy.

 

There is no way to tell whether an iterator actually is part of a specific list.

 

There is no way to tell if an iterator has already been removed.

 

I really prefer the BlitzMax way of managing lists like this:

link = list.AddLast(object)
list.Remove(link)

 

Of course lists in C++ can work with any data type:

std::list<int>;

std::list<Entity*>;

std::list<Surface*>;

 

I have never actually built my own templates in C++, but that is the first step to creating a new list. Any suggestions on this?

[Rick]

My first thought is don't.

 

Can you give a scenario of the issue? I don't think generally you keep iterators around. They are generally just for iterating at that specific point. Are you trying to store iterators for later use? It's been some time since I've been in C++ but I don't recall needing to do that.

[Josh]

Yes, I do that all the time. That is the only way to quickly remove an object from a list. For example, in the Entity constructor I do this:

world->entities.push_front(this);

it = world.begin();

 

And in the destructor I do this:

world.erase(it);

 

If you use list.remove(this) it has to iterate through the entire list looking for that value, which is very slow. It's amazing how many people don't know this. Look at all these people who think they are experts but don't understand the most basic concepts of data management in C++:

[Roland]

Yes, I do that all the time. That is the only way to quickly remove an object from a list. For example, in the Entity constructor I do this:

world->entities.push_front(this);

it = world.begin();

 

And in the destructor I do this:

world.erase(it);

 

If you use list.remove(this) it has to iterate through the entire list looking for that value, which is very slow. It's amazing how many people don't know this. Look at all these people who think they are experts but don't understand the most basic concepts of data management in C++:

http://www.blitzbasic.com/Community/posts.php?topic=93291

Node need to have iterators dangling around

 

world->entities.push_front(this); // or world->entities.push_back(this);
//...
//..
std::remove(world->entities.begin(), world->entities.end(), this);

[Josh]

I don't understand. Isn't that just telling the function to iterate through from the beginning to the end and remove all elements with the specified value?

 

Imagine if you had a list with 1000 elements and you used remove() to remove 10 of them. (This is a pretty realistic example for a game engine.) It would be ridiculously inefficient.

[Rick]

I think like the one guy mentioned you are already interating over the list at some point in your program (a main reason for why the list exists right), so when you want to delete an object in the list you set a flag of the object itself and at the one iteration point you check that flag and if it's set for deletion, you delete it there while you have the iterator handy. I think, while storing iterators is possible, it has its disadvantages and possible issues that you are seeing, and trying to work around those will more than likely cause more unforeseen issues.

[Josh]

There are many situations where you would not iterate through each list constantly. That is an awful suggestion.

 

For example, each entity stores a list of its children. If a child entity is deleted, it automatically removes itself from the parent's list by erasing the right iterator. Otherwise you would have a lot of invalid pointers of deleted objects being stored in the list.

 

Why do so many people not understand this idea? Why make weird passive-aggressive workarounds to avoid what is needed?

[Rick]

We understand it, storing iterators just has potential for issue and disadvantages as you're saying and so it's generally avoided. In your example you are storing an entity in the world. I would assume you are looping over each entity each frame given that a script can be attached thst might have an UpdateWorld function that needs to be called each frame.

 

Data management can be done 100 different ways to Sunday. You gave us one example so it's what we have to go from. You're also making a highly specialized piece of software, game engine. The business world where most of the code exists in the world, doesn't care about the small performance hit of erasing from a list with the data itself.

 

So it's not that people don't "get it".

 

I would also add that my understanding is that most game engines try to avoid dynamic creation and deletion when possible and favor object pooling for speed reasons which changes all of that.

[Josh]

But it scales extremely badly. In games you always have to think about scalability.

 

I have an idea for a safer linked list that would work something like this:

class Link

{

Link* prev;

Link* next;

<datatype> value;

};

 

class LinkedList

{

Link* first;

 

void Remove(Link* link)

{

if (first == link) first = link->next;

if (link->prev!=nullptr) link->prev->next = link->next;

if (link->next!=nullptr) link->next->prev = link->prev;

link->prev = nullptr;

link->next = nullptr;

}

}

 

LinkedList list;

Link* link = list->AddLast(object);

 

list.Remove(link);// sets link->prev and next to NULL;

 

for (link = list->first; link!=nullptr; link = link->next)

{

whatever = link->value;

}

[Roland]

I don't understand. Isn't that just telling the function to iterate through from the beginning to the end and remove all elements with the specified value?

 

Imagine if you had a list with 1000 elements and you used remove() to remove 10 of them. (This is a pretty realistic example for a game engine.) It would be ridiculously inefficient.

Unfortunately I have no idea how the remove work behind the scene.

[Josh]

 

Unfortunately I have no idea how the remove work behind the scene.

 

Basically this:

for (auto it = list.begin(); it!=list.end(); it++)

{

if ((*it) == value)

{

it = list.erase(it);

}

}

[Rick]

I guess the question is what are the examples where you aren't iterating over the list each frame and even if you aren't is there harm in setting a deletion flag and deleting it when you do eventuslly iterate over the list.

 

When we don't know the details of your data storage scenarios it makes it hard to give suggestions so we only give based on specific situations. There aren't that many game engine developers in the world either so most people don't run into your scenarios perhaps.

[Roland]

Just some free thoughts on this

 

 

If you are after most efficiency use either std::vector or simple arrays. Using std::list or std::map is not at all suited for games as iterating over them is quite slow compared to vector

 

If possible store the objects and not pointers to them in your array in order to get contiguous memory. Iterating over any data in non-contiguous memory imposes a lot of cache misses in general and removes the ability for the compiler and CPU to do effective cache prefetching. This alone can kill performance

 

When removing from your vector use the 'swap/pop' method. This way you keep your array contiguous

std::swap(entitys[index], entitys());

entitys.pop_back();

 

This of course assumes you know the index of your object. This can be known this way

myArray.push_back(object);

object.index = myArray.size()-1

 

then you removes it with

std::swap(myArray[object.index],myArray.back());

myArray.pop_back();

[martyj]

I assume you're wanting to do something like this?

 

https://stackoverflow.com/questions/596162/can-you-remove-elements-from-a-stdlist-while-iterating-through-it

[Josh]

Roland, to instantly remove an element you would then have to store the vector index of that element (instead of the iterator), and if things moved around in the vector all those elements would become wrong.

 

If the user deletes an entity, how should that entity be removed from the world container that contains all entities? How can it instantly be removed from the parent's container of children? What if the parent has 1000 children? With my method it runs the same speed no matter what. By iterating through the entire list to remove an element the program will run slower and slower as more objects are added.

 

MartyJ, I solved the problem of removing items while iterating through lists by deferring object deletion until after the loop. This is done using System::GCPause() before the loop and System::GCResume() after.

 

My lists above could be made even simpler, where you just Delete the link object to remove it from the list:

Link::~Link()

{

if (list)

{

if (prev) prev->next = next;

if (next) next->prev = prev;

if (list->first == this) list->first = next;

prev = nullptr;

next = nullptr;

list = nullptr;

}

}

 

So instead of having this in the entity deconstructor:

if (parent) parent->kids.erase(it);

 

It would just be this:

delete parentlink;

[Roland]

With my method it runs the same speed no matter what.

Well great then If it works it does. So problem solved

[Josh]

Well, iterators are easy to make mistakes with.

 

So my question is, how do I made a link class where I can define the value to be any type of variable? I have so far never needed to make a C++ template.

class Link<DATATYPE>

{

Link();

~Link();

 

Link* next;

Link* prev;

Link* list;

<DATATYPE> value;

};

 

Where DATATYPE can be an entity, an int, a string, whatever.

[Roland]

template <typename T>
class Link
{
public:
   Link();
  ~Link();

  Link* next;
  Link* prev;
  Link* list;

  T value;
};

int main()
{
  Link<int> link1;
  link1.value = 10;

  Link<std::string> link2;
  link2.value = "Hello World";

  return 0;
}

 

[Josh]

Very nice, thank you.

 

I'm going to see if I can figure out a way to not make the links pointers and have them still work. I want to be able to clear the list and not worry about deleting each link object.

 

If I can get that to work it will be a huge improvement for anyone who uses C++ for anything.

[Josh]

First pass:

#include "App.h"

 

using namespace Leadwerks;

 

template <typename T>

class List;

 

template <typename T>

class Link;

 

//-------------------------------------------------------------

//Link Class

//-------------------------------------------------------------

template <typename T>

class Link

{

public:

Link();

~Link();

 

Link<T>* next;

Link<T>* prev;

List<T>* list;

 

T value;

};

 

template <typename T>

Link<T>::Link() : next(nullptr), prev(nullptr) {}

 

template <typename T>

Link<T>::~Link()

{

if (next) next->prev = prev;

if (prev) prev->next = next;

}

 

//-------------------------------------------------------------

//List Class

//-------------------------------------------------------------

template <typename T>

class List

{

public:

List();

 

Link<T>* first;

 

Link<T>* AddFirst(T value);

};

 

template <typename T>

List<T>::List() : first(nullptr) {}

 

template <typename T>

Link<T>* List<T>::AddFirst(T value)

{

Link<T>* link = new Link<T>;

link->value = value;

if (first)

{

first->prev = link;

link->next = first;

}

first = link;

return link;

}

 

//-------------------------------------------------------------

//-------------------------------------------------------------

int main(int argc,const char *argv[])

{

List<int> list;

 

Link<int>* link0 = list.AddFirst(3);

Link<int>* link1 = list.AddFirst(2);

auto link2 = list.AddFirst(1);// simpler way to do the same thing

 

//Loop through list

for (auto link = list.first; link != NULL; link = link->next)

{

Print(link->value);

}

 

return 0;

}

[Josh]

Here it is working with link removal:

#include "App.h"

 

using namespace Leadwerks;

 

template <typename T>

class List;

 

template <typename T>

class Link;

 

//-------------------------------------------------------------

//Link Class

//-------------------------------------------------------------

template <typename T>

class Link

{

public:

Link();

~Link();

 

Link<T>* next;

Link<T>* prev;

List<T>* list;

T value;

 

void Remove();

};

 

template <typename T>

Link<T>::Link() : next(nullptr), prev(nullptr) {}

 

template <typename T>

Link<T>::~Link()

{

Remove();

}

 

template <typename T>

void Link<T>::Remove()

{

if (list)

{

if (list->first == this) list->first = next;

}

if (next) next->prev = prev;

if (prev) prev->next = next;

list = nullptr;

prev = nullptr;

next = nullptr;

}

 

//-------------------------------------------------------------

//List Class

//-------------------------------------------------------------

template <typename T>

class List

{

public:

List();

 

Link<T>* first;

 

Link<T>* AddFirst(T value);

Link<T>* GetFirst();

};

 

template <typename T>

List<T>::List() : first(nullptr) {}

 

template <typename T>

Link<T>* List<T>::GetFirst()

{

return first;

}

 

template <typename T>

Link<T>* List<T>::AddFirst(T value)

{

Link<T>* link = new Link<T>;

link->list = this;

link->value = value;

if (first)

{

first->prev = link;

link->next = first;

}

first = link;

return link;

}

 

//-------------------------------------------------------------

//-------------------------------------------------------------

int main(int argc,const char *argv[])

{

List<int> list;

 

auto link0 = list.AddFirst(3);

auto link1 = list.AddFirst(2);

auto link2 = list.AddFirst(1);

 

delete link1;

 

//Loop through list

for (auto link = list.GetFirst(); link != NULL; link = link->next)

{

Print(link->value);

}

 

return 0;

}

[Josh]

What I really want is to be able to do this:

Link<int> link = list.AddFirst(element);

link.Remove();

 

Right now if we clear the list and make it delete all those links automatically, it can create a bunch of invalid pointers.

[Josh]

I think what I have is probably the best solution for linked lists in C++. The only thing I don't like is that you have to delete the links, but I don't think there is any way around that.

#include "App.h"

 

using namespace Leadwerks;

 

template <typename T>

class LinkedList;

 

template <typename T>

class Link;

 

//-------------------------------------------------------------

//Link Class

//-------------------------------------------------------------

template <typename T>

class Link : public Object

{

public:

Link();

~Link();

 

Link<T>* next;

Link<T>* prev;

LinkedList<T>* list;

T value;

 

T GetValue();

Link<T>* Prev();

Link<T>* Next();

void Remove();

};

 

template <typename T>

Link<T>::Link() : next(nullptr), prev(nullptr), list(nullptr) {}

 

template <typename T>

Link<T>::~Link()

{

Remove();

}

 

template <typename T>

Link<T>* Link<T>::Prev()

{

return prev;

}

 

template <typename T>

Link<T>* Link<T>::Next()

{

return next;

}

 

template <typename T>

T Link<T>::GetValue()

{

return value;

}

 

template <typename T>

void Link<T>::Remove()

{

if (list)

{

if (list->first == this) list->first = next;

}

if (next) next->prev = prev;

if (prev) prev->next = next;

list = nullptr;

prev = nullptr;

next = nullptr;

}

 

//-------------------------------------------------------------

//List Class

//-------------------------------------------------------------

template <typename T>

class LinkedList : public Object

{

public:

LinkedList();

~LinkedList();

 

Link<T>* first;

 

Link<T>* AddFirst(T value);

Link<T>* GetFirst();

void Clear();

};

 

template <typename T>

LinkedList<T>::LinkedList() : first(nullptr) {}

 

template <typename T>

LinkedList<T>::~LinkedList()

{

Clear();

}

 

template <typename T>

Link<T>* LinkedList<T>::GetFirst()

{

return first;

}

 

template <typename T>

void LinkedList<T>::Clear()

{

Link<T>* link = first;

Link<T>* nextlink = nullptr;

while (link)

{

nextlink = link->next;

link->next = nullptr;

link->prev = nullptr;

link->list = nullptr;

link = nextlink;

}

first = NULL;

}

 

template <typename T>

Link<T>* LinkedList<T>::AddFirst(T value)

{

Link<T>* link = new Link<T>;

link->list = this;

link->value = value;

if (first)

{

first->prev = link;

link->next = first;

}

first = link;

return link;

}

 

//-------------------------------------------------------------

//-------------------------------------------------------------

int main(int argc,const char *argv[])

{

LinkedList<int> list;

 

//Try doing this with an iterator, lol!!!

Link<int> link;

link.Remove();

 

auto link0 = list.AddFirst(3);

auto link1 = list.AddFirst(2);

auto link2 = list.AddFirst(1);

 

//We can safely remove the link multiple times

link2->Remove();

link2->Remove();

delete link2;

 

//Loop through list

for (auto link = list.GetFirst(); link != NULL; link = link->Next())

{

Print(link->value);

}

 

return 0;

}

[Josh]

It looks like we can use C++11 shared pointers to do what I want, but this is doing my head in.

[Josh]

When I try to call this function the compiler complains that the int version is not found:

    template <typename T>

Link<T> LinkedList<T>::AddFirst(T value)

{

LinkNode<T>* linknode = new LinkNode<T>;

linknode->list = this;

linknode->value = value;

if (first)

{

first->prev = linknode;

linknode->next = first;

}

first = linknode;

Link<T> link;

link.linknode = linknode->self;

linknode.valid = true;

return link;

}

 

	LinkedList<int> list;

Link<int> link = list.AddFirst(3);