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

更新1

你怎么看这个thing :

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

?我仍然在想是否可以使用不那么棘手的方法来完成。

更新 2

好的!在@SergV 输入后我决定，最好的方法可能是使用 switch，因为它看起来不像 reinterpret_cast 那样棘手，并且有时会导致 O(1) 复杂度.非常感谢@SergV 提供的大量新信息。当然对我来说是新的。

更新 3

Why not to do your own jump table?

Answer 1

正如@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)。