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();
}
}
iterating through vectors
Author
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:
What do you think?
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).
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)
// 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)
Author
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).
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.
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.
Author
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).
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).
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)
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
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 obviousclass 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
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).
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).
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 Vecwhile(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 loopfor(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.
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:
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]
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]
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.
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
