I've always been told vectors are fast, and in my years of programming experience, I've never seen anything to contract that. I decided to (prematurely optimize and) write a associative class that was a thin wrapper around a sequential container (namely ::std::vector
and provided the same interface as ::std::map
. Most of the code was really easy, and I got it working with little difficulty.
However, in my tests of various sized POD types (4 to 64 bytes), and std::strings
, with counts varying from eight to two-thousand, ::std::map::find
was faster than my ::associative::find
, usually around 15% faster, for almost all tests. I made a Short, Self Contained, Correct (Compilable), Example that clearly shows this at ideone I checked MSVC9's implementation of ::std::map::find
and confirmed that it matches my vecfind
and ::std::lower_bound
code quite closely, and cannot account for why the ::std::map::find
runs faster, except for a discussion on Stack Overflow where people speculated that the binary search method does not benefit at all from the locality of the vector until the last comparison (making it no faster), and that it's requires pointer arithmetic that ::std::map
nodes don't require, making it slower.
Today someone challenged me on this, and provided this code at ideone, which when I tested, showed the vector to be over twice as fast.
Do the coders of StackOverflow want to enlighten me on this apparent discrepancy? I've gone over both sets of code, and they seem euqivalent to me, but maybe I'm blind from playing with both of them so much.
(Footnote: this is very close to one of my previous questions, but my code had several bugs which were addressed. Due to new information/code, I felt this was different enough to justify a separate question. If not, I'll work on merging them.)
lower_bound
a custom comparator that only comparesfirst
, since that's what map will be doing. After these changes VS2011 shows the vector as faster for the same number of elements (although the ideone time doesn't change significantly). ideone.com/b3OnH