0

我正在尝试在 C++ 中学习向量类。为此，我试图从数组转换为向量形式。

以数组形式

int find_recursively(int *a, int low, int high) {
    int mid = (low+high)/2;

    if(....)
        return find_recursively(a,low,mid+1);
    else if(...)
        return find_recursively(a,mid+1,high);
}

我的向量形式的转换是这样的：

int find_recursively(vector<int> a) {
    int low = 0;
    int high = a.size() - 1;
    int mid = (low + high) / 2;

    if(....) {

        vector<int> temp ( a.begin(), a.begin() + mid-2 );
        return find_recursively(temp);
    }

    else if(...) {
        vector<int> temp (a.begin()+mid+1, a.begin()+high);
        return find_recursively(temp);
    }
}

我测试了它，并直接给力关闭。我认为问题出在边界上，我没有得到向量中边界的逻辑。提前致谢

4

3 回答 3

1

一旦您的递归深入到大小为 2 或更少的向量，您编写的代码就会出现问题。此时，您的“中间”值为 1，并且您的第一个“if”块中上限的“中间 2”计算产生 -1。此外，您的函数会打开一个没有返回语句的代码路径（如果两个“if”条件都评估为 false）。

无论如何，您不应该像这样递归地克隆向量。您应该使用迭代器，如下所示：

template< class Iter >
int find_recursively(Iter low, Iter high) {
   Iter mid = low + distance(low, high) / 2;

   if (...some test of *mid...) {
      return find_recursively(low, mid);
   }
   else if (...some other test of *mid...) {
      return find_recursively(++ mid, high);
   }
   else {
      return (something);
   }
}

// call site:
find_recursively(my_vector.begin(), my_vector.end());
于 2013-03-07T20:58:02.953 回答
1

.begin()并且.end()是迭代器，它提供了一种简单地遍历容器的方法：

for(auto it = vec.begin(); it != vec.end(); ++vec)
    cout << *it << " "; // print the contents of vec

请注意，这end()实际上并不是容器的一部分。为什么这很重要？因为它可用于创建更通用的算法版本：

template <class ForwardIt>
int find_recursively(ForwardIt first, ForwardIt last) {
    const size_t length = std::distance(first,last);
    if(length == 0) {
        /* do something accordinlgy */
    } else if (length == 1) {
        /* do something accordingly */
    }
    auto mid = first;
    std::advance(mid,length/2);

    if(....) {
        return find_recursively(first, mid);
    }

    else if(...) {
        return find_recursively(mid, first);
    }
}

/* example calls: */
std::vector<int> vec = {....};
int result1 = find_recursively(vec.begin(), vec.end());
int array[] = {....};
int result2 = find_recursively(std::begin(array), std::end(array));
于 2013-03-07T20:58:51.480 回答
1

vector 支持索引运算符，所以不要使用向量切片作为函数参数。传递对向量和索引的引用。与数组相同的东西，但使用向量：

int find_recursively(const vector <int> &a, int low, int high)

您可以使用 a[index]（例如 a[low]）来访问您的值。但是如果 "high" == a.size，尝试使用 a[high] 会使你的 SW 崩溃。永远记得检查索引是否在向量内。

当您递归调用时，只需传递相同的“a”：

find_recursively(a, low, mid+1);

例如。

于 2013-03-07T20:46:21.227 回答