Lazy evaluation delays the evaluation of an expression until its value is needed.1 Adding a mechanism to an
stl::map that calculates the value based on the key adds optional lazy evaluation. This can be used to populate the
map on demand, spreading the cost of calculating the keys over the time that they are first requested. This can also be a cache to store values that are expensive to calculate and needed multiple times, where you don't know a priori what values will be needed.
Deriving the new class from
std::map is not safe since the base class lacks a virtual destructor. If the derived class was stored as a pointer to the base class, then incorrect destruction and memory leaking could happen. As much as we'd like to inherit from
std::map it violates the Liskov Substitution Principle and the No Nasty Surprises mandate. The Liskov Substitution Principle says, given two classes
Derived, any place we can use
Base* we can also use
Derived* respectively. The program is not required to behave identically if the substitution is made (indeed, what would be the point of the substitution?) but it must remain well-formed and behave "correctly" for some version of "correctly." It is easier to understand the LSP intuitively than it is formally.
Composition to the Rescue
Instead of inheritance, the code uses composition and an implementation of
operator(const key_type&). While it would be wonderful if there was a mechanism in C++ to forward the member functions of
std::map to the
LazyMap interface, it does not exist. We cannot use the Curiously Recurring Template Pattern (CRTP), also known as Mixins-from-Above, because the base class,
std::map, is not parameterized on they equivalent of the derived class. An accessor,
getMap() and a mutator
map() make the usual
std::map functionality available. A little extra work for the client, but they are spared a Nasty Surprise.
Giving the compiler a helping hand
Take a look at the implementation of
operator() and you see the keyword
typename used any place that uses a nested type within
Map. Why? Because any type with the required type traits can be used as the parameterizing type, the compiler does not know if
Map::key_type refers to a
- Member variable
- Member function
- Nested typedef
To help the compiler out, we give it direction with the
typename keyword. Be careful to use it even if your particular compiler doesn't complain. Sometimes the compiler can figure it out on its own and let's you slide. This is a problem when moving between compilers. I've had a lot of grief over this moving between VS2010 and g++4.4. VS2010 let's me slide and then I port the code and g++ complains all over the place.
LazyMapExameple.cpp? That is new but is interesting and powerful enough that it deserves its own post.
[crayon url="2012/05/LazyMap.hpp" lang="cpp"/]
[crayon url="2012/05/LazyMapExample.cpp" lang="cpp"/]
The speedup shown in the example is better than 12X. You may think this example is artificial, but it is not too different from database access. Using a similar technique on production code that traversed graphs achieved a speedup of better than 50X. The
LazyMap.hpp class is designed for re-use and has a friendly license. The driver program and test data are included so you can take LazyMap for a test drive.