How can I check, straight away, if a set of pairs have a commom number?-CodePudding

Suppose we have 4 pairs, e.g.:

pair<int, int> P1(1, 2);
pair<int, int> P2(3, 1);
pair<int, int> P3(2, 1);
pair<int, int> P4(1, 5);

How can I compare those 4 pairs straight away and conclude that they all have the number 1 in common? I can only think of comparing two by two, but that is a lot of work for a lot of pairs...

Is there some function that does that for any given set of pairs?

CodePudding user response：

There is no helper "built in" to check that all pairs contain a certain number, but it's a fairly easy operation to make!

For this you would need a function that receives a list of pairs.

bool allPairsShareNumber(list<pair<int, int>> pairs, int number) {
    return all_of(pairs.begin(), pairs.end(), [&number](pair<int,int> pair){
        return pair.first == number || pair.second == number;
    });
}

And then you can just pass the list to the function!

pair<int, int> P1(1, 2);
pair<int, int> P2(3, 1);
pair<int, int> P3(2, 1);
pair<int, int> P4(1, 5);

list<pair<int, int>> pairList = { P1, P2, P3, P4 };

bool doTheyAllContain1 = allPairsShareNumber(pairList, 1);

CodePudding user response：

In the sample code you've given, you need to check each pair (P1, P2, etc) separately (e.g. if (P1.first == 1 || P1.second == 1 || P2.first == 1 || <etc> )).

If you insist on having P1, ... P4 as distinct variables, there are no shortcuts on that, since you've defined P1, P2, ... P4 in a way that imposes no logical or structural relationship between them. (e.g. there is no guarantee where they are located in machine memory - they could be together, they could be in completely unrelated memory locations).

But having multiple variables with sequential names like P1, P2, ..... is an indication that you need to use a raw array (e.g. pair<int, int> P[4]) or a standard container (e.g. vector<pair<int, int> > P). If you structure your code using a raw array or a standard container then there are options. For example, a raw array;

 std::pair<int, int> P[4];
  //  set the four elements of P
 bool has_one = false;
 for (int i = 0; has_one == false && i < 4;   i)
     if (P[i].first == 1 || P[i].second == 1) has_one = true;

which is readily extendable to an arbitrary number of pairs, as long as the number is fixed at compile time. Keep in mind that array indexing starts at zero, not one (i.e. P[0] exists in the above but P[4] does not).

The danger in such code is not updating the number correctly (e.g. changing the number of elements of P from 4 to 27, but forgetting to make the same change in the loop).

Instead of a raw array, a better option is to use a standard container - particularly if you want to do multiple things with the set of pairs. If the number of pairs is fixed at compile time, the definition of P above can be changed to use the array standard container.

 std::array<std::pair<int, int>, 4> P;      // array is from standard header <array>
  //  assign the four elements of P (code omitted)

which offers a number of advantages over using a raw array.

If the number of pairs is not known at compile time (e.g. the number is computed based on values read at run time) you can use another standard container, such as

// compute n as the number of elements
std::vector<std::pair<int, int> > P (n);

In all cases a raw array (with care to avoid problems such as checking more elements than an array has) and the standard containers can be used in loops.

However, it is considered better (since it is less error prone) to avoid - where possible - using loops, and instead use algorithms supplied by the C standard library. For example (C 11 and later) you could do

#include <algorithm>
#include <vector>

int main()
{
    // compute n as the number of elements  (code omitted)

    std::vector<std::pair<int, int>> P(n);

    // populate elements of P  (code omitted)

    auto check_if_one = [](std::pair<int, int> a)
                        {return a.first == 1 || a.second == 1;};

    bool has_one = (std::find_if(std::begin(P), std::end(P), check_if_one) != std::end(P));

}

The advantage of this is that the code always accounts correctly for the number of elements in P. The approach for calculating the value for has_one in the above is identical, regardless of whether P is a raw array, a std::array, a std::vector, or any other container in the standard library.