in languages that lack direct support for parametricity, parametric behavior can often be achieved using other mechanisms, such as macros or function pointers in C. Choice of parametricity. In C++, parametric polymorphism and dynamic binding have advantages and disadvantages as it comes to deriving propagators.

Templates are compiled by *monomorphization:* the code is replicated and specialized for each instance. The compiler can generate optimized code for each instance, for example by inlining the transformations that a view implements.

Achieving high efficiency in C++ with templates sacrifices some expressiveness. Instantiation can *only* happen at compile-time. Hence, either C++ must be used for modeling, or all potentially required propagator variants must be instantiated explicitly.

The *choice* which propagator to use can however be made at runtime: for linear equations, for instance, if all coefficients are units, the optimized original propagator can be posted.

For n-ary constraints, compile-time instantiation can be a limitation, as all arrays must be monomorphic (contain only a single kind of view). For example, one cannot mix scale and minus views in linear constraints. For some propagators, we can work around this restriction using more than a single array of views. For example, a propagator for a linear constraint can employ two arrays of different view types, one of which may then be instantiated with identity views and the other with minus views. While this poses a limitation in principle, our experience from Gecode suggests that there are only few propagators in practice that suffer from this limitation.

Dynamic binding is more flexible than parametric polymorphism, as instantiation happens at runtime and arrays can be polymorphic. This flexibility comes at the cost of reduced efficiency, as the transformations done by view operations typically cannot be inlined and optimized, but require additional virtual method calls. Section 7 evaluates empirically how these virtual method calls affect performance. Compile-time versus runtime constants. Some views involve a parameter, such as the coefficient of a scale view or the constant of a constant view. These parameters can again be instantiated at compile-time or at runtime. For instance, one can regard a minus view as a compile-time specialization of a scale view with coefficient −1, and a zero view may specialize a constant view. With the constants being known at compile-time, the compiler can apply more aggressive optimizations.

## 5.4 Iterators

Typical domain operations involve a single integer value, for instance adjusting the minimum or maximum of an integer variable. These operations are not efficient if a propagator performs full domain reasoning on integer variables or deals with set variables. Therefore, set-valued operations, like updating a whole integer variable domain to a new set, or excluding a set of elements from a set variable domain, are important for efficiency. Many constraint programming systems provide an abstract set-datatype for accessing and updating variable domains, as for example in Choco [6], ECLiPSe[8],
SICStus Prolog [35], and Mozart [23]. ILOG Solver [17] only allows access by iterating over the values of a variable domain.

This section develops*iterators* as one particular abstract datatype for set-valued operations on variables and views. There are two main reasons to discuss iterators in this paper. First, iterators provide simple, expressive, and efficient set-valued operations on