Funkcja sprawdzająca, czy pierwszy vector zawiera wszystkie elementy drugiego

Question

Witam, mam do napisania funkcję, która będzie sprawdzać, czy pierwszy vector zawiera wszystkie elementy drugiego vectora. Problem w tym, że nie wiem jak obsłużyć sytuację, w której pojawiają się duplikaty. Oto mój kod:

#include <iostream>
#include <string>
#include <vector>

void contains_all(std::vector<int> vec, std::vector<int> vec2)
{
        size_t count = 0;
        for(size_t i = 0; i < vec.size(); i++)
        {
                for(size_t j = 0; j < vec2.size(); j++)
                {
                        if(vec2[j]==vec[i])
                        {
                                count++;
                        }       
                } 

        }

        if(count>=vec2.size())
        {
                std::cout<<"Pierwszy vector zawiera wszystkie elementy drugiego vectora"<<std::endl;
        }
        else
        {
                std::cout<<"Pierwszy vector nie zawiera wszystkich elementów drugiego vectora"<<std::endl;
        }

}

auto main() -> int
{
        auto vec = std::vector<int>{2,3,5,2,1,4,5,6,7,8};
        auto vec2 = std::vector<int>{2,3,5,2,9};
         
        contains_all(vec, vec2);

return 0;
}

Byłbym wdzięczny za pomoc z napisaniem poprawnego kodu. Z góry dzięki!

Answer 1

Jak można rozwiązać taki problem:

1. Sprawdzić czy istnieją już funkcje, które to rozwiązują lub upraszczają rozwiązanie.  Przykładowo:

//** funkcja FIND  -  sprawdzenie czy wektor V zawiera element X  **/

#include <algorithm>

if( std:: find(  v .begin() , v .end() , x ) != v .end() ) {
    /* ZAWIERA*/
} else {
    /* NIE ZAWIERA */
}


//** funkcja INCLUDES -  sprawdzenie czy posortowany zakres zawiera inny posortowany zakres   **/
template <typename T>
bool IsSubset(std::vector<T> A, std::vector<T> B)
{
    std ::sort( A .begin() ,  A .end() );
    std ::sort( B .begin() , B .end());
    return std ::includes( A .begin() ,  A .end() , B .begin() , B .end() );
}

2. Twój pomysł może osiągnąć poziom rozwiązania poprawnego. Wystarczy przeanalizować jego działanie i szukać co nie działa tak jak planowałeś.  Gdyby wystarczył rezultat: "Pierwszy vector zawiera wszystkie elementy drugiego vectora w przynajmniej jednej kopii" wtedy wystarczyła by prosta zmiana:

count++;
break;

W przeciwnym razie podszedłbym to rozwiązania inaczej:

bool contains_all( std::vector<int> vec, std::vector<int> vec2 )
{
//** KROK 1: Sortowanie wektorów **/
        std::sort( vec .begin(), vec .end() ); 
        std::sort( vec2 .begin(), vec2 .end() );

        auto v_pos { vec .begin() };

//** KROK 2: Czy każdy element vectora 2... **/      
        for ( auto& elem : vec2 ) 
        {
            //** KROK 3: Zawiera się w wektorze pierwszym **/
            while ( v_pos < vec .end() )
            {
                //cout << format( " [ {0} ] == [ {1} ] " , elem , *v_pos ) << endl;
                if ( elem == *v_pos )
                {
                    /** Tak, więc przechodzę do następnego elementu vec **/
                    ++v_pos;
                    /** Sprawdzam kolejny element vec2 **/
                    break;
                }
                else if ( *v_pos > elem )
                {
                    /** Dalej już nie znajdziemy bo wektory są posortowane. **/
                    return false;
                }
                v_pos++;
            }
        }
      
        return( ( v_pos < vec .end() ) ); // TRUE gdy Nie przekroczyło zakresu vec i sprawdzono wszystkie elementy vec2.
 
}

Przepis masz podany wraz z rozwiązaniem, które cię pewnie nie zainteresuje ;), ale korzystając z przepisu możesz ugotować własną funkcję.

Comments

Wielkie dzięki, naprawdę bardzo mi pomogłeś :)

Answer 2

#include <iostream>
#include <string>
#include <vector>
#include <set>

bool contains_all(const std::vector<int>& vec, const std::vector<int>& vec2)
{
    std::set<int> a1(vec.begin(), vec.end());
    std::set<int> a2(vec2.begin(), vec2.end());
    if(a1.size()<=a2.size())
    {
        for(const auto& i :a1)
        {
            if(a2.find(i)==a2.end())
            {
                return false;
            }
        }
    }
    return true;
}
 
auto main() -> int
{
    auto vec1 = std::vector<int>{2,4,2,3,3,5,0,9};
    auto vec2 = std::vector<int>{2,3,5,2,1,4,5,9,7,8};
      
    std::cout<<contains_all(vec1, vec2);
}

 

Comments

Wydaje mi się, że OP chodziło o to, by uwzględniać ilość wystąpień.

---

Tak, ilość wystąpień ma być uwzględniona, ale dzięki i tak bardzo pomogłeś.

---

Możesz użyć mapy wartość -> ilość wystąpień, wtedy będziesz mógł uwzględnić wystąpienia.

---

@tkz, 

bool contains_all(const std::vector<int>& vec, const std::vector<int>& vec2) {
    std::set<int> a1(vec.begin(), vec.end());
    std::set<int> a2(vec2.begin(), vec2.end());
    a1.insert(a2.begin(),a2.end());
    if(a1.size()==a2.size()) return true;
    else return false;
}

Wolniejsze, ale krócej zapisane.

---

Może <algorithm>

bool contains_all(std::vector<int>& vec, std::vector<int>& vec2) {
    std::vector<int>diff{};
    std::sort(vec.begin(),vec.end());
    std::sort(vec2.begin(),vec2.end());
    std::set_difference(vec.begin(), vec.end(),vec2.begin(), vec2.end(),std::back_inserter(diff));
    return diff.empty();
}