С++: Как найти пересечение двух Set или Vector

Question

Допустим есть два Set или Vector. Например:

vector<int> a {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
vector<int> b {1, 5, 8};
vector<int> Intersect;

set<int> a1 { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
set<int> b1 { 1, 5, 8};
set<int> Intersection;

Как мне найти и записать в Intersect или Intersection все элементы из 'b' которые входят в 'a' в другой массив Intersect (в случае vector) или Intersection (в случае Set) ?

Answer 1

Если множества отсортированные (как set, для vector сначала отсортировать), то как вариант

template<class InputIt1, class InputIt2, class OutputIt>
OutputIt set_intersection(InputIt1 first1, InputIt1 last1,
                          InputIt2 first2, InputIt2 last2, OutputIt d_first)
{
    while (first1 != last1 && first2 != last2)
    {
        if (*first1 < *first2)
            ++first1;
        else
        {
            if (!(*first2 < *first1))
                *d_first++ = *first1++; // *first1 and *first2 are equivalent.
            ++first2;
        }
    }
    return d_first;
}

Или еще более обобщенно

template<class InputIt1, class InputIt2, class OutputIt, class Compare>
OutputIt set_intersection(InputIt1 first1, InputIt1 last1,
                          InputIt2 first2, InputIt2 last2, OutputIt d_first, Compare comp)
{
    while (first1 != last1 && first2 != last2)
    {
        if (comp(*first1, *first2))
            ++first1;
        else
        {
            if (!comp(*first2, *first1))
                *d_first++ = *first1++; // *first1 and *first2 are equivalent.
            ++first2;
        }
    }
    return d_first;
}

БЛОГ НА HUSL

С++: Как найти пересечение двух Set или Vector

Ответы (1 шт):