Building a safer linked list for C++

Roland · May 21, 2017

Hard to say without seeing how Link, LinkedList and LinkNode looks like.

Josh · May 21, 2017

I got it all worked out. Here's how you use it:

LinkedList<Entity*> list;

Link<Entity*> link = list.AddLast(e);

To iterate through a list do this:

for (link = list.First(); link.IsValid(); link++)

{

link.Value()->SetPosition(1,2,3);

}

You can remove a link at any time:

link.Remove();

Or multiple times, with no errors:

link.Remove();

link.Remove();// does nothing

You can clear the list at any time:

list.Clear()

And you can safely call remove on links when the list was already cleared:

list.Clear();

link.Remove();// does nothing

You can safely remove links that have not been added to a list:

Link<int> link;

link.Remove();// does nothing

No more worried about whether a list iterator is valid. All those examples above would cause horrible crashes with STL lists.

#include "App.h"

using namespace Leadwerks;

template <typename T>

class LinkedList;

template <typename T>

class LinkNode;

template <typename T>

class Link;

template <typename T>

class Link : public Object

{

public:

weak_ptr<LinkNode<T>> link;

bool IsValid();

T Value();

Link<T> Prev();

Link<T> Next();

Link<T>& operator++(int i);

Link<T>& operator--(int i);

void Remove();

};

template <typename T>

class LinkNode : public Object

{

public:

LinkNode();

~LinkNode();

shared_ptr<LinkNode<T>> self;

LinkNode<T>* next;

LinkNode<T>* prev;

LinkedList<T>* list;

T value;

void Remove();

};

template <typename T>

class LinkedList : public Object

{

public:

LinkedList();

~LinkedList();

LinkNode<T>* first;

LinkNode<T>* last;

Link<T> AddFirst(T value);

Link<T> AddLast(T value);

Link<T> GetFirst();

Link<T> GetLast();

void Clear();

};

template <typename T>

LinkNode<T>::LinkNode() : next(nullptr), prev(nullptr), list(nullptr)

{

self = shared_ptr<LinkNode<T>>(this);

}

template <typename T>

LinkNode<T>::~LinkNode()

{

Print("Deleting link");

}

template <typename T>

void LinkNode<T>::Remove()

{

if (list)

{

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

if (list->last == this) list->last = prev;

}

if (next) next->prev = prev;

if (prev) prev->next = next;

list = nullptr;

prev = nullptr;

next = nullptr;

self.reset();

}

template <typename T>

void Link<T>::Remove()

