Elegant way to create a vector of reference

Question

I have a vector of Foo

vector<Foo> inputs

Foo is a struct with some score inside

struct Foo {
    ...
    float score
    bool winner
}

Now I want to sort inputs by score and only assign winner to the top 3. But I don't want to change the original inputs vector. So I guess I need to create a vector of reference then sort that? Is it legal to create a vector of reference? Is there an elegant way to do so?

Answer 1

The only example code given was for pointers, and the IMO far more fitting std::reference_wrapper was only mentioned, with no indication of how it might be used in a situation like this. I want to fix that!

---

Non-owning pointers have at least 3 drawbacks:

• the visual, from having to pepper &, *, and -> in code using them;
• the practical: if all you want is a reference to one object, now you have a thing that can be subtracted from other pointers (which may not be related), be inc/decremented (if not const), do stuff in overload resolution or conversion, etc. – none of which you want. I'm sure everyone is laughing at this and saying 'I'd never make such silly mistakes', but you know in your gut that, on a long enough timeline, it will happen.
• and the lack of self-documentation, as they have no innate semantics of ownership or lack thereof.

---

I typically prefer std::reference_wrapper, which

• clearly self-documents its purely observational semantics,
• can only yield a reference to an object, thus not having any pointer-like pitfalls, and
• sidesteps many syntactical problems by implicitly converting to the real referred type, thus minimising operator noise where you can invoke conversion (pass to a function, initialise a reference, range-for, etc.)... albeit interfering with the modern preference for auto – at least until we get the proposed operator. or operator auto – and requiring the more verbose .get() in other cases or if you just want to avoid such inconsistencies. Still, I argue that these wrinkles are neither worse than those of pointers, nor likely to be permanent given various active proposals to prettify use of wrapper/proxy types.

I'd recommend that or another vocabulary class, especially for publicly exposed data. There are experimental proposal(s) for observer_ptrs and whatnot, but again, if you don't really want pointer-like behaviour, then you should be using a wrapper that models a reference... and we already have one of those.

---

So... the code in the accepted answer can be rewritten like so (now with #includes and my preferences for formatting):

#include <algorithm>
#include <functional>
#include <vector>

// ...

void
modify_top_n(std::vector<Foo>& v, int const n)
{
    std::vector< std::reference_wrapper<Foo> > tmp{ v.begin(), v.end() };

    std::nth_element( tmp.begin(), tmp.begin() + n, tmp.end(),
        [](Foo const& f1, Foo const& f2){ return f1.score > f2.score; } );

    std::for_each( tmp.begin(), tmp.begin() + n,
        [](Foo& f){ f.winner = true; } );
}

This makes use of the range constructor to construct a range of reference_wrappers from the range of real Foos, and the implicit conversion to Foo& in the lambda argument lists to avoid having to do reference_wrapper.get() (and then we have the far less messy direct member access by . instead of ->).

Of course, this can be generalised: the main candidate for factoring out to a reusable helper function is the construction of a vector< reference_wrapper<Foo> > for arbitrary Foo, given only a pair of iterators-to-Foo. But we always have to leave something as an exercise to the reader. :P

Answer 2

Here two different way of creating a vector<Foo*>:

vector<Foo*> foor; 
for (auto& x:inputs)
   foor.push_back(&x);

vector<Foo*> foob(inputs.size(),nullptr); 
transform(inputs.begin(), inputs.end(), foob.begin(), [](auto&x) {return &x;}); 

You can then use standard algorithms to sort your vectors of pointers without changing the original vector (if this is a requirement):

// decreasing order according to score
sort(foob.begin(), foob.end(), [](Foo*a, Foo*b)->bool {return a->score>b->score;}); 

You may finally change the top n elements, either using for_each_n() algorithm (if C++17) or simply with an ordinary loop.

Online demo