Can I create a view on a vector?

Question

I have a function which needs to sort the elements given. The original vector must not be altered, so I need a shallow copy of the vector. Since I do not need the elements to be copied itself, as they are only read, I decided to make a vector of pointers. Currently I have a simple loop filling the vector, but I wonder if a build-in/standard solution exists which even may be faster.

void calcFindMinLeftAndSort(std::vector<Location>& locationsComplete, std::vector<Location*>& locationsSorted) {
    // ...

    // copy data in new array, to keep the original untouched
    locationsSorted.reserve(locationsComplete.size());
    // looking for locationsSorted.assign(&elements)
    // yes, I could use for each instead
    for (size_t i = 0; i < locationsComplete.size(); i++)
        locationsSorted.emplace_back(&locationsComplete[i]);

    // sort 
    std::sort(locationsSorted.begin(), locationsSorted.end(), compare);
}

Additional info: The locationsComplete vector is sorted in a specific order which must not be altered. That vector is never changed during the runtime of the app. The sorted locationsSorted vector is consumed once by another function (could have been used in same function, but seemed clearer that way). After the result of the next function is returned, the locationsSorted vector is retired. As such it can be seen as a very short lived temporary vector.

Answer 1

What you can do, and probably want to do, is not use pointers at all - just sort the set of indices into locationsCompare, with the comparison function looking up the value in the original area. Easy-peasy with C++11:

template <typename T>
std::vector<size_t> get_sorted_positions(const std::vector<T> &v)
{
  std::vector<size_t> indices(v.size());

  std::iota(indices.begin(), indices.end(), 0); // indices now holds 0 ... v.size()-1
  std::sort(indices.begin(), indices.end(),
       [&v](size_t i_1, size_t i_2) { return v[i_1] < v[i_2]; }
  );

  return indices;
}

Notes:

• The only data getting mutated are the indices.
• Don't worry about returning a long vector; the compiler will use a move constructor, due to an optimization known as the NRVO.
• This code is mostly lifted from this answer, but the approach is basically folklore.
• You might also want to abstract away the fact that your input is a vector, and just take a reference to an arbitrary container (and return std::vector<typename Container::size_type>); or take a pair of iterators; or in C++20 - take any range.

Answer 2

The original vector must not be altered.

Consider to enforce this constraint by generating a vector of non owing pointers to const

template <class Container>
auto make_vector_of_const_pointers(Container& c)
{
    std::vector<typename Container::const_pointer> result;
    result.reserve(c.size());
    std::generate_n(std::back_inserter(result), c.size(),
                    [it = c.cbegin()]() mutable { return &(*(it++)); });
    return result;
}

See, e.g. here an example of usage, compared with a non const version.