How to catch bad scoping at compile-time? Multidimensional iterator

[mike_2000_17]

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.

[alwaysLearning0]

Hi,

I was waiting for someone to post a better and more specific solution to you.
I dont consider myself as c++ guru. So definitely there will be better solution, but here is one of the technique i learned from Modern C++ deisgn of Andrei Alexderscu.

you can catch compile time error like below

template <bool>
struct CompileTimeChecker
{
        public:
        CompileTimeChecker(...){}
};

template <>
struct CompileTimeChecker <false> { };

#define STATIC_CHECK(expr, msg)\
{\
    class ERROR_##msg{};\
    CompileTimeChecker<expr> tempvar(new ERROR_##msg());\
}

int main(int argc, char *args[]){

        // This will give compile time error, use it like traditional assert()
        STATIC_CHECK(false, MY_ERROR_MSG);
      
        //this will generate compile time error
        STATIC_CHECK(false, MY_ERROR_MSG);

       //example
       /*
Following is the error i get on my mac book for the following check.
compiletime.cpp:34: error: no matching function for call to ‘CompileTimeChecker<false>::CompileTimeChecker(main(int, char**)::ERROR_two_is_not_smaller_than_one*)’
        */

       STATIC_CHECK(2< 1, two_is_not_smaller_than_one);
        return 1;
}

I believe i dont have to explain this code to you.

Happy coding.

Shaikat

[alwaysLearning0]

Oppss miss typed, any true wont generate error

//No compile time error
STATIC_CHECK(2 >= 1, two_is_not_smaller_than_one);

//No Compile time error
STATIC_CHECK(true, two_is_not_smaller_than_one);

[mike_2000_17]

thank you for your answer. I was familiar with the compile-time assert from Alexandrescu (I am consulting his "Modern C++" book almost daily). There are of course many more ways to catch errors at compile-time, but neither of them solves my problem.

Basically what I need is to somehow make "iter2" constant as long as "iter3" exists. The problem is that the only way to do something when iter3 is created and destroyed is via the constructor (or function begin()) and its destructor. These happen at run-time and thus cannot trigger a compile-time error. Since the scope of the variable "iter3" is determined at compile-time, I thought there might be a way to catch that kind of illegal uses of "iter2" while "iter3" is in scope or exists. So the problem is not to do a compile-time assert, but to come up with a compile-time conditional that triggers the assert. I have very little hope at this point and I am contemplating to just not have any error-checking at all (to avoid run-time overhead).