# Most efficient way to populate a vector of integers with no duplicates

I am trying to populate a vector of integers with one billion random number. The only constraint is that there can be no duplicates in the array.

#include <iostream>
#include <algorithm>
#include <vector>
#include <ctime>

using namespace std;

int main()
{
srand(time(NULL));

vector<int> container;

vector<int>::iterator i1;

for (int i=0;i<1000000000;i++) //a billion numbers
{
int number = rand() ;

i1 = find (container.begin(),container.end() , number );

if ( i1 != container.end() )
{
container.push_back(number);
}

}

}


How can my solution be improved on? It can be anything, like time taken or space complexity.

• 1) rand sucks. On some machines there might not even be enough distinct values for rand to return. RAND_MAX may be as small as 2^15. 2) A hash set based approach would be much faster. Alternatively you could also use a sorting or tree based approach, but those tend to be slower than hashing. Commented Feb 10, 2014 at 14:26

Your solution as it stands currently is going to be incredibly slow - it's complexity is O(n^2), so you're looking at roughly 10^18 "operations" for a billion numbers. This is because you need to search through the vector as it grows to see if you have a duplicate, which will go through the vector (on average) (1 + 2 + ... + 999,999,999) / 2 times over the course of the algorithm.

Edit: In fact, it's actually slightly worse than this, since as you generate more numbers, the probability that you generate something you've already "seen" increases.

I'd suggest the following: since an int on most platforms is still 4 bytes, this still has a maximum value of a bit over 2 billion. Hence create a vector with the first billion values in order, and use std::shuffle. This will give you a billion "random" values, with the constraint that nothing will be selected from the upper range [1e9, INT_MAX].

int main()
{
constexpr int num_values = 1000000000;
std::vector<int> rand_values(num_values);
std::mt19937 eng{std::random_device{}()};

for(int i = 0; i < num_values; ++i) {
rand_values[i] = i;
}

std::shuffle(rand_values.begin(), rand_values.end(), eng);
}

• In the event that OP wishes to use truly random numbers, this approach will not work. The constraint of the domain of values doesn't seem reasonable in the general case. Commented Feb 17, 2014 at 23:24

I would just load from a file of predetermined random numbers:

std::ifstream      randFile("NameOfFileWithRandoms");
std::vector<int>   randvalues(std::istream_iterator<int>(randFile),
std::istream_iterator<int>());

• And what if there ever is a need for different random numbers? After all the code in the OP seeds with the current time so your solution doesn't has the same behavior. Commented Jan 24, 2015 at 14:15
• @user45891: And that is a different question (if you ask that question I will be sure to answer it). But that was not the question. The question was just to fill a vector with unique values As quickly as possible. Commented Jan 24, 2015 at 19:20

A possible solution would be to store the values in a std::unordered_set (std::unordered_set will only store unique values), and once your set reaches the desired size, to copy the set into a vector.

This is probably not the most efficient solution but it would push the logic of determining if values are unique into the standard library and simplify your own code.

srand(time(NULL));
auto uniqueSetOfValues = unordered_set<int>();
while(uniqueSetOfValues.size() < 1000000000)
{
// this will only insert unique values into the set
uniqueSetOfValues.insert(rand());
}

// start the vector with the correct size
auto uniqueVectorOfValues = vector<int>(uniqueSetOfValues.size());
// copy the set into the vector
copy(
begin(uniqueSetOfValues),
end(uniqueSetOfValues),
begin(uniqueVectorOfValues));

• You might even be able to use std::move instead of std::copy since you probably don't need to keep the unordered_set around. Commented Feb 11, 2014 at 20:36
• This has amortized O(n) time complexity. I approve. :) Commented Feb 17, 2014 at 23:27

As per Yuushi, since the upper limit for int is 2 billion, you might just want to start with 0 and keep adding 1 or 2 a billion times. This way you are guaranteed

• unique numbers
• to stay within the int range
• no lookups or swaps

So something like this:

#include <iostream>
#include <algorithm>
#include <vector>
#include <ctime>

using namespace std;

int main()
{
srand(time(NULL));

vector<int> container;