CODEWITHSUNDEEP
c++c++11
Fuzzy Stussy
Fuzzy Stussy

Reputation: 3

How do you sort a STL list without mutating the original?

Let's say I have something like this below:

#include <iostream> 
#include <list> 
using namespace std; 

int main() 
{ 
    list<int> mylist{ 1, 5, 3, 2, 4 }; 

    // sort
    mylist.sort(); 

    // printing the list after sort 
    for (auto it = mylist.begin(); it != mylist.end(); ++it) 
        cout << ' ' << *it; 
    return 0; 
}

However, if I do that, the original list is permanently changed. I know there are a lot of ways to do it. But specifically I want to know how I can sort it without making a copy of the original list explicitly. I want to do it with a function that is passed by value so that changes will be temporary.

Upvotes: 0

Views: 779

Answers (2)

Scheff&#39;s Cat
Scheff&#39;s Cat

Reputation: 20141

Re-arrange elements of a list without changing the list itself reminds me to something what I would call a proxy.

In this case, a std::vector of list iterators could be used as proxy. I would consider a std::vector as cache friendly (contiguous storage of contents) which may be an additional advantage concerning the performance of sorting.

The proxy vector is sorted with a custom predicate which considers the contents at iterators.

A sample:

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

int main()
{
  using listInt = std::list<int>;
  listInt myList{ 1, 5, 3, 2, 4 };
  // proxy for sorted access
  { std::vector<listInt::iterator> proxy;
    proxy.reserve(myList.size());
    for (listInt::iterator iter = myList.begin();
      iter != myList.end(); ++iter) {
      proxy.push_back(iter);
    }
    // sort proxy:
    std::sort(proxy.begin(), proxy.end(),
      [](listInt::iterator iter1, listInt::iterator iter2)
      {
        return *iter1 < *iter2;
      });
    // show proxy result
    for (listInt::iterator iter : proxy) {
      std::cout << ' ' << *iter;
    }
    std::cout << '\n';
  }
  std::cout << "The list (still in original order):\n";
  for (int value : myList) {
    std::cout << ' ' << value;
  }
  std::cout << '\n';
}

Output:

 1 2 3 4 5
The list (still in original order):
 1 5 3 2 4

Live Demo on coliru

Please note, as long as none of the list elements is deleted the list iterators are stable. (Get pointer to node in std::list or std::forward_list)

It might be questionable whether to store iterators instead of the values (which are plain int) is an advantage in any way. However, the size of iterator probably won't change if the list would contain elements of a "heavier" type where a deep copy would have a significant impact or even prohibited.

Googling a bit afterwards, I found this:

SO: Sort by proxy (or: sort one container by the contents of another) in C++

which might be related (IMHO).

Upvotes: 0

463035818_is_not_an_ai
463035818_is_not_an_ai

Reputation: 122460

I want to do it with a function that is passed by value so that changes will be temporary.

Sure you can do that:

#include <iostream> 
#include <list> 
using namespace std; 

void foo(list<int> l) {   // pass by copy !
    l.sort();
    // printing the list after sort 
    for (auto it = l.begin(); it != l.end(); ++it) 
        cout << ' ' << *it; 
}


int main() 
{ 
    list<int> mylist{ 1, 5, 3, 2, 4 }; 

    // sort
    foo(mylist);     


    return 0; 
}

Upvotes: 2

Related Questions