Alex Chudinov - 1 year ago 56
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?

``````#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;
vec.comp<1>() = 1; vec.comp<2>() = 2; vec.comp<3>() = 3;

cout << vec << endl;

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

return 0;
}
``````

V2:

`````` 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.

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)`.

Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download