How can I return a container of pointers using std::sample on a container of ?

Question

I have a vector<T> input from which I want to get n randomly selected elements via the std::sample algorithm from STL C++17 (http://en.cppreference.com/w/cpp/algorithm/sample). The code works fine in case results is of type vector<T>.

Code example 1 (no pointers returned)

auto getSamples(unsigned int noSamples, const vector<T> &input)
{
    vector<T> results;
    std::mt19937 twisterEngine;
    std::sample(input.begin(), input.end(), std::back_inserter(results),
        noSamples, twisterEngine);
    return results;
}

However, I am looking not for values/copies of the elements stored in input but I would like to get pointers to the n sampled elements. Are there any tips how I can get pointer returned by vector<T*> results using only standard c++ code (e.g. not using boost library, etc.)? How do I need to adjust following code to get it done?

Code example 2 (intention to get pointers returned)

auto getSamples(unsigned int noSamples, const vector<T> &input)
{
    vector<T*> results;
    std::mt19937 twisterEngine;
    std::sample(input.begin(), input.end(), std::back_inserter(results),
        noSamples, twisterEngine);
    return results;
}

I would *not* return pointers to samples, because `input` is a function local vector, so you'd be passing back out a vector of dangling pointers. The only time this would be safe is if `input` was passed by `const&` and you could guarantee `input` would exist for the lifetime of `results` — Cory Kramer, Oct 16 '17 at 18:32
Code adjusted so that input is passed by const&. However, I would like to return pointers in results. — StefanW, Oct 16 '17 at 18:39
i dont think `sample` is the right algorithm. I would fill a vector with all pointers available and then pick the first `n` elements of a random permutation of that vector — 463035818_is_not_an_ai, Oct 16 '17 at 18:43
...erm or use `sample` on the vector that contains all the pointers (you need to fill that first). was a bit confused, because first time I see `sample` — 463035818_is_not_an_ai, Oct 16 '17 at 18:44

score 3 · Answer 1 · edited Oct 17 '17 at 01:58

3

You just need an OutputIterator. It doesn't actually have to emit something as if it were an iterator. It could just... do something else entirely. Like, invoke a function.

#include <iterator>

template <class F>
struct function_output_iterator {
    F f;

    using iterator_category = std::output_iterator_tag;
    using value_type = void;
    using difference_type = void;
    using pointer = void;
    using reference = void;

    function_output_iterator& operator++() { return *this; }
    function_output_iterator& operator*() { return *this; }
    function_output_iterator& operator++(int) { return *this; }

    template <class U,
        std::enable_if_t<!std::is_base_of<
            function_output_iterator, std::decay_t<U>>{}, int> = 0>
    void operator=(U&& u) {
        f(std::forward<U>(u));
    }
};

template <class F>
function_output_iterator(F ) -> function_output_iterator<F>;

And then, you can do whatever arbitrary operation you want:

auto getSamples(unsigned int noSamples, const vector<T> &input)
{
    vector<T*> results;
    results.reserve(noSamples);

    std::mt19937 twisterEngine;
    std::sample(input.begin(), input.end(),
        function_output_iterator{[&](T const& elem){ results.push_back(&elem); }, // <==
        noSamples, twisterEngine);
    return results;
}

edited Oct 17 '17 at 01:58

Eric

95,302
53
242
374

answered Oct 16 '17 at 19:03

Barry

286,269
29
621
977

Or `boost::make_function_output_iterator` if you don't want to write your own (ah, I now see OP said no Boost, but still, maybe useful for others that don't have such restrictions) – Praetorian Oct 16 '17 at 19:08
@Praetorian I notice that Boost's `operator*` returns a proxy that has `operator=` implemented - do you know why they did it that way? (I assume it's more correct than this for some reason) – Barry Oct 16 '17 at 19:13
Don't know, a Google search turned up [this proposal](http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2003/n1530.html) (from the Boost authors) that says *The motivation for this iterator is that creating a conforming output iterator is non-trivial, particularly because the proper implementation usually requires a proxy object.*, but I can't think of cases where it makes a difference. Also found [this comment](https://stackoverflow.com/questions/38719522/output-iterator-adapter-to-count-but-not-copy#comment64818610_38720126), so you've had this question for a while :) – Praetorian Oct 16 '17 at 19:24
@Praetorian HA! Indeed, maybe I should ask a proper question or something. – Barry Oct 16 '17 at 19:36
@Barry: It's more correct because it stops you writing `out_it = val` or `****out_it = val` and having them mean the same thing. You should really do what boost does, which makes only `*out_it = val` legal – Eric Oct 16 '17 at 20:39
@Eric Is it though? None of those are necessarily valid `OutputIterator` operations, so none of them should be being performed anyway. – Barry Oct 16 '17 at 21:15
Yes, because right now you violate the [`CopyAssignable`](http://en.cppreference.com/w/cpp/concept/CopyAssignable) concept that [`Iterator`](http://en.cppreference.com/w/cpp/concept/Iterator) inherits - so this is neither a necessary nor sufficient implementation of `OutputIterator`. If I do `function_output_iterator f_it; f_it = f_it` then your code does the wrong thing. – Eric Oct 16 '17 at 22:44
@Eric That's fair, but that's an argument simply for constraining `operator=`. – Barry Oct 17 '17 at 01:28
There's no valid constraint. What if I'm iterating over output iterators themselves? Suddenly your output iterator doesn't work correctly any more – Eric Oct 17 '17 at 01:52
Admittedly that's contrived, but wrong in a contrived corner case is still wrong – Eric Oct 17 '17 at 02:03
@Eric Sure there is. My iterator is copy assignable now. Well, as long as `F` is (should take a `std::ref` really). I don't know what you mean by "iterating over output iterators" – Barry Oct 17 '17 at 02:27
I mean that the original iterable _contains_ iterators: `vector> results`. Under that scenario, `*it = x` would be treated as `it = x`, which would be wrong. – Eric Oct 17 '17 at 17:40
@Eric Assuming `it` there is an iterator into `results`, then... who cares? `*it = x` isn't a defined operation for that output iterator. There's no mandate that it *not work*. Mind you, `libstdc++` implements [`back_insert_iterator`](https://github.com/gcc-mirror/gcc/blob/master/libstdc%2B%2B-v3/include/bits/stl_iterator.h#L478-L504) like this. – Barry Oct 17 '17 at 17:50

How can I return a container of pointers using std::sample on a container of ?

1 Answers1