Самый эффективный способ заполнения вектора целых чисел без дубликатов

Ваше решение в его нынешнем виде будет невероятно медленным - сложность O(n^2), поэтому вы смотрите примерно на 10 ^ 18 «операций» за миллиард чисел. Это связано с тем, что вам нужно искать через вектор по мере его роста, чтобы увидеть, есть ли у вас дубликат, который пройдет через вектор (в среднем) (1 + 2 + ... + 999,999,999) / 2 раз в течение алгоритма.

Изменить: на самом деле это на самом деле немного хуже, потому что, поскольку вы генерируете больше чисел, вероятность того, что вы создадите то, что вы уже видели, увеличивается.

Я бы предложил следующее: поскольку на большинстве платформ int все еще 4 байта, это все еще имеет максимальное значение бит более 2 миллиардов. Следовательно, создайте вектор с порядком первого миллиарда и используйте std::shuffle. Это даст вам миллиард «случайных» значений с ограничением, что ничто не будет выбрано из верхнего диапазона [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);
}

Я бы просто загрузил из файла заданных случайных чисел:

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

Возможным решением было бы сохранить значения в std :: unordered_set (std :: unordered_set будет хранить только уникальные значения), и как только ваш набор достигнет желаемого размера, скопируйте набор в вектор.

Это, вероятно, не самое эффективное решение, но оно подталкивает логику определения того, являются ли значения уникальными в стандартной библиотеке и упрощают собственный код.

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));

Согласно Yuushi, поскольку верхний предел для int равен 2 миллиардам, вы можете просто начать с 0 и продолжать добавлять 1 или 2 миллиарда раз. Таким образом, вы гарантированы

• уникальные номера
• , чтобы оставаться в пределах диапазона int
• Поиск или свопы

Так что-то вроде этого:

#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);
    }    
}

Я не эксперт на C ++, не стесняйтесь, если я ошибаюсь.