What algorithm is behind the STL search?

Question

I just created a custom search function for lines on a map. I developed some kind of 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 my own map function: map :: find .

It was incredibly faster than the linear algorithm that I used.

In another example, the STL find function was also much faster than the other linear function I use.

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

Also, how do you find out the algorithms underlying these core functions? Is there a list or some kind of database to find out about this?

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

Floor:)

Answer 1

I developed some kind of 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 my own map function: map::find.

It was incredibly faster than the linear algorithm that I used.

std::map designed to store data sorted as it is inserted into the container. This is one of his main tasks. This is also the reason that you must define some kind of partial order for the data that you entered in std::map .

This means that each insertion takes a little longer than insertion into other containers (insertion into std::list - after you have an insertion point - for example, O (1), as added to std::vector or adding / addition to std::deque ). But the search is guaranteed to use a binary search (or rather move through the red-black tree behind std::map (in the "Premature or Reasonable Optimization" section)).

In another example, the STL search function was much faster than the other linear function we used.

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

There is nothing hypothetical about this. Sorting your data takes time and always takes more time than more data items.

std::find is capable of handling unsorted data, so it should be implemented as a linear search (compare std::binary_search / std::lower_bound ). But std::find allowed to hide and expand loops, compare more than one element at a time (if the elements are small, and especially if they are primitive types that lend themselves to low-level bit-reproduction), etc.

Also, how do you find out the algorithms underlying these core functions? Is there a list or some kind of database to find out about this?

Personally, I learned a lot of algorithms by reading what was available in STL and in several other languages. At first it was easier for me to study the containers.

Answer 2

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

std::map::find uses this and uses a dichotomous search .

Answer 3

Technically, there are no such algorithms. The standard defines how well each algorithm should perform, and not how it should do it. Each compiler sends an implementation of the standard library.

Saying there are free STL implementations. You can look at their code. For example, an STL port .

Also, how do you find out the algorithms underlying these core functions? Is there a list or some kind of database to find out about this?

Well, there is a Dictionary of algorithms and data structures , but it's a little messy.

Answer 4

Implementation is good, implementation dependent.

But as for the general complexity classes, you can check, for example, this page with an overview of the common STL methods:

http://www.cplusplus.com/reference/stl/

Answer 5

STL algorithms are almost always faster than anything you could write yourself, because it makes a lot of optimizations under the covers. It also uses iterators faster than the [] operator when iterating through a vector or other random access container, since there is less overhead.

You should check out Scott Meyers' books Effective C ++ Third Edition and Effective STL. (Material in More Effective C ++ is contained in the 3rd edition of Effective C ++.)