Iterators are pointers?
Author
Hi!
I have an STL linked list. I want to remove elements from random positions, but I want elements to know their own position, so they can also remove themselves from the list.
Is an iterator the way to go? For example, when I add a new element to the list, I can get its iterator from end()-1.
After removing elements from before this one, does the iterator still remain valid? Is an iterator like a pointer to the data rather than an index?
I know if I just stored the index, then it would not be.
Thanks.
Yes, iterators are what you need. However, the design implications of this are strong: you can only store an object inside a single list this way, and the object must be aware of this storage. Is this acceptable?
Quote:Original post by xDan
After removing elements from before this one, does the iterator still remain valid? Is an iterator like a pointer to the data rather than an index?
Quoted from http://www.sgi.com/tech/stl/List.html:
Lists have the important property that insertion and splicing do not invalidate iterators to list elements, and that even removal invalidates only the iterators that point to the elements that are removed. The ordering of iterators may be changed (that is, list<T>::iterator might have a different predecessor or successor after a list operation than it did before), but the iterators themselves will not be invalidated or made to point to different elements unless that invalidation or mutation is explicit.
Note that this does not apply to vectors, deques... only the list.
Author
Nice link, thanks.
ToohrVyk, I think this is acceptable. It's for a game decal system, with a maximum amount. After this, the first one added to the list is removed. Also a decal can be removed when it exceeds a distance from the camera. The list is only used by the decal class.
ToohrVyk, I think this is acceptable. It's for a game decal system, with a maximum amount. After this, the first one added to the list is removed. Also a decal can be removed when it exceeds a distance from the camera. The list is only used by the decal class.
If the removal of items is not performance sesitive (isn't done thousands of times per second), then why not just use remove_if to do this. Removing an element which matches the element you have / are is a common situation, and one of the only reasons you need to do things like "know" your position in a list is usually as a performance optimization (usually a performance optimization of relationship management or sorting).
Unless the decals have lifetimes, this is uneccessary. Your description of motivations suggests you are using these for things like bullet holes, meaning that holes stay there indefinitly. Since the oldest one is always the one that gets destroyed, all you need to do is your_list.pop_front(). No need to store an iterator to do that!
A minor point. Your thread title is "Iterators are pointers?". Actually it's the reverse. Iterators are a generalisation of pointers.
Σnigma
Σnigma
Quote:Original post by Xai
If the removal of items is not performance sesitive (isn't done thousands of times per second), then why not just use remove_if to do this. Removing an element which matches the element you have / are is a common situation, and one of the only reasons you need to do things like "know" your position in a list is usually as a performance optimization (usually a performance optimization of relationship management or sorting).
Seconded. Especially because of the use case that is described: instead of trying to remove each element as soon as it goes out of range, you can remove_if on all the out-of-range decals every frame. That also frees you up to consider other containers - since you also want to remove the first ("oldest") when adding something beyond a maximum size, you might want a std::deque for example. With care, you can even create a circular array class that handles it properly - something like (not tested! completely off the top of my head!)
template <typename T, unsigned int size>class CircularBufferWithRemovals { public: CircularBufferWithRemovals() : b(0, this), e(0, this) {} T& push(const T& thing) { storage[e] = thing; advance(e); if (e == b) { advance(b); } return storage[e]; } T pop() { T result = storage; advance(b); return result; } /*** THE INTERESTING PART :) ***/ template <typename Predicate> // Keep only those elements satisfying the Predicate. void filter(Predicate p) { e = std::remove_if(b, e, std::not1(p)); } struct iterator { unsigned int pos; CircularBufferWithRemovals* parent; // Hmm... these might need a bit more thought... unsigned correctness and all iterator& operator+=(int amount) { pos += amount; pos %= (size + 1); return *this; } iterator& operator-=(int amount) { return *this += -amount; } iterator& operator++() { return *this += 1; } iterator operator++(int) { iterator result(*this); ++(*this); return result; } iterator& operator--() { return (*this += size); } iterator operator--(int) { iterator result(*this); --(*this); return result; } iterator(unsigned int pos, CircularBufferWithRemovals* parent) : pos(pos), parent(parent) {} T& operator*() { return parent.storage[pos]; } }; iterator begin() { return b; } iterator end() { return e; } private: iterator b, e; // We need to waste one spot because otherwise begin==end when the buffer // is "full", and that messes up iterator loops etc. // I mentally tested this for size==1. size==0 is useless anyway ;) // If you're paranoid, you could maybe add a partial specialization to // disallow that? T storage[size + 1];};// Used something like this:class Decal { static CircularBufferWithRemovals<Decal, 512> manager; // other stuff Decal& create() { Decal d; return manager.push(d); } private: Decal();};CircularBufferWithRemovals<Decal, 512> Decal::manager;// somewhere in the codeDecal::manager.filter(mem_fun_ref(&Decal::isVisible)); // boost::lambda may help// if you need to pass arguments to that member function...
Author
Thanks all for the posts - i'm a little busy at the moment with other things but i've bookmarked this thread and will come back to it!
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
