Как вы сортируете список STL, не изменяя оригинал?

Question

Допустим, у меня есть что-то вроде этого ниже:

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

Однако, если я это сделаю, исходный список будет навсегда изменен. Я знаю, что есть много способов сделать это. Но, в частности, я хочу знать, как я могу отсортировать это без явной копии оригинального списка. Я хочу сделать это с помощью функции, которая передается по значению, чтобы изменения были временными.

Answer 1

Я хочу сделать это с помощью функции, которая передается по значению, чтобы изменения были временными.

Конечно, вы можете сделать это:

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

Answer 2

Переупорядочение элементов списка без изменения самого списка напоминает мне нечто, что я бы назвал прокси.

В этом случае std::vector итераторов списка можно использовать в качестве прокси. Я бы посчитал std::vector дружественным для кэша (непрерывное хранение содержимого), что может быть дополнительным преимуществом в отношении производительности сортировки.

Прокси-вектор сортируется с помощью пользовательского предиката, который учитывает содержимое в итераторах.

Образец:

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

Выход:

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

Живая демонстрация на coliru

Обратите внимание, что пока ни один из элементов списка не удален, итераторы списка стабильны. ( Получить указатель на узел в std :: list или std :: forward_list )

Может быть сомнительно, хранить ли итераторы вместо значений (которые являются простыми int) преимущество в любом случае. Тем не менее, размер итератора, вероятно, не изменится, если список будет содержать элементы «более тяжелого» типа, где глубокая копия будет иметь значительное влияние или даже запрещена.

---

После этого немного погуглим, Я нашел это:

SO: Сортировать по прокси (или: отсортировать один контейнер по содержимому другого) в C ++

, что может быть связано (IMHO).