Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

What algorithm is behind STL's find?

I just created a custom finding function for strings in a map. I developed some kind of the linear search algorithm (which I found out later) and was not satisfied with the speed of the function. So I searched for a faster function and found map's own function: map::find.

This was incredibly faster than the linear algorithm I was using.

In another example STL's function find was also much faster than another linear function I am using.

But how is this possible? If you use the binary search algorithm you need to sort the map first which would take (hypothetically) more time the bigger your map is.

Also how to find out the algorithms behind those core functions? Is there a list or some kind of database to find this out?

Thanks for all your answers! I upvoted the best answers and accepted Max Lybbert's answer because it was the most detailed one.

Paul :)

like image 346
Paul Avatar asked Mar 21 '11 20:03

Paul


People also ask

What algorithm does std :: find use?

The algorithm to use is std::binary_search , that directly returns a bool representing whether the searched value has equivalent elements in the collection.

How are the STL algorithms implemented?

STL supports various algorithms that act on containers through iterators. As these algorithms act on iterators and not directly on containers, they can be used on any type of iterators. STL algorithms are built-in and thus save a lot of time and are more reliable too. They also enhance code reusability.

How many STL algorithms are there?

Iterators. The STL implements five different types of iterators.

Which sorting algorithm is used in STL in C++?

sort (C++) sort is a generic function in the C++ Standard Library for doing comparison sorting. The function originated in the Standard Template Library (STL).


1 Answers

std::map stores its elements in sorted order (almost always in a self-balancing binary search tree).

std::map::find takes advantage of this and uses a dichotomic search.

like image 186
James McNellis Avatar answered Oct 09 '22 20:10

James McNellis