# 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

## 4 Answers

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;

int number = 0; //Start with the number 0

for (int i=0;i<1000000000;i++) //a billion numbers
{
number += rand() & 1 + 1; //Keep right most bit, add 1 to get 1 or 2
container.push_back(number);
}
}


I am not a C++ expert, feel free to burninate if I am wrong.

• -1 you have way too much rep to be a regular javascript bunny. (nah, kidding) – Mathieu Guindon Feb 12 '14 at 1:19
• It looks like the distribution of numbers using this method is heavily weighted towards smaller numbers: there is approximately a 50% chance the first number is a 1 (and a 100% chance the first number is either 1 or 2) and almost no chance of ever getting the number 2 billion. Also the numbers in the container are in order from smallest to largest so you may still need to shuffle the container afterwards to make them feel more random and less ordered. – YoungJohn Jan 16 '15 at 22:02