Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Is there any way to swap nodes in std::list?

Tags:

c++

I'm implementing LRUCache, where in unordered_map I store an iterator to list. When I move the most "fresh" element to the head, I need to iterator not changed.

I need to swap exactly nodes, not values in nodes. I'm finding the way to do it.

I tried to do it with std::iter_swap, but it's just implemented as std::swap(*it_first, *it_second)

std::list<std::string> list;
list.emplace_back("first");
list.emplace_back("second");

auto it_first = list.begin();
auto it_second = ++list.begin();

std::iter_swap(it_first, it_second);

assert(list.begin() == it_second); 

I need to swap two nodes to passed assert.

like image 458
Ivan Vankovich Avatar asked Aug 16 '19 10:08

Ivan Vankovich


People also ask

How do you swap nodes in a list of nodes?

Initialize another variable of node type. It should point to the first node in the list. Say temp = list;. Next we need to locate the nodes to swap and node previous to them. Run a loop from 1 to maximum position to swap. prev1 to temp if (i == pos1 - 1) (where i is loop counter variable).

Why is swapping data of nodes of linked lists so expensive?

Swapping data of nodes may be expensive in many situations when data contains many fields. It may be assumed that all keys in the linked list are distinct. Attention reader! Don’t stop learning now. Get hold of all the important DSA concepts with the DSA Self Paced Course at a student-friendly price and become industry ready.

How to swap nodes between two keys in a linked list?

Given a linked list and two keys in it, swap nodes for two given keys. Nodes should be swapped by changing links. Swapping data of nodes may be expensive in many situations when data contains many fields. It may be assumed that all keys in the linked list are distinct. Attention reader!

How to add a node at the beginning of a list?

/* Function to add Node at beginning of list. */ /* 2. Make next of new Node as head */ /* 3. Move the head to point to new Node */ /* Function to add Node at beginning of list. */ /* 2.


1 Answers

splice looks like it can do this with something like:

list.splice(it_first, list, it_second);

That says "Splice in it_second from myself (list, the second argument), before the first node in myself". The method guarantees that "the iterators to moved elements remain valid, but now refer into *this, not into other.", which implies the raw nodes themselves are moved.

like image 97
ShadowRanger Avatar answered Oct 23 '22 02:10

ShadowRanger