在 C++ 中计算有序集的并集

Question

我想结合游程编码方案的三种变体（游程是累积的，因此是变体）。
让我们从其中两个开始：
第一个包含布尔值列表，第二个包含计数器列表。假设第一个看起来如下：（值：该值的位置）：

[(true:6), (false:10), (true:14), (false:20)]
// From 1 to 6, the value is true
// From 7 to 10, the value is false
// From 11 to 14, the value is true
// From 15 to 20, the value is false

第二个看起来如下（再次（值：该值的位置））：

[(1:4), (2:8), (4:16), (0:20)]
// From 1 to 4, the value is 1
// From 5 to 8, the value is 2
// From 9 to 16, the value is 4
// From 17 to 20, the value is 0

如您所见，两种情况的位置略有不同：

Case 1 : [6, 10, 14, 20]
Case 2 : [4, 8, 16, 20]

我想通过计算它们的并集来合并这些 "position arrays"：

[4, 6, 8, 10, 14, 16, 20]

一旦我有了这个，我就会从那里得到新的方案：

[(true:4), (true:6), (false:8), (false:10), (true:14), (false:16), (false:20)]
[(1:4), (2:6), (2:8), (4:10), (4:14), (4:16), (0:20)]

我想知道：是否有任何 C++ 标准 type/class 可以包含 "arrays" [6, 10, 14, 20] 和 [4, 8, 16, 20]，计算他们的联合并排序？

谢谢
多米尼克

Answer 1

您需要使用 <algorithm> 中的 std::set_union。

我这里用的是std::vector<int>，但是可以是任何模板类型。

#include <iostream>
#include <array>
#include <algorithm>

int main() {
  std::vector<int> a{6, 10, 14, 20};
  std::vector<int> b{4, 8, 16, 20};
  std::vector<int> c;

  std::set_union(a.begin(), a.end(), b.begin(), b.end(), std::back_inserter(c));
  for(auto e: c) {
    std::cout << e << ' ';
  }
  std::cout << '\n';
}

Here's the ideone

如果你想只维护两个 std::vector 而不引入 c，你可以简单地将 b 附加到 a，对数组进行排序，然后调用std::unique 在 a 上。在 O(n) 中可能是一种聪明的方法，但这是天真的方法：

#include <iostream>
#include <algorithm>
#include <vector>

int main() {
  std::vector<int> a{6, 10, 14, 20};
  std::vector<int> b{4, 8, 16, 20};

  a.insert(a.end(), b.begin(), b.end());

  std::sort(a.begin(), a.end());
  auto last = std::unique(a.begin(), a.end());
  a.erase(last, a.end());

  for(auto e: a) {
    std::cout << e << ' ';
  }
  std::cout << '\n';
}

Here's the ideone

最后，您可以使用 std::inplace_merge 而不是 std::sort。在最坏的情况下它是 O(nlogn) 就像 std::sort，但在最好的情况下它是 O(n)。性能大幅提升：

#include <iostream>
#include <algorithm>
#include <vector>

int main() {
  std::vector<int> a{6, 10, 14, 20};
  std::vector<int> b{4, 8, 16, 20};

  auto a_size = a.size();

  a.insert(a.end(), b.begin(), b.end());

  // merge point is where `a` and `b` meet: at the end of original `a`.    
  std::inplace_merge(a.begin(), a.begin() + a_size, a.end());

  auto last = std::unique(a.begin(), a.end());
  a.erase(last, a.end());

  for(auto e: a) {
    std::cout << e << ' ';
  }
  std::cout << '\n';
}

Here's the ideone

Answer 2

正如所暗示的那样，有一种算法只需要您将两个向量迭代一次。作为前提，它们都必须在开始时进行排序。您可以使用该事实始终检查哪个较小，并且仅将该向量中的值附加到结果。它还允许您删除重复项，因为如果您想要添加一个值，那么只有当它是添加到结果向量的最后一个值时，该值才会是重复项。

我编写了一些代码；我还没有运行对其进行广泛的测试，因此它可能仍然存在一些问题，但是现在开始吧：

// Assume a and b are the input vectors, and they are sorted.
std::vector<int> result;

// We know how many elements we will get at most, so prevent reallocations
result.reserve(a.size() + b.size());

auto aIt = a.cbegin();
auto bIt = b.cbegin();

// Loop until we have reached the end for both vectors
while(aIt != a.cend() && bIt != b.cend())
{
    // We pick the next value in a if it is smaller than the next value in b.
    // Of course we cannot do this if we are at the end of a.
    // If b has no more items, we also take the value from a.
    if(aIt != a.end() && (bIt == b.end() || *aIt < *bIt))
    {
        // Skip this value if it equals the last added value
        // (of course, for result.back() we need it to be nonempty)
        if(result.size() == 0 || *aIt != result.back())
        {
            result.push_back(*aIt);
        }
        ++aIt;
    }
    // We take the value from b if a has no more items, 
    // or if the next item in a was greater than the next item in b
    else
    {
        // If we get here, then either aIt == a.end(), in which case bIt != b.end() (see loop condition)
        // or bIt != b.end() and *aIt >= *bIt.
        // So in either case we can safely dereference bIt here.
        if(result.size() == 0 || *bIt != result.back())
        {
            result.push_back(*bIt);
        }
        ++bIt;
    }
}

它允许在样式和性能方面进行一些优化，但我认为它总体上有效。

当然如果你想把结果返回到a，你可以修改这个算法直接插入到a，但是这样保持它可能更快，只是[=13] =] 最后。

您可以看到它的实际效果 here。

Answer 3

I would like to know: is there any C++ standard type/class which can contain the "arrays" [6, 10, 14, 20] and [4, 8, 16, 20], calculate their union and sort it?

我猜你在问这个问题之前没有做太多研究。有一个管理有序集的 class 模板，称为 set。如果将两个集合的所有元素添加到一个集合中，就会得到并集。

std::set<int> s1{6, 10, 14, 20};
std::set<int> s2{4, 8, 16, 20};

std::set<int> union = s1;
union.insert(s2.begin(), s2.end());

在 C++ 中计算有序集的并集

Calculate the union of an ordered set in C++

c++

types

stl

class

set