CODEWITHSUNDEEP
c++stlc++11
Samaursa
Samaursa

Reputation: 17241

std::forward_list swap() implementation in C++11

My assumption is that in a std::list<> the swap function for the list itself is done by swapping the anchor node. The node can access the previous node and update the previous node's next pointer easily to point to the anchor of the other list; but this cannot be done in std::forward_list (well, it can be, it is just very costly).

If my assumption is correct, how is swap() implemented in std::forward_list in an efficient manner? And while we are at it, how is swap() implemented for the iterators of std::forward_list?

Upvotes: 3

Views: 839

Answers (3)

Terry Mahaffey
Terry Mahaffey

Reputation: 11981

I think you're confused (or I am confused as to what you're asking). std::forward_list::swap(std::forward_list& other) is trivial, with each list object exchanging pointers to the head of their list (and any other member variables) - just like std::list.

The iterator object doesn't have a swap method. The contained object might, or may use the global swap method - but that operates on the objects, and doesn't mutate the list itself or its nodes.

Upvotes: 3

templatetypedef
templatetypedef

Reputation: 372982

This is completely implementation-specific, but if the forward lists are implemented by having the class just store a pointer to the first and last linked list cells, then swap could just swap those two pointers. Since forward-linked lists don't have any back pointers, there aren't any more updates to be made and the whole operation can be done in O(1).

As for swap with iterators, this doesn't actually exchange the linked list cells between the two lists; it just has the first iterator point to the cell referenced by the second iterator and vice-versa. If you want to swap the values being pointed at, then this can be done by just modifying the objects in the linked list cells so that they change values. You don't need to rewire the lists in any way.

Hope the helps!

Upvotes: 3

Jason
Jason

Reputation: 32530

A std::forward_list is simply a singly-linked rather than doubly-linked list like std::list, therefore you can simply swap the head and tail pointers of the list to accomplish a swap() operation.

Upvotes: 5

Related Questions