CODEWITHSUNDEEP
c++arraysqtvectorduplicates
Deto24
Deto24

Reputation: 93

Create Array as Vector with 10 Million elements and assign random numbers without duplicates

I try to code myself a Table with random generated Numbers. While that is simple as it is, causing that Vector not having any duplicates isn't as easy as I thought. So far my Code looks like that:

QStringList generatedTable;

srand (QTime::currentTime().msec());
std::vector<int> array(10000000);
for(std::size_t i = 0; i < array.size(); i++){
    array[i] = (rand() % 10000000000)+1;
}

It generates numbers just fine, but because I'm generating a large amount of array elements (10 Million), even though I'm using 10 Billion possible numbers, it will create duplicates. I already browsed a bit and found something that seems handy to use, but doesn't work properly in my Program. The code is from another stackoverflow User:

#include<iostream>
#include<algorithm>
#include<functional>
#include<set>

int main()
{
    int arr[] = {0, 0, 1, 0, 0, 0, 1, 1, 0, 1, 0, 0, 1, 1, 0, 1, 1, 1, 1, 1, 0, 1, 0, 1, 0, 1};
    std::set<int> duplicates;

    auto it = std::remove_if(std::begin(arr), std::end(arr), [&duplicates](int i) {
        return !duplicates.insert(i).second;
    });
    size_t n = std::distance(std::begin(arr), it);

    for (size_t i = 0; i < n; i++)
        std::cout << arr[i] << " ";

    return 0;
}

It basically moves all the duplicates to the end of the Array, but for some reason does it not work anymore when the array gets bigger. The code will always place the iterator n at 32.768 as long the Array stays above a Million. Under a Million it drops slightly to ~31.000. So while the code is nice it doesn't really help me alot. Does someone have a better option I could use? Since I'm still a Qt and C++ beginner do I not know how to solve that problem properly.

Upvotes: 0

Views: 698

Answers (2)

G. De Mitri
G. De Mitri

Reputation: 115

The simplest but at the same time most efficient thing is to implement a binary search tree. Generate the random number in your range and check if it's not already there. Note that the operations are performed in a time O(n)

Upvotes: -1

cigien
cigien

Reputation: 60228

If you want to sample N integers without replacement from the range [low, high) you can write this:

std::vector<int> array(N);   // or reserve space for N elements up front
 
auto gen = std::mt19937{std::random_device{}()};
    
std::ranges::sample(std::views::iota(low, high), 
                    array.begin(),
                    N, 
                    gen);

std::ranges::shuffle(array, gen);  // only if you want the samples in random order

Here's a demo.

Note that this requires C++20, otherwise the range to be sampled from can't be generated lazily, which would require it to be stored in memory. If you want to write something similar before C++20, you can use the range-v3 library.

Upvotes: 2

Related Questions