How to get a std::list<T>::iterator from an element of that list?

Viewed 7582

Given a std:: list

std::list< int > myList

and a reference (or a pointer) to an element in that list

int& myElement    |     int* pElement

So, basically I know the address of that element

How can I get an std::list<int>::iterator to that element efficiently?

A slow yet working example is

const_iterator it
for( it = myList.begin(); it != &myElement; ++it)
{
    // do nothing, for loop terminates if "it" points to "myElem"
}

Is there a quicker way? like

const_iterator it = magicToIteratorConverter( myList, myElem )

Case of vector (but I need list):

For a vector, you could do the following:

const int* pStart = &myVector[0] // address of first element
const int* pElement = &myElem; // address of my element
const idx = static_cast< int >( pElement- pStart ); // no need to divide by size of an elem

std::vector< int >::iterator it = myVector.begin() + idx;

Case of std::list:

4 Answers

This is actually a good question and IMHO a shame that there is no std way to do what OP has asked. If you understand that a list node looks essentially like this

struct list_node {
    list_node* prev;
    list_node* next;
    T yourType;
}

it is bad that there is no default way to get to the node (the iterator is a pointer to the node) if you have a pointer to yourType without searching through the whole container.


Since std is not helping you have to get your hands dirty:

#include <list>
#include <iostream>

//This is essentially what you are looking for:
std::list<int>::iterator pointerToIter (int* myPointer) {
    //Calculates the distance in bytes from an iterator itself
    //to the actual type that is stored at the position the
    //iterator is pointing to.
    size_t iterOffset = (size_t)&(*((std::list<void*>::iterator)nullptr));
    //Subtract the offset from the passed pointer and make an
    //iterator out of it
    std::list<int>::iterator iter;
    *(intptr_t*)&iter = (intptr_t)myPointer - iterOffset;
    //You are done
    return iter;
}

int main () {
    std::list<int> intList;
    intList.push_back (10);
    int* i1 = &intList.back ();
    intList.push_back (20);
    intList.push_back (30);
    int* i3 = &intList.back ();
    intList.push_back (40);
    intList.push_back (50);
    int* i5 = &intList.back ();

    std::cout << "Size: " << intList.size () << " | Content: ";
    for (const int& value : intList)
        std::cout << value << " ";
    std::cout << std::endl;

    intList.erase (pointerToIter (i1));
    intList.erase (pointerToIter (i3));
    intList.erase (pointerToIter (i5));

    std::cout << "Size: " << intList.size () << " | Content: ";
    for (const int& value : intList)
        std::cout << value << " ";
    std::cout << std::endl;
    return 0;
}

Output (to prove that it works as intended):

Size: 5 | Content: 10 20 30 40 50
Size: 2 | Content: 20 40

This works perfectly even if an implementation of std::list would use a different layout for the list-node or add some more members to it. I also included the assembler code generated to see that the function is essentially reduced to myPointer - 0x10 (0x10 = 16 is the size of 2 pointers on a 64bit machine).

Assembler (with at least -O1):

std::list<int>::iterator pointerToIter (int* myPointer) {
   0:   48 8d 47 f0             lea    rax,[rdi-0x10]
}
   4:   c3                      ret    

This is a dissected, formalized (C++11) and commented version of the very interesting solution of Xatian above. That solution is O(1) (that is one of the reasons it is so interesting), but it assumes some things that should be taken into account (Xatian's deep knowledge of the STL implementation of lists is the other reason why it is so interesting).

#include <iostream>
#include <list>
#include <cstdint>

int main(void)
{
    // ASSUMPTIONS:

    //  1.- nullptr == 0
    //  2.- A std::list iterator is an object that contains just one thing: a pointer to the body of the iterator.
    //  3.- A std::list iterator has a constructor that admits a pointer to a body provided by the user, which creates the iterator with that (assumed) existing body.


    using DataType = int;
    using DataList = std::list<DataType>;

    std::cout << "Nullptr= " << reinterpret_cast<size_t>(nullptr) << std::endl;
    std::cout << "Size of a pointer = " << sizeof(nullptr) << ", size of iterator = " << sizeof(DataList::iterator) << std::endl;

    static_assert(reinterpret_cast<size_t>(nullptr) == 0,
                "In this compiler, nullptr is not 0 and this will not work");


    // we have a list filled with something.
    DataList mylist{1,2,3,4};
    // and an iterator pointing to some data.
    DataList::iterator itaux{mylist.begin()};
    ++itaux;
    ++itaux;


    // 1. calculate the offset of the data in a list iterator w.r.t. the beginning of the iterator body

    DataList::iterator it{nullptr}; // call the iterator constructor. Nullptr becomes the address of the body where the iterator would store prev/next/data
                                // since nullptr is assumed to be 0, this is the same as to declare an iterator with its body at 0x00000000
    DataType & itp = *it; // this is a reference to the user's data in the iterator body
                      // that iterator is a fake and does not contain any data, but since we are only dealing with addresses, no problem...
    DataType * aitp = & itp; // this gets the address equivalent to the reference, which is at some point in memory from 0
    size_t iteroffset = reinterpret_cast<size_t>(aitp); // That address becomes, actually, the offset of the data w.r.t. the beginning of the iterator body

    std::cout << "Offset from iterator body start to data = " << iteroffset << std::endl;


    // 2. we can get the pointer to the data from our existing iterator
    DataType * mypointer = &(*itaux);

    // 3. we can create a valid iterator from the pointer to the data
    DataList::iterator iter;
    *(reinterpret_cast<intptr_t*>(&iter)) = reinterpret_cast<intptr_t>(mypointer) - iteroffset; // the address of the beginning of the body (mypointer-iteroffset) is stored into 
                                                                                                // the pointer to the body that the iterator actually is

    std::cout << "pointed element: " << (*iter) << std::endl;

    return(0);
}
Related