Hey y'all,
I have been working on a tensor library (Nth-order multi-dimensional arrays) and I've been having trouble coming up with a good scheme for a multi-dimensional iterator template. Basically, I have a class template "tensor_container" which stores all the values of the N-order array (as a std::vector of one dimension) and the size of each dimension. The values themselves are thus serialized as a 1D vector with the lowest level being continuous (e.g. a second order tensor would correspond to a column-major matrix).
Now, I pretty much managed to get the indexing to work just fine with a few template specializations, such that now, an element of tensor "a" of order 4 can be accessed as "a[2][5][1][4]". This is accomplished by this simple code:
template <class Iterator,int Level> //here, Iterator is an iterator for the 1D array or vector and Level is the level of the index.
class tensor_indexer : public boost::noncopyable {
private:
Iterator start; //stores the start iterator for this level, on flat data storage.
int *dim; //stores the pointer to the dimension of the current level
int accum; //stores the accumulated stride for indexing.
tensor_indexer(Iterator aStart, int* aDim, int aAccum) : start(aStart), dim(aDim), accum(aAccum) { };
public:
//this operator[] just returns a tensor_indexer for the next level.
tensor_indexer<Iterator,Level-1> operator[](int i) {
accum *= dim[0];
return tensor_indexer<Iterator,Level-1>(start+i*accum,dim+1,accum);
};
friend class tensor_container<typename std::iterator_traits<Iterator>::value_type, Level+1>;
friend class tensor_indexer<Iterator,Level+1>;
};
template <class Iterator> //template specialization for level 1 (terminal level)
class tensor_indexer<Iterator,1> : public boost::noncopyable {
private:
Iterator start;
int *dim;
int accum;
tensor_indexer(Iterator aStart, int* aDim, int aAccum) : start(aStart), dim(aDim), accum(aAccum) { };
public:
typedef typename std::iterator_traits<Iterator>::reference reference;
//here, the operator returns the de-reference of the iterator at the given index i.
reference operator[](int i) {
accum *= dim[0];
return start[i*accum];
};
friend class tensor_container<typename std::iterator_traits<Iterator>::value_type, 2>;
friend class tensor_indexer<Iterator,2>;
};
template <class Iterator> //partial specialization for level 0 (no iterator needed)
class tensor_indexer<Iterator,0> : public boost::noncopyable {
private:
Iterator start;
tensor_indexer(Iterator aStart, int*,int) : start(aStart) { };
public:
typedef typename std::iterator_traits<Iterator>::reference reference;
operator reference() { return *start; }; //just implicit conversion operator.
friend class tensor_container<typename std::iterator_traits<Iterator>::value_type,1>;
};
//this is the tensor container itself, containing elements T and of order Order.
template <class T, int Order>
class tensor_container {
private:
std::vector<T> data; //stores data as 1D vector.
int dim[Order]; //stores the sizes or dimensions of each level (row, column, etc. until Order).
public:
//a bunch of tensor traits:
typedef T element_type;
typedef array_order<Order> order;
typedef typename std::vector<T>::iterator iterator;
typedef typename std::vector<T>::const_iterator const_iterator;
typedef tensor_indexer<iterator,Order-1> indexer;
indexer operator[](int i) {
return tensor_indexer<iterator,Order-1>(data.begin() + i,dim,1);
};
//a whole bunch of other stuff...
};
//template is specialized for 0th order, to take out the [] operator.
template <class T>
class tensor_container<T,0> {
private:
T value;
public:
//...
};Of course, the above is not perfect and pretty much requires the compiler to optimize away all those temporary indexer objects. If you have a better solution to suggest, it is very welcomed!
Now, to get to the topic of my post... I want to implement some iterators for this tensor_container (or any other class with the same traits). Basically, this would be a typical use of them, for a 3rd-order tensor:
tensor_container<double,3> a;
for(tensor_container<double,3>::iterator<1> iter1 = a.begin<1>(); iter1 != a.end<1>(); ++iter1) {
for(tensor_container<double,3>::iterator<2> iter2 = iter1.begin<2>(); iter2 != iter1.end<2>(); ++iter2) {
for(tensor_container<double,3>::iterator<3> iter3 = iter2.begin<3>(); iter3 != iter2.end<3>(); ++iter3) {
*iter3 = 0.0; //set all data elements to zero.
};
};
};Now, I can obviously make the above work quite easily with a tensor_iterator class template and a few specializations (very similar to the indexer, but more efficient because the iterators are not temporary). However, my main problem is that I cannot force the compiler to catch illegal uses of the iterators at compile-time. In the example above:
- trying to modify iter2 after iter3 has been issued (i.e. with iter2.begin() inside the third loop) should be illegal because it makes iter3 desynchronized w.r.t. iter2.
- trying to issue iter3 in the scope of the second for-loop should be illegal as well because iter2 needs to remain constant for the entire scope of iter3.
Basically, I can verify the above conditions at run-time with some flags and reference counting of the issued sub-iterators (to check for example that no object iter3 is still in scope when I try to modify iter2). However, this is essentially a compile-time mistake and I would like to be able to catch this at compile-time. Does anyone know a clever trick to accomplish this? I've been banging my head against the wall for several days now on this problem! I tried to turn the iterators into linked-lists of iterators to enforce synchronization, but realized that I was losing all the benefits of iterators by doing that.
thanks in advance,
Mike.
