Resource Management and std::map::find Speed

[anonymous23323124]

I am writing resource management code for a game engine. My resource manager currently is a template class so that it only handles one particular type of resource at a time. That is, I would have a separate resource manager for textures, models, WAVE sounds, music, etc.

Internally the manager uses an std::map to associate pointers to resources with string IDs. I am now considering changing the resource manager to allow multiple types of resource, and just to use a singleton resource manager which accepts any resource type inherited from some (yet to be created) abstract base.

This would be nice, as a singleton resource manager would make it easier to handle resources in a unified manner. However, from the documentation here, std::map::find is

logarithmic in size

So if I merge 4 or 5 equally sized std::map objects into one, so std::map::size quadruples/quintuples, would this result in a performance drop of the order 10^4 or 10^5?

Sorry for the verbose phrasing, and thanks in advance for any help.

[kbw]

You'll cause upto 2 extra compares per search.

[Athar]

Logarithmic just means that when the size multiplies by x, the time needed increases by a constant y.
So searching through a map with say, a billion elements only takes slightly longer than searching through a map with a million elements.

See also: http://en.wikipedia.org/wiki/Logarithm

[anonymous23323124]

OK great - thanks for the help. I knew what a logarithm was, but was misled by the phrase "logarithmic scale", which in fact results in exponential growth, thus the confusion.

[anonymous23323124]

Sorry to reopen this thread, but I just read from here http://cplus.about.com/od/glossar1/g/bigo.htm
that

An algorithm with linear running time is preferable to Logarithmic etc.

But according to what you have said, doubling size for a logarithmic algorithm increases operation count by some constant. But on the other hand, doubling size with a linear algorithm must surely double the number of operations.

Either I'm missing something, or that constant is really massive.

[m4ster r0shi]

An algorithm with linear running time is preferable to Logarithmic

He is wrong. The order of preference should be:

(1) Logarithmic O(log(n))
(2) Linear O(n)
(3) n-log-n O(n * log(n))
(4) Quadratic O(n²)

[anonymous23323124]

Thanks for your help.