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.

With that solution, you need to be aware that any operation on original container that cause it to be resized would invalidate the pointers in the second (sorted) container. — Phil1970, Sep 10 '19 at 23:17
storing the sorted index would be more compact compared to storing the pointers — phuclv, Sep 12 '19 at 12:40

einpoklum · Accepted Answer · 2022-10-24T08:14:09.933

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. The indices would still be a vector though.

As I pointed out "The original vector must not be altered". Interesting concept though. — Gunnar Bernstein, Sep 14 '19 at 14:59
@GunnarBernstein: The original vector is not being altered, einpoklum is only doing lookups. (through a const reference, which aids in preventing modification) — Ben Voigt, Sep 14 '19 at 15:26

score 2 · Answer 2 · answered Sep 10 '19 at 22:58

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.

The const is probably for "security" reasons on not altering the original vector. I do not see a benefit in a short lived functional use. Not really my question. — Gunnar Bernstein, Sep 14 '19 at 15:04

Can I create a view on a vector?

2 Answers2