Can you convert a pointer to an element in std::forward_list to the iterator to this element?

Question

Since the std::forward_list is implemented as a single-linked list, its iterator should be just a pointer to the underlying element ± some offset.

Is there a way to convert a pointer to an element on a list to the iterator to this element without iterating through the entire 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;
}

Answer 1

Short answer: Yes, I could hack a function makeIterator that does that:

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);
}

Essentially, it does some pointer arithmetic to derive the address of the underlying list node and constructs an iterator from the derived pointer. The function learnOffset returns the offset needed in the pointer arithmetics.

See the long answer for details on how the function learnOffset is implemented. Note however, that this solution depends on the implementation of your C++ standard library. I am not aware of any public API function that does what you are asking for.

Long answer

I studied the implementation of the forward list iterator in the file /usr/include/c++/11/bits/forward_iterator.h and specifically the implementation of template<typename _Tp> struct _Fwd_list_iterator. It exposes a public member variable that points at the node in the linked list:

_Fwd_list_node_base* _M_node;

and is used for example from the dereferencing operator:

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

Reading the source code further suggests that the value stored in a list node is stored by value in the node itself. If so, there should be a constant offset between the pointer to that value and the list node itself. To test that, I wrote the function 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());
}

which returns 8 bytes. We can now directly call this function from the implementation of makeIterator above.

The above implementation of learnOffset leaves a lot to be desired. This code should just be considered a proof-of-concept.

Edited: Made learnOffset a template and to return offset in bytes.

Answer 2

It is generally impossible to convert pointers to iterators (without searching the whole container/range). This is only possible for contiguous iterators, and std::forward_list isn't a contiguous container.

Answer 3

The iterator to a std::forward_list is probaly a Node of the List. Unfortunately there is no compatible way to access the structure of the Node.

If you have a certain compiler and know its underlying Node and iterator implemtation, then you could simply access it with some simple pointer arithmetic.

So, basically yes, possible, but this is of totally incompatible and higly dangerous.

Then, the answer is. With the given prototype of the function, it is not possible.

If you change the prototype of the function and give it a reference to the list, then we can simply iterate along the complete std::forward_list and compare pointers.

This could then look like this:

#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';
}