C++: alternative to std::find

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.

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.

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();
}


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.

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;
};


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?

[font=courier new,courier,monospace]std::[/font][color=#000000]

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

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.

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.

Thanks for all the suggestions, I used the std::binary_search and that seems to have done the trick: the results are returned way more quickly than before.
Of course, if there are other improvements, like the cache-approach as ViperG mentioned, I will try that as well and see if there are even more benefits in terms of speed.

The dosomething() does not modifier the data. Here are some more details about the application I'm developing.

In practice, what I do is clicking on a head model (displayed in opengl), collecting the triangles hit with the mouse in a std::vector.

So, basically the vector holds a list of triangle indexes. Then, I sort and erase duplicates (because the user can obviously hit the same triangle more than once), and then, in the opengl main loop, I render the head model, using std::find (well, binary_search) to test if the triangle drawn is in that vector or not. If it is, it will get a red color, if not, a white.

That sounds like you may want some sort of space-partitioning system like an octtree. Then you can only iterate through the follicles that are nearby the picking ray.

Or just remove all the triangles from the original array and insert them into a "selected"-array. Then you first draw the normal array, and then the selected ones in red...

Typically, how big is LIMIT relative to follicleArray.size()?
My gut says that you should be using some other data structure for follicleArray than a vector, but would need to understand how follicleArray is used. Off the top of my head, if it needs to be ordered and you need to find stuff in it, yeah, use an std::map but if you are trying to find nearly all of the items, i.e. if LIMIT is close to the size of the array, then a map might be a bad idea.