# 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. – CodesInChaos Feb 10 '14 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. – Emily L. Feb 17 '14 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. – user45891 Jan 24 '15 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. – Martin York Jan 24 '15 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. – YoungJohn Feb 11 '14 at 20:36
• This has amortized O(n) time complexity. I approve. :) – Emily L. Feb 17 '14 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;