operator []为基于模板的O（1）复杂性阵列

Question

我想使用模板的递归来创建数组类型，如下面的代码块。 This is code dump on ideone。

实际上，我无法弄清楚如何为这种类型的数组创建O（1）复杂度的double& operator[](int)和const double& operator[](int) const。你有没有任何暗示如何在不改变主要意识形态的情况下做到这一点？它甚至有可能吗？

请帮忙。

#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

你怎么看待这个thing什么：

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

？而且，如果可以用不那么棘手的方式来完成，我还是会徘徊。

UPDATE2

OK！在@SergV输入之后，我决定，最好的方法是使用开关，因为它看起来不像reinterpret_cast那么棘手，并且可能会给O（1）复杂性带来些许希望。非常感谢@SergV提供了大量新信息。对我来说是新的，因为。

UPDATE3

Why not to do your own jump table?

Answer 1

交换机运营商通常具有O（1）复杂性。你可以在operator []函数中使用它。例如：

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

可以在操作符[]使用宏用于产生开关一些中号。这样的一代好工具是boost preprocessor。请参阅关于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,) 

要生成operator []的所有可能的N，你就可以使用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,); 

这是你的代码的修改：

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

如果你不想使用升压你可以自己实现这样的宏。这种方法的缺点 - 在编译时必须知道Array的最大大小。

P.S. 该代码在VC 2015进行了测试和升压1.61

UPDATE

亚历丘季诺夫提出在评论指出开关运营商具有O（N）的复杂性。即使是第一个C编译器也有很好的实现switch。原因很简单 - 有很多代码有数百或数千case in switch operator。

我发现有关代码是非常有用的物品，其编译器为开关 - Something You May Not Know About the Switch

Answer 2

正如在评论中提到通过@PeterBecker，这里使用递归可能不是一个好主意，但对于运动的缘故，你可以简单地做：

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

请注意，这是递归的，并会给你访问O(n)（如果没有编译器优化），而任何像样的std::array（std::vector）的实施要求为O(1)。