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