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

Question

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.

The only way is to make a copy of the list. Whether it's an explicit copy or in any way hidden behind a layer of abstraction, it's still a copy. — DeiDei, Apr 16 '20 at 11:18
@Fuzzy Stussy And what is the problem?! Pass the list by value to your function. — Vlad from Moscow, Apr 16 '20 at 11:19
Passing by value is a copy. You can't have two lists without a copy, that's just not possible. — freakish, Apr 16 '20 at 11:19
sorting without making a copy, but keeping the original unmodified ? how should that be possible? Why don't you want to make a copy and keep the original unmodified at the same time? — 463035818_is_not_an_ai, Apr 16 '20 at 11:19
Implement a basic sorting algorithm yourself that uses `std::swap` to rearrange the values in the list, without changing the list itself. — Sam Varshavchik, Apr 16 '20 at 11:20
You want to rearrange the elements without rearranging the elements? — Galik, Apr 16 '20 at 11:25
You could make some kind of flat copy of your list elements - storing iterators to all nodes of the list in a `std::vector::iterator>`. As long as you don't erase anything in the `std::list`, the iterators remain valid. With the appropriate custom predicate, you can sort the `std::vector`, and this will not effect the list itself. — Scheff's Cat, Apr 16 '20 at 11:25
I know that in C++ everything is passed by the value to the calling function. How can I use that logic to sort the list without touching the original list? — Fuzzy Stussy, Apr 16 '20 at 11:31
it is not clear what problem you are facing, instead of entering more discussions, I just posted "the obvious" as answer. Still, out of curiosity, I would be interested in what is your "problem" — 463035818_is_not_an_ai, Apr 16 '20 at 11:33
By definition, sorting a list changes the list, since it reorders elements. If you want to keep the original list, then it is necessary create a copy before sorting - and sort either the original or the copy (not both). You can't have your cake (a sorted list) and eat it to (have the unsorted version without creating a copy). — Peter, Apr 16 '20 at 11:44

score 2 · Accepted Answer · answered Apr 16 '20 at 11:29

2

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; 
}

answered Apr 16 '20 at 11:29

463035818_is_not_an_ai

109,796
11
89
185

That makes sense. So you can actually pass the entire list as an argument. Thanks! – Fuzzy Stussy Apr 16 '20 at 11:37
Although this doesn't meet the requirement of not copying the list. Passing a list by value works by passing a copy. – Peter Apr 16 '20 at 11:47
@Peter original question was changed from "without making a copy of the original list" to "without making a copy of the original list explicitly". Not sure what that is supposed to mean though – 463035818_is_not_an_ai Apr 16 '20 at 11:50
Maybe the OP is looking for an equivalent to LINQ's [OrderBy](https://learn.microsoft.com/en-us/dotnet/api/system.linq.enumerable.orderby?view=netframework-4.8) extension method. The function should in C++return something like a list of reference wrappers, or rather an iterator so that one can do deferred execution... – Peter - Reinstate Monica Apr 16 '20 at 11:52
@Peter-ReinstateMonica actually I wasnt sure what OP is looking for, the question is a bit unclear and instead of discussing I decided to simply post that. Their comment suggests that there was just a misunderstanding about passing a list as parameter – 463035818_is_not_an_ai Apr 16 '20 at 11:55
Sorry about the confusion. Basically I didn't want to make an actual copy by myself but to make a copy with passing by value. That way the original remains untouched. @idclev463035818 showed me exactly what I needed. Thanks – Fuzzy Stussy Apr 16 '20 at 19:18

Scheff's Cat · Answer 2 · 2020-04-16T11:51:27.283

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).

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

2 Answers2