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

Question

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;
}

UPDATE1

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.

UPDATE2

OK! After @SergV input I decided that, probably, the best way is to use switch, cause it looks not so tricky as reinterpret_cast and could give the O(1) complexity somethimes. Thanks a lot to @SergV for a lot of new information. New for me, ofcause.

UPDATE3

Why not to do your own jump table?

Recursion should only be used when it's necessary. If you dump the recursion, you can simply change `double x;` to `double x[N];` and everything will be much simpler. — Pete Becker, Sep 21 '16 at 14:07
Agreed. But, it is still interesting if it is possible to do the operator[] here. I mean theoretically. — Alex Chudinov, Sep 21 '16 at 14:11
Yes, it can be done. Roughly: `return `index == 0 ? x : `static_cast*>(this).operator[](index - 1);`. Not tested. — Pete Becker, Sep 21 '16 at 14:14
It would be an interesting exercise to *prove* that it cannot be done without some array of length N somewhere. — n. m. could be an AI, Sep 21 '16 at 15:13
@PeteBecker @n.m. Yes, it is just intereting, probably, nothing more. And I am still wander if it could be done, because we actually have such an array of xs belonging to different Arrays in memory, is it? May be some trick can be used like `reinterpret_cast` to `double*`? — Alex Chudinov, Sep 21 '16 at 17:02
@AlexChudinov - the language definition does not require that that cast does anything sensible. It **might** work with your compiler and the particular compiler options that you use, but if you rely on it, you must either have documentation from the compiler implementor that it will work or you must test every compiler configuration that you use. — Pete Becker, Sep 21 '16 at 17:15
@AlexChudinov, Are you sure that " the Array is a kind of a POD data"? Add next line to your code - "static_assert(std::is_pod >::value, "Array is not POD!!!");". Opinion of the compiler is very important too :-) — SergV, Sep 23 '16 at 15:07
@SergV [It is not POD](https://ideone.com/A2bCsu). Because it has a base class, has it? — Alex Chudinov, Sep 23 '16 at 15:58

score 3 · Answer 1 · edited Sep 21 '16 at 14:44

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

Thank you, but, I still wander if there is any way to do an operator[] of O(1) complexity? That was the main idea of my question, because O(n) is a quite strightforward. — Alex Chudinov, Sep 21 '16 at 15:01

SergV · Accepted Answer · 2016-09-26T09:43:07.823

switch operator has usually O(1) complexity. You can use it in operator[] function. For example:

template <> double&  Array<3>::operator[](size_t i)
{
    switch (i)
   {
        case 0: return Array<0+1>::x;
        case 1: return Array<1+1>::x;
        case 2: return Array<2+1>::x;
   }
}

You can use macro for generation switch in operator[] for some M. Good tool for such generation is boost preprocessor. See documentation about BOOST_PP_REPEAT.

//this macro generate one line of switch 
#define DECL(z, n, text) case n: return Array<n+1>::x;

//this macro generate operator[] for  Array<M>
#define DEF_OPER(z,M,text)\
template <> double&  Array<M>::operator[](size_t i)\
{\
    switch (i)\
    {\
        BOOST_PP_REPEAT(M, DECL, );\
    }\
}\

//generate template <> double&  Array<3>::operator[](size_t i)
DEF_OPER(, 3, )

To generate operator[] for all possible N you can use BOOST_PP_REPEAT_FROM_TO:

#define MAX_ARRAY_N 15
//This macro generate all operator[] from Array<2> to Array<MAX_ARRAY_N>
BOOST_PP_REPEAT_FROM_TO(2, MAX_ARRAY_N, DEF_OPER, );

It is modification of your code:

#include <iostream>
#include <sstream>
#include <boost/preprocessor.hpp>
using namespace std;

template <int N> struct Array : Array <N - 1>
{
    double x;
    double&  operator[](size_t i);   //!!!
    //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;
    double&  operator[](size_t i) { return 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;
    }
};

//this macro generate one line of switch 
#define DECL(z, n, text) case n: return Array<n+1>::x;

//this macro generate operator[] for  Array<M>
#define DEF_OPER(z,M,text)\
template <> double&  Array<M>::operator[](size_t i)\
{\
    switch (i)\
    {\
        BOOST_PP_REPEAT(M, DECL, );\
    }\
}\

#define MAX_ARRAY_N 15
//This macro generate all operator[] from Array<2> to Array<MAX_ARRAY_N>
BOOST_PP_REPEAT_FROM_TO(2, MAX_ARRAY_N, DEF_OPER, );

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

int main()
{
    Array<3> vec;
    vec[0] = 1; vec[1] = 2; vec[2] = 3;

    cout << vec << endl;
    cout << (vec += vec) << endl;
    return 0;
}

If you do not want to use boost you can implement such macro yourself. Disadvantage of this method - you must know max size of Array in compile time.

P.S. This code was tested in VC++ 2015 and boost 1.61

UPDATE

Alex Chudinov suggested in comments that switch operator has O(N) complexity. Even the first C compilers had very good implementation of switch. The reason quite simple - there are a lot of code with hundreds or thousands case in switch operator.

I found very useful article about code which compiler generate for switch - Something You May Not Know About the Switch

Nice idea, but compiler will do with your code something like it will do with the @Holt 's example. Because, the `switch` is the same as a lot of `if` put one by another. You can consider it as an O(1) only because it has a finite number of states, but in fact it still has O(n). — Alex Chudinov, Sep 23 '16 at 12:14
@AlexChudinov, usual implementation in this case - jump table. So it is O(1). There is not any "if else". It is very old optimization of first C compilers. See for example - http://stackoverflow.com/questions/2596320/how-does-switch-compile-in-visual-c-and-how-optimized-and-fast-is-it . You can see assembler listing too. — SergV, Sep 23 '16 at 13:52
OK! Sorry, I did a too hasty consumption. So, the **switch** can be optimized like an array of double ponters which are pointing to probably different locations in memory. Awesome! — Alex Chudinov, Sep 23 '16 at 16:06
@AlexChudinov more like "increment instruction pointer by N bytes" where there is a lookup table from possible arguments to values of N — M.M, Sep 26 '16 at 09:45

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

2 Answers2