Alex Chudinov Alex Chudinov - 2 months ago 8
C++ Question

operator[] for a template based array of O(1) complexity

I want to make an array type using template's recursion as in the code chunk below. This is code dump on ideone.

Acctually, I can not figure out how to create the

double& operator[](int)
and
const double& operator[](int) const
of O(1) complexity for this type of an array. Do you have any assumtions of how it could be done without changing the main ideology? Is it even possible?

Please, help.

#include <iostream>
#include <sstream>
using namespace std;

template <int N> struct Array : Array <N - 1>
{
double x;

template<int M> double& comp() { return Array<M>::x; }
template<int M> const double& comp() const { return Array<M>::x; }

//Prints vector
ostream& print(ostream& out) const
{
static_cast<const Array<N-1>*>(this)->print(out);
out << ", " <<x;
return out;
}

//Vector in place summation, without looping
Array& operator+=(const Array& v)
{
x+=v.x;
*static_cast<Array<N-1>*>(this) +=
static_cast<const Array<N-1>&>(v);
return *this;
}
};

template <> struct Array<1>
{
double x;

template<int M> double& comp() { return Array<M>::x; }
template<int M> const double& comp() const { return Array<M>::x; }

//Prints vector
ostream& print(ostream& out) const
{
out << x;
return out;
}

//Vector in place summation, without looping
Array& operator+=(const Array& v)
{
x+=v.x;
return *this;
}
};

template<int N>
ostream& operator<<(ostream& out, const Array<N>& v)
{
out << "("; v.print(out); out << ")";
return out;
}

int main()
{
Array<3> vec;

//Here I want to do something like: vec[0] = 1; vec[1] = 2; vec[3] = 3;
//instead of what you see
vec.comp<1>() = 1; vec.comp<2>() = 2; vec.comp<3>() = 3;

cout << vec << endl;

cout << (vec+=vec) << endl;

return 0;
}


V2:
What do you think about this thing:

double& operator[] (int i) {
return reinterpret_cast<double*>(this)[i];
}


? And I still wander if it could be done using not such a tricky way.

Answer

As mentioned by @PeterBecker in comments, using recursion here is probably not a good idea, but for the sake of the exercise, you could simply do:

// Generic case:
double& operator[] (size_t i) {
    if (i == N - 1) {
        return x;
    }
    return Array<N - 1>::operator[](i);
}

// Trivial case:
double& operator[](size_t i) {
    if (i != 0) { // If you don't care about strange behavior, you can remove this.
        throw std::out_of_range("Oops!");
    }
    return x; 
}

Note that this is recursive and will give you access in O(n) (if not optimized by the compiler) while any decent std::array (std::vector) implementation is required to be O(1).