c++ - set_difference并不总是返回正确的答案

Question

我目前正在研究一种进化算法。我编写了一个程序来实现交叉功能，即在 vector k和A之间交换B元素。这是代码:

#include <algorithm>
#include <cstdio>
#include <ctime>
#include <iostream>
#include <iterator>
#include <random>
#include <set>
#include <vector>

using namespace std;

vector<int> reservoir_sampling(vector<int> input, int k)
{
    vector<int> output(k);
    int i;
    for (i = 0; i < k; i++)
    {
        output[i] = input[i];
    }
    srand(time(nullptr));
    while(i < input.size())
    {
        int j = rand() % (i+1);
        if (j < k)
        {
            output[j] = input[i];
        }
        i++;
    }
    return output;
}

template<typename T>
void vprintf(vector<T> V)
{
    for (T v : V)
    {
        cout << v << " ";
    }
    cout << endl;
}

void test()
{
    // crossover between A and B at k points
    vector<int> A = {0, 1, 2, 3, 4, 5};
    vector<int> B = {6, 7, 8, 9};
    printf("A: ");
    vprintf(A);
    printf("B: ");
    vprintf(B);
    int k = 2;
    vector<int> outers = reservoir_sampling(A, k);
    vector<int> inners = reservoir_sampling(B, k);
    printf("outers: ");
    vprintf(outers);
    printf("inners: ");
    vprintf(inners);
    // uS = A + inners
    vector<int> uS;
    set_union(A.begin(), A.end(), inners.begin(), inners.end(), inserter(uS, uS.end()));
    sort(uS.begin(), uS.end());
    printf("uS =  A + inners: ");
    vprintf(uS);
    // dS = uS - outers
    vector<int> dS;
    set_difference(uS.begin(), uS.end(), outers.begin(), outers.end(), inserter(dS, dS.end()));
    sort(dS.begin(), dS.end());
    printf("dS = uS - outers: ");
    vprintf(dS);
}

int main()
{
    test();
    return 0;
}

有时，输出是正确的，例如:

A: 0 1 2 3 4 5
B: 6 7 8 9
outers: 3 4
inners: 9 7
uS =  A + inners: 0 1 2 3 4 5 7 9
dS = uS - outers: 0 1 2 5 7 9

有时，输出不正确，例如:

A: 0 1 2 3 4 5
B: 6 7 8 9
outers: 3 1
inners: 9 7
uS =  A + inners: 0 1 2 3 4 5 7 9
dS = uS - outers: 0 1 2 4 5 7 9

原来set_union总是可以的，但set_difference却不可以。我不知道我做错了什么。 SO的全能用户，请帮帮我!

Answer 1

您违反了 std::set_union 和 std::set_difference 的先决条件:

Constructs a sorted union beginning at d_first consisting of the set of elements present in one or both sorted ranges [first1, last1) and [first2, last2).

Copies the elements from the sorted range [first1, last1) which are not found in the sorted range [first2, last2) to the range beginning at d_first.

在一般情况下，reservoir_sampling函数不会产生排序的 vector 。您的程序的行为是不确定的。
标准库提供 std::sample function用于随机采样。如果给它一对正向或随机访问迭代器，它将保留所选元素的相对顺序。

template<typename T>
std::vector<T> sampling(const std::vector<T>& input, std::size_t k) {
    std::vector<T> output;
    output.reserve(k);
    std::sample(input.begin(), input.end(), std::back_inserter(output),
        k, std::mt19937{std::random_device{}()});    

    // the relative order of elements in output is the same as in input
    return output;
}