set_interaction 自定义矢量无效的示例

Question

我正在寻找两个自定义向量的交集 - v and w -，然后从原始向量 - v 中删除公共元素。但是在我的例子中 y 的大小总是 0

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

class A{
    public:
    int x;
    A(int i) { x = i; } 
    ~A() {}
    void getx() { cout << x << " "; } 
    friend ostream &operator<<(ostream &o, const A&a) {
        cout << a.x;
        return o;
    }
};

struct mycomparer {
    bool operator()(const A* a, const A* b) {
        return a->x < b->x;
    }
};

int main()
{
    vector<A*> v;
    v.push_back(new A(1));
    v.push_back(new A(2));
    v.push_back(new A(4));
    v.push_back(new A(3));
    v.push_back(new A(5));

    vector<A*> w;
    w.push_back(new A(3));
    w.push_back(new A(2));

    vector<A*> y;
    vector<A*>::iterator it, st;
    it = set_intersection(v.begin(), v.end(), w.begin(), w.end(), y.begin(), mycomparer());

    cout << " y size "  << y.size() << endl;

    if (y.size()) {
        for (st = y.begin(); st != y.end(); st++)
            v.erase(st);
    }

    for (st = v.begin(); st != v.end(); st++) {
        printf("%d ", (*st)->x);
    }
    cout << endl;

    return 0;
}

这只是我编写的示例，我不打算检查任何其他 C++ 规则。

Answer 1

1) 在向量 w 中，您应该先按 new A(2)，然后 new A(3)。对于您的实际代码，您的向量必须事先根据比较器排序，如前文评论所述，否则您绝对不能使用 set_intersection.

2) 向量 y 的大小为 0，因为 set_intersection 不会 在迭代器中插入 新元素，而是分配与运算符 =。您应该使用 std::back_inserter(y) 而不是 y.begin()，这实际上会在赋值时插入元素。

Answer 2

您没有遵守 std::set_intersection 的要求。

Constructs a sorted range beginning at d_first consisting of elements that are found in both sorted ranges [first1, last1) and [first2, last2). If some element is found m times in [first1, last1) and n times in [first2, last2), the first std::min(m, n) elements will be copied from the first range to the destination range. The order of equivalent elements is preserved. The resulting range cannot overlap with either of the input ranges.

v 和 w 都未排序 w.r.t mycomparer。这是第一个未定义的行为。

仅仅通过 y.begin() 并不意味着元素被添加到 y，因为你需要 std::back_inserter(y)。这是第二个未定义的行为。

您没有遵守std::vector::erase的要求。它的参数是 that vector 的迭代器。您正在使用来自 y 的迭代器，而不是 v。这是第三个未定义的行为。

#include <iostream>
#include <vector>
#include <algorithm>
#include <iterator>

class A{
    public:
    int x;
    A(int i) { x = i; } 
    ~A() {}
    void getx() { cout << x << " "; } 
    friend ostream &operator<<(ostream &o, const A&a) {
        cout << a.x;
        return o;
    }
};

struct mycomparer {
    bool operator()(const A* a, const A* b) {
        return a->x < b->x;
    }
};

int main()
{
    std::vector<A*> v;
    v.push_back(new A(1));
    v.push_back(new A(2));
    v.push_back(new A(4));
    v.push_back(new A(3));
    v.push_back(new A(5));

    std::sort(v.begin(), v.end(), mycomparer());

    std::vector<A*> w;
    w.push_back(new A(3));
    w.push_back(new A(2));

    std::sort(w.begin(), w.end(), mycomparer());

    std::vector<A*> y;
    set_intersection(v.begin(), v.end(), w.begin(), w.end(), std::back_inserter(y), mycomparer());

    std::cout << " y size "  << y.size() << std::endl;

    for (st = y.begin(); st != y.end(); st++)
        v.erase(std::find(v.begin(), v.end(), *st));

    for (st = v.begin(); st != v.end(); st++) {
        std::cout << (*st)->x) << std::endl;
    }

    return 0;
}

顺便说一句，您可以使用 std::set_difference 来查找 v 中的元素，而不是直接在 w 中查找元素。

Answer 3

你的代码有很多问题...我只是把它们放在修改后的代码中

#include <iostream>
#include <memory>
#include <vector>
#include <algorithm>

// don't using namespace std;

class A {
private:
    int x; // don't expose internals
public:
    constexpr A(int i) noexcept : x(i) {}

    constexpr int GetX() const noexcept { return x; } // don't make a getter to print

    friend std::ostream& operator<< (std::ostream& o, const A& a) {
        o << a.x; // don't push to cout in an ostream operator <<
        return o;
    }
};

// use lambda instead of functors
static constexpr auto mycomparer =
[](std::shared_ptr<A> const& a, std::shared_ptr<A> const& b) noexcept {
        return a->GetX() < b->GetX();
};

int main()
{
    // you were not deleting the new elements: memory leak
    std::vector<std::shared_ptr<A>> v; // e.g. use smart pointers
    v.push_back(std::make_shared<A>(1));
    v.push_back(std::make_shared<A>(2));
    v.push_back(std::make_shared<A>(4));
    v.push_back(std::make_shared<A>(3));
    v.push_back(std::make_shared<A>(5));

    std::vector<std::shared_ptr<A>> w;
    w.push_back(std::make_shared<A>(3));
    w.push_back(std::make_shared<A>(2));

    std::vector<std::shared_ptr<A>> y;

    //you have to sort before calling set_intersection
    std::sort(std::begin(v), std::end(v), mycomparer);
    std::sort(std::begin(w), std::end(w), mycomparer);

    std::set_intersection(
        std::cbegin(v), std::cend(v), // use const iterators
        std::cbegin(w), std::cend(w),
        std::back_inserter(y), mycomparer); // you cannot iterate over an empty array. Use the backinserter

    std::cout << " y size " << y.size() << '\n';

    // you cannot use an iterator to a vector y to delete from vector v!
    //if (y.size() > 0) { // not required
        for (auto const& el : y)
            v.erase(std::find(std::cbegin(v), std::cend(v), el)); 
    //}

    for (auto const& el : v) {
        std::cout << el->GetX() << " ";
    }
    std::cout << '\n'; // prefer \n over endl for speed

    //return 0; // not required
}

set_interaction 自定义矢量无效的示例

set_interaction example with custom vector not working

c++

vector

set-intersection