Fill vector with unrepeated random numbers. why not working?

Question

I've seen the approaches for creating a vector of unrepeated random numbers based on std::random_shuffle, however I need to implement an alternative approach. This is my code:

std::vector<int> create_unrepeated_random(int v_size, int v_max) {

  // Max index value must be grater than the number of vector size
  assert(v_max > v_size);

  std::vector<int> ret;

  int val = 0;

  for (int i = 0; i < v_size; i++) {

    val = std::rand() % v_max; 

    // Keep generating new values until we generate one that is not already in  
    // output vector
    if (ret.size() > 0) {
      while (!std::binary_search(ret.begin(), ret.end(), val)) {
        val = std::rand() % v_max; 
      }
    }

    ret.push_back(val);

  }


  assert ((int)ret.size() == v_size);
  for (auto &v: ret) printf("%d ", v);printf("\n");

  return ret;

}

However, this is not working, don't know why. Some numbers appear repated sometimes.

BUT if I change the while loop to

 while (std::binary_search(ret.begin(), ret.end(), val))

this creates a vector of repeated random numbers. What is wrong here?

Looks to me like you are using a binary search, which requires a sorted list, on a list that is not sorted. As you generate new numbers which are not in the list, you should do an insertion sort so that the numbers in the list will remain sorted. — Richard Chambers, Dec 09 '15 at 11:03
See [how do you insert the value in a sorted vector](http://stackoverflow.com/questions/15843525/how-do-you-insert-the-value-in-a-sorted-vector) for a discussion as well as [C++ vector insertion sort algorithm method - pass vector into method](http://stackoverflow.com/questions/5709637/c-vector-insertion-sort-algorithm-method-pass-vector-into-method). — Richard Chambers, Dec 09 '15 at 11:07
As an improvement, you can change the `vector` declaration to `std::vector ret(v_size);` — CinCout, Dec 09 '15 at 11:10
Just a suggestion to make your code more readable you can change this if (ret.size() > 0) to this if(!ret.empty() ) It will essentially do the same as vector::size() will return an unsigned int. Sorry was small typo, re-posting comment :) — silvergasp, Dec 09 '15 at 11:19

Baum mit Augen · Accepted Answer · 2015-12-09T11:29:36.640

std::binary_search

only works on sorted ranges. Use std::find instead:

while (std::find(ret.begin(), ret.end(), val) != ret.end())

Alternatively, you may use std::unordered_set:

std::unordered_set<int> ret;
while (ret.size() < v_size) {
    ret.insert(rand() % v_max);
}

Keep in mind that with this approach the order of the generated number will be unspecified, i.e. probably less random than the vector approach. If you want a sorted sequence of random numbers, consider std::set.

Remark: The use of rand() is discouraged in modern C++, although it will probably do the trick for toy programs. See also https://channel9.msdn.com/Events/GoingNative/2013/rand-Considered-Harmful

Fill vector with unrepeated random numbers. why not working?

1 Answers1