CODEWITHSUNDEEP
c++linked-liststdlist
user4385532
user4385532

Reputation:

I can move elements within the std::list without invalidating iterators nor references, but how?

From cppreference article on std::list:

Addition, removal and moving the elements within the list or across several lists does not invalidate the iterators or references. An iterator is invalidated only when the corresponding element is deleted.

And indeed, this is the case while sorting elements. From cppreference article on std::list::sort:

This function also differs from std::sort in that it does not require the element type of the list to be swappable, preserves the values of all iterators, and performs a stable sort.

But how may I arbitrarily swap the positions of two elements while preserving the values of all iterators?

For example, assume I have a list:

std::list<int> l({1, 2, 3, 4});
auto it = l.begin(), jt = ++l.begin();

Now it points to 1 and jt points to 2. Can I reorder this list so that 2 comes before 1, but it still points to 1?

I can do:

std::swap(*it, *jt);

But then, while 2 will come before 1, I will not preserve the values of iterators, since clearly it will point to 2.

Given the aforementend citation from cppreference, I suppose it should be possible to achieve what I want to achieve; but how?

Edit: To make things clear: One more example:

std::list<int> l({2, 1, 3, 4, 5});
auto it = l.begin(), jt = ++l.begin();

Now it points to 2 and jt points to 1.

std::list::sort has the semantics I'm looking for:

l.sort();

Now the list's ordering is: 1, 2, 3, 4, 5, however it is still pointing at 2 and jt is still pointing at 1.

On the other hand, std::swap(it, jt) nor std::swap(*it, *jt) does not have the semantics I want. Calling any of them will make it point to 1 and jt point to 2. (ideone proof)

Upvotes: 5

Views: 4776

Answers (2)

HolyBlackCat
HolyBlackCat

Reputation: 96430

But how may I arbitrarily swap the positions of two elements while preserving the values of all iterators?

As suggested by @cpplearner, use .splice().

It can operate on individual elements or ranges. It can also transfer elements across lists.

Here's a simple example demonstrating how to move a single element.

std::list<int> list{1,2,3,4,5};

// This element will be moved
auto source = std::find(list.begin(), list.end(), 4);

// It will be inserted before this element
auto destination = std::find(list.begin(), list.end(), 2);

list.splice(destination, list, source);
// ^                      ^
// |                      `- A list to move from
// `- A list to move to   

// Prints `1 4 2 3 5`.
for (int it : list) std::cout << it << ' ';

Upvotes: 9

Sid S
Sid S

Reputation: 6125

You're swapping values. Not iterator values. So the iterators stay the same, while the values they point to change (are swapped).

Think about iterators like pointers, at least in this respect.

So what you would do to swap the iterators and the values is just that:

std::swap(*it, *jt);
std::swap(it, jt);

Upvotes: -1

Related Questions