Subject: Re: [boost] Review Request: Boost.Itl; The Interval Template Library
From: Joachim Faulhaber (afojgo_at_[hidden])
Date: 2009-10-03 11:07:50
2009/10/1 Jeff Flinn <TriumphSprint2000_at_[hidden]>:
> More importantly, I'd like to be able to
> use std::inserter of std::back_inserter with std::copy or std::transform to
> fill the split_interval_map from my domain data.
Thanks Jeff for raising this issue. The current version did not
work so I fixed the code. If you update the code from the
sandbox, std::copy should work now with std::inserter for
> I see there is an insert
> method, but I'm not sure just how it differs from add.
(1) For integral domain_types the behavior of 'insert' on interval maps
is identical to 'insert' on maps of elements. You could say it has
std::insert semantics. Or more formalized:
M: interval_map or split_interval_map of integral
m: itl::map (that implements std::insert semantics)
f: atomize: Transforms interval containers
into containers of elements.
p: interval value pair
p': set of element value pairs
this diagram commutes
(M,p) -------> M
|f = |f
V Insert V
(m,p') ------> m
or as a formula:
For all M y, p r:
where capitalized 'Insert' iterates over
the set of element value pairs f(r) and
then applies member function 'm::insert'
on map f(y) for the element level.
(2) Member function 'add' does not
provide 'std::insert' semantics (in general).
It performs an aggregation on associated
values, if intervals overvlap or elements
collide (aggregate on overlap). Addition
(via operator += on codomain_type) is the
default, but you can customize via template
(3) Both 'insert' and 'add' can be expressed
by a more general member function
template _add<Combiner> (that has been
suffixed by '_' to make life easier for the
M::insert == M::_add<itl::inplace_identity>
M::add == M::_add<itl::inplace_plus>
'inplace_plus' propagates += to aggregate
associated values on overlap.
'inplace_identity' propagates the identity
function to aggregate values, which leaves
> I'd like to see the
> public interface paired down and just expose the more std::map like
I think that the characteristics of interval containers sets
certain limits to the pervasive and powerful use of iterators
and algorithms that is known from stl::containers.
IMO it makes no sense to try to iterate an
interval_set<double>, interval_set<string>, interval_set<rational<int> >
etc. on the level of *elements*.
Only for interval containers of integral domain_types a completely
std conform element iterator can be implemented. But still this
would be a permanent invitation to produce inefficient code particularly
for cases where the granularity of your intervals is very fine.
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk