c++ - 如何从 vector 中提取子 vector ？

Question

我正在编写用于在旋转排序数组中查找最小元素的递归解决方案。该函数的输入是 const vector ，我必须获得一个用于递归的子数组。

findMin(const vector<int> &A) {
    int l=0,r=A.size()-1;
    if(r<l)return A[0];
    if(r==l)return A[l];

    int m=(l+r)/2;
    if((m<r)&&(A[m+1]<A[m]))
        return A[m+1];
    if((m<r)&&(A[m]<A[m-1]))
        return A[m];
    if(A[m]<A[r]){
        const vector<int> &B(&A[0],&A[m-1]);
        return findMin(B);
    }
    const vector<int> &C(&A[m+1],&A[r]);
    return findMin(C);
}

错误是关于子 vector B和C

Answer 1

vector 存储和拥有数据，它们不是数据的 View 。 vector 没有“子 vector ”，因为没有其他对象拥有该 vector 的数据。

您可以将数据从您的 vector 复制到另一个 vector ，但称其为“子 vector ”会产生误导。

最简单的解决方案是重写您的函数以使用迭代器启动和完成而不是容器。您可以采用现有接口(interface)，并让它调用双迭代器版本，以维护 API。

更难的解决方案是写一个 array_view<T>存储两个 T* 的类并且表现得像一个带有你想要的接口(interface)的范围，包括一个隐式的从 vector 转换。替换你的 const vector<int>&B同样C写得正确 array_view<int const> B ，以及你的 A ，并且(假设您的代码中没有其他错误)您已完成。

here是一个 array_view我已经写了。 here正在添加到 std 中.