c++ - 无限数组 C++ 在一个表达式中使用两个新值调整数组大小

Question

我已经开始使用 C++ 中的模板实现无限数组。添加整数效果很好，除了一种特殊情况，我在一个表达式中添加了两个新项目，这需要一个接一个地调整大小(参见下面)。

#include <iostream>
#include <cstddef>
#include <new>
#include <string.h>

template <typename T>
struct infinite_array {
    infinite_array();
    auto operator[](unsigned long long idx) -> T&;

    auto size() const -> unsigned long long;
    void resize(unsigned long long idx);

    private:
        T *data;
        unsigned long long array_length;
};

template <typename T>
void infinite_array<T>::resize(unsigned long long idx)
{
    std::cout << "Resize with idx " << idx << std::endl;
    T* temp = new T[idx];
    memset(temp, 0, sizeof(T) * idx);

    for (int i = 0; i < array_length; ++i) {
        temp[i] = data[i];
        std::cout <<  temp[i] << " ";
    }
    std::cout << std::endl; 
    //std::copy(data, data+size(), temp);
    delete [] data;

    data = temp;
    array_length = idx;
}

template <typename T>
infinite_array<T>::infinite_array() 
{
    data = NULL;
    array_length = 0;
}

template <typename T>
auto infinite_array<T>::size() const -> unsigned long long {
    //array_length = sizeof(data)/sizeof(T);
    return array_length;
}

template <typename T>
auto infinite_array<T>::operator[](unsigned long long idx) -> T& {
    //std::cout << "Accessing element at idx " << idx << std::endl;
    if (idx+1 > size()) {
        resize(idx+1);  
    }
    return data[idx];
}

int main() {
    infinite_array<int> ar; 
    for (int i = 0; i < 10; ++i) {
        ar[i] = i;
    }
    // PROBLEM: ONLY ar[31] is initialized successfully to 10
    ar[30] = ar[31] = 10;

    for (int i = 0; i < ar.size(); ++i)
        std::cout << ar[i] << ' ';  
    std::cout << std::endl;

    return 0;
}

Answer 1

恐怕无法解决您的问题，因为您无法控制调用 operator[] 的顺序。这就是问题所在:

• 您的编译器选择首先评估 ar[30]，这将调整您的数组大小并返回对其元素之一的引用。

• 之后，对 ar[31] 求值，再次调整数组大小，返回对其中一个新数组元素的另一个引用。 旧引用仍然指向旧数组中的元素(已删除!)。

• 最后，您的编译器执行分配，将 10 分配给两个元素。但由于这些元素之一存在于旧的已删除数组中，您在新数组中看不到它。

一个简单的事实是，你不能像这样对你的 operator[] 进行链式调用，你无法解决这个事实，即允许编译器以任何顺序执行调用.

---

旁白:逐个调整任何缓冲区的大小通常不是一个好主意，其复杂度是二次方的。典型的代码使用至少一个因子 2 的增量。精确的因子不是那么相关，相关的是你使用一个因子，因为这样你就可以将复杂性降低到 O(n)。值 2 只是空间和时间开销之间的一个很好的权衡。