Menu
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 :)
346
The algorithm to use is std::binary_search , that directly returns a bool representing whether the searched value has equivalent elements in the collection.
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.
Iterators. The STL implements five different types of iterators.
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).
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.
186
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
