On Mon, 11 Mar 2002, Lars Gullik Bjønnes wrote:
> all lookup functions has changed from O(n) to O(log n)
> delete_layout is still O(n), but with a higer constant factor.
> + typedef std::map<string, int> LayoutMap;
Please note that std::map has a terrible constant factor in practically
all implementations today.
It is often much, much faster to use a std::vector by hand, sort it and
use binary search.
Now, in this case, I would think that the distribution of lookups
is such that the function will return the same value in 95% of
all cases.
Therefore, I believe you will get the best results by caching the
last lookup, and then it is not worth it to have O(log n) lookup
in the other cases:
int lookup(std::string const & key) {
static std::string lastKey;
static int lastIndex;
if (key == lastKey) {
return lastIndex;
}
// Now, just do a linear search in a vector and update the
// lastKey and lastIndex values when the entry is found
...
}
Greets,
Asger
