Best way to get intersection of 2 unordered sets?

General JUCE discussion
1

Hi everyone,
I was wondering if anyone could point me towards the best way to get the intersection of two unordered sets in JUCE? Should I use the cpp code below, or is there something built into JUCE?

The example code uses sorted sets, and a call from #include :

set_intersection ( InputIterator1 first1, InputIterator1 last1,
InputIterator2 first2, InputIterator2 last2,
OutputIterator result )

See http://www.cplusplus.com/reference/algorithm/set_intersection/

Cheers,
Owen

2

so far I wrote an implementation like this:

int numberOfIntersections(const Array<int>& itemSeti, const Array<int>& itemSetj)
{
    int i = 0, j = 0;
    int m = itemSeti.size();
    int n = itemSetj.size();
    
    int intersectionCount = 0;
    
    while(i < m && j < n)
    {
        if(itemSeti[i] < itemSetj[j])
            i++;
        else if(itemSetj[j] < itemSeti[i])
            j++;
        else /* if itemSeti[i] == arr2[j] */
        {
            intersectionCount++;
            j++;
            i++;
        }
    }   

    return intersectionCount;

}

This assumes the Arrays are sorted, and preferably as a set. Does this seem like it would work?

3

i thought you said your sets were unordered. if they’re not too big, you could just take each element of the first and see if it’s a member of the second and, if so, add it to your intersection set.

if they’re large, you could sort them first, then go through them both at once taking matching elements and bumping each iterator whilst it’s less than the other ordered set.

4

They data was unordered, but it turns out the algorithm works fine/faster if I collapse the data down to ordered sets before I store them. I also modified the code to return the difference between two ordered sets. always curious to see if there are faster JUCE calls to do stuff though.

void S2MP::differenceOfSets (Array <int> &set1, Array <int> &set2)
{
    int i = 0, j = 0;
    int m = set1.size();
    int n = set2.size();
        
    while (i < m && j < n)
    {
        if (set1.getUnchecked(i) < set2.getUnchecked(j))
        {
            i++;
        }
        else if (set2.getUnchecked(j) < set1.getUnchecked(i))
        {
            j++;
        }
        else /* if set1[i] == set2[j] */
        {
            set1.remove(i);
            i++;
            j++;
        }
    }      
}
5

Just found the SortedSet class :smiley: Exactly what I was looking for! I knew JUCE had something like this.