How do you select a random value from a vector and pop that value too

[E8A4Nwbp]

Hi,

How can you select a random value of a vector, and at the same time pop THAT element?

[keskiverto]

C++ is not that high level.

1. Select an element
2. Store value of that element
3. Erase the element
4. Use the value

[JLBorges]

If the relative order of the elements remaining in the vector need not be preserved,
it can be done quite efficiently, in O(1) time.

#include <iostream>
#include <vector>
#include <random>
#include <algorithm>

// select a random value from a vector and pop that value 
// the relative order of the elements remaining in the vector is not preserved
// return a copy of the value that was popped
template < typename T, typename A >
auto pop_random( std::vector<T,A>& vec )
{
    static std::mt19937 rng( std::random_device{}() ) ;
    static std::uniform_int_distribution<std::size_t> distrib ;
    using param_type = decltype(distrib)::param_type ;

    if( vec.empty() ) throw std::out_of_range( "pop from an empty vector" ) ;

    else if( vec.size() > 1 )
    {
        // bring a random element to the back of the vector
        // (swap with the element currently at the back)
        distrib.param( param_type( 0, vec.size()-1 ) ) ;
        std::iter_swap( vec.begin()+distrib(rng), --vec.end() ) ;
    }
    
    auto popped_value = vec.back() ;
    vec.pop_back() ;
    
    return popped_value ;
}

int main()
{
    std::vector<int> vec { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 } ;

    while( !vec.empty() )
    {
        for( int v : vec ) std::cout << v << ' ' ;
        std::cout << '\n' ;

        std::cout << "popped " << pop_random(vec) << '\n' ;
    }
}

http://coliru.stacked-crooked.com/a/106987ada2f46a67

EDIT: Note that --vec.end() assumes that the iterator of the vector is of a class type.
To relax this assumption, rewrite using reverse iterators, use a local variable for the iterator or use std::swap to swap the elements.

[deleted account xyzzy]

#include <iostream>
#include <vector>
#include <random>

int main()
{
   std::vector<int> vec { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };

   // setup a random engine
   std::default_random_engine rng(std::random_device{}());

   // setup a uniform distribution
   std::uniform_int_distribution<int> dis(0, vec.size() - 1);

   std::cout << "Vector before erasing:\n";
   for (const auto& itr : vec) { std::cout << itr << ' '; } std::cout << "\n\n";

   // choose which vector element to erase
   int del { dis(rng) };

   std::cout << "Erasing element#: " << del << "\n\n";

   // get an iterator at the requesting position
   auto itr_elem { vec.begin() + del };

   // use the overloaded erase vector method to erase a single element
   vec.erase(itr_elem);

   std::cout << "Vector after erasing:\n";
   for (const auto& itr : vec) { std::cout << itr << ' '; } std::cout << '\n';
}

Vector before erasing:
0 1 2 3 4 5 6 7 8 9 10

Erasing element#: 2

Vector after erasing:
0 1 3 4 5 6 7 8 9 10

No need to change the erasure code when changing the vector's data type:

#include <iostream>
#include <vector>
#include <random>
#include <string>

int main()
{
   std::vector<std::string> vec { "Six", "Four", "Two", "Zero", "One", "Three", "Five" };

   // setup a random engine
   std::default_random_engine rng(std::random_device{}());

   // setup a uniform distribution
   std::uniform_int_distribution<int> dis(0, vec.size() - 1);

   std::cout << "Vector before erasing:\n";
   for (const auto& itr : vec) { std::cout << itr << ' '; } std::cout << "\n\n";

   // choose which vector element to erase
   int del { dis(rng) };

   std::cout << "Erasing element#: " << del << "\n\n";

   // get an iterator at the requesting position
   auto itr_elem { vec.begin() + del };

   // use the overloaded erase vector method to erase a single element
   vec.erase(itr_elem);

   std::cout << "Vector after erasing:\n";
   for (const auto& itr : vec) { std::cout << itr << ' '; } std::cout << '\n';
}

Vector before erasing:
Six Four Two Zero One Three Five

Erasing element#: 5

Vector after erasing:
Six Four Two Zero One Five

[deleted account xyzzy]

Just for giggles I revised the code to use templated functions for the erasure code and output:

#include <iostream>
#include <vector>
#include <random>
#include <string>

template <typename T>
std::ostream& operator<<(std::ostream&, const std::vector<T>&);

template <typename T>
void vec_erase(std::vector<T>&);

int main()
{
   std::vector<int> vec_int { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };

   std::cout << "integer vector before erasing:\n" << vec_int << "\n\n";

   vec_erase(vec_int);

   std::cout << "Integer vector after erasing:\n" << vec_int << "\n\n";

   std::vector<std::string> vec_str { "Six", "Four", "Two", "Zero", "One", "Three", "Five" };

   std::cout << "String vector before erasing:\n" << vec_str << "\n\n";

   vec_erase(vec_str);

   std::cout << "String vector after erasing:\n" << vec_str <<'\n';
}

template <typename T>
std::ostream& operator<<(std::ostream& os, const std::vector<T>& v)
{
   for (auto const& x : v)
   {
      os << x << ' ';
   }

   return os;
}

template <typename T>
void vec_erase(std::vector<T>& vec)
{
   // setup a random engine
   static std::default_random_engine rng(std::random_device {}());

   // setup a uniform distribution
   std::uniform_int_distribution<int> dis(0, vec.size() - 1);

   // choose which vector element to erase
   int del { dis(rng) };

   std::cout << "Erasing element#: " << del << "\n\n";

   // get an iterator at the requesting position
   auto itr_elem { vec.begin() + del };

   // use the overloaded erase vector method to erase a single element
   vec.erase(itr_elem);
}

integer vector before erasing:
0 1 2 3 4 5 6 7 8 9 10

Erasing element#: 7

Integer vector after erasing:
0 1 2 3 4 5 6 8 9 10

String vector before erasing:
Six Four Two Zero One Three Five

Erasing element#: 0

String vector after erasing:
Four Two Zero One Three Five