# C++: alternative to std::find

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

## Recommended Posts

I need to search into a std::vector<int>, with a size of about 20000. The search needs to be done in opengl-application main loop, and it's extremely slow.
This is my code:

 std::vector<int> folliclesArray; for (int i=0; i<LIMIT; i++) { iter = std::find(folliclesArray.begin(), folliclesArray.end(), i); if (iter!=folliclesArray.end()) dosomething(); } 

Please tell me there are alternatives to to this search faster. I've read that std::map would allow to improve perfomances, but didn't understand how to implement that.
Or, would a simple dynamic array be faster than a std::vector ?

Thanks

##### Share on other sites
Do you know anything about the contents of the array? Is it sorted? std::vector and a manually managed dynamic array will have almost the same performance in release mode. There may be additional overhead in a debug build, but that overhead is generally due to checks that are appropriate for debug execution.

##### Share on other sites
Hi SiCrane, yes the vector content is sorted. I modified the OP code so that maybe it's more understandable what I'm trying to do.

##### Share on other sites
Generally speaking, it's ill-advised to do any searches or in some cases sorts in a realtime application (such as a opengl application where you have a desired framerate)

When you hit an array or vector of that size, it will simply take to long to iterate through it every loop to do a search.

So i would suspect you have a design issue rather than looking for a programming solution via alternative method.

Some of the things you need to look at when iterating through alot of elements:

1) how often does this vector change size or sorted (gets re-indexed)?
2) Can you find what you are looking for once, then keep track of that element's index (inserts or deletes after the index are irrelevant, it's only changes < the index)? aka caching the results...
3) do you have to search and iterate every single loop? would every other loop suffice?
4) since your vector is sorted a binary search will be as fast as a map.

I like to deal with vectors almost exclusively and I do everything in my power to reduce the amount of searches and sorts that I possibly can.

Here is a small sample code that might assist you (this is not my code):

 int value_to_find; vector<int> cont; // main container map<int, size_t> contPos; // position cache // first see if the value is in cache map<int, size_t>::const_iterator foundCache = contPos.find(value_to_find); if (foundCache != contPos.end()) { do_this(); } // not in cache, now do brute force search vector<int>::const_iterator found = cont.find(value_to_find); if (found != cont.end()) { // cache the value with its position contPos[value_to_find] = found - cont.begin(); do_this(); } else { // in neither do_that(); } 

##### Share on other sites
In this case, it'd probably just be easiest, instead of searching from the beginning each time, set iter to begin() once, and search from iter to end. If your vector is already sorted, this would prevent you from searching the whole thing every single time. Probably use std::lower_bound for search instead as well.

##### Share on other sites
It's also worth ensuring that you have the debugging features of your C++ library disabled. For Visual C++, set _SECURE_SCL=0 and ensure _HAS_ITERATOR_DEBUGGING isn't defined.

Edited to add: there might be a way of avoiding the search entirely. How do you know which values to search for? Can you rearrange your algorithm to know about indices in to the vector/array, rather than values that must be found?

Alternatively, do the ints in the vector have a high degree of contiguity? If so, you could perhaps reduce the number of elements (and therefore work needed to perform a search) by storing ranges? e.g.

 struct range { int first; int last; }; 

##### Share on other sites
This maybe a silly question, but if the vector (which is really an array) is sorted, why not do a binary search on the content you're looking for?

##### Share on other sites
[font=courier new,courier,monospace]std::[/font][color=#000000]

### [font=courier new,courier,monospace]binary_search[/font] ?

##### Share on other sites
Well at least Hodgman and ViperG (whose mentioning of this in his previous post I did not see the first time), have convinced me that I'm not crazy.

##### Share on other sites
Does "dosomething" modify the container? Is there a reason you are doing the same lookup LIMIT times? There might be a higher level change you can make, if you were to give us more information.

Is there any patterns you can take advantage of in your follicles vector? As edd[sup]2[/sup] shows, if it consists of contiguous chunks you could model it as ranges. If it has lots of duplication, then some kind of run length encoding storing (value, count) might be more efficient.

1. 1
2. 2
Rutin
21
3. 3
4. 4
A4L
15
5. 5
khawk
14

• 13
• 26
• 10
• 11
• 9
• ### Forum Statistics

• Total Topics
633737
• Total Posts
3013609
×