CODEWITHSUNDEEP
c++liststl
heeat
heeat

Reputation: 158

List and Iterator after and before sorting behavior

I am going through STL in cpp and I found List.

Wrote below code :

#include <bits/stdc++.h>
using namespace std;

int main()
{
    list<int> ls;
    ls.push_back(23);
    ls.push_front(34);
    ls.push_front(39);
    ls.push_front(334);
    ls.push_front(434);
    ls.push_front(7834);
    ls.push_front(634);
    ls.push_front(934);

    list<int>::iterator it10 = ls.begin();
    list<int>::iterator it11 = ls.end();
    list<int>::reverse_iterator it12 = ls.rbegin();
    list<int>::reverse_iterator it13 = ls.rend();

    ls.sort();

    for (auto it = it10; it != it11; it++)
    {
        cout << *(it) << "\n";
    }
}

So here I am defining iterators before sorting the list and I get Output as :

934
7834

But if I sort the before defining the Iterators like:


ls.sort();

list<int>::iterator it10 = ls.begin();
list<int>::iterator it11 = ls.end();
list<int>::reverse_iterator it12 = ls.rbegin();
list<int>::reverse_iterator it13 = ls.rend();

I am getting correct output :

23
34
39
334
434
634
934
7834

Why is it behaving like this how does this work? please explain. Thanks!

Upvotes: 0

Views: 219

Answers (1)

463035818_is_not_an_ai
463035818_is_not_an_ai

Reputation: 122717

it10 is an iterator to the element 934 in the list. it11 is an iterator to the end of the list. After sorting it10 is an iterator to the element 934 and it11 is an iterator to the end of the list. The elements starting from 934 after sorting are:

943 
7834

From cppreference about std::list::sort:

std::sort requires random access iterators and so cannot be used with list . 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.

With std::sort iterators get invalidated. Thats not the case with std::list::sort. Sloppy speaking, iterators into std::lists are more stable than others generally. In your example it10 and it11 still point to the same elements. After sorting, the element that was at the first position is no longer at the first position. It is at the second but last position and it11 still points to the lists end.

Consider that a std::list is a linked list, to change order it isnt necessary to modify or move elements to other postion in memory, only links have to be updated.

Upvotes: 1

Related Questions