Jump to content
  • Advertisement
Sign in to follow this  
xDan

Iterators are pointers?

This topic is 4353 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

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.

Share this post


Link to post
Share on other sites
Advertisement
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?

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
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).

Share this post


Link to post
Share on other sites
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!

Share this post


Link to post
Share on other sites
A minor point. Your thread title is "Iterators are pointers?". Actually it's the reverse. Iterators are a generalisation of pointers.

Σnigma

Share this post


Link to post
Share on other sites
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 code
Decal::manager.filter(mem_fun_ref(&Decal::isVisible)); // boost::lambda may help
// if you need to pass arguments to that member function...

Share this post


Link to post
Share on other sites
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!

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!