mercredi 9 juin 2021

Is it possible to insert/erase an element from std::list in O(1) if I store the iterators somewhere. Iterators are kind of pointers.right?

say

    list<int> l={1,2,3,4,5};
    typedef list<int> lst ;
    lst l={1,2,3,4,5};
    lst::iterator i=l.begin();
    advance(i,2);//let the time complexity be n
    l.erase(i);//what is the time complexity here?
    for(auto i:l)
        cout<<i<<endl;

Since list is implemented as doubly linked list, can it not find its previous and next pointer join both and remove the middle one in o(1) time?

Aucun commentaire:

Enregistrer un commentaire