What is the best way to sort a vector that leaves the original unchanged?

Question

As the name says, I'm looking for a way to sort a vector without changing the original. My first idea, of course, is to create a copy of the vector before sorting, for example:

std::vector<int> not_in_place_sort(const std::vector<int>& original)
{
   auto copy = original;
   std::sort(copy.begin(), copy.end());
   return copy;
}

However, there may be a more efficient way to do sorting using the standard C ++ algorithm (maybe a combination of sortand transform?)

Answer 1

Here is my favorite. Sort the index, not the original array / vector.

#include <algorithm>

int main() {

    int intarray[4] = { 2, 7, 3, 4 };//Array of values
    //or you can have vector of values as below
    //std::vector<int> intvec = { 2, 7, 3, 4 };//Vector of values
    int indexofarray[4] = { 0, 1, 2, 3 };//Array indices

    std::sort(indexofarray, indexofarray + 4, [intarray](int index_left, int index_right) { return intarray[index_left] < intarray[index_right]; });//Ascending order.
    //have intvec in place of intarray for vector.


}

After that, the elements indexofarray[]will be 0, 2, 3, 1, intarray[]not change.

Answer 2

As stated in the comments, pass the argument to the function by value std::vector<int> original:

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

std::vector<int> not_in_place_sort(std::vector<int> original) {
    std::sort(original.begin(), original.end());
    return original;
}

int main() {
    std::vector<int> v = { 8, 6, 7, 2, 3, 4, 1, 5, 9 };
    std::vector<int> v2 = not_in_place_sort(v); // pass the vector by value
    std::cout << "v1: " << '\n';
    for (auto el : v) {
        std::cout << el << ' ';
    }
    std::cout << "\nv2: " << '\n';
    for (auto el : v2) {
        std::cout << el << ' ';
    }
}

, . , , RVO, vector move constructor return.

Answer 3

, - ( ), , , (, std::list). :

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

template <typename Container>
auto sorted_indices(const Container& c) {
  std::vector<typename Container::size_type> indices(c.size());
  std::iota(indices.begin(), indices.end(), 0);
  std::sort(indices.begin(), indices.end(), [&c](auto lhs, auto rhs) {
    return (*(std::next(c.begin(), lhs)) < *(std::next(c.begin(), rhs)));
  });
  return indices;
}

template <typename Container, typename Indices>
auto display_sorted(const Container& c, const Indices& indices) {
  std::cout << "sorted: ";
  for (auto&& index : indices) {
    std::cout << *(std::next(c.begin(), index)) << " ";
  }
  std::cout << std::endl;
}

template <typename Container>
auto display_sorted(const Container& c) {
  return display_sorted(c, sorted_indices(c));
}

template <typename Container>
auto display(const Container& c) {
  std::cout << "as provided: ";
  for (auto&& ci : c) std::cout << ci << " ";
  std::cout << std::endl;
}

int main() {
  // random access
  const std::vector<int> a{9, 5, 2, 3, 1, 6, 4};
  display(a);
  display_sorted(a);
  display(a);

  std::cout << "---\n";

  // no random access
  const std::list<int> b{9, 5, 2, 3, 1, 6, 4};
  display(b);
  display_sorted(b);
  display(b);
}

:

$ clang++ example.cpp -std=c++17 -Wall -Wextra
$ ./a.out
as provided: 9 5 2 3 1 6 4 
sorted: 1 2 3 4 5 6 9 
as provided: 9 5 2 3 1 6 4 
---
as provided: 9 5 2 3 1 6 4 
sorted: 1 2 3 4 5 6 9 
as provided: 9 5 2 3 1 6 4 

, - . : , , , , . , , : std::vector, std::next(v.begin(), n) - O(1), std::list, std::next(l.begin(), n) O(n).

Answer 4

int , ; , , , memcpy; ; , ; .

, . ; - , ; .

Answer 5

part_sort_copy. :

vector<int> v{9,8,6,7,4,5,2,0,3,1};
vector<int> v_sorted(v.size());
partial_sort_copy(begin(v), end(v), begin(v_sorted), end(v_sorted));

v , v_sorted {0,1,2,3,4,5,6,7,8,9}.