c++ - 查找两个排序向量之间的共同元素

Question

我需要编写一个函数，它接受对向量的 const 引用，并返回一个数字的升序向量。

我有两个整数的排序向量作为参数，并且需要仅使用<vector>header查找所有常见元素。

有什么想法吗？我想不通。

标签： c++vector

Answer 1

因为元素是有序的，你只需要跳过它们一次。

每个都有迭代器，如果两个范围都没有结束，则继续

如果两个元素都不小于另一个，则它们相等，您可以将一个写入结果。

否则，您需要推进指向较小元素的迭代器。

查看std::set_intersection的可能实现

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++;
            }
            ++first2;
        }
    }
    return d_first;
}

让我们让它适应“无非<vector>”规则

#include <vector>

template <typename T>
std::vector<T> set_intersection(const std::vector<T> & one, const std::vector<T> & two)
{
    std::vector<T> result;

    std::vector<T> const_iterator first1 = one.begin(), last1 = one.end(), first2 = two.begin(), last2 = two.end();

    while (first1 != last1 && first2 != last2) {
        if (*first1 < *first2) {
            ++first1;
        } else  {
            if (!(*first2 < *first1)) {
                result.push_back(*first1++);
            }
            ++first2;
        }
    }

    return result;
}