C++ source code: in loop erase safe containers, skip list, and quad linked node
Update on 2011, Mar.6, changes:
- Bug fix.
Tested compilers:
- Microsoft Visual C++ VC 2008 Express
- MingW GCC 4.4.0 and 4.5.2
Who may interest in this article:
- If you are seeking for a solution to erase elements safely while iterating through a container in C++, this article is for you.
- If you are seeking for some interesting containers, such as skip list, skip list based map (dictionary), quad linked node, this article is for you.
- If you are creating a game scene graph or event dispatch/listener system (like the one in Flash Action Script 3), this article is for you.
1, Motivation
Every of us may have a lot of chance to remove an element from a container while iterating through the container.
The pseudo code may look like,
while(not reach the end) {
if(satisfyTheContion) {
remove(currentElement);
}
else {
iterate to next element
}
}
Apparently we can't simply implement the code as,
for(SomeIteratorType it = container.begin(); it != container.end(); ++it) {
if(satisfyTheContion) {
container.erase(it);
}
}
Or,
for(int i = 0; i < container.size(); ++i) {
if(satisfyTheContion) {
container.removeAtIndex(i);
}
}
All of those will crash the program because the removing action destroys the iterator (it or i).
A google of "c++ iterator erase loop safe" (no quote mark) will give some excellent solutions,
http://stackoverflow.com/questions/4175896/safe-way-to-continuously-erase-from-a-stdvector
http://stackoverflow.com/questions/596162/can-you-remove-elements-from-a-stdlist-while-iterating-through-it
The problem is, all solutions require that current iterator is known and manipulated directly. So all iterating loops have to be quite simple.
But the real life is not that simple. Most time we may not know current iterator.
For example, in a game scene graph, we iterate through all active entities and update their AI. And some of the AI decides to destroy some other entities, or just itself, from the scene graph. The container items are removed from a function which may be nine levels deep from where the iterating happens.
For another example, in an event listerner & dispatch system, we loop over a listerner list and send event to each listerner, some listerners need to remove themselves after processed the event.
All these kind of arbitrary element erasing during an iterating may cause crash because the erasing may happen far away from the loop and can't know the iterator.
2, Solution
The attached source code, gcontainer.h, have serveral containers that are "in loop erase safe".
All containers can guarantee:
- An iterator returned by function begin() or rbegin() is "in loop erase safe" (or safe deleting while iterating).
- Erasing any element will not invalidate any iterators that returned by function begin() or rbegin().
- The "in loop erase safe" iterator is still "in loop erase safe" after it is increased or decreased. (++ or --).
- If the iterating is forwarding, that's to say, from begin() to end(), or from rbegin() to rend(), use ++ operator, erasing any element will keep the iterating order correct. So erasing any element will not cause either processing one element for more than one time, or missing any element.
3, How
The mechanism behind this kind of safe iterator is GWiseIteratorRetainer. Each container has a retainer.
When any iterator is created, the iterator will add itself to the retainer.
When any iterator is destroyed, the iterator will remove itself from the retainer.
And most important, when any element is going to be erased, the retainer will enumerate all existing iterators, and if any iterator's data is same as the element being erased, the iterator will be adjusted back one step.
Because all containers are implemented with linked node, it's quite easy to check the node equivalence without really bothering the real data type that the containers are holding.
4, A brief documentation of all containers
Here is a very brief documentation of all containers. Only introduction, no API document. All containers exposes functions that quite similar with STL. So if you ever know std::list, std::map, etc, it's quite easy for you to just check each container's public functions to see how they work.
All containers are in namespace "cpgf".
Only the classes the name begins with "GWise" are "in loop erase safe".
GWiseList
template <typename ValueType, typename Deleter = GContainerDeleter_None<ValueType> >
class GWiseList;
Quite similar with std::list. No extra features except "in loop erase safe".
It's implemented using double linked list.
GWiseSkipList
template <typename ValueType, typename Comparer = std::less<ValueType>, typename Deleter = GContainerDeleter_None<ValueType> >
class GWiseSkipList;
A sorted list using the algorithm "skip list". It's "in loop erase safe" container. All elements in the list are always sorted using the Comparer functor.
So to use it, you must either provide a "<" operator to the ValueType (to use the default comparer) or provide a compare functor explicitly by yourself.
This skip list is self maintained, the max level will automatically grow when more items are added, so the performance will be always good no matter how many elements there are.
GWiseMap
template<typename KeyType, typename ValueType, typename KeyComparer = std::less<KeyType> >
class GWiseMap;
A sorted map based on GWiseSkipList. It's "in loop erase safe" container.
According to some very basic and rough test, this container is a litter faster than std::map (VC 2008 Express), but need to double verify.
GQuadNode
template <typename ValueType, typename Deleter = GContainerDeleter_None<ValueType> >
class GQuadNode;
NOT "in loop erase safe" container.
This container, and itself is a node too, is to implement a quad linked node.
Its most benefit is that the time complexity of insert/delete a child from its parent is always O(1). (See the setParentNode function).
And itself is partially (only partially) "in loop erase safe".
It needs eight pointers to store the links.
It's NOT recommended to use this container as a general container because it's too memory consuming.
If you want O(1) insert/delete children, just use a simpler double linked node.
But if you want to create an "in loop erase safe" scene graph, the wrapped GWiseQuadNode may be the first choice.
GWiseQuadNode
template <typename ValueType, typename Deleter = GContainerDeleter_None<ValueType> >
class GWiseQuadNode : public GQuadNode<ValueType, Deleter>;
A full "in loop erase safe" version of GQuadNode.
5, Notes:
- When operating on iterators, please always prefer to ++it/--it (preincrement and predecrement) to it++/it-- (postincrement and postdecrement) if the return value does not matter. The reason is that the post operation will cause a copy constructor and thus the new iterator need to attach to retainer, that will always cause compiler generate more and slower code.
- Though the containers expose a similar function set as STL, they are not 100% compatible with STL.
- reverse_iterator has no "base" iterator. So it's completely not compatible with STL reverse_iterator.
- Only the iterators returned by function begin() and rbegin() are "in loop erase safe", the others, such as the ones returned by erase(), are not. That's to avoid unnecessary performance overhead.
- Use the code on your own risk. Though some test cases were written to test the code, it's not guaranteed all code is covered. If you find any bug, just let me know.
6, License:
Apache License 2.0
http://www.apache.org/licenses/LICENSE-2.0.html
However, if you need a different license, just contact the original author, with the information that: who are you, how do you want to use of the code, what license would you like, and then I will decide to or not to give you a suitable license.