StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<blockquote> <p>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: <code>map::find.</code></p> <p>This was incredibly faster than the linear algorithm I was using.</p> </blockquote> <p><code>std::map</code> is designed to keep data sorted as it is inserted into the container. That's one of its main jobs. It's also the reason you must define some sort of partial ordering for the data you put into a <code>std::map</code>.</p> <p>This means each insertion takes a little longer than inserting into other containers (inserting into a <code>std::list</code> -- once you have the insertion point -- for instance is O(1), as is appending to a <code>std::vector</code> or appending/prepending to a <code>std::deque</code>). But look up is guaranteed to use binary search (or, rather, to <a href="http://www.artima.com/intv/abstreffiP.html" rel="nofollow">navigate the red-black tree behind the <code>std::map</code></a> (under "Premature or Prudent Optimization")).</p> <blockquote> <p>In another example STL's function find was also much faster than another linear function I am using.</p> <p>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.</p> </blockquote> <p>There's nothing hypothetical about it. Sorting your data takes time, and always takes more time the more items of data.</p> <p><code>std::find</code> is able to handle unsorted data, so it must be implemented as a linear search (compare <code>std::binary_search</code>/<code>std::lower_bound</code>). But <code>std::find</code> is allowed to be sneaky and unroll loops, compare more than one item at a time (if the items are small, and especially if they are primitive types that lend themselves to low-level bit fiddling), etc.</p> <blockquote> <p>Also how to find out the algorithms behind those core functions? Is there a list or some kind of database to find this out?</p> </blockquote> <p>Personally, I learned a lot of algorithms by reading what was available in the STL and a few other languages. I found it easier to study the containers first.</p>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload