c++ - 如何找到两个袋子的交点

Question

好的，我已经记下了这段代码。

包界面

#ifndef BAGINTERFACE_H
#define    BAGINTERFACE_H

#include <vector>
#include <algorithm>

template<class ItemType>
class BagInterface
{
    public:

    virtual int getCurrentSize() const = 0;
    virtual bool isEmpty() const = 0;
    virtual bool add(const ItemType& newEntry) = 0;
    virtual bool remove(const ItemType& anEntry) = 0;
    virtual void clear() = 0;
    virtual int getFrequencyOf(const ItemType& anEntry) const = 0;
    virtual bool contains(const ItemType& anEntry) const = 0;
    virtual std::vector<ItemType> toVector() const = 0;
}; 

#endif    /* BAGINTERFACE_H */

包 #ifndef BAG_H #定义 BAG_H

#include "BagInterface.h"

template <class ItemType>
class Bag: public BagInterface<ItemType>
{

public:

    int getCurrentSize() const { return v.size(); }
    bool isEmpty() const { return v.empty(); }
    bool add(const ItemType& newEntry) { v.push_back(newEntry); return true; }
    bool remove(const ItemType& anEntry) { std::remove(v.begin(), v.end(), anEntry); return true; }
    void clear() { v.clear(); }
    int getFrequencyOf(const ItemType& anEntry) const { return std::count(v.begin(), v.end(), anEntry); }
    bool contains(const ItemType& anEntry) const { return true; }
    std::vector<ItemType> toVector() const { return v; }

private:

  std::vector<ItemType> v;

};

#endif    /* BAG_H */

和我的实际程序 main.cpp

#include <iostream> // For cout and cin
#include <string> // For string objects
#include "Bag.h" // For ADT bag
using namespace std;
int main()
{
string clubs[] = { "Joker", "Ace", "Two", "Three",
"Four", "Five", "Six", "Seven",
"Eight", "Nine", "Ten", "Jack",
"Queen", "King" };
// Create our bag to hold cards
Bag<string> grabBag;
Bag<string> dumpBag;

grabBag.add(clubs[1]);
grabBag.add(clubs[2]);
grabBag.add(clubs[4]);
grabBag.add(clubs[8]);
grabBag.add(clubs[10]);
grabBag.add(clubs[12]);

dumpBag.add(clubs[3]);
dumpBag.add(clubs[5]);
dumpBag.add(clubs[7]);
dumpBag.add(clubs[9]);
dumpBag.add(clubs[10]);
dumpBag.add(clubs[12]);

Bag<string> Itersection(Bag<string> bagToCompare){


    return grabBag;
}


return 0;
}; // end main

我试图找到两个袋子的交集，这将是一个新袋子，其中包含出现在两个原始袋子中的条目。所以基本上我需要设计和指定一个方法交集，它作为一个新包返回接收方法调用的包和作为方法的一个参数的包的交集。假设 bag1 和 bag2 是包； bag1 包含字符串 a 、 b 和 c ； bag2 包含字符串 b 、 b 、 d 和 e 。表达式 bag1.intersection(bag2) 返回一个只包含字符串 b 的包。

我已经制作了两个包来相互比较，但我不太确定如何设计交集方法。

任何帮助都会很棒。谢谢。

Answer 1

由于枚举包中项目的唯一方法是使用 toVector，因此您需要迭代其中一个输入包的 toVector。对于每个项目，在任一输入包中获取该项目的最小频率，并确保输出包包含具有该频率的项目。由于 toVector 可能重复包含相同的项目，您必须检查输出包以查看它是否已经包含您正在考虑的项目。

我还没有跟上 C++11 的速度，所以我将采用老式的方式:

template<class T>
Bag<T> intersection(BagInterface<T> const &a, BagInterface<T> const &b) {
    Bag<T> c;
    std::vector<T> aItems = a.toVector();
    for (int i = 0; i < aItems.size(); ++i) {
        T const &item = aItems[i];
        int needed = std::min(a.getFrequencyOf(item), b.getFrequencyOf(item));
        int lacking = needed - c.getFrequencyOf(item);
        for ( ; lacking > 0; --lacking) {
            c.add(item);
        }
    }
    return c;
}