CODEWITHSUNDEEP
c++algorithmc++11
Martin Drozdik
Martin Drozdik

Reputation: 13303

How can I sort a portion of std::list?

#include <iostream>
#include <list>
#include <algorithm>

int main()
{
    std::list<int> numbers = {1, 3, 0, -8, 5, 3, 1};
    auto positionInMiddle = std::find(numbers.begin(), numbers.end(), -8);

    std::sort(positionInMiddle, numbers.end()); // This doesn't work,
                                                // Needs random access iterator.

    numbers.sort(); // This sorts the entire list.

    for (int i : numbers)
        std::cout << i << std::endl;
    return 0;
}

Is there some trick I can use? For example if there was a method that swaps two nodes in the list, then I could use mergesort.

Upvotes: 2

Views: 1056

Answers (2)

BlackMamba
BlackMamba

Reputation: 10254

You can't use std::sort to sort std::list, because std::sort requires iterators to be random access, and std::list iterators are only bidirectional.

However, std::list has a member function sort that will sort it:

Upvotes: -2

jrok
jrok

Reputation: 55395

Lists have constant time insertions and removal, so making a temporary list with splice to sort is quite fast insertion wise (still linear in copying elements, unfortunately):

#include <iostream>
#include <list>
#include <algorithm>

int main()
{
    std::list<int> numbers = {1, 3, 0, -8, 5, 3, 1};
    auto positionInMiddle = std::find(numbers.begin(), numbers.end(), -8);

    std::list<int> temp;
    temp.splice(temp.end(), numbers, positionInMiddle, numbers.end());
    temp.sort();
    numbers.splice(numbers.end(), temp, temp.begin(), temp.end());

    for (int i : numbers)
        std::cout << i << std::endl;
    return 0;
}

Upvotes: 4

Related Questions