c++ - 为什么我的模板化函数需要从一个迭代器到另一个迭代器的转换？

Question

我正在尝试实现一个二进制搜索树容器。目前，我必须实现一个find()函数，该函数能够返回迭代器或常量迭代器。我选择重载find函数以适应两种可能性

MyIterator<treepair> find(const key& x)
{
    return tree_search<MyIterator<treepair>>(root,x);   
}
const_MyIterator<treepair> find(const key& x) const
{
    return tree_search<const_MyIterator<treepair>>(root,x); 
}

然后，函数tree_search通过遍历树来递归地找到包含所需键的节点:

template<typename iterator>
iterator tree_search(Node<treepair>* x, const key& y) const
{
    if(x == nullptr)
    {
        std::cout<<"element not found"<<std::endl;
        iterator x = end();//HERE I HAVE A PROBLEM
        return x;
    }
    else if (y == x->value.first)
    {
        iterator i{x,tree_maximum()};
        std::cout<<"element found"<<std::endl;
        return i;
    }
    if(y < x->value.first) 
        return tree_search<iterator>(x->left,y);
    else return tree_search<iterator>(x->right,y);
}

现在，end()函数被重载以提供const_iterator和常规迭代器:

MyIterator<treepair> end(){
return MyIterator<treepair>{nullptr,tree_maximum()};
}

const_MyIterator<treepair> end() const{
return const_MyIterator<treepair>{nullptr,tree_maximum()};
}

但是我收到这个错误

test_on_iterators.cc:508:12: error: conversion from ‘const_MyIterator<std::pair<int, int> >’ to non-scalar type ‘MyIterator<std::pair<int, int> >’ requested
      iterator x = end();

是否由于类型之间的转换要求而导致此错误？编译器不是应该根据必须产生的迭代器类型来选择所需的end()函数吗？

Answer 1

Isn't the compiler supposed to choose the wanted end() function according to the iterator type it has to produce?

没有。
tree_search()是 const方法。这意味着它的 this指针指向 const对象(即使调用了 tree_search()对象不是 const)。

这样，当 tree_search()内部调用 end()时，它将调用可在 const对象上调用的重载。该重载返回 const_MyIterator。然后 tree_search()尝试将该 const_MyIterator分配给非const MyIterator，这是您收到错误的地方，因为没有定义从 const_MyIterator到 MyIterator的转换。

您需要将 x设为 const_MyIterator，以匹配 const版本的 end()返回的内容。

您还应该使 tree_search()也返回 const_MyIterator，而不是返回非const iterator。如果您希望 tree_search()返回非常量 Iterator，则不要将其声明为 const方法。