Lazy Evaluation

Lazy evaluation delays the evaluation of an expression until its value is needed.¹ 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.

Inheritance

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 Base and Derived, any place we can use Base& or Base* we can also use Derived& and 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.

See boost::ref in 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"/]

LazyMap Performance Comparison

Input data file used with LazyMapExample

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.