Как найти пересечение двух мешков

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

Answer 2

Попробуйте использовать перечисление для клубов. Вы можете использовать строки, но сравнение строк сложнее.

enum ClubsType { 
    Joker, 
    Ace, 
    Two, 
    Three, 
    Four, 
    Five, 
    Six, 
    Seven, 
    Eight, 
    Nine, 
    Ten, 
    Jack, 
    Queen, 
    King, 
    ClubsTypeSize 
} 

Bag<ClubsType> Intersection(const Bag<ClubsType>& other) { 
    set<ClubsType> common; 
    int n = v.size(); 
    for (int i=0;i<n;i++) { 
     common.insert(v[i]); 
    } 
    otherAsVector = other.toVector(); 
    n = otherAsVector.size(); 
    for (int i=0;i<n;i++) { 
     common.insert(otherAsVector[i]); 
    } 
    Bag<ClubsType> result; 
    for (set<ClubsType>::iterator it = common.begin(); it!=common.end();++it) { 
     result.add(*it); 
    } 
    return result; 
} 

Answer 3

std::set_intersection от <algorithm> делает это для отсортированных входных диапазонов:

vector<int> as { 1, 2, 3 }; 
vector<int> bs { 2, 3, 4 }; 
vector<int> cs; 

set_intersection(
    begin(as), end(as), 
    begin(bs), end(bs), 
    back_inserter(cs) 
); 

// 2 3 
for (const auto c : cs) 
    cout << c << ' '; 

Он работает с помощью цикла над входными диапазонами до тех пор, по крайней мере, один не будет исчерпан, копирования этих элементов из одного диапазона, которые появляются в других , в соответствии со строгим слабым порядком, налагаемым operator<:

while (first1 != last1 && first2 != last2) { 
    if (*first1 < *first2) { 
     ++first1; 
    } else { 
     if (!(*first2 < *first1)) { 
      *output++ = *first1++; 
     } 
     ++first2; 
    } 
} 
return output;