Sign in to follow this  

iterating through vectors

This topic is 4743 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

I do it a lot. Forward and back. No only do I do it a lot, I examine a variable in each item in the vector for one reason or another. How slow and stupid is this? ex:
std::vector<CClass*> Vector;
std::vector<CClass*>::iterator my_iter;

for(my_iter = Vector.begin(); my_iter != Vector.end(); my_iter++)
{
  if((*my_iter)->someVar == someOtherVar)
  {
    DoSomeWork();
  }
}

What do you think?

Share this post


Link to post
Share on other sites
Might be worth looking at functors, for a number of reasons (Meyers Effective STL has the best section on this that I've read). Then you'd end up with something like this (if I haven't got any code wrong).



// Assuming checking ints, change as required (even template if you want)
class functor
{
functor(int checkVar) : checkVar_(checkVar) {}
void operator() (const CClass* &in)
{
if(in->someVar == checkVar_)
DoSomeWork();
}

private:
int checkVar_;
};

// Need to include <algorithm>

std::for_each(Vector.begin(), Vector.end(), functor(someOtherVar));






Jim.

Edit : Digging out the Meyer book - he cites 3 reasons for using algorithms :
Efficiency (for example, in your example you calculate Vector.end() every time you run through the loop, as opposed to once only)
Correctness (less likely to get errors with a library function)
Maintainability (working from a known vocabulary)

Share this post


Link to post
Share on other sites
Quote:
Original post by JimPrice
Might be worth looking at functors, for a number of reasons (Meyers Effective STL has the best section on this that I've read). Then you'd end up with something like this (if I haven't got any code wrong).

*** Source Snippet Removed ***

Jim.

Edit : Digging out the Meyer book - he cites 3 reasons for using algorithms :
Efficiency (for example, in your example you calculate Vector.end() every time you run through the loop, as opposed to once only)
Correctness (less likely to get errors with a library function)
Maintainability (working from a known vocabulary)


I'll have to look into that.

But how bad is iterating through a vector? Really bad? the ones I use arent that huge (yet).

Share this post


Link to post
Share on other sites
I'll be honest, I can't personally quantify what improvements you might make - and even Meyer, in the same article, pretty much says that the use of algorithms versus hand-crafted loops is situationally dependent - and in your example, it sounds like he'd probably hand-craft (to avoid the creation of a functor that ostensibly does very little).

The other efficiency considerations (and these are the ones that are noted as more important than just re-calculating Vector.end() each time) I suspect are more relevant to specific algoithms, as opposed to for_each. The interesting example is where he talks about how the STL algorithms are likely to be optimised for the container you are using - for example, a deque is likely to store it's data in one or more fixed size arrays - and therefore the STL can use this knowledge to use pointer-based traversal instead of iterator-based traversal. He quotes some (container-specific) implementations as being 20% faster than "normal" traversal.

Finally, I thought I'd add some links to Guru of the Week that deal with this. Firstly, a general examination of creation of temporaries using hand-crafted loops: GotW #3. And finally my favorite : creating mastermind using algorithms: GotW #41.

Jim.

Share this post


Link to post
Share on other sites
What about the find() method? Does that work on vectors? I was under the impression it didn't. I would think that would be a better way to do what I want.

Basically, I've got two vectors full of pointers to one of my own classes. I want to search one vector for an object that meets a certain criteria. Once I find that object, I want to add it to the second vector (I've just been using push_back()) and then remove it from the first. I'm using vectors instead of lists because I need the my_list[] syntax. I use an int to hold my current position in the list (for various reasons).

Share this post


Link to post
Share on other sites
Morning,

Vector has no find member function, but the algorithm functions work with all iterators. So you'd use something like this (off the top of my head, so no guarantees it will work)


#include <vector>
#include <algorithm>

// You said one of your own classes, so taking it literally
// - although the extension to polymorphism is obvious
class Base
{
//stuff
};

bool FindCorrectPointer(const Base* &in)
{
if(in->YesPlease)
return true;
return false;
}

int main()
{
typedef std::vector<Base*> MyTypedef;
typedef MyTypedef::iterator MyIterator;

MyTypedef myContainer1;
MyTypedef myContainer2;
MyIterator myIterator;

// This line becomes more complicated if you want to pass parameters to the search function
// Need to look up function adapters - like bind2nd
// Also note find_if only returns first occurrence
// - but you can get around this using a loop containing find_if that exits when it hits myContainer1.end()
myIterator = std::find_if(myContainer1, myContainer2, FindCorrectPointer());
// Check to see if this element existed
if(myIterator != myContainer1.end())
{
myContainer2.push_back(*myIterator);
// The erase function now points at the next element in the container
myIterator = myContainer1.erase(myIterator);
}
};







Benefits - if later on you decide to change to storage container, you can now do it just be changing the typedef statements at the beginning (no need to worry about [] and storing ints). The one thing you might want to change is the use of find - member functions (when present) are always preferred to algorithms, for the same reasons as mentioned previously (ie they are tailored to the underlying structure of the container).

HTH,
Jim.

Edit : loads of silly typos

Share this post


Link to post
Share on other sites
The main problem with using STL algorithms for what you want to do is that algorithms work over a range of items, completely. You want to find one value, copy it, remove it, and stop (right?).

See, the really nice thing about using STL algos instead of for loops is that they're more predictable... i.e. when you see a for loop, you have to go scan through its contents to see if there are any 'break's or any statements that affect the iterating variable.

OTOH, when you need those things you have to write a for loop.

Anyway, efficiency is not really your main worry, because erasing from vectors is damn slow... and how does that affect iterators? I know some operations invalidate iterators, but I'm not sure when or how. You should be fine though, since you don't use the iterator after you erase it.

If you gave a more specific description of what you're trying to accomplish overall, STL might be able to help you do it differently (i.e. if you maintained sorted vectors, you could use lower_bound(), or maybe [] syntax isn't so important after all and you can use std::set).

Share this post


Link to post
Share on other sites
Quote:

The main problem with using STL algorithms for what you want to do is that algorithms work over a range of items, completely. You want to find one value, copy it, remove it, and stop (right?).


Er - I don't think they do. The find and find_if algorithms stop when they hit first object found - otherwise they wouldn't be able to return an iterator (I suppose they could return a std::vector of iterators, for example, but I'm guessing they don't do this for exactly the reason you point out). That's why you have to write code like this:


std::vector<int> Vec;
std::vector<int>::iterator It;

// Possibly populate Vec

while(It != Vec.end())
{
It = std::find(Vec.begin(), Vec.end(), value);
if(It != Vec.end())
{
It->DoSomething;
// And you could use erase here, for example, because it returns an iterator to the next element of Vec
}
}



Here's a comparison of hand-crafted, algorithm and member function codes (pretty much taken from effective STL). Take this code:


set<int> s;
// Populate s with 1,000,000 ints

//Method 1:
set<int>::iterator i; // Have to define here so I can use i outside the loop
for(i = s.begin(); i != s.end(); ++i)
{
if(*i == 727)
break;
}

//Method 2:
set<int>::iterator i = std::find(s.begin(), s.end(), 727);

//Method 3:
set<int>::iterator i = s.find(727);



Method 1 : stops when it hits first 727 - so could loop once or a million times.
Method 2 : stops when it hits first 727 - so could loop once or a million times.
Method 3 : stops when it hits first 727 - but set is stored as a red-black tree, so at most loops about 40 times.

This is why member functions are preferred to algorithms - an algorithm has to be generic so it can work with any iterator-providing container, but a member function can be written to take advantage of the structure of the container.

OK - so this doesn't make a big difference with std::vector in these simple examples (unless the underlying implementation uses pointer-based traversal, as vectors are typically stored as a big array), but if there is a change in container type then this becomes relevant.

Quote:

OTOH, when you need those things you have to write a for loop.


No you don't - for the reasons mentioned above. But I do agree that choice of hand-crafted versus algorithm is situationally dependent - but it's not as clear cut as this.

Quote:

Anyway, efficiency is not really your main worry, because erasing from vectors is damn slow


This is a good point and is something I'd overlooked. Depending upon how frequently you're doing it a std::list might be more efficient.

Quote:

I know some operations invalidate iterators, but I'm not sure when or how.


Another reason for using algorithms, because they do know what's happening to the iterator.

Jim.

Share this post


Link to post
Share on other sites
it looks to me like you are using the wrong container for the job. if you are looping thruogh the container looking for a specific value frequently, you should be using either a std::set or a std::map. this is what these containers were designed for! each std::container has its own place and purpose, don't restrict yourself to only using vectors. i think i use almost all of the containers in my current project (deque,set,map,vector,list..) your code would turn to (something like) this:


std::set<int>::iterator it = my_set.find(_checkVar);

if(it != my_set.end())
{
DoSomeWork();
}






not only does this make your code cleaner and easier to write, but it also makes it faster. sorry if this was already suggested, im at work and could only skim through the thread.

[Edited by - graveyard filla on December 16, 2004 1:14:15 PM]

Share this post


Link to post
Share on other sites
Quote:
Original post by benutne
I do it a lot. Forward and back. No only do I do it a lot, I examine a variable in each item in the vector for one reason or another.

How slow and stupid is this?

ex:
*** Source Snippet Removed ***

What do you think?


Prefer ++iter to iter++, iter++ creates a temporary.

Share this post


Link to post
Share on other sites
i dont like iterators but i love vectors so when i need to accsess a variable pice of data i go like this

for exmp erase:

vector.erase(vector.begin()+X)

were x is the element you want
you can of course do this with other functions (anything that takes an iterator) and you can avoid al the iterator hastle. Its also more flexible because you use ints so you can put it in a for loop easily and whatever math you can do with ints you can do with that value.
its a good idea to sign X so that your not accessing the -4 vector of somthing accidently

Share this post


Link to post
Share on other sites
Quote:
Original post by JimPrice
Er - I don't think they do. The find and find_if algorithms stop when they hit first object found - otherwise they wouldn't be able to return an iterator


right. I was trying to think of how to use remove_if or for_each, but in his situation it was not wise. So I made an over-generalized statement.

Anyway, I'm not sure if the std::find() example you use is such a lovely thing. I had a situation very recently where I was doing a std::lower_bound() to look up values on a sorted vector... but then I started doing deletes on that vector, so changed it to a set. Well of course my performance sucked simply because lower_bound() doesn't work well on sets, and I'd forgotten to change it to the .find() version. If the performance hit had been more subtle, that could still be haunting my code. So anyway, point being, it's a double-edged sword.

Share this post


Link to post
Share on other sites
Quote:

So anyway, point being, it's a double-edged sword.


Yeah - fair point.

Algorithms : work for all containers, but sacrifice efficiency.
Member functions : don't work for all containers, but might get better efficiency for some containers.

Hence if you're changing containers, just changing a few typedefs at the beginning might not give you all you need....

Jim.

Share this post


Link to post
Share on other sites
Can you be more specific about what exactly you are scanning this vector for? Is it positional information, state information (dead vs. alive) etc?

I assume that whatever variable you are checking must be dynamically updated every frame. I would think that if this were the case, it would be fairly easy to create a different data structure to keep these in. Why do you need to copy them to a second vector? If you are content with scanning the first vector every frame then you are not gaining anything by creating a second vector of only the interesting objects. You are only doing more work. Does that make sense?

Share this post


Link to post
Share on other sites

This topic is 4743 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.

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this