c++ - How to circumvent iteration over an output iterator? -

the algorithm implemented below well-known robert floyd algorithm returns m random numbers out of array of n numbers in total. algorithm returns set of elements, within algorithm need loop on result set check if found element has been added result set before.

it not possible loop on output iterator, because states in documentation output iterator should dereferenced once.

template<typename iter, typename randomgenerator> iter random_element(iter start, iter end, randomgenerator& g) {     if (start == end) return start;     std::uniform_int_distribution<> dis(0, std::distance(start, end) - 1);     std::advance(start, dis(g));     return start; }  template<typename iter> iter random_element(iter start, iter end) {     static std::random_device rd;     static std::mt19937 gen(rd());     return random_element(start, end, gen); }  //! @brief algorithm of robert floyd. template<typename inputiterator, typename outputiterator> outputiterator random_n(inputiterator first, inputiterator last, outputiterator result, size_t number) {     // "misuse" glibc functions enforce notions conform documentation     typedef typename std::iterator_traits<inputiterator>::value_type valuetype;     __glibcxx_function_requires(_inputiteratorconcept<inputiterator>);     __glibcxx_function_requires(_outputiteratorconcept<outputiterator, valuetype>);     __glibcxx_requires_valid_range(first1, last1);      if (first == last) return result;     if (number == 0) return result;     assert (number <= (last - first));      // create container store distances, not value itself, neither iterator values     std::vector<size_t> distance;     inputiterator j = last - number + 1;      // in case of number=1, j need end of array, full array searched     while (j <= last) {         inputiterator rand_index = random_element(first,j);         size_t rand = std::distance(first, rand_index);         if (std::find(distance.begin(), distance.end(), rand) != distance.end()) {             distance.push_back(std::distance(first,j) - 1);         } else {             distance.push_back(rand);         }         ++j;     }     // fill result container     (size_t = 0; < distance.size(); ++i) {         *result = *(first+distance[i]);         ++result;     }     return result; } 

the current solution creates temporary vector stores distances respect iterator first , fills result array in 1 go, using these distances. looks ugly me though. there maybe special iterator construct used cope fact cannot loop multiple times on output iterator?

you can tighten requirements of algorithm , require forwarditerator point output.