C++ 中两个指针向量的减法和交集

Question

我有两个向量，它们都有指向我的自定义类对象的指针。
这两个向量中的指针并不指向同一个对象，但对象中存储的值是相同的。

我的自定义类结构是：

Class Item
{
   string ItemId;
   string ItemDescription;
   float ItemPrice;
}

The first vector(V1) is having n entries and the second vector(V2) is having m entries (n>m).

我必须执行两项操作：

获取一个在V1和V2中都有共同对象的向量。 通过共同点，我的意思是说元素的 ItemId 是相同的。（可以称为V1 和 V2 的交集）。< p>

获取一个向量，其中包含 V2 中不存在的元素。 （可称为V1-V2）。

如何有效地做到这一点？

Answer 1

以下是如何使用 STL set_intersection 和 set_difference 来获得您想要的内容的示例：

class Item
{
public:
    Item(int i):ItemId(i){}

   int ItemId;
   string ItemDescription;
   float ItemPrice;

   bool operator<(const Item& rhs)
   {
       return ItemId < rhs.ItemId;
   }
   bool operator==(const Item& rhs)
   {
       return ItemId == rhs.ItemId;
   }
};

int main()
{
    std::vector<Item> myvec1;
    myvec1.push_back(Item(1));
    myvec1.push_back(Item(2));
    myvec1.push_back(Item(1));
    myvec1.push_back(Item(10));
    myvec1.push_back(Item(5));
    myvec1.push_back(Item(3));
    myvec1.push_back(Item(10));


    std::vector<Item> myvec2;
    myvec2.push_back(Item(10));
    myvec2.push_back(Item(1));
    myvec2.push_back(Item(10));
    myvec2.push_back(Item(1));
    myvec2.push_back(Item(3));

    std::sort(myvec1.begin(), myvec1.end());
    std::sort(myvec2.begin(), myvec2.end());

    myvec1.erase(std::unique(myvec1.begin(), myvec1.end()), myvec1.end());
    myvec2.erase(std::unique(myvec2.begin(), myvec2.end()), myvec2.end());

    std::vector<Item> myvec3; //Intersection of V1 and V2
    std::vector<Item> myvec4; //V1-V2
    set_intersection(myvec1.begin(),myvec1.end(), myvec2.begin(),myvec2.end(), std::back_inserter(myvec3)); //myvec3: 1 3 10
    set_difference(myvec1.begin(),myvec1.end(), myvec2.begin(),myvec2.end(), std::back_inserter(myvec4));   //myvec4: 2 5 
}

Answer 2

如果您使用的是stl，对于第一个问题，您可以使用set_intersection，对于第二个问题< a href="http://www.sgi.com/tech/stl/set_difference.html" rel="nofollow">set_difference

Answer 3

@Amresh，这是您想要使用带有指针的向量的示例。但我使用了 boost::shared_ptr 而不是原始指针，所以你需要担心内存管理：

class Item;
typedef boost::shared_ptr<Item> MyPtr;
typedef std::vector<MyPtr> VecType;

class Item
{
public:
    Item(int i):ItemId(i){}
    friend bool operator<(MyPtr lhs, MyPtr rhs);
    friend bool operator==(MyPtr lhs, MyPtr rhs);

   int ItemId;
   string ItemDescription;
   float ItemPrice;

   bool operator<(const Item& rhs)
   {
       return ItemId < rhs.ItemId;
   }
   bool operator==(const Item& rhs)
   {
       return ItemId == rhs.ItemId;
   }
};



bool operator<(MyPtr lhs, MyPtr rhs)
{
    return lhs->ItemId < rhs->ItemId ;
}

bool operator==(MyPtr lhs, MyPtr rhs)
{
    return lhs->ItemId == rhs->ItemId ;
}

int main()
{

    VecType myvec1;
    myvec1.push_back(MyPtr(new Item(2)));
    myvec1.push_back(MyPtr(new Item(1)));
    myvec1.push_back(MyPtr(new Item(10)));
    myvec1.push_back(MyPtr(new Item(5)));
    myvec1.push_back(MyPtr(new Item(3)));
    myvec1.push_back(MyPtr(new Item(10)));

    VecType myvec2;
    myvec2.push_back(MyPtr(new Item(10)));
    myvec2.push_back(MyPtr(new Item(1)));
    myvec2.push_back(MyPtr(new Item(10)));
    myvec2.push_back(MyPtr(new Item(1)));
    myvec2.push_back(MyPtr(new Item(3)));

    std::sort(myvec1.begin(), myvec1.end());
    std::sort(myvec2.begin(), myvec2.end());

    myvec1.erase(std::unique(myvec1.begin(), myvec1.end()), myvec1.end());
    myvec2.erase(std::unique(myvec2.begin(), myvec2.end()), myvec2.end());

    VecType myvec3; //Intersection of V1 and V2
    VecType myvec4; //V1-V2
    set_intersection(myvec1.begin(),myvec1.end(), myvec2.begin(),myvec2.end(), std::back_inserter(myvec3)); //myvec3: 1 3 10
    set_difference(myvec1.begin(),myvec1.end(), myvec2.begin(),myvec2.end(), std::back_inserter(myvec4));   //myvec4: 2 5 
}