Barend Gehrels wrote:
Phil Endecott wrote:
Do things like your clipping and simplification algorithms work in-place or out-of-place, or both? I can imagine that both of these examples will often return a result identical to the input, in typical usage; avoiding a copy in that case would be worthwhile.
They work out-of-place, they deliver a copy. And indeed this might result in an identical one, I will consider to avoid that. Do you want to have a boolean returned or something like that? However, to me it would seem awkward to check each time if my result is in the source or in a copy. Besides that, in many algorithms you know (or even then don't know) that the algorithm resulted in the same output as the input after the process is completed. The copy is then ready, so in those cases it is not more efficient.
Have a look at the string algorithms, for example to_upper. There are three variants: template<typename WritableRangeT> void to_upper(WritableRangeT & Input, const std::locale & Loc = std::locale()); template<typename OutputIteratorT, typename RangeT> OutputIteratorT to_upper_copy(OutputIteratorT Output, const RangeT & Input, const std::locale & Loc = std::locale()); template<typename SequenceT> SequenceT to_upper_copy(const SequenceT & Input, const std::locale & Loc = std::locale()); So I can do it in-place (first), returning a copy (third), or to an output iterator (second). You could also imagine a copy-on-write version, but we would probably want to implement general-purpose copy-on-write containers or smart-pointers before trying that. When I look at the OutputIterator variant, I like to imagine that it's possible to chain together a pipeline of operations using output iterators and input iterators. People have mentioned "dataflow" sometimes on this list. I have never thought through what's necessary to achieve this. If I had a linestring with lots of elements, and I wanted to clip it to a viewbox and then render it, I would prefer to do it segment-by-segment to avoid copying it; e.g. (naively) for each segment in linestring clip this segment to bounding box plot resulting segment, if any It's a bit more complicated because there isn't a 1:1 relationship between input line segments and output line segments. How about a clip functor: class Clipper { public: Clipper(box clip_to); linestring operator()(line l); // retuns a linestring with 0, 1 or more segments, // depending on how l lies w.r.t. the clip_to box }; or alternatively: class Clipper { public: Clipper(box clip_to, OutputIterator iter); void operator()(line l); // outputs clipped line segments, if any, to iter. }; (Functors for variable-width character set conversions are a bit like this. Are there any examples in the standard library, or elsewhere in Boost?) It's also interesting to consider how this could work in the context of more intelligent containers, e.g. polygons with bounding-boxes or with spatial indexing. Say I have a polygon that is the coastline of a continent, with millions of points, and I'm zoomed in on a bit of coast. How long does it take to get the clipped polygon to render? Say the container can iterate efficiently over a 2d range: indexed_polygon continent_coastline = ...; box viewbox = ...; Clipper cl(viewbox); indexed_polygon::range2d r(continent_coastline,viewbox); for(range2d::const_iterator i = r.begin(); i != r.end(); ++i) { // We get each line from continent_coastline that is within, or crosses, the viewbox cl(*i); // Clip to the viewbox, do something with the resulting line-segments. ... } That's quite straightforward, as long as the clipper does the right thing for all the peculiar cases. But if you have a whole-polygon-at-a-time clip algorithm, it's not clear how you do it: indexed_polygon continent_coastline = ...; box viewbox = ...; polygon visible_outline = clip(viewbox,continent_coastline); // Could be efficient if the clip algorithm knew that continent_coastline had range2d, maybe? // Similarly, could be efficient for a polygon-with-bounding-box, if the clip algorithm // knew that it had it. This sounds like a case for specialisations with enable_if. // But most likely, clip() will not exploit the indexing in inexed_polygon and treat it // like a std::vector<point>. So I could pass a range to the algorithm: indexed_polygon continent_coastline = ...; box viewbox = ...; indexed_polygon::range2d r(continent_coastline,viewbox); polygon visible_outline = clip(viewbox, r.begin(), r.end()); This is all very interesting. But you should stop me from waffling about details, and instead focus on "what is the way forward?". Phil.