c++ 可以将std::forward_list中元素的指针转换为该元素的迭代器吗?

aamkag61  于 2022-12-01  发布在  其他
关注(0)|答案(3)|浏览(147)

由于std::forward_list是作为一个单链表实现的,它的迭代器应该只是一个指向底层元素的指针±某个偏移量。
有没有一种方法可以将指向列表中某个元素的指针转换为指向该元素的迭代器,而无需迭代整个列表?

#include <forward_list>

template<typename T>
typename std::forward_list<T>::iterator makeIterator(T *element)
{
    // magic here
}

int main()
{
    std::forward_list<int> list;
    list.emplace_front(101);
    auto i = makeIterator(&list.front());
    return i == list.begin() ? 0 : 1;
}
bihw5rsg

bihw5rsg1#

简短回答:是的,我可以破解一个函数makeIterator来实现这一点:

template<typename T>
typename std::forward_list<T>::iterator makeIterator(T *element)
{
  typedef typename std::forward_list<T>::iterator Iter;
  typedef decltype(Iter()._M_node) NodeType;
  static int offset = learnOffset<T>();
  auto node = reinterpret_cast<NodeType>(reinterpret_cast<uint8_t*>(element) - offset);
  return Iter(node);
}

实际上,它执行一些指针运算来导出底层列表节点的地址,并根据导出的指针构造一个迭代器。函数learnOffset返回指针运算中所需的偏移量。
关于learnOffset函数是如何实现的详细信息,请参阅详细答案。但是请注意,此解决方案取决于您的C++标准库的实现。我不知道有任何公共API函数可以实现您所要求的功能。

长长的回答

我研究了/usr/include/c++/11/bits/forward_iterator.h文件中的forward列表迭代器的实现,特别是template<typename _Tp> struct _Fwd_list_iterator的实现,它公开了一个指向链表中节点的公共成员变量:

_Fwd_list_node_base* _M_node;

例如,从取值运算符中使用:

reference
  operator*() const noexcept
  { return *static_cast<_Node*>(this->_M_node)->_M_valptr(); }

阅读源代码可以进一步发现,存储在列表节点中的值是 by value 存储在节点本身中的。如果是这样,那么在指向该值的指针和列表节点本身之间应该有一个常量偏移量。为了测试这一点,我编写了函数learnOffset

template <typename T>
int learnOffset() {
  // Populate a list with some data
  std::forward_list<T> list;
  for (int i = 0; i < 10; i++) {
    list.emplace_front(T());
  }

  // Iterate over the populated list and the address differences
  // between the stored element and the list node address held
  // by the iterator.
  std::unordered_set<int> offsets;
  for (auto i = list.begin(); i != list.end(); i++) {
    uint8_t* valAddr = reinterpret_cast<uint8_t*>(&(*i));
    auto node = reinterpret_cast<uint8_t*>(i._M_node);
    offsets.insert(valAddr - node);
  }

  // We expect exactly one difference. If not, produce an error.
  if (offsets.size() != 1) {
    std::cerr << "Couldn't learn forward_list iterator offset :-(" << std::endl;
    abort();
  }
  return *(offsets.begin());
}

返回8字节,我们现在可以直接从上面makeIterator的实现中调用这个函数。
上面的learnOffset实现还有很多需要改进的地方。这段代码只应被视为概念验证

**已编辑:**使learnOffset成为模板并返回偏移量(以 * 字节 * 为单位).

mspsb9vt

mspsb9vt2#

std::forward_list的迭代器可能是 ListNode。遗憾的是,没有兼容的方法来访问 Node 的结构。
如果你有一个特定的编译器,并且知道它的底层 Nodeiterator实现,那么你可以简单地用一些简单的指针算法来访问它。
所以,基本上是的,可能的,但这是完全不相容的和高度危险的。
那么,答案是。以给定的函数原型,这是不可能的。
如果你改变了函数的原型,并给它一个对列表的引用,那么我们就可以简单地沿着完整的std::forward_list迭代并比较指针。
这可能如下所示:

#include <forward_list>
#include <iostream>
#include <iterator>

template<typename T>
typename std::forward_list<T>::iterator makeIterator(std::forward_list<T>& list, T* element)
{
    typename std::forward_list<T>::iterator i = list.begin();
    for (; i != list.end(); ++i)
        if (&*i == element)
            return i;
    return i;
}
int main() {
    std::forward_list<int> list{};
    list.push_front(1);
    list.push_front(2);
    list.push_front(3);

    std::forward_list<int>::iterator iter = std::next(list.begin());
    int* valuePtr = &*iter;
    std::cout << *valuePtr << '\n';

    std::forward_list<int>::iterator calculatedIter = makeIterator(list, valuePtr);
    std::cout << *calculatedIter << '\n';
}
moiiocjp

moiiocjp3#

通常不可能将指针转换为迭代器(不搜索整个容器/范围)。这只可能用于 * 连续迭代器 *,并且std::forward_list不是连续容器。

相关问题