STL question - does sorting speed up find() for vector?

[boltar2003]

Hi

I have a vector containing an list of integers I need to search for. I'm
not sure how the find() algorithm works internally so if I sort the vector
will it speed up find() or should I not bother? Does the same apply to a
list?

Thanks

B2003

 

[Neelesh]

Hi

I have a vector containing an list of integers I need to search for. I'm
not sure how the find() algorithm works internally so if I sort the vector
will it speed up find() or should I not bother? Does the same apply to a
list?

Exact definition of std::find() is left to the implementation. The
standard guanratees that this algorithm runs in worst case O(n), where
n is the length of the segment we wish to run the search on. However,
it does not guarantee any kind of "performance improvements" if the
container is sorted. Moreover,
(a) There is no way you can tell std::find that the vector is sorted.
(b) A vector is a "sequence" container, which means that the order of
the elements in it matters. You would end up in changing the order
while sorting, even if you don't intend that.

Finally, even if we assume that you use a sorting algorithm and then a
hypothetical "optimized" find() on the sorted container, you would end
up with complexity O(n log(n)) + O(log(n)), i.e. O(n log(n)), which is
not as better as O(n) guaranteed by std::find.

std::list is also a sequence container, and hence the same would apply
for std::list too.

Thanks.

 

[Christopher Dearlove]

Exact definition of std::find() is left to the implementation. The
standard guanratees that this algorithm runs in worst case O(n), where
n is the length of the segment we wish to run the search on. However,
it does not guarantee any kind of "performance improvements" if the
container is sorted.

True. But if the container is sorted, and you know it, then don't use
std::find, use (depending on exactly what you want to know)
std::binary_search, std::lower_bound, std::upper_bound or
std::equal_range.

Finally, even if we assume that you use a sorting algorithm and then a
hypothetical "optimized" find() on the sorted container, you would end
up with complexity O(n log(n)) + O(log(n)), i.e. O(n log(n)), which is
not as better as O(n) guaranteed by std::find.

Thus sorting to improve a single search is a bad idea. But if you are
searching the same container, without changing it, many times, it may
be worthwhile. As may in some cases using a set or multiset (or map
or multimap). Or if you have them, their unordered (hash) equivalents.

Of course this is subject to the usual "premature optimization" warning,
especially if the container is small.

 

[guy.tristram]

Hi

I have a vector containing an list of integers I need to search for. I'm
not sure how the find() algorithm works internally so if I sort the vector
will it speed up find() or should I not bother? Does the same apply to a
list?

find() can't take advantage of a sorted vector, but binary_search()
does (the vector *must* be sorted first). Yes, you should bother if
you're going to search the vector many times. You can use the same
function with a list, but the gains would be negligable (or negative)
because list iterators are not random access.

HTH - Guy