Boost C++ Libraries of the most highly regarded and expertly designed C++ library projects in the world. Herb Sutter and Andrei Alexandrescu, C++ Coding Standards


Addability, Subtractability and Aggregate on Overlap

While addition and subtraction on Sets are implemented as set union and set difference, for Maps we want to implement aggregation on the associated values for the case of collision (of key elements) or overlap (of key intervals), which has been refered to as aggregate on overlap above. This kind of Addability and Subtractability allows to compute a lot of useful aggregation results on an interval_map's associated values, just by adding and subtracting value pairs. Various examples of aggregate on overlap are given in section examples. In addition, this concept of Addability and Subtractability contains the classical Insertability and Erasability of key value pairs as a special case so it provides a broader new semantics without loss of the classical one.

Aggregation is implemented for functions add and subtract by propagating a Combiner functor to combine associated values of type CodomainT. The standard Combiner is set as default template parameter template<class>class Combine = inplace_plus, which is again generically implemented by operator += for all Addable types.

For Combine functors, the Icl provides an inverse functor.


inverse<Combine<T> >::type













The meta function inverse is mutually implemented for all but the default functor Functor such that e.g. inverse<inplace_minus<T> >::type yields inplace_plus<T>. Not in every case, e.g. max/min, does the inverse functor invert the effect of it's antetype. But for the default it does:

_add<Combine<CodomainT> >((k,x))

_subtract<inverse<Combine<CodomainT> >::type>((k,x))


_add<inplace_plus<int> >((k,x))

_subtract<inplace_minus<int> >((k,x))


adds x on overlap. This inverts a preceding subtract of x on k

subtracts x on overlap. This inverts a preceding add of x on k

As already mentioned aggregating Addability and Subtractability on Maps contains the classical Insertability and Erasability of key value pairs as a special case:

aggregating function

equivalent classical function

_add<inplace_identity<CodomainT> >(const value_type&)

insert(const value_type&)

_subtract<inplace_erasure<CodomainT> >(const value_type&)

erase(const value_type&)

The aggregating member function templates _add and _subtract are not in the public interface of interval_maps, because the Combine functor is intended to be an invariant of interval_map's template instance to avoid, that clients spoil the aggregation by accidentally calling varying aggregation functors. But you could instantiate an interval_map to have insert/erase semantics this way:

             inplace_identity //Combine parameter specified
            > m;
interval<int>::type itv = interval<int>::rightopen(2,7);
m.add(make_pair(itv,42));      //same as insert
m.subtract(make_pair(itv,42)); //same as erase 

This is, of course, only a clarifying example. Member functions insert and erase are available in interval_map's interface so they can be called directly.