-1

我有一个模板函数，用于 .find 用于我收到的用于分配的 sorted_vector 头文件中的向量。我正在使用 BOOST 库对不同的方法/构造函数等进行单元测试，以确保没有错误并在引入错误时使代码更加万无一失。我刚刚对这两个代码块之间的区别提出了一个简短的问题：

template <typename T>
typename sorted_vector<T>::iterator sorted_vector<T>::find( value_type const& value ) const {
    auto front = beg_;
    auto back = end_;

        for( ;; ) {
            auto p = (back - front)/2 + front;
            if( p == end_ )
                return p;
            else if( *p == value )
                return p;
            else if( *p > value )
                back = p;
            else
                front = p + 1;
        }
}

而这个块：

template <typename T>
typename sorted_vector<T>::iterator sorted_vector<T>::find( value_type const& value ) const {
    auto front = beg_;
    auto back = end_;

    for( ;; ) { 
        auto p = (back - front)/2 + front;
        if( p == back )
            return end_;
        else if( *p == value )
            return p;
        else if( *p > value )
            back = p;
        else
            front = p + 1;
     }
}

我的问题是关于无限 for 中的第一个 if 语句。在第一个代码块中，如果它找不到值而不是结尾，它是否在每次遍历向量时都返回中间值？或者这两个 if 语句之间的主要区别是什么？

谢谢。

编辑 beg_ 和 end_ 它们以这种方式实例化：

private beg_;
private end_;

以下是它们的正常使用方式：

sorted_vector() : beg_(nullptr), end_(nullptr), cap_(nullptr) { }
iterator begin() { return iterator( beg_ ); }
iterator end() { return iterator( end_ ); }
4

2 回答 2

6

好吧，看起来beg_和end_是类的成员变量，用于指定存储序列的开始和结束[beg_, end_)。由于这些值永远不会改变，所以代码的第一个版本根本不正确：在二进制搜索期间，值p将没有机会变得等于end_（除了少数特定情况，例如当键大于任何存储的值）。如果键不存在于数组中并且不大于数组中的最后一个值，我希望第一个版本陷入无限循环。

同时，第二个版本正确实现（假设它没有其他错误）：它检查原始序列p的当前子段[front, back)的结尾，而不是原始序列的结尾。

无论如何，如果不知道那里遵循了哪些约定，就不可能完全分析这段代码。end_例如，什么是？是数组最后一个元素的迭代器吗？或者它是数组的最后一个元素的迭代器？

于 2013-09-25T15:37:51.857 回答
1

它们是有区别的。您对它所做的事情是完全正确的，但请记住“back = p;”这一行。

在几个循环之后会发生什么，back 很可能会变成一个更大的值。（因为如果 p 大于某个值，则将 back 设置为 p）

于 2013-09-25T15:36:35.573 回答