6.7. Writing Your Own Algorithms

Our first piece of advice for anyone wishing to implement a metafunction that does low-level sequence traversal is, "Leave the traversal to us!" It's usually much more effective to simply reuse the MPL algorithms as primitives for building higher-level ones. You could say we took that approach in Chapter 3, when we implemented divide_dimensions in terms of transform. You'll save more than just coding effort: MPL's primitive iteration algorithms have been specially written to avoid deep template instantiations, which can drastically slow down compilation or even cause it to fail.^[5] Many of the MPL algorithms are ultimately implemented in terms of iter_fold for the same reasons.

^[5] See Appendix C for more information.

Because the MPL provides such an extensive repertoire of linear traversal algorithms, if you find you must write a metafunction that does its own sequence traversal, it will probably be because you need some other traversal pattern. In that case your implementation will have to use the same basic recursive formulation that we introduced in Chapter 1 with the binary template, using a specialization to terminate the recursion. We recommend that you operate on iterators rather than on successive incremental modifications of the same sequence for two reasons. First, it's going to be efficient for a wider variety of sequences. Not all sequences support O(1) pop_front operations, and some that do may have a rather high constant factor, but all iterators support O(1) incrementation via next. Second, as we saw with iter_fold, operating on iterators is slightly more general than operating on sequence elements. That extra generality costs very little at implementation time, but pays great dividends in algorithm reusability.