{

if (!link.expired())

{

shared_ptr<LinkNode<T>> ptr = link.lock();

ptr->Remove();

}

template <typename T>

T Link<T>::Value()

{

if (!link.expired())

{

shared_ptr<LinkNode<T>> ptr = link.lock();

return ptr->value;

}

template <typename T>

Link<T>& Link<T>::operator++(int i)

{

shared_ptr<LinkNode<T>> ptr = link.lock();

if (ptr->next)

{

link = ptr->next->self;

}

else

{

link.reset();

}

return *this;

}

template <typename T>

Link<T>& Link<T>::operator--(int i)

{

shared_ptr<LinkNode<T>> ptr = link.lock();

if (ptr->prev)

{

link = ptr->prev->self;

}

else

{

link.reset();

}

return *this;

}

template <typename T>

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

{

Link<T> linkref;

shared_ptr<LinkNode<T>> ptr = link.lock();

if (ptr->next) linkref.link = ptr->next->self;

return linkref;

}

template <typename T>

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

{

Link<T> linkref;

shared_ptr<LinkNode<T>> ptr = link.lock();

if (ptr->prev) linkref.link = ptr->prev->self;

return linkref;

}

template <typename T>

bool Link<T>::IsValid()

{

return (!link.expired());

}

template <typename T>

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

template <typename T>

LinkedList<T>::~LinkedList()

{

Clear();

}

template <typename T>

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

{

Link<T> linkref;

if (first) linkref.link = first->self;

return linkref;

}

template <typename T>

Link<T> LinkedList<T>::GetLast()

{

Link<T> linkref;

if (last) linkref.link = last->self;

return linkref;

}

template <typename T>

void LinkedList<T>::Clear()

{

LinkNode<T>* link = first;

LinkNode<T>* nextlink = nullptr;

while (link)

{

nextlink = link->next;

link->self.reset();

link = nextlink;

}

first = nullptr;

last = nullptr;

}

template <typename T>

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

{

Link<T> linkref;

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

link->list = this;

link->value = value;

if (first)

{

first->prev = link;

link->next = first;

}

first = link;

linkref.link = link->self;

if (last == nullptr) last = link;

return linkref;

}

template <typename T>

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

{

Link<T> linkref;

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

link->list = this;

link->value = value;

if (last)

{

last->next = link;

link->prev = last;

}

last = link;

linkref.link = link->self;

if (first == nullptr) first = link;

return linkref;

}

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

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

{

LinkedList<int> list;

Link<int> link;

link = list.AddLast(1);

link = list.AddLast(2);

link = list.AddLast(3);

link = list.AddLast(4);

link = list.AddLast(5);

link = list.AddLast(6);

//link++;

link.Remove();

for (link = list.GetFirst(); link.IsValid(); link++)

{

Print(link.Value());

}

list.Clear();

//Try doing this with an iterator, lol!

link.Remove();

list.AddFirst(200);

list.AddFirst(100);

for (link = list.GetFirst(); link.IsValid(); link = link.Next())

{

Print(link.Value());

}

return 0;

}

Josh · May 21, 2017

However, you can see in the test below, my lists are slower. With 1000000 elements STL lists take 36 msec and mine takes 125:

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

{

std::list<int> stllist;

LinkedList<int> list;

for (int i = 0; i < 1000000; ++i)

{

list.AddLast(i);

stllist.push_back(i);

}

uint64_t time = Time::Millisecs();

int n;

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

{

n = (*it);

}

System::Print(int(Time::Millisecs() - time));

time = Time::Millisecs();

for (auto link = list.GetFirst(); link.IsValid(); link++)

{

n = link.Value();

}

System::Print(int(Time::Millisecs() - time));

return 0;

}

These are really extreme loads though.

Josh · May 21, 2017

This example shows how slow std::list::remove is:

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

{

std::vector < std::list<int>::iterator> it;

std::list<int> list;

uint64_t time;

for (int i = 0; i < 10000; ++i)

{

list.push_front(i);

it.push_back(list.begin());

}

time = Time::Millisecs();

for (int i = 0; i < 10000; ++i)

{

list.erase(it);

}

System::Print("Erase");

System::Print(int(Time::Millisecs() - time));

list.clear();

for (int i = 0; i < 10000; ++i)

{

list.push_front(i);

}

time = Time::Millisecs();

for (int i = 0; i < 10000; ++i)

{

list.remove(i);

}

System::Print("Remove");

System::Print(int(Time::Millisecs() - time));

return 0;

}

Erase
2

Remove

1657

Josh · May 21, 2017

std::set is basically a map without a value, just the key. Iterating through 1000000 elements takes 50 msecs, slower than STL lists but faster than my lists. Sets allow fast removal of elements by value. Insertion, however, is monstrously slow.

Roland · May 21, 2017

The reason why remove is slow is that all non-removed item are shifted towards the front of the list while the container keeps it's size. After the operation remove returns an iterator past the last non removed item. Removed items are actually not removed but just marked as removed. The idea is to bring down the amount of memory allocations and get a continuous vector. You can also use remove to remove all items of a certain value from the vector

Here's some notes on iteration on a vector

http://fastcpp.blogspot.se/2011/03/fast-iteration-over-stl-vector-elements.html?m=1

There are quite a few types of containers, each one suited for different situations and with their drawbacks in other situations. There is no "the fastest" I'm afraid.

Crazycarpet · May 21, 2017

Josh is using a std::list, in linked lists the shift doesn't occur. In vectors it occurs to keep the data contiguous. Lists do not guarantee contiguity in any way.

This is why he's using a list instead of a vector, he's not worried about fast access or iteration. He's interested in the constant time for removal in the middle of the list, where as removal in the middle of a vector as you said causes copies.

+1 for the "There is no 'the fastest'" comment. More true words have never been spoken.

Josh is comparing the difference between the underlying std::erase and std::remove.... std::remove has a higher complexity as it traverses the whole list til it finds the element that matches... where as std::erase uses an iterator position (or index in a vector) to remove at an already known location.

std::remove is so much slower because the location of the item isn't known.

Consider:

std::list<Item*> myList;

The function declarations look like:

myList::remove(Item* pItem); // It has to find what element == pItem..

where as with

myList::erase(iter<Item*> pIter); // The location is already known!! (p.s: I know iter isn't the underlying type, pseudocode.)

Note that std::vector doesn't have a method that uses the underlying std::remove method although it'd be easy to implement. This method would likely be faster in a vector due to the contiguous nature allowing for range-based loops without iterators.

Josh · May 22, 2017

I'm trying another approach. Why doesn't the iterator member compile here?

template <typename T>

class Link

{

public:

Link();

bool valid;

std::list<T>::iterator it;

T GetValue();

Link<T> Prev();

Link<T> Next();

void Remove();

};

Crazycarpet · May 22, 2017

I'd assume because the list of this type doesn't exist at the time, the concept itself is flawed.

You'd need a list member, then in the constructor create a iterator for the list member.

Edit: This is because the template nature.

Edit#2: Same issue with the constructor, I don't know what I was thinking... this will be hard to implement look how the standard does it using the auto keyword. I'd really re-think your design before trying to make a custom container type to fight against the standard. C++ containers are the way they are for a VERY good reason.

How about using (the now deprecated) std::iterator?

http://en.cppreference.com/w/cpp/iterator/iterator

See the Range example and how they create a custom iterator type.

Josh · May 22, 2017

Okay, I now have something that is safer than STL lists and 2-3 times as fast:

STL Insertion: 158
LW Insertion: 71

STL Iteration: 38

LW Iteration: 20

Press any key to continue . . .

#include "App.h"

using namespace Leadwerks;

template <typename T>

class LinkedList;

template <typename T>

class LinkNode;

template <typename T>

class Link;

template <typename T>

class Link : public Object

{

public:

uint64_t listid;

LinkNode<T>* link;

//weak_ptr<LinkNode<T>> link;

bool IsValid();

T Value();

Link<T> Prev();

Link<T> Next();

Link<T>& operator++(int i);

Link<T>& operator--(int i);

void Remove();

};

template <typename T>

class LinkNode : public Object

{

public:

LinkNode();

~LinkNode();

//shared_ptr<LinkNode<T>> self;

LinkNode<T>* next;

LinkNode<T>* prev;

LinkedList<T>* list;

T value;

void Remove();

};

template <typename T>

class LinkedList : public Object

{

public:

LinkedList();

~LinkedList();

uint64_t listid;

LinkNode<T>* first;

LinkNode<T>* last;

Link<T> AddFirst(T value);

Link<T> AddLast(T value);

Link<T> GetFirst();

Link<T> GetLast();

void Clear();

};

template <typename T>

LinkNode<T>::LinkNode() : next(nullptr), prev(nullptr), list(nullptr)

{

//self = shared_ptr<LinkNode<T>>(this);

}

template <typename T>

LinkNode<T>::~LinkNode()

{

//Print("Deleting link");

}

template <typename T>

void LinkNode<T>::Remove()

{

if (list)

{

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

if (list->last == this) list->last = prev;

}

if (next) next->prev = prev;

if (prev) prev->next = next;

list = nullptr;

prev = nullptr;

next = nullptr;

//self.reset();

}

template <typename T>

void Link<T>::Remove()

{

if (IsValid())

{

link->Remove();

delete link;

link = NULL;

}

/*if (!link.expired())

{

shared_ptr<LinkNode<T>> ptr = link.lock();

ptr->Remove();

}*/

}

template <typename T>

T Link<T>::Value()

{

if (IsValid())

{

return link->value;

}

/*if (!link.expired())

{

shared_ptr<LinkNode<T>> ptr = link.lock();

return ptr->value;

}*/

}

template <typename T>

Link<T>& Link<T>::operator++(int i)

{

/*

shared_ptr<LinkNode<T>> ptr = link.lock();

if (ptr->next)

{

link = ptr->next->self;

}

else

{

link.reset();

}*/

if (IsValid())

{

if (link) link = link->next;

}

return *this;

}

template <typename T>

Link<T>& Link<T>::operator--(int i)

{

if (IsValid())

{

if (link) link = link->prev;

}

return *this;

/*shared_ptr<LinkNode<T>> ptr = link.lock();

if (ptr->prev)

{

link = ptr->prev->self;

}

else

{

link.reset();

}

return *this;*/

}

template <typename T>

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

{

Link<T> linkref;

if (IsValid())

{

linkref.listid = listid;

if (link) linkref.link = link->next;

}

return linkref;

}

template <typename T>

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

{

Link<T> linkref;

if (IsValid())

{

linkref.listid = listid;

if (link) linkref.link = link->prev;

}

return linkref;

}

template <typename T>

bool Link<T>::IsValid()

{

if (link == NULL) return false;

if (link->list->listid != listid) return false;

return link != NULL;// (!link.expired());

}

template <typename T>

LinkedList<T>::LinkedList() : first(nullptr), last(nullptr), listid(0) {}

template <typename T>

LinkedList<T>::~LinkedList()

{

Clear();

}

template <typename T>

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

{

Link<T> linkref;

linkref.listid = listid;

if (first) linkref.link = first;

return linkref;

}

template <typename T>

Link<T> LinkedList<T>::GetLast()

{

Link<T> linkref;

linkref.listid = listid;

if (last) linkref.link = last;

return linkref;

}

template <typename T>

void LinkedList<T>::Clear()

{

listid++;

LinkNode<T>* link = first;

LinkNode<T>* nextlink = nullptr;

while (link)

{

nextlink = link->next;

delete link;

link = nextlink;

}

first = nullptr;

last = nullptr;

}

template <typename T>

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

{

Link<T> linkref;

linkref.listid = listid;

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

link->list = this;

link->value = value;

if (first)

{

first->prev = link;

link->next = first;

}

first = link;

linkref.link = link;

if (last == nullptr) last = link;

return linkref;

}

template <typename T>

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

{

Link<T> linkref;

linkref.listid = listid;

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

link->list = this;

link->value = value;

if (last)

{

last->next = link;

link->prev = last;

}

last = link;

linkref.link = link;

if (first == nullptr) first = link;

return linkref;

}

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

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

{

LinkedList<int> list;

/*

list.AddFirst(1);

list.AddFirst(2);

auto link = list.AddFirst(3);

link.Remove();

list.AddFirst(4);

list.AddFirst(5);

for (auto link = list.GetFirst(); link.IsValid(); link++)

{

Print(link.Value());

}

*/

//list.AddFirst(62);

//Link<int> link = list.GetFirst();

//link.Remove();

std::map<int,int> mymap;

int g = mymap[42];

int sz2 = mymap.size();

std::list<int>::iterator it2;

std::vector < std::vector<int>::iterator> it;

std::list<int> stllist;

uint64_t time;

//std::unordered_map<int,bool> map;

time = Time::Millisecs();

for (int i = 0; i < 1000000; ++i)

{

stllist.push_front(i);

}

time = Time::Millisecs() - time;

System::Print("STL Insertion: " + String(time));

time = Time::Millisecs();

for (int i = 0; i < 1000000; ++i)

{

list.AddFirst(i);

}

time = Time::Millisecs() - time;

System::Print("LW Insertion: " + String(time));

int n;

time = Time::Millisecs();

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

{

n = *it;

}

time = Time::Millisecs() - time;

System::Print("STL Iteration: " + String(time));

time = Time::Millisecs();

for (auto link = list.GetFirst(); link.IsValid(); link++)

{

n = link.Value();

}

time = Time::Millisecs() - time;

System::Print("LW Iteration: " + String(time));

stllist.clear();

list.Clear();

/*

int n;

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

{

n = (*it);

}

map.clear();

list.clear();

for (int i = 0; i < 10000; ++i)

{

list.push_back(i);

}

time = Time::Millisecs();*/

/*

for (int i = 0; i < 10000; ++i)

{

list.erase(i);

}

System::Print("Remove");

System::Print(int(Time::Millisecs() - time));

*/

return 0;

}

/*

link = list.AddLast(1);

link = list.AddLast(2);

link = list.AddLast(3);

link = list.AddLast(4);

link = list.AddLast(5);

link = list.AddLast(6);

//link++;

link.Remove();

for (link = list.GetFirst(); link.IsValid(); link++)

{

Print(link.Value());

}

list.Clear();

//Try doing this with an iterator, lol!

link.Remove();

list.AddFirst(200);

list.AddFirst(100);

for (link = list.GetFirst(); link.IsValid(); link = link.Next())

{

Print(link.Value());

}

return 0;

}*/

Josh · May 22, 2017

Here are some of the safety features:

#include "App.h"

using namespace Leadwerks;

template <typename T>

class LinkedList;

template <typename T>

class LinkNode;

template <typename T>

class Link;

template <typename T>

class Link : public Object

{

public:

uint64_t listid;

LinkNode<T>* link;

LinkedList<T>* list;

//weak_ptr<LinkNode<T>> link;

bool IsValid();

T Value();

Link<T> Prev();

Link<T> Next();

Link<T>& operator++(int i);

Link<T>& operator--(int i);

void Remove();

};

template <typename T>

class LinkNode : public Object

{

public:

LinkNode();

~LinkNode();

//shared_ptr<LinkNode<T>> self;

LinkNode<T>* next;

LinkNode<T>* prev;

LinkedList<T>* list;

T value;

void Remove();

};

template <typename T>

class LinkedList : public Object

{

public:

LinkedList();

~LinkedList();

uint64_t listid;

LinkNode<T>* first;

LinkNode<T>* last;

Link<T> AddFirst(T value);

Link<T> AddLast(T value);

Link<T> GetFirst();

Link<T> GetLast();

void Clear();

};

template <typename T>

LinkNode<T>::LinkNode() : next(nullptr), prev(nullptr), list(nullptr)

{

//self = shared_ptr<LinkNode<T>>(this);

}

template <typename T>

LinkNode<T>::~LinkNode()

{

//Print("Deleting link");

}

template <typename T>

void LinkNode<T>::Remove()

{

if (list)

{

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

if (list->last == this) list->last = prev;

}

if (next) next->prev = prev;

if (prev) prev->next = next;

list = nullptr;

prev = nullptr;

next = nullptr;

//self.reset();

}

template <typename T>

void Link<T>::Remove()

{

if (IsValid())

{

link->Remove();

delete link;

link = NULL;

}

/*if (!link.expired())

{

shared_ptr<LinkNode<T>> ptr = link.lock();

ptr->Remove();

}*/

}

template <typename T>

T Link<T>::Value()

{

if (IsValid())

{

return link->value;

}

/*if (!link.expired())

{

shared_ptr<LinkNode<T>> ptr = link.lock();

return ptr->value;

}*/

}

template <typename T>

Link<T>& Link<T>::operator++(int i)

{

/*

shared_ptr<LinkNode<T>> ptr = link.lock();

if (ptr->next)

{

link = ptr->next->self;

}

else

{

link.reset();

}*/

if (IsValid())

{

if (link) link = link->next;

}

return *this;

}

template <typename T>

Link<T>& Link<T>::operator--(int i)

{

if (IsValid())

{

if (link) link = link->prev;

}

return *this;

/*shared_ptr<LinkNode<T>> ptr = link.lock();

if (ptr->prev)

{

link = ptr->prev->self;

}

else

{

link.reset();

}

return *this;*/

}

template <typename T>

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

{

Link<T> linkref;

if (IsValid())

{

listref list = list;

linkref.listid = listid;

if (link) linkref.link = link->next;

}

return linkref;

}

template <typename T>

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

{

Link<T> linkref;

if (IsValid())

{

listref list = list;

linkref.listid = listid;

if (link) linkref.link = link->prev;

}

return linkref;

}

template <typename T>

bool Link<T>::IsValid()

{

if (link == NULL) return false;

if (list->listid != listid) return false;

return link != NULL;// (!link.expired());

}

template <typename T>

LinkedList<T>::LinkedList() : first(nullptr), last(nullptr), listid(0) {}

template <typename T>

LinkedList<T>::~LinkedList()

{

Clear();

}

template <typename T>

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

{

Link<T> linkref;

linkref.listid = listid;

linkref.list = this;

if (first) linkref.link = first;

return linkref;

}

template <typename T>

Link<T> LinkedList<T>::GetLast()

{

Link<T> linkref;

linkref.listid = listid;

linkref.list = this;

if (last) linkref.link = last;

return linkref;

}

template <typename T>

void LinkedList<T>::Clear()

{

listid++;// makes list incompatbie with all existing links

LinkNode<T>* link = first;

LinkNode<T>* nextlink = nullptr;

while (link)

{

nextlink = link->next;

delete link;

link = nextlink;

}

first = nullptr;

last = nullptr;

}

template <typename T>

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

{

Link<T> linkref;

linkref.list = this;

linkref.listid = listid;

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

link->list = this;

link->value = value;

if (first)

{

first->prev = link;

link->next = first;

}

first = link;

linkref.link = link;

if (last == nullptr) last = link;

return linkref;

}

template <typename T>

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

{

Link<T> linkref;

linkref.list = this;

linkref.listid = listid;

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

link->list = this;

link->value = value;

if (last)

{

last->next = link;

link->prev = last;

}

last = link;

linkref.link = link;

if (first == nullptr) first = link;

return linkref;

}

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

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

{

LinkedList<int> list;

Link<int> link;

link.Remove();// safe to remove uninitialized link

link = list.AddFirst(5);

link = list.AddFirst(4);

link = list.AddFirst(3);

link.Remove();

link.Remove();// safe to remove link twice

link = list.AddFirst(2);

link = list.AddFirst(1);

list.Clear();

link.Remove();// save to remove link after list is cleared!

list.AddLast(1);

list.AddLast(2);

link = list.AddLast(3);

auto anotherlink = link;

anotherlink.Remove();

//link.Remove();// this CAN cause a crash

list.AddLast(4);

list.AddLast(5);

//Iterate through list and print out values

for (auto link = list.GetFirst(); link.IsValid(); link++)

{

Print(link.Value());

}

return 0;

}

Crazycarpet · May 22, 2017

STL iteration is faster if you do:

auto _end = stllist.end(); / Obviously BEFORE the Time::GetCurrent();

Than make your loop look like this:

for (auto it = stllist.begin(); it != _end; it++)

Otherwise you're creating a new iterator every iteration, which normally wouldn't matter but 1 million iterator creations adds up. This is where your version implicitly has the advantage, I bet if you made the test case use a smaller sample the stl container and the original way would be faster.

STL container is faster because it doesn't do your error checking which is why it's almost immeasurably faster.

So far I can't poke holes in the insertion performance improvements.

There is a lot of memory leaks to be fixed though if I'm reading the code correctly.

Edit:

Note that when compiler optimizations are enabled for speed. (O2) the whole auto _end = myList.end() thing is done by the compiler automatically.

Josh · May 22, 2017

This version uses reference counting so the links can never cause an error:

#include "App.h"

using namespace Leadwerks;

#define USEREFCOUNT

template <typename T>

class LinkedList;

template <typename T>

class LinkNode;

template <typename T>

class Link;

template <typename T>

class Link : public Object

{

public:

uint64_t listid;

LinkNode<T>* node;

LinkedList<T>* list;

Link();

~Link();

T value;

inline bool IsValid()

{

if (node == nullptr) return false;

return (list->listid == listid);

}

inline T Value()

{

return node->value;

};

Link<T> Prev();

Link<T> Next();

Link<T>& operator=(const Link<T>& link);

inline Link<T>& operator++(int i)

{

if (node)

{

#ifdef USEREFCOUNT

node->refcount--;

if (node->refcount == 0)

{

LinkNode<T>* oldnode = node;

delete node;

node = oldnode;

}

#endif

node = node->next;

if (node)

{

value = node->value;

#ifdef USEREFCOUNT

node->refcount++;

#endif

}

return *this;

};

Link<T>& operator--(int i);

void Remove();

};

template <typename T>

class LinkNode : public Object

{

public:

LinkNode();

~LinkNode();

#ifdef USEREFCOUNT

uint64_t refcount;

#endif

LinkNode<T>* next;

LinkNode<T>* prev;

LinkedList<T>* list;

T value;

void Remove();

};

template <typename T>

class LinkedList : public Object

{

public:

LinkedList();

~LinkedList();

uint64_t listid;

LinkNode<T>* first;

LinkNode<T>* last;

Link<T> AddFirst(T value);

Link<T> AddLast(T value);

Link<T> GetFirst();

Link<T> GetLast();

void Clear();

};

template <typename T>

Link<T>& Link<T>::operator=(const Link<T>& link)

{

#ifdef USEREFCOUNT

if (node)

{

node->refcount--;

if (node->refcount == 0) delete node;

}

#endif

this->node = link.node;

#ifdef USEREFCOUNT

if (node) node->refcount++;

#endif

this->list = link.list;

this->listid = link.listid;

return *this;

}

template <typename T>

Link<T>::Link() : node(NULL)

{}

template <typename T>

Link<T>::~Link()

{

#ifdef USEREFCOUNT

if (node)

{

Debug::Assert(node->refcount > 0);

node->refcount--;

if (node->refcount == 0) delete node;

}

#endif

}

template <typename T>

LinkNode<T>::LinkNode() : next(nullptr), prev(nullptr), list(nullptr)

{

#ifdef USEREFCOUNT

refcount = 1;

#endif

}

template <typename T>

LinkNode<T>::~LinkNode()

{

int g = 4;//use this to set breakpoint for testing

}

template <typename T>

void LinkNode<T>::Remove()

{

if (list)

{

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

if (list->last == this) list->last = prev;

}

if (next) next->prev = prev;

if (prev) prev->next = next;

list = nullptr;

prev = nullptr;

next = nullptr;

}

template <typename T>

void Link<T>::Remove()

{

if (IsValid())

{

node->Remove();

#ifdef USEREFCOUNT

node->refcount--;

if (node->refcount == 0) delete node;

#else

delete node;

#endif

node = NULL;

}

/*template <typename T>

T Link<T>::Value()

{

return value;

}*/

/*template <typename T>

Link<T>& Link<T>::operator++(int i)

{

if (IsValid())

{

//link->refcount--;

//if (link->refcount == 0) delete link;

if (link)

{

link = link->next;

if (link) value = link->value;

}

return *this;

}*/

template <typename T>

Link<T>& Link<T>::operator--(int i)

{

if (IsValid())

{

if (link)

{

#ifdef USEREFCOUNT

node->refcount--;

if (node->refcount == 0)

{

LinkNode<T>* oldnode = node;

delete node;

node = oldnode;

}

#endif

node = node->prev;

if (node) value = node->value;

#ifdef USEREFCOUNT

node->refcount++;

#endif

}

return *this;

}

template <typename T>

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

{

Link<T> linkref;

if (IsValid())

{

listref list = list;

linkref.listid = listid;

linkref.value = value;

if (link)

{

linkref.link = link->next;

#ifdef USEREFCOUNT

linkref.link->refcount++;

#endif

}

return linkref;

}

template <typename T>

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

{

Link<T> linkref;

if (IsValid())

{

listref list = list;

linkref.listid = listid;

linkref.value = value;

if (link)

{

linkref.link = link->prev;

#ifdef USEREFCOUNT

linkref.link->refcount++;

#endif

}

return linkref;

}

/*template <typename T>

bool Link<T>::IsValid()

{

if (link == NULL) return false;

return (list->listid == listid);

}*/

template <typename T>

LinkedList<T>::LinkedList() : first(nullptr), last(nullptr), listid(0) {}

template <typename T>

LinkedList<T>::~LinkedList()

{

Clear();

}

template <typename T>

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

{

Link<T> linkref;

linkref.listid = listid;

linkref.list = this;

if (first)

{

linkref.node = first;

linkref.value = first->value;

#ifdef USEREFCOUNT

linkref.node->refcount+=2;

#endif

}

return linkref;

}

template <typename T>

Link<T> LinkedList<T>::GetLast()

{

Link<T> linkref;

linkref.listid = listid;

linkref.list = this;

if (last)

{

linkref.node = last;

linkref.value = value

#ifdef USEREFCOUNT

linkref.node->refcount++;

#endif

}

return linkref;

}

template <typename T>

void LinkedList<T>::Clear()

{

listid++;// makes list incompatbie with all existing links

LinkNode<T>* link = first;

LinkNode<T>* nextlink = nullptr;

while (link)

{

nextlink = link->next;

#ifdef USEREFCOUNT

link->refcount--;

if (link->refcount == 0) delete link;

#else

delete link;

#endif

link = nextlink;

}

first = nullptr;

last = nullptr;

}

template <typename T>

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

{

Link<T> linkref;

linkref.list = this;

linkref.listid = listid;

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

link->list = this;

link->value = value;

if (first)

{

first->prev = link;

link->next = first;

}

first = link;

linkref.node = link;

#ifdef USEREFCOUNT

linkref.node->refcount+=2;

#endif

if (last == nullptr) last = link;

return linkref;

}

template <typename T>

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

{

Link<T> linkref;

linkref.list = this;

linkref.listid = listid;

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

link->list = this;

link->value = value;

if (last)

{

last->next = link;

link->prev = last;

}

last = link;

linkref.node = link;

#ifdef USEREFCOUNT

linkref.node->refcount++;

#endif

if (first == nullptr) first = link;

return linkref;

}

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

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

{

LinkedList<int>* list = new LinkedList<int>;

Link<int> link;

link = list->AddFirst(1);

int g = 2;

link = list->AddFirst(2);

int f = 3;

link = list->AddFirst(3);

Link<int> b = link;

//list->Clear();

delete list;

link.Remove();

b.Remove();

/*for (link = list.GetFirst(); link.IsValid(); link++)

{

System::Print(link.Value());

}*/

/*

std::list<int>::iterator it2;

std::list<int> stllist;

uint64_t time;

//std::unordered_map<int,bool> map;

time = Time::Millisecs();

for (int i = 0; i < 1000000; ++i)

{

stllist.push_front(i);

}

time = Time::Millisecs() - time;

System::Print("STL Insertion: " + String(time));

time = Time::Millisecs();

for (int i = 0; i < 1000000; ++i)

{

list.AddFirst(i);

}

time = Time::Millisecs() - time;

System::Print("LW Insertion: " + String(time));

int n;

auto end = stllist.end();

time = Time::Millisecs();

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

{

n = *it;

}

time = Time::Millisecs() - time;

System::Print("STL Iteration: " + String(time));

time = Time::Millisecs();

for (auto link = list.GetFirst(); link.IsValid(); link++)

{

n = link.Value();

}

time = Time::Millisecs() - time;

System::Print("LW Iteration: " + String(time));

stllist.clear();

list.Clear();

*/

return 0;

}

Josh · May 22, 2017

Aliright here is my final version for the day. I opted not to use my own ref counting. It was very fast, but I worry about it causing mistakes and this works the way I want:

#include "App.h"

using namespace Leadwerks;

//#define USEREFCOUNT

template <typename T>

class LinkedList;

template <typename T>

class LinkNode;

template <typename T>

class Link;

template <typename T>

class Link : public Object

{

public:

uint64_t listid;

LinkNode<T>* node;

LinkedList<T>* list;

Link();

~Link();

inline bool IsValid()

{

if (node == nullptr) return false;

return (list->listid == listid);

}

inline T Value()

{

return node->value;

};

Link<T> Prev();

Link<T> Next();

#ifdef USEREFCOUNT

inline Link<T>& operator=(const Link<T>& link)

{

//#ifdef USEREFCOUNT

if (node != nullptr)

{

node->refcount--;

if (node->refcount == 0) delete node;

}

//#endif

memcpy(this, &link, sizeof(link));

//this->node = link.node;

//this->list = link.list;

//this->listid = link.listid;

//#ifdef USEREFCOUNT

if (node != nullptr) node->refcount++;

//#endif

return *this;

}

#endif

inline Link<T>& operator++(int i)

{

if (node)

{

#ifdef USEREFCOUNT

node->refcount--;

if (node->refcount == 0)

{

LinkNode<T>* oldnode = node;

delete node;

node = oldnode;

}

#endif

node = node->next;

if (node)

{

//value = node->value;

#ifdef USEREFCOUNT

node->refcount++;

#endif

}

return *this;

};

Link<T>& operator--(int i);

void Remove();

};

template <typename T>

class LinkNode : public Object

{

public:

LinkNode();

~LinkNode();

#ifdef USEREFCOUNT

uint64_t refcount;

#endif

LinkNode<T>* next;

LinkNode<T>* prev;

LinkedList<T>* list;

T value;

void Remove();

};

template <typename T>

class LinkedList : public Object

{

public:

LinkedList();

~LinkedList();

uint64_t listid;

LinkNode<T>* first;

LinkNode<T>* last;

uint32 size;

LinkedList<T>& operator=(const LinkedList<T>& list);

T operator[](unsigned int n);

Link<T> AddFirst(T value);

void AddFirst2(T value);

void AddLast(T value);

Link<T> GetFirst();

Link<T> GetLast();

void Clear();

uint32 GetSize();

};

template <typename T>

T LinkedList<T>::operator[](unsigned int n)

{

if (n >= size) return 0L;

int index = 0;

for (auto link = GetFirst(); link.IsValid(); link++)

{

if (index == n) return link.Value();

index++;

}

return 0L;

}

template <typename T>

LinkedList<T>& LinkedList<T>::operator=(const LinkedList<T>& list)

{

for (auto link = list.GetFirst(); link.IsValid(); link++)

{

AddLast(link.Value());

}

returh *this;

}

/*#ifdef USEREFCOUNT

template <typename T>

Link<T>& Link<T>::operator=(const Link<T>& link)

{

//#ifdef USEREFCOUNT

if (node!=nullptr)

{

node->refcount--;

if (node->refcount == 0) delete node;

}

//#endif

this->node = link.node;

this->list = link.list;

this->listid = link.listid;

//#ifdef USEREFCOUNT

if (node != nullptr) node->refcount++;

//#endif

return *this;

}

#endif*/

template <typename T>

Link<T>::Link() : node(NULL)

{}

template <typename T>

Link<T>::~Link()

{

#ifdef USEREFCOUNT

if (node)

{

node->refcount--;

if (node->refcount == 0) delete node;

}

#endif

}

template <typename T>

LinkNode<T>::LinkNode() : next(nullptr), prev(nullptr), list(nullptr)

{

#ifdef USEREFCOUNT

refcount = 1;

#endif

}

template <typename T>

LinkNode<T>::~LinkNode()

{

int g = 4;//use this to set breakpoint for testing

}

template <typename T>

void LinkNode<T>::Remove()

{

if (list)

{

list->size--;

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

if (list->last == this) list->last = prev;

}

if (next) next->prev = prev;

if (prev) prev->next = next;

list = nullptr;

prev = nullptr;

next = nullptr;

}

template <typename T>

void Link<T>::Remove()

{

if (IsValid())

{

node->Remove();

#ifdef USEREFCOUNT

node->refcount--;

if (node->refcount == 0) delete node;

#else

delete node;

#endif

node = NULL;

}

/*template <typename T>

T Link<T>::Value()

{

return value;

}*/

/*template <typename T>

Link<T>& Link<T>::operator++(int i)

{

if (IsValid())

{

//link->refcount--;

//if (link->refcount == 0) delete link;

if (link)

{

link = link->next;

if (link) value = link->value;

}

return *this;

}*/

template <typename T>

Link<T>& Link<T>::operator--(int i)

{

if (IsValid())

{

if (link)

{

#ifdef USEREFCOUNT

node->refcount--;

if (node->refcount == 0)

{

LinkNode<T>* oldnode = node;

delete node;

node = oldnode;

}

#endif

node = node->prev;

if (node) value = node->value;

#ifdef USEREFCOUNT

node->refcount++;

#endif

}

return *this;

}

template <typename T>

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

{

Link<T> linkref;

if (IsValid())

{

listref list = list;

linkref.listid = listid;

//linkref.value = value;

if (link)

{

linkref.link = link->next;

#ifdef USEREFCOUNT

linkref.link->refcount++;

#endif

}

return linkref;

}

template <typename T>

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

{

Link<T> linkref;

if (IsValid())

{

listref list = list;

linkref.listid = listid;

//linkref.value = value;

if (link)

{

linkref.link = link->prev;

#ifdef USEREFCOUNT

linkref.link->refcount++;

#endif

}

return linkref;

}

/*template <typename T>

bool Link<T>::IsValid()

{

if (link == NULL) return false;

return (list->listid == listid);

}*/

template <typename T>

LinkedList<T>::LinkedList() : size(0), first(nullptr), last(nullptr), listid(0) {}

template <typename T>

LinkedList<T>::~LinkedList()

{

Clear();

}

template <typename T>

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

{

Link<T> linkref;

linkref.listid = listid;

linkref.list = this;

if (first)

{

linkref.node = first;

//linkref.value = first->value;

#ifdef USEREFCOUNT

linkref.node->refcount += 2;

#endif

}

return linkref;

}

template <typename T>

Link<T> LinkedList<T>::GetLast()

{

Link<T> linkref;

linkref.listid = listid;

linkref.list = this;

if (last)

{

linkref.node = last;

//linkref.value = value

#ifdef USEREFCOUNT

linkref.node->refcount++;

#endif

}

return linkref;

}

template <typename T>

void LinkedList<T>::Clear()

{

listid++;// makes list incompatbie with all existing links

LinkNode<T>* link = first;

LinkNode<T>* nextlink = nullptr;

while (link)

{

nextlink = link->next;

#ifdef USEREFCOUNT

link->refcount--;

if (link->refcount == 0) delete link;

#else

delete link;

#endif

link = nextlink;

}

first = nullptr;

last = nullptr;

size = 0;

}

template <typename T>

uint32 LinkedList<T>::GetSize()

{

return size;

}

template <typename T>

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

{

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

link->list = this;

link->value = value;

if (first)

{

first->prev = link;

link->next = first;

}

first = link;

if (last == nullptr) last = link;

size++;

Link<T> linkref;

linkref.listid = listid;

linkref.list = this;

linkref.node = link;

#ifdef USEREFCOUNT

linkref.node->refcount += 2;

#endif

return linkref;

}

template <typename T>

void LinkedList<T>::AddFirst2(T value)

{

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

link->list = this;

link->value = value;

if (first)

{

first->prev = link;

link->next = first;

}

first = link;

if (last == nullptr) last = link;

size++;

}

template <typename T>

void LinkedList<T>::AddLast(T value)

{

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

link->list = this;

link->value = value;

if (last)

{

last->next = link;

link->prev = last;

}

last = link;

if (first == nullptr) first = link;

size++;

}

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

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

{

LinkedList<int> list;

Link<int> link;

std::list<int>::iterator it2;

std::list<int> stllist;

uint64_t time;

//std::unordered_map<int,bool> map;

time = Time::Millisecs();

for (int i = 0; i < 1000000; ++i)

{

stllist.push_front(i);

}

time = Time::Millisecs() - time;

System::Print("STL Insertion: " + String(time));

time = Time::Millisecs();

for (int i = 0; i < 1000000; ++i)

{

list.AddFirst2(i);

}

time = Time::Millisecs() - time;

System::Print("LW Insertion: " + String(time));

int n;

auto end = stllist.end();

time = Time::Millisecs();

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

{

n = *it;

}

time = Time::Millisecs() - time;

System::Print("STL Iteration: " + String(time));

time = Time::Millisecs();

for (auto link = list.GetFirst(); link.IsValid(); link++)

{

n = link.Value();

}

//I gain like a millisecond doing this:

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

{

n = link->value;

}*/

time = Time::Millisecs() - time;

System::Print("LW Iteration: " + String(time));

stllist.clear();

list.Clear();

return 0;

}

Crazycarpet · May 22, 2017

Bad news! I found out for some reason optimizations were disabled in release mode. When I went back and enabled compiler optimizations lists took lead once again.

Had a feeling something was off... the standard library containers are very, very fast for what they are.

All in all though, good linked list implementation! you can certainly continue to make it faster while maintaining the added safety too.

With <int>:

STL Insertion: 68

LW Insertion: 69

STL Iteration: 0

LW Iteration: 15

Press any key to continue .

With <MyStruct>:

STL Insertion: 84

LW Insertion: 100

STL Iteration: 0

LW Iteration: 16

Press any key to continue . . .

struct MyStruct {

MyStruct() {

one = 0;

two = 0;

three = 0;

four = 0;

five = 0;

for (int i = 0; i < 6; ++i) {

six = 0;

}

MyStruct(int pIn) {

one = pIn;

two = pIn;

three = pIn;

four = pIn;

five = pIn;

for (int i = 0; i < 6; ++i) {

six = pIn;

}

int one;

int two;

int three;

int four;

int five;

int six[6];

};. .

The code:

auto end = stllist.end();

in place of just using stllist.end() directly in the loop can be reverted because the compiler automatically does this when optimizations are enabled.

Admin · May 22, 2017

The compiler might be optimizing out that loop entirely since it doesn't do anything.

Crazycarpet · May 22, 2017

I thought this were the case too as the 0 ms iteration time seemed odd, however I used n each time it was assigned. (via print, etc) and this is still the case.. Keep in mind generally the stl library will be fast as it takes advantage of tricks and ideas that have been thought of by many people before us over years. If we think of an optimization technique, odds are it's been though of by someone before and implemented into the C++ standard.

Josh · May 22, 2017

If I can find a way to make a template iterator member I can just make a wrapper class around the STL list and add some small checks to prevent bad iterator removal.

Crazycarpet · May 22, 2017

I don't think this is necessary, and the only way I know how to do that has been deprecated in C++ 17... so I'd advise against it. (Inheriting from std::template).

Your LinkedList class is more than fast enough, and I'm sure can be made faster over time as you think of newer, more clever ways to optimize. (Maybe allocate more memory in chunks, then only expand the container when you reach this limit.)

Either way, this is fast enough for what you want to use it for... keep in mind stl container is ~twice as fast with 1 million elements. If you're storing a few thousands pointers the speed difference really is negligible. Pointers are smaller yet than the integers you tested with.

Josh · May 22, 2017

There's a bunch of different ways to do this:

Shared pointers: this gives lists that behave like full garbage-collected lists.
Ref counted links: Much faster, prevents most errors, but won't prevent errors with things like removing a link from a lists that no longer exists.
Non-ref counted link: Still simpler and safer than STL, and within the same range of performance.

I'm mostly concerned with having safe easy-to-use lists in Leadwerks Editor 5, so the performance on these is not that critical since it is not a real-time app.

aiaf · May 22, 2017

A strange implementation of a linked list (was really confused first time i saw this) , from linux kernel

https://github.com/torvalds/linux/blob/master/include/linux/list.h

Sign In

Building a safer linked list for C++

Recommended Posts

Link to comment

Share on other sites

Link to comment

Share on other sites

Link to comment

Share on other sites

Link to comment

Share on other sites

Link to comment

Share on other sites

Link to comment

Share on other sites

Link to comment

Share on other sites

Link to comment

Share on other sites

Link to comment

Share on other sites

Link to comment

Share on other sites

Link to comment

Share on other sites

Link to comment

Share on other sites

Link to comment

Share on other sites

Link to comment

Share on other sites

Link to comment

Share on other sites

Link to comment

Share on other sites

Link to comment

Share on other sites

Link to comment

Share on other sites

Link to comment

Share on other sites

Link to comment

Share on other sites

Link to comment

Share on other sites

Join the conversation