Remove core::list and replace uses with std::list (#105)

15 files changed, 200 insertions, 694 deletions

diff --git a/include/IGUIElement.h b/include/IGUIElement.h
index 2e76a0f..2efeb05 100644
--- a/include/IGUIElement.h
+++ b/include/IGUIElement.h
@@ -6,7 +6,6 @@
 #define __I_GUI_ELEMENT_H_INCLUDED__

 

 #include "IReferenceCounted.h"

-#include "irrList.h"

 #include "rect.h"

 #include "irrString.h"

 #include "IEventReceiver.h"

@@ -14,6 +13,10 @@
 #include "EGUIAlignment.h"

 #include "IAttributes.h"

 #include "IGUIEnvironment.h"

+#include <cassert>

+#include <algorithm>

+#include <list>

+#include <vector>

 

 namespace irr

 {

@@ -50,12 +53,9 @@ public:
 	//! Destructor

 	virtual ~IGUIElement()

 	{

-		// delete all children

-		core::list<IGUIElement*>::Iterator it = Children.begin();

-		for (; it != Children.end(); ++it)

-		{

-			(*it)->Parent = 0;

-			(*it)->drop();

+		for (auto child : Children) {

+			child->Parent = nullptr;

+			child->drop();

 		}

 	}

 

@@ -239,10 +239,9 @@ public:
 		recalculateAbsolutePosition(false);

 

 		// update all children

-		core::list<IGUIElement*>::Iterator it = Children.begin();

-		for (; it != Children.end(); ++it)

+		for (auto child : Children)

 		{

-			(*it)->updateAbsolutePosition();

+			child->updateAbsolutePosition();

 		}

 	}

 

@@ -263,20 +262,19 @@ public:
 	{

 		IGUIElement* target = 0;

 

-		// we have to search from back to front, because later children

-		// might be drawn over the top of earlier ones.

-

-		core::list<IGUIElement*>::ConstIterator it = Children.getLast();

-

 		if (isVisible())

 		{

-			while(it != Children.end())

+			// we have to search from back to front, because later children

+			// might be drawn over the top of earlier ones.

+			auto it = Children.rbegin();

+			auto ie = Children.rend();

+			while (it != ie)

 			{

 				target = (*it)->getElementFromPoint(point);

 				if (target)

 					return target;

 

-				--it;

+				++it;

 			}

 		}

 

@@ -308,17 +306,19 @@ public:
 	//! Removes a child.

 	virtual void removeChild(IGUIElement* child)

 	{

-		core::list<IGUIElement*>::Iterator it = Children.begin();

-		for (; it != Children.end(); ++it)

-			if ((*it) == child)

-			{

-				(*it)->Parent = 0;

-				(*it)->drop();

-				Children.erase(it);

-				return;

-			}

+		assert(child->Parent == this);

+		Children.erase(child->ParentPos);

+		child->Parent = nullptr;

+		child->drop();

 	}

 

+	//! Removes all children.

+	virtual void removeAllChildren() {

+		while (!Children.empty()) {

+			auto child = Children.back();

+			child->remove();

+		}

+	}

 

 	//! Removes this element from its parent.

 	virtual void remove()

@@ -333,9 +333,8 @@ public:
 	{

 		if ( isVisible() )

 		{

-			core::list<IGUIElement*>::Iterator it = Children.begin();

-			for (; it != Children.end(); ++it)

-				(*it)->draw();

+			for (auto child : Children)

+				child->draw();

 		}

 	}

 

@@ -345,9 +344,8 @@ public:
 	{

 		if ( isVisible() )

 		{

-			core::list<IGUIElement*>::Iterator it = Children.begin();

-			for (; it != Children.end(); ++it)

-				(*it)->OnPostRender( timeMs );

+			for (auto child : Children)

+				child->OnPostRender( timeMs );

 		}

 	}

 

@@ -555,20 +553,15 @@ public:
 

 	//! Brings a child to front

 	/** \return True if successful, false if not. */

-	virtual bool bringToFront(IGUIElement* element)

+	virtual bool bringToFront(IGUIElement* child)

 	{

-		core::list<IGUIElement*>::Iterator it = Children.begin();

-		for (; it != Children.end(); ++it)

-		{

-			if (element == (*it))

-			{

-				Children.erase(it);

-				Children.push_back(element);

-				return true;

-			}

-		}

-

-		return false;

+		if (child->Parent != this)

+			return false;

+		if (std::next(child->ParentPos) == Children.end()) // already there

+			return true;

+		Children.erase(child->ParentPos);

+		child->ParentPos = Children.insert(Children.end(), child);

+		return true;

 	}

 

 

@@ -576,24 +569,17 @@ public:
 	/** \return True if successful, false if not. */

 	virtual bool sendToBack(IGUIElement* child)

 	{

-		core::list<IGUIElement*>::Iterator it = Children.begin();

-		if (child == (*it)) // already there

+		if (child->Parent != this)

+			return false;

+		if (child->ParentPos == Children.begin()) // already there

 			return true;

-		for (; it != Children.end(); ++it)

-		{

-			if (child == (*it))

-			{

-				Children.erase(it);

-				Children.push_front(child);

-				return true;

-			}

-		}

-

-		return false;

+		Children.erase(child->ParentPos);

+		child->ParentPos = Children.insert(Children.begin(), child);

+		return true;

 	}

 

 	//! Returns list with children of this element

-	virtual const core::list<IGUIElement*>& getChildren() const

+	virtual const std::list<IGUIElement*>& getChildren() const

 	{

 		return Children;

 	}

@@ -610,14 +596,13 @@ public:
 	{

 		IGUIElement* e = 0;

 

-		core::list<IGUIElement*>::ConstIterator it = Children.begin();

-		for (; it != Children.end(); ++it)

+		for (auto child : Children)

 		{

-			if ((*it)->getID() == id)

-				return (*it);

+			if (child->getID() == id)

+				return child;

 

 			if (searchchildren)

-				e = (*it)->getElementFromId(id, true);

+				e = child->getElementFromId(id, true);

 

 			if (e)

 				return e;

@@ -663,7 +648,7 @@ public:
 		if (wanted==-2)

 			wanted = 1073741824; // maximum s32

 

-		core::list<IGUIElement*>::ConstIterator it = Children.begin();

+		auto it = Children.begin();

 

 		s32 closestOrder, currentOrder;

 

@@ -806,10 +791,40 @@ protected:
 			child->remove(); // remove from old parent

 			child->LastParentRect = getAbsolutePosition();

 			child->Parent = this;

-			Children.push_back(child);

+			child->ParentPos = Children.insert(Children.end(), child);

 		}

 	}

 

+#ifndef NDEBUG

+	template<typename Iterator>

+	static size_t _fastSetChecksum(Iterator begin, Iterator end) {

+		std::hash<typename Iterator::value_type> hasher;

+		size_t checksum = 0;

+		for (Iterator it = begin; it != end; ++it) {

+			size_t h = hasher(*it);

+			checksum ^= 966073049 + (h * 3432918353) + ((h >> 16) * 461845907);

+		}

+		return checksum;

+	}

+#endif

+

+	// Reorder children [from, to) to the order given by `neworder`

+	void reorderChildren(

+		std::list<IGUIElement*>::iterator from,

+		std::list<IGUIElement*>::iterator to,

+		const std::vector<IGUIElement*> &neworder)

+	{

+		assert(_fastSetChecksum(from, to) == _fastSetChecksum(neworder.begin(), neworder.end()));

+		for (auto e : neworder)

+		{

+			*from = e;

+			e->ParentPos = from;

+			++from;

+		}

+		assert(from == to);

+	}

+

+

 	// not virtual because needed in constructor

 	void recalculateAbsolutePosition(bool recursive)

 	{

@@ -931,10 +946,9 @@ protected:
 		if ( recursive )

 		{

 			// update all children

-			core::list<IGUIElement*>::Iterator it = Children.begin();

-			for (; it != Children.end(); ++it)

+			for (auto child : Children)

 			{

-				(*it)->recalculateAbsolutePosition(recursive);

+				child->recalculateAbsolutePosition(recursive);

 			}

 		}

 	}

@@ -942,11 +956,14 @@ protected:
 protected:

 

 	//! List of all children of this element

-	core::list<IGUIElement*> Children;

+	std::list<IGUIElement*> Children;

 

 	//! Pointer to the parent

 	IGUIElement* Parent;

 

+	//! Our position in the parent list. Only valid when Parent != nullptr

+	std::list<IGUIElement*>::iterator ParentPos;

+

 	//! relative rect of element

 	core::rect<s32> RelativeRect;

 

diff --git a/include/ISceneNode.h b/include/ISceneNode.h
index 3f50c6e..1f8c2c6 100644
--- a/include/ISceneNode.h
+++ b/include/ISceneNode.h
@@ -13,8 +13,8 @@
 #include "irrString.h"

 #include "aabbox3d.h"

 #include "matrix4.h"

-#include "irrList.h"

 #include "IAttributes.h"

+#include <list>

 

 namespace irr

 {

@@ -24,7 +24,7 @@ namespace scene
 	class ISceneManager;

 

 	//! Typedef for list of scene nodes

-	typedef core::list<ISceneNode*> ISceneNodeList;

+	typedef std::list<ISceneNode*> ISceneNodeList;

 

 	//! Scene node interface.

 	/** A scene node is a node in the hierarchical scene graph. Every scene

@@ -81,7 +81,7 @@ namespace scene
 		{

 			if (IsVisible)

 			{

-				ISceneNodeList::Iterator it = Children.begin();

+				ISceneNodeList::iterator it = Children.begin();

 				for (; it != Children.end(); ++it)

 					(*it)->OnRegisterSceneNode();

 			}

@@ -103,7 +103,7 @@ namespace scene
 

 				// perform the post render process on all children

 

-				ISceneNodeList::Iterator it = Children.begin();

+				ISceneNodeList::iterator it = Children.begin();

 				for (; it != Children.end(); ++it)

 					(*it)->OnAnimate(timeMs);

 			}

@@ -289,7 +289,7 @@ namespace scene
 		e.g. because it couldn't be found in the children list. */

 		virtual bool removeChild(ISceneNode* child)

 		{

-			ISceneNodeList::Iterator it = Children.begin();

+			ISceneNodeList::iterator it = Children.begin();

 			for (; it != Children.end(); ++it)

 				if ((*it) == child)

 				{

@@ -309,7 +309,7 @@ namespace scene
 		*/

 		virtual void removeAll()

 		{

-			ISceneNodeList::Iterator it = Children.begin();

+			ISceneNodeList::iterator it = Children.begin();

 			for (; it != Children.end(); ++it)

 			{

 				(*it)->Parent = 0;

@@ -519,7 +519,7 @@ namespace scene
 

 		//! Returns a const reference to the list of all children.

 		/** \return The list of all children of this node. */

-		const core::list<ISceneNode*>& getChildren() const

+		const std::list<ISceneNode*>& getChildren() const

 		{

 			return Children;

 		}

@@ -611,7 +611,7 @@ namespace scene
 

 			// clone children

 

-			ISceneNodeList::Iterator it = toCopyFrom->Children.begin();

+			ISceneNodeList::iterator it = toCopyFrom->Children.begin();

 			for (; it != toCopyFrom->Children.end(); ++it)

 				(*it)->clone(this, newManager);

 		}

@@ -622,7 +622,7 @@ namespace scene
 		{

 			SceneManager = newManager;

 

-			ISceneNodeList::Iterator it = Children.begin();

+			ISceneNodeList::iterator it = Children.begin();

 			for (; it != Children.end(); ++it)

 				(*it)->setSceneManager(newManager);

 		}

@@ -646,7 +646,7 @@ namespace scene
 		ISceneNode* Parent;

 

 		//! List of all children of this node

-		core::list<ISceneNode*> Children;

+		std::list<ISceneNode*> Children;

 

 		//! Pointer to the scene manager

 		ISceneManager* SceneManager;

diff --git a/include/irrList.h b/include/irrList.h
deleted file mode 100644
index 27044a4..0000000
--- a/include/irrList.h
+++ /dev/null
@@ -1,414 +0,0 @@
-// Copyright (C) 2002-2012 Nikolaus Gebhardt

-// This file is part of the "Irrlicht Engine".

-// For conditions of distribution and use, see copyright notice in irrlicht.h

-

-#ifndef __IRR_LIST_H_INCLUDED__

-#define __IRR_LIST_H_INCLUDED__

-

-#include "irrTypes.h"

-#include "irrAllocator.h"

-#include "irrMath.h"

-

-namespace irr

-{

-namespace core

-{

-

-

-//! Doubly linked list template.

-template <class T>

-class list

-{

-private:

-

-	//! List element node with pointer to previous and next element in the list.

-	struct SKListNode

-	{

-		SKListNode(const T& e) : Next(0), Prev(0), Element(e) {}

-

-		SKListNode* Next;

-		SKListNode* Prev;

-		T Element;

-	};

-

-public:

-	class ConstIterator;

-

-	//! List iterator.

-	class Iterator

-	{

-	public:

-		Iterator() : Current(0) {}

-

-		Iterator& operator ++()    { Current = Current->Next; return *this; }

-		Iterator& operator --()    { Current = Current->Prev; return *this; }

-		Iterator  operator ++(s32) { Iterator tmp = *this; Current = Current->Next; return tmp; }

-		Iterator  operator --(s32) { Iterator tmp = *this; Current = Current->Prev; return tmp; }

-

-		Iterator& operator +=(s32 num)

-		{

-			if(num > 0)

-			{

-				while (num-- && this->Current != 0) ++(*this);

-			}

-			else

-			{

-				while(num++ && this->Current != 0) --(*this);

-			}

-			return *this;

-		}

-

-		Iterator  operator + (s32 num) const { Iterator tmp = *this; return tmp += num; }

-		Iterator& operator -=(s32 num) { return (*this)+=(-num); }

-		Iterator  operator - (s32 num) const { return (*this)+ (-num); }

-

-		bool operator ==(const Iterator&      other) const { return Current == other.Current; }

-		bool operator !=(const Iterator&      other) const { return Current != other.Current; }

-		bool operator ==(const ConstIterator& other) const { return Current == other.Current; }

-		bool operator !=(const ConstIterator& other) const { return Current != other.Current; }

-

-		T & operator * () { return Current->Element; }

-		T * operator ->() { return &Current->Element; }

-

-	private:

-		explicit Iterator(SKListNode* begin) : Current(begin) {}

-

-		SKListNode* Current;

-

-		friend class list<T>;

-		friend class ConstIterator;

-	};

-

-	//! List iterator for const access.

-	class ConstIterator

-	{

-	public:

-

-		ConstIterator() : Current(0) {}

-		ConstIterator(const Iterator& iter) : Current(iter.Current)  {}

-

-		ConstIterator& operator ++()    { Current = Current->Next; return *this; }

-		ConstIterator& operator --()    { Current = Current->Prev; return *this; }

-		ConstIterator  operator ++(s32) { ConstIterator tmp = *this; Current = Current->Next; return tmp; }

-		ConstIterator  operator --(s32) { ConstIterator tmp = *this; Current = Current->Prev; return tmp; }

-

-		ConstIterator& operator +=(s32 num)

-		{

-			if(num > 0)

-			{

-				while(num-- && this->Current != 0) ++(*this);

-			}

-			else

-			{

-				while(num++ && this->Current != 0) --(*this);

-			}

-			return *this;

-		}

-

-		ConstIterator  operator + (s32 num) const { ConstIterator tmp = *this; return tmp += num; }

-		ConstIterator& operator -=(s32 num) { return (*this)+=(-num); }

-		ConstIterator  operator - (s32 num) const { return (*this)+ (-num); }

-

-		bool operator ==(const ConstIterator& other) const { return Current == other.Current; }

-		bool operator !=(const ConstIterator& other) const { return Current != other.Current; }

-		bool operator ==(const Iterator&      other) const { return Current == other.Current; }

-		bool operator !=(const Iterator&      other) const { return Current != other.Current; }

-

-		const T & operator * () { return Current->Element; }

-		const T * operator ->() { return &Current->Element; }

-

-		ConstIterator & operator =(const Iterator & iterator) { Current = iterator.Current; return *this; }

-

-	private:

-		explicit ConstIterator(SKListNode* begin) : Current(begin) {}

-

-		SKListNode* Current;

-

-		friend class Iterator;

-		friend class list<T>;

-	};

-

-	//! Default constructor for empty list.

-	list()

-		: First(0), Last(0), Size(0) {}

-

-

-	//! Copy constructor.

-	list(const list<T>& other) : First(0), Last(0), Size(0)

-	{

-		*this = other;

-	}

-

-

-	//! Destructor

-	~list()

-	{

-		clear();

-	}

-

-

-	//! Assignment operator

-	void operator=(const list<T>& other)

-	{

-		if(&other == this)

-		{

-			return;

-		}

-

-		clear();

-

-		SKListNode* node = other.First;

-		while(node)

-		{

-			push_back(node->Element);

-			node = node->Next;

-		}

-	}

-

-

-	//! Returns amount of elements in list.

-	/** \return Amount of elements in the list. */

-	u32 size() const

-	{

-		return Size;

-	}

-	u32 getSize() const

-	{

-		return Size;

-	}

-

-

-	//! Clears the list, deletes all elements in the list.

-	/** All existing iterators of this list will be invalid. */

-	void clear()

-	{

-		while(First)

-		{

-			SKListNode * next = First->Next;

-			allocator.destruct(First);

-			allocator.deallocate(First);

-			First = next;

-		}

-

-		//First = 0; handled by loop

-		Last = 0;

-		Size = 0;

-	}

-

-

-	//! Checks for empty list.

-	/** \return True if the list is empty and false if not. */

-	bool empty() const

-	{

-		return (First == 0);

-	}

-

-

-	//! Adds an element at the end of the list.

-	/** \param element Element to add to the list. */

-	void push_back(const T& element)

-	{

-		SKListNode* node = allocator.allocate(1);

-		allocator.construct(node, element);

-

-		++Size;

-

-		if (First == 0)

-			First = node;

-

-		node->Prev = Last;

-

-		if (Last != 0)

-			Last->Next = node;

-

-		Last = node;

-	}

-

-

-	//! Adds an element at the begin of the list.

-	/** \param element: Element to add to the list. */

-	void push_front(const T& element)

-	{

-		SKListNode* node = allocator.allocate(1);

-		allocator.construct(node, element);

-

-		++Size;

-

-		if (First == 0)

-		{

-			Last = node;

-			First = node;

-		}

-		else

-		{

-			node->Next = First;

-			First->Prev = node;

-			First = node;

-		}

-	}

-

-

-	//! Gets first node.

-	/** \return A list iterator pointing to the beginning of the list. */

-	Iterator begin()

-	{

-		return Iterator(First);

-	}

-

-

-	//! Gets first node.

-	/** \return A const list iterator pointing to the beginning of the list. */

-	ConstIterator begin() const

-	{

-		return ConstIterator(First);

-	}

-

-

-	//! Gets end node.

-	/** \return List iterator pointing to null. */

-	Iterator end()

-	{

-		return Iterator(0);

-	}

-

-

-	//! Gets end node.

-	/** \return Const list iterator pointing to null. */

-	ConstIterator end() const

-	{

-		return ConstIterator(0);

-	}

-

-

-	//! Gets last element.

-	/** \return List iterator pointing to the last element of the list. */

-	Iterator getLast()

-	{

-		return Iterator(Last);

-	}

-

-

-	//! Gets last element.

-	/** \return Const list iterator pointing to the last element of the list. */

-	ConstIterator getLast() const

-	{

-		return ConstIterator(Last);

-	}

-

-

-	//! Inserts an element after an element.

-	/** \param it Iterator pointing to element after which the new element

-	should be inserted.

-	\param element The new element to be inserted into the list.

-	*/

-	void insert_after(const Iterator& it, const T& element)

-	{

-		SKListNode* node = allocator.allocate(1);

-		allocator.construct(node, element);

-

-		node->Next = it.Current->Next;

-

-		if (it.Current->Next)

-			it.Current->Next->Prev = node;

-

-		node->Prev = it.Current;

-		it.Current->Next = node;

-		++Size;

-

-		if (it.Current == Last)

-			Last = node;

-	}

-

-

-	//! Inserts an element before an element.

-	/** \param it Iterator pointing to element before which the new element

-	should be inserted.

-	\param element The new element to be inserted into the list.

-	*/

-	void insert_before(const Iterator& it, const T& element)

-	{

-		SKListNode* node = allocator.allocate(1);

-		allocator.construct(node, element);

-

-		node->Prev = it.Current->Prev;

-

-		if (it.Current->Prev)

-			it.Current->Prev->Next = node;

-

-		node->Next = it.Current;

-		it.Current->Prev = node;

-		++Size;

-

-		if (it.Current == First)

-			First = node;

-	}

-

-

-	//! Erases an element.

-	/** \param it Iterator pointing to the element which shall be erased.

-	\return Iterator pointing to next element. */

-	Iterator erase(Iterator& it)

-	{

-		// suggest changing this to a const Iterator& and

-		// working around line: it.Current = 0 (possibly with a mutable, or just let it be garbage?)

-

-		Iterator returnIterator(it);

-		++returnIterator;

-

-		if(it.Current == First)

-		{

-			First = it.Current->Next;

-		}

-		else

-		{

-			it.Current->Prev->Next = it.Current->Next;

-		}

-

-		if(it.Current == Last)

-		{

-			Last = it.Current->Prev;

-		}

-		else

-		{

-			it.Current->Next->Prev = it.Current->Prev;

-		}

-

-		allocator.destruct(it.Current);

-		allocator.deallocate(it.Current);

-		it.Current = 0;

-		--Size;

-

-		return returnIterator;

-	}

-

-	//! Swap the content of this list container with the content of another list

-	/** Afterward this object will contain the content of the other object and the other

-	object will contain the content of this object. Iterators will afterward be valid for

-	the swapped object.

-	\param other Swap content with this object */

-	void swap(list<T>& other)

-	{

-		core::swap(First, other.First);

-		core::swap(Last, other.Last);

-		core::swap(Size, other.Size);

-		core::swap(allocator, other.allocator); // memory is still released by the same allocator used for allocation

-	}

-

-	typedef T value_type;

-	typedef u32 size_type;

-

-private:

-

-	SKListNode* First;

-	SKListNode* Last;

-	u32 Size;

-	irrAllocator<SKListNode> allocator;

-

-};

-

-

-} // end namespace core

-}// end namespace irr

-

-#endif

-

diff --git a/include/irrlicht.h b/include/irrlicht.h
index 9786436..4773e43 100644
--- a/include/irrlicht.h
+++ b/include/irrlicht.h
@@ -111,7 +111,6 @@
 #include "IRandomizer.h"

 #include "IRenderTarget.h"

 #include "IrrlichtDevice.h"

-#include "irrList.h"

 #include "irrMath.h"

 #include "irrString.h"

 #include "irrTypes.h"

diff --git a/source/Irrlicht/CBoneSceneNode.cpp b/source/Irrlicht/CBoneSceneNode.cpp
index ccce982..04ef8c7 100644
--- a/source/Irrlicht/CBoneSceneNode.cpp
+++ b/source/Irrlicht/CBoneSceneNode.cpp
@@ -71,7 +71,7 @@ void CBoneSceneNode::OnAnimate(u32 timeMs)
 		//updateAbsolutePosition();

 

 		// perform the post render process on all children

-		ISceneNodeList::Iterator it = Children.begin();

+		ISceneNodeList::iterator it = Children.begin();

 		for (; it != Children.end(); ++it)

 			(*it)->OnAnimate(timeMs);

 	}

@@ -82,7 +82,7 @@ void CBoneSceneNode::helper_updateAbsolutePositionOfAllChildren(ISceneNode *Node
 {

 	Node->updateAbsolutePosition();

 

-	ISceneNodeList::ConstIterator it = Node->getChildren().begin();

+	ISceneNodeList::const_iterator it = Node->getChildren().begin();

 	for (; it != Node->getChildren().end(); ++it)

 	{

 		helper_updateAbsolutePositionOfAllChildren( (*it) );

diff --git a/source/Irrlicht/CFileSystem.cpp b/source/Irrlicht/CFileSystem.cpp
index e1d0248..2adbe63 100644
--- a/source/Irrlicht/CFileSystem.cpp
+++ b/source/Irrlicht/CFileSystem.cpp
@@ -16,7 +16,7 @@
 #include "CMemoryFile.h"

 #include "CLimitReadFile.h"

 #include "CWriteFile.h"

-#include "irrList.h"

+#include <list>

 

 #if defined (__STRICT_ANSI__)

     #error Compiling with __STRICT_ANSI__ not supported. g++ does set this when compiling with -std=c++11 or -std=c++0x. Use instead -std=gnu++11 or -std=gnu++0x. Or use -U__STRICT_ANSI__ to disable strict ansi.

@@ -714,11 +714,10 @@ path CFileSystem::getRelativeFilename(const path& filename, const path& director
 	io::path path1, file, ext;

 	core::splitFilename(getAbsolutePath(filename), &path1, &file, &ext);

 	io::path path2(getAbsolutePath(directory));

-	core::list<io::path> list1, list2;

+	std::list<io::path> list1, list2;

 	path1.split(list1, _IRR_TEXT("/\\"), 2);

 	path2.split(list2, _IRR_TEXT("/\\"), 2);

-	u32 i=0;

-	core::list<io::path>::ConstIterator it1,it2;

+	std::list<io::path>::const_iterator it1,it2;

 	it1=list1.begin();

 	it2=list2.begin();

 

@@ -742,19 +741,19 @@ path CFileSystem::getRelativeFilename(const path& filename, const path& director
 	#endif

 

 

-	for (; i<list1.size() && i<list2.size()

+	for (; it1 != list1.end() && it2 != list2.end()

 #if defined (_IRR_WINDOWS_API_)

 		&& (io::path(*it1).make_lower()==io::path(*it2).make_lower())

 #else

 		&& (*it1==*it2)

 #endif

-		; ++i)

+		;)

 	{

 		++it1;

 		++it2;

 	}

 	path1=_IRR_TEXT("");

-	for (; i<list2.size(); ++i)

+	for (; it2 != list2.end(); ++it2)

 		path1 += _IRR_TEXT("../");

 	while (it1 != list1.end())

 	{

diff --git a/source/Irrlicht/CGUIEnvironment.cpp b/source/Irrlicht/CGUIEnvironment.cpp
index 040cbff..0a12af3 100644
--- a/source/Irrlicht/CGUIEnvironment.cpp
+++ b/source/Irrlicht/CGUIEnvironment.cpp
@@ -387,11 +387,7 @@ void CGUIEnvironment::clear()
 		HoveredNoSubelement = 0;

 	}

 

-	// get the root's children in case the root changes in future

-	const core::list<IGUIElement*>& children = getRootGUIElement()->getChildren();

-

-	while (!children.empty())

-		(*children.getLast())->remove();

+	getRootGUIElement()->removeAllChildren();

 }

 

 

diff --git a/source/Irrlicht/CGUIModalScreen.cpp b/source/Irrlicht/CGUIModalScreen.cpp
index ce8b32e..5318d55 100644
--- a/source/Irrlicht/CGUIModalScreen.cpp
+++ b/source/Irrlicht/CGUIModalScreen.cpp
@@ -57,17 +57,12 @@ bool CGUIModalScreen::isVisible() const
     }

 

     // any child visible?

-    bool visible = false;

-    core::list<IGUIElement*>::ConstIterator it = Children.begin();

-    for (; it != Children.end(); ++it)

+    for (const auto& child : Children)

     {

-        if ( (*it)->isVisible() )

-        {

-            visible = true;

-            break;

-        }

+        if ( child->isVisible() )

+            return true;

     }

-    return visible;

+    return false;

 }

 

 bool CGUIModalScreen::isPointInside(const core::position2d<s32>& point) const

@@ -98,7 +93,7 @@ bool CGUIModalScreen::OnEvent(const SEvent& event)
 			if ( !canTakeFocus(event.GUIEvent.Caller))

 			{

 				if ( !Children.empty() )

-					Environment->setFocus(*(Children.begin()));

+					Environment->setFocus(Children.front());

 				else

 					Environment->setFocus(this);

 			}

@@ -110,7 +105,7 @@ bool CGUIModalScreen::OnEvent(const SEvent& event)
             	if ( isMyChild(event.GUIEvent.Caller) )

 				{

 					if ( !Children.empty() )

-						Environment->setFocus(*(Children.begin()));

+						Environment->setFocus(Children.front());

 					else

 						Environment->setFocus(this);

 				}

@@ -171,15 +166,14 @@ void CGUIModalScreen::draw()
 	u32 now = os::Timer::getTime();

 	if (BlinkMode && now - MouseDownTime < 300 && (now / 70)%2)

 	{

-		core::list<IGUIElement*>::Iterator it = Children.begin();

 		core::rect<s32> r;

 		video::SColor c = Environment->getSkin()->getColor(gui::EGDC_3D_HIGH_LIGHT);

 

-		for (; it != Children.end(); ++it)

+		for (auto child : Children)

 		{

-			if ((*it)->isVisible())

+			if (child->isVisible())

 			{

-				r = (*it)->getAbsolutePosition();

+				r = child->getAbsolutePosition();

 				r.LowerRightCorner.X += 1;

 				r.LowerRightCorner.Y += 1;

 				r.UpperLeftCorner.X -= 1;

diff --git a/source/Irrlicht/CGUIToolBar.cpp b/source/Irrlicht/CGUIToolBar.cpp
index 2f4bf4e..6d4cf93 100644
--- a/source/Irrlicht/CGUIToolBar.cpp
+++ b/source/Irrlicht/CGUIToolBar.cpp
@@ -34,11 +34,8 @@ CGUIToolBar::CGUIToolBar(IGUIEnvironment* environment, IGUIElement* parent, s32
 		parentwidth = Parent->getAbsolutePosition().getWidth();

 		s32 parentheight = Parent->getAbsolutePosition().getHeight();

 

-		const core::list<IGUIElement*>& children = parent->getChildren();

-		core::list<IGUIElement*>::ConstIterator it = children.begin();

-		for (; it != children.end(); ++it)

+		for (const auto& e : parent->getChildren())

 		{

-			const IGUIElement* e = *it;

 			if (	e->hasType(EGUIET_CONTEXT_MENU) 

 				||	e->hasType(EGUIET_MENU) 

 				||	e->hasType(EGUIET_TOOL_BAR)  )

diff --git a/source/Irrlicht/CGUITreeView.cpp b/source/Irrlicht/CGUITreeView.cpp
index b348a79..5c082e0 100644
--- a/source/Irrlicht/CGUITreeView.cpp
+++ b/source/Irrlicht/CGUITreeView.cpp
@@ -66,11 +66,10 @@ void CGUITreeViewNode::setIcon( const wchar_t* icon )
 

 void CGUITreeViewNode::clearChildren()

 {

-	core::list<CGUITreeViewNode*>::Iterator	it;

-

-	for( it = Children.begin(); it != Children.end(); it++ )

+	for (auto child : Children)

 	{

-		( *it )->drop();

+		child->Parent = nullptr;

+		child->drop();

 	}

 	Children.clear();

 }

@@ -83,9 +82,8 @@ IGUITreeViewNode* CGUITreeViewNode::addChildBack(
 	void*					data /*= 0*/,

 	IReferenceCounted*			data2 /*= 0*/ )

 {

-	CGUITreeViewNode*	newChild = new CGUITreeViewNode( Owner, this );

-

-	Children.push_back( newChild );

+	auto newChild = new CGUITreeViewNode( Owner, this );

+	newChild->ParentPos = Children.insert(Children.end(), newChild);

 	newChild->Text = text;

 	newChild->Icon = icon;

 	newChild->ImageIndex = imageIndex;

@@ -107,9 +105,8 @@ IGUITreeViewNode* CGUITreeViewNode::addChildFront(
 	void*					data /*= 0*/,

 	IReferenceCounted*			data2 /*= 0*/ )

 {

-	CGUITreeViewNode*	newChild = new CGUITreeViewNode( Owner, this );

-

-	Children.push_front( newChild );

+	auto newChild = new CGUITreeViewNode( Owner, this );

+	newChild->ParentPos = Children.insert(Children.begin(), newChild);

 	newChild->Text = text;

 	newChild->Icon = icon;

 	newChild->ImageIndex = imageIndex;

@@ -124,7 +121,7 @@ IGUITreeViewNode* CGUITreeViewNode::addChildFront(
 }

 

 IGUITreeViewNode* CGUITreeViewNode::insertChildAfter(

-	IGUITreeViewNode*	other,

+	IGUITreeViewNode*	iother,

 	const wchar_t*		text,

 	const wchar_t*		icon /*= 0*/,

 	s32					imageIndex /*= -1*/,

@@ -132,33 +129,27 @@ IGUITreeViewNode* CGUITreeViewNode::insertChildAfter(
 	void*					data /*= 0*/,

 	IReferenceCounted*			data2/* = 0*/ )

 {

-	core::list<CGUITreeViewNode*>::Iterator	itOther;

-	CGUITreeViewNode*									newChild = 0;

-

-	for( itOther = Children.begin(); itOther != Children.end(); itOther++ )

-	{

-		if( other == *itOther )

-		{

-			newChild = new CGUITreeViewNode( Owner, this );

-			newChild->Text = text;

-			newChild->Icon = icon;

-			newChild->ImageIndex = imageIndex;

-			newChild->SelectedImageIndex = selectedImageIndex;

-			newChild->Data = data;

-			newChild->Data2 = data2;

-			if( data2 )

-			{

-				data2->grab();

-			}

-			Children.insert_after( itOther, newChild );

-			break;

-		}

-	}

+	// This cast is needed to access the ParentPos member of `other`.

+	// The abstraction was already broken, because Children is a list of

+	// CGUITreeViewNode, not IGUITreeViewNode. The existing code was

+	// implicitly casting through pointer comparison.

+	auto other = static_cast<CGUITreeViewNode*>(iother);

+	assert(other->Parent == this);

+	auto newChild = new CGUITreeViewNode( Owner, this );

+	newChild->ParentPos = Children.insert(std::next(other->ParentPos), newChild);

+	newChild->Text = text;

+	newChild->Icon = icon;

+	newChild->ImageIndex = imageIndex;

+	newChild->SelectedImageIndex = selectedImageIndex;

+	newChild->Data = data;

+	newChild->Data2 = data2;

+	if( data2 )

+		data2->grab();

 	return newChild;

 }

 

 IGUITreeViewNode* CGUITreeViewNode::insertChildBefore(

-	IGUITreeViewNode*	other,

+	IGUITreeViewNode*	iother,

 	const wchar_t*		text,

 	const wchar_t*		icon /*= 0*/,

 	s32					imageIndex /*= -1*/,

@@ -166,28 +157,18 @@ IGUITreeViewNode* CGUITreeViewNode::insertChildBefore(
 	void*					data /*= 0*/,

 	IReferenceCounted*			data2/* = 0*/ )

 {

-	core::list<CGUITreeViewNode*>::Iterator	itOther;

-	CGUITreeViewNode*									newChild = 0;

-

-	for( itOther = Children.begin(); itOther != Children.end(); itOther++ )

-	{

-		if( other == *itOther )

-		{

-			newChild = new CGUITreeViewNode( Owner, this );

-			newChild->Text = text;

-			newChild->Icon = icon;

-			newChild->ImageIndex = imageIndex;

-			newChild->SelectedImageIndex = selectedImageIndex;

-			newChild->Data = data;

-			newChild->Data2 = data2;

-			if( data2 )

-			{

-				data2->grab();

-			}

-			Children.insert_before( itOther, newChild );

-			break;

-		}

-	}

+	auto other = static_cast<CGUITreeViewNode*>(iother);

+	assert(other->Parent == this);

+	auto newChild = new CGUITreeViewNode( Owner, this );

+	newChild->ParentPos = Children.insert(other->ParentPos, newChild);

+	newChild->Text = text;

+	newChild->Icon = icon;

+	newChild->ImageIndex = imageIndex;

+	newChild->SelectedImageIndex = selectedImageIndex;

+	newChild->Data = data;

+	newChild->Data2 = data2;

+	if( data2 )

+		data2->grab();

 	return newChild;

 }

 

@@ -199,7 +180,7 @@ IGUITreeViewNode* CGUITreeViewNode::getFirstChild() const
 	}

 	else

 	{

-		return *( Children.begin() );

+		return Children.front();

 	}

 }

 

@@ -211,54 +192,25 @@ IGUITreeViewNode* CGUITreeViewNode::getLastChild() const
 	}

 	else

 	{

-		return *( Children.getLast() );

+		return Children.back();

 	}

 }

 

 IGUITreeViewNode* CGUITreeViewNode::getPrevSibling() const

 {

-	core::list<CGUITreeViewNode*>::Iterator	itThis;

-	core::list<CGUITreeViewNode*>::Iterator	itOther;

-	CGUITreeViewNode*									other = 0;

-

-	if( Parent )

-	{

-		for( itThis = Parent->Children.begin(); itThis != Parent->Children.end(); itThis++ )

-		{

-			if( this == *itThis )

-			{

-				if( itThis != Parent->Children.begin() )

-				{

-					other = *itOther;

-				}

-				break;

-			}

-			itOther = itThis;

-		}

-	}

-	return other;

+	if (!Parent || ParentPos == Parent->Children.begin())

+		return nullptr;

+	return *std::prev(ParentPos);

 }

 

 IGUITreeViewNode* CGUITreeViewNode::getNextSibling() const

 {

-	core::list<CGUITreeViewNode*>::Iterator	itThis;

-	CGUITreeViewNode*									other = 0;

-

-	if( Parent )

-	{

-		for( itThis = Parent->Children.begin(); itThis != Parent->Children.end(); itThis++ )

-		{

-			if( this == *itThis )

-			{

-				if( itThis != Parent->Children.getLast() )

-				{

-					other = *( ++itThis );

-				}

-				break;

-			}

-		}

-	}

-	return other;

+	if (!Parent)

+		return nullptr;

+	auto nextIt = std::next(ParentPos);

+	if (nextIt == Parent->Children.end())

+		return nullptr;

+	return *nextIt;

 }

 

 IGUITreeViewNode* CGUITreeViewNode::getNextVisible() const

@@ -286,73 +238,40 @@ IGUITreeViewNode* CGUITreeViewNode::getNextVisible() const
 	return next;

 }

 

-bool CGUITreeViewNode::deleteChild( IGUITreeViewNode* child )

+bool CGUITreeViewNode::deleteChild( IGUITreeViewNode* ichild )

 {

-	core::list<CGUITreeViewNode*>::Iterator	itChild;

-	bool	deleted = false;

-

-	for( itChild = Children.begin(); itChild != Children.end(); itChild++ )

-	{

-		if( child == *itChild )

-		{

-			child->drop();

-			Children.erase( itChild );

-			deleted = true;

-			break;

-		}

-	}

-	return deleted;

+	auto child = static_cast<CGUITreeViewNode*>(ichild);

+	assert(child->Parent == this);

+	Children.erase(child->ParentPos);

+	child->Parent = nullptr;

+	child->drop();

+	return true;

 }

 

-bool CGUITreeViewNode::moveChildUp( IGUITreeViewNode* child )

+bool CGUITreeViewNode::moveChildUp( IGUITreeViewNode* ichild )

 {

-	core::list<CGUITreeViewNode*>::Iterator	itChild;

-	core::list<CGUITreeViewNode*>::Iterator	itOther;

-	CGUITreeViewNode*									nodeTmp;

-	bool													moved = false;

-

-	for( itChild = Children.begin(); itChild != Children.end(); itChild++ )

-	{

-		if( child == *itChild )

-		{

-			if( itChild != Children.begin() )

-			{

-				nodeTmp = *itChild;

-				*itChild = *itOther;

-				*itOther = nodeTmp;

-				moved = true;

-			}

-			break;

-		}

-		itOther = itChild;

-	}

-	return moved;

+	auto child = static_cast<CGUITreeViewNode*>(ichild);

+	assert(child->Parent == this);

+	if (child->ParentPos == Children.begin())

+		return false;

+	auto curPos = child->ParentPos;

+	auto prevPos = std::prev(child->ParentPos);

+	std::swap(*curPos, *prevPos);

+	std::swap((*curPos)->ParentPos, (*prevPos)->ParentPos);

+	return true;

 }

 

-bool CGUITreeViewNode::moveChildDown( IGUITreeViewNode* child )

+bool CGUITreeViewNode::moveChildDown( IGUITreeViewNode* ichild )

 {

-	core::list<CGUITreeViewNode*>::Iterator	itChild;

-	core::list<CGUITreeViewNode*>::Iterator	itOther;

-	CGUITreeViewNode*									nodeTmp;

-	bool													moved = false;

-

-	for( itChild = Children.begin(); itChild != Children.end(); itChild++ )

-	{

-		if( child == *itChild )

-		{

-			if( itChild != Children.getLast() )

-			{

-				itOther = itChild;

-				++itOther;

-				nodeTmp = *itChild;

-				*itChild = *itOther;

-				*itOther = nodeTmp;

-				moved = true;

-			}

-			break;

-		}

-	}

-	return moved;

+	auto child = static_cast<CGUITreeViewNode*>(ichild);

+	assert(child->Parent == this);

+	auto nextPos = std::next(child->ParentPos);

+	if (nextPos == Children.end())

+		return false;

+	auto curPos = child->ParentPos;

+	std::swap(*curPos, *nextPos);

+	std::swap((*curPos)->ParentPos, (*nextPos)->ParentPos);

+	return true;

 }

 

 void CGUITreeViewNode::setExpanded( bool expanded )

diff --git a/source/Irrlicht/CGUITreeView.h b/source/Irrlicht/CGUITreeView.h
index bdcf035..1c34eb5 100644
--- a/source/Irrlicht/CGUITreeView.h
+++ b/source/Irrlicht/CGUITreeView.h
@@ -5,7 +5,6 @@
 #define __C_GUI_TREE_VIEW_H_INCLUDED__

 

 #include "IGUITreeView.h"

-#include "irrList.h"

 

 

 namespace irr

@@ -93,7 +92,7 @@ namespace gui
 

 		//! returns the child item count

 		virtual u32 getChildCount() const _IRR_OVERRIDE_

-		{ return Children.getSize(); }

+		{ return Children.size(); }

 

 		//! removes all children (recursive) from this node

 		virtual void clearChildren() _IRR_OVERRIDE_;

@@ -231,7 +230,10 @@ namespace gui
 		void*				Data;

 		IReferenceCounted*		Data2;

 		bool				Expanded;

-		core::list<CGUITreeViewNode*>	Children;

+		std::list<CGUITreeViewNode*>	Children;

+		// Position of this node in Parent->Children.

+		// Only valid when Parent != NULL

+		std::list<CGUITreeViewNode*>::iterator ParentPos;

 	};

 

 

diff --git a/source/Irrlicht/CIrrDeviceOSX.mm b/source/Irrlicht/CIrrDeviceOSX.mm
index 066539c..eb3f816 100644
--- a/source/Irrlicht/CIrrDeviceOSX.mm
+++ b/source/Irrlicht/CIrrDeviceOSX.mm
@@ -14,7 +14,6 @@
 #include "CIrrDeviceOSX.h"
 
 #include "IEventReceiver.h"
-#include "irrList.h"
 #include "os.h"
 #include "CTimer.h"
 #include "irrString.h"
diff --git a/source/Irrlicht/CIrrDeviceSDL.cpp b/source/Irrlicht/CIrrDeviceSDL.cpp
index c66cfda..6a31ee7 100644
--- a/source/Irrlicht/CIrrDeviceSDL.cpp
+++ b/source/Irrlicht/CIrrDeviceSDL.cpp
@@ -8,7 +8,6 @@
 

 #include "CIrrDeviceSDL.h"

 #include "IEventReceiver.h"

-#include "irrList.h"

 #include "os.h"

 #include "CTimer.h"

 #include "irrString.h"

diff --git a/source/Irrlicht/CIrrDeviceWin32.cpp b/source/Irrlicht/CIrrDeviceWin32.cpp
index 0bb8c1f..0ea188b 100644
--- a/source/Irrlicht/CIrrDeviceWin32.cpp
+++ b/source/Irrlicht/CIrrDeviceWin32.cpp
@@ -12,7 +12,6 @@
 

 #include "CIrrDeviceWin32.h"

 #include "IEventReceiver.h"

-#include "irrList.h"

 #include "os.h"

 

 #include "CTimer.h"

diff --git a/source/Irrlicht/CSceneManager.cpp b/source/Irrlicht/CSceneManager.cpp
index e0a2084..0e49789 100644
--- a/source/Irrlicht/CSceneManager.cpp
+++ b/source/Irrlicht/CSceneManager.cpp
@@ -855,7 +855,7 @@ ISceneNode* CSceneManager::getSceneNodeFromName(const char* name, ISceneNode* st
 	ISceneNode* node = 0;

 

 	const ISceneNodeList& list = start->getChildren();

-	ISceneNodeList::ConstIterator it = list.begin();

+	ISceneNodeList::const_iterator it = list.begin();

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

 	{

 		node = getSceneNodeFromName(name, *it);

@@ -879,7 +879,7 @@ ISceneNode* CSceneManager::getSceneNodeFromId(s32 id, ISceneNode* start)
 	ISceneNode* node = 0;

 

 	const ISceneNodeList& list = start->getChildren();

-	ISceneNodeList::ConstIterator it = list.begin();

+	ISceneNodeList::const_iterator it = list.begin();

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

 	{

 		node = getSceneNodeFromId(id, *it);

@@ -903,7 +903,7 @@ ISceneNode* CSceneManager::getSceneNodeFromType(scene::ESCENE_NODE_TYPE type, IS
 	ISceneNode* node = 0;

 

 	const ISceneNodeList& list = start->getChildren();

-	ISceneNodeList::ConstIterator it = list.begin();

+	ISceneNodeList::const_iterator it = list.begin();

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

 	{

 		node = getSceneNodeFromType(type, *it);

@@ -925,7 +925,7 @@ void CSceneManager::getSceneNodesFromType(ESCENE_NODE_TYPE type, core::array<sce
 		outNodes.push_back(start);

 

 	const ISceneNodeList& list = start->getChildren();

-	ISceneNodeList::ConstIterator it = list.begin();

+	ISceneNodeList::const_iterator it = list.begin();

 

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

 	{