Quote:Original post by taz0010
I have a bunch of math/geometry algorithms that I would like to make container independent. I figured I'd go the STL route and have them take iterators to the start() and end() of the container in question.

One of the main tasks performed is: Given a container filled with 3D coplanar vertex data, project the coords into 2D and operate on them as if the input were a set of 2D coordinates.

One way of doing this would be to have a type of iterator that transforms a 3D vector in to a 2D vector via some kind of projection when that iterator is dereferenced. This means you won't have to write a special version of the algorithm that does a projection internally.

You should take care with this approach, though. If your algorithm would dereference each iterator multiple times, the cost of the projections might accumulate. But if you do take this approach, have a look at boost's transform_iterator.

Quote:
I'd like to remove the logic of iteration/interpreting coord layout from the algorithms in question, and instead pass in a "2d iterator" which is able to iterate over a range of different containers, regardless of the actual arrangement of data within.
My 2D algorithms currently operate on 4 different coordinate layouts:
- Vector of 2D coordinates (simplest arrangement possible)
- Vector of 3D coordinates, where the vector is "projected" into 2D by simply disregarding one of the xyz components of each coord.
- Vector of 3D coordinates as above, with additional data attached to each coord (normal, colour, etc).
- Link list of pointers to 3D coordinates, which are otherwise as above

I'm sure I can get away with only writing each algorithm once, and having it rely on iterators instead of a particular container with a particular layout. But what's the best way to do this?

This last sentence seems to imply that you can think of multiple ways of doing this. What are they? It's hard to guess what your thoughts are here. In other words, what's to stop you following the STL model?

Also, why do you think of 3D coordinates with additional data e.g. normals as a different kind of data?

Possibly you're thinking that there might be algorithms that need to construct new coordinates by some kind of interpolation. In that case, the algorithm could take a functor that performs this interpolation, which would take care of creating correctly interpolated colours, pressure, viscosity, or whatever else.

As for the linked list case, I don't see how that's any different. std::list exposes an interface for iterators and it's reasonably straight forward to add an interface to a custom linked list implementation, too.

Quote:
Should I change my containers (which are mostly typedef'd to STL containers) so they inherit from the STL instead?

The STL containers aren't designed to be used as base classes. I don't think you need to touch them if all you care about are sequences of 3D points.

However, some algorithms might need additional information inherent to more graph-like structures (3D meshes). In that case, you might look at the general approach taken by the algorithms in CGAL. They have an STL flavour, but make concessions and introduce extensions needed to perform algorithms effectively on connected 3D structures.

Quote:
And add variants of the begin() and end() methods to return custom iterators?

Not needed. See my comments about boost::transform_iterator.

Quote:Should the custom iterators themselves inherit from std::iterator?

They should at least implement the functionality and include the nested types expected of STL iterators. The easiest way to do this is to inherit from an instantiation of std::iterator<>.

Quote:I think all the algorithms require is a bidirectional iterator in order to function, if that makes any difference.

The only thing your algorithms need to do is document that requirement. The best way of doing this is to have a static assert that checks the iterators passed to the algorithm are indeed forward iterators (at least). If your iterators follows the STL conventions and define an iterator_category typedef, or specialize std::iterator_traits appropriately then that won't be a problem. This is one of the things that inheriting from std::iterator<> gives you.

Quote:Original post by taz0010

Quote:You should take care with this approach, though. If your algorithm would dereference each iterator multiple times, the cost of the projections might accumulate. But if you do take this approach, have a look at boost's transform_iterator.

The vector version of the iterator will probably store pointers to the projected x and y coords. Incrementing the iterator is simply a matter of adding sizeof(Container) bytes to each.
Two parallel dereferences are needed to construct and return a 2D coord. e.g. return Vec2(*pProjX, *pProjY). The iterators are const by the way, so a value is returned, not a mutable reference.
The link list iterator will be more expensive to dereference. Two dereferences and 2 additions probably.

The reason I mentioned the cost of dereferencing/projection was because in theory, it might be cheaper to construct a vector of 2D objects upfront and apply the algorithm to that, depending on how expensive projection really is.

The cost of incrementing the iterator is less relevant because you'd have to do that whether or not you were to make a copy first.

Quote:

Quote:Also, why do you think of 3D coordinates with additional data e.g. normals as a different kind of data?

Because you can't iterate over a std::vector<CoordWithAdditionalData> using an iterator constructed from a std::vector<Coord>.

True, but why can't you use a std::vector<CoordWithAdditionalData>::iterator?

Quote:This can be resolved by making the iterator parameters template types. i.e. the iterator type is: std::vector<T>::iterator where T is a format which possesses x and y coords. But then there's still the need to transform each element into the desired state, which is required in most cases.

Perhaps the answer to my previous question lies in here, but I can't quite work out what you mean.

Quote:Original post by taz0010
So this is what I'm looking at:
- Have all algorithms take begin() and end() iterators, which are template types

Presumably you mean the algorithms are template functions, rather than the iterators necessarily having to be template instantiations themselves. If so, that sounds fine.

Quote:
- If the algorithm requires 3D coords, containers of Coord and CoordWithAdditionalData simply use the STL container::iterator
- If the algorithm requires 2D projected coords, and the container has 3D coords, use a custom iterator solution

Sounds fine.