2

It seems to me given what I know about linked lists that this should be possible but I haven't found anywhere that has the answer so I'm asking here.

Given two iterators to items in the same list. I'd like to take the item pointed to by iterator "frm" and "insert" it into the list before the item pointed to by iterator "to".

It seems that all that is needed is to change the pointers on the items in the list pointing to "frm" (to remove "frm"), then changing the pointers on the item pointing at "to" so that it references "frm" then changing the pointers on "frm" node to point to "to".

I looked everywhere for this and couldn't find an answer.

NOTE that I cannot use splice as I do not have access to the list only the iterators to the items in the list.

template <typename T>
void move(typename std::list<T>::iterator frm, typename std::list<T>::iterator to) {
    //remove the item from the list at frm

    //insert the item at frm before the item at to
}
ceorron
  • 1,230
  • 1
  • 17
  • 28
  • 1
    An iterator cannot be used to remove itself from it's container without also knowing which container it belongs to. It also can't be used to append new items to a container. Iterators don't necessarily know what container they belong to. – François Andrieux May 29 '17 at 14:25

2 Answers2

1

Iterators contain the minimal information required to point to a piece of data, what you are missing is the fact that linked lists have other bookkeeping that go along with it as well, so essentially the list class looks something like the following

template <typename Type>
class list {
    int size; // for O(1) size()
    Type* head;
    Type* tail;

    class Iterator {
        Type* element;
        // no back pointer to list<Type>*
    };
    ...
};

And to remove an element from the list you would need to update those data members as well. And to do that an iterator must contain a back pointer to the list itself, which is not required as per the interface offered for most iterators. Notice also that the algorithms in the STL do not actually modify the bookkeeping for the containers the operate on, only maybe swap elements, and rearrange things.

I would encourage you took look into the <algorithm> header, as well as into facilities like std::back_inserter and std::move_iterator to get an idea of how iterators are wrapped to actually modify the container they represent.

Curious
  • 20,870
  • 8
  • 61
  • 146
1

The implementation of this is implementation defined but the c++ standard allows the use of iter_swap though it doesn't do this exactly. This maybe optimized to swap the pointers on the values held in the linked list similar to what I have described effectively reordering the items in the list without a full swap needed.

iter_swap() versus swap() -- what's the difference?

ceorron
  • 1,230
  • 1
  • 17
  • 28