合并和排序，同时记住类型和（也许）位置

Question

我有两个

std::vector<double> v1, v2

已排序并且没有重复项（对于

double

的

==

）。假设

v1

中的数字属于类型 1，而

v2

中的数字属于类型 2。如何在保留类型的同时合并

v1

和

v2

排序并删除重复项到

std::vector<double>

中？

例如，如果

v1 = {2.3, 8.9, 10.0, 13.0}

和

v2 = {2.3, 4.4, 7.6, 10.0, 11.4, 12.6, 13.0}

我会有

v3 = {2.3, 4.4, 7.6, 8.9, 10.0, 11.4, 12.6, 13.0}

，假设有一个

v3types = {3, 2, 2, 1, 3, 2, 2, 3}

类型的向量，其中

v3types[i] == 3

类型表示

v3[i]

属于

v1

和

v2

。

如果我还想保留有关

v3

的元素在原始向量中的位置的信息，该怎么办——因此类型 3 的元素需要两个索引？

（理想情况下，我更愿意依赖 STL。此外，性能很重要，但并不那么重要，因为这只会在需要性能的执行上下文中执行一次，并且执行其他 ram+cpu 密集型计算。）

Answer 1

您基本上需要的是实现

std::merge

（合并两个已排序的范围），只不过您放置有关元素所属范围的信息，而不是复制元素本身。

您可以从 cppreference 获取 引用实现，并将

std::copy

替换为

std::fill_n

以及值的副本，并在需要时存储

1

和

2

：

template<class InputIt1, class InputIt2, class OutputIt>
OutputIt merge(InputIt1 first1, InputIt1 last1,
               InputIt2 first2, InputIt2 last2,
               OutputIt d_first)
{
    for (; first1 != last1; ++d_first)
    {
        if (first2 == last2)
            // std::copy(first1, last1, d_first);
            return std::fill_n(d_first, std::distance(first1, last1), 1);
 
        if (*first2 < *first1)
        {
            // *d_first = *first2;
            *d_first = 2;
            ++first2;
        }
        else if (*first1 < *first2) // new
        {
            // *d_first = *first1;
            *d_first = 1;
            ++first1;
        }
        else {
            // new case which also deals with duplicates
            *d_first = 3;
            ++first1;
            ++first2;
        }
    }
    return std::fill_n(d_first, std::distance(first2, last2), 2);
}

如果您同时将合并元素存储在一个输出迭代器中，并将索引存储在另一个输出迭代器中，则还可以同时生成合并范围和索引。