4

我想要一种有效的方法来将排序向量与另一个排序向量进行就地联合。就地，我的意思是算法不应该创建一个全新的向量或其他存储来存储联合，即使是暂时的。相反，第一个向量应该简单地增长新元素的数量。

就像是：

void inplace_union(vector & A, const vector & B);

其中，之后，A包含A并集B的所有元素 并已排序。

std::set_unionin<algorithm>不会起作用，因为它会覆盖其目的地，即A。

另外，这可以通过两个向量只通过一次来完成吗？

编辑： A和B中的元素只能在A 中出现一次。

4

3 回答 3

6

我相信你可以使用算法std::inplace_merge。这是示例代码：

void inplace_union(std::vector<int>& a, const std::vector<int>& b)
{
    int mid = a.size(); //Store the end of first sorted range

    //First copy the second sorted range into the destination vector
    std::copy(b.begin(), b.end(), std::back_inserter(a));

    //Then perform the in place merge on the two sub-sorted ranges.
    std::inplace_merge(a.begin(), a.begin() + mid, a.end());

    //Remove duplicate elements from the sorted vector
    a.erase(std::unique(a.begin(), a.end()), a.end());
}
于 2010-09-03T04:58:08.490 回答
2

是的，这可以在 O( n ) 时间内就地完成，假设两个输入都已排序，并且一次通过两个向量。就是这样：

扩展A（目标向量）B.size()- 为我们的新元素腾出空间。

向后迭代两个向量，从 的末尾B和 的原始末尾开始A。如果向量按小→大排序（最后大），则取指向较大数字的迭代器，并将其粘贴在A. 继续直到B的迭代器到达B. 反向迭代器在这里应该特别好。

例子：

A: [ 1, 2, 4, 9 ]
B: [ 3, 7, 11 ]

* = iterator, ^ = where we're inserting, _ = unitialized
A: [ 1, 3, 4, 9*, _, _, _^ ]   B: [ 3, 7, 11* ]
A: [ 1, 3, 4, 9*, _, _^, 11 ]  B: [ 3, 7*, 11 ]
A: [ 1, 3, 4*, 9, _^, 9, 11 ]  B: [ 3, 7*, 11 ]
A: [ 1, 3, 4*, 9^, 7, 9, 11 ]  B: [ 3*, 7, 11 ]
A: [ 1, 3*, 4^, 4, 7, 9, 11 ]  B: [ 3*, 7, 11 ]
A: [ 1, 3*^, 3, 4, 7, 9, 11 ]  B: [ 3, 7, 11 ]

超级编辑：你考虑过std::inplace_merge吗？（我可能刚刚重新发明了它？）

于 2010-09-03T04:56:42.197 回答
0

这个set_difference想法很好，但缺点是我们不知道我们需要提前增长多少向量。

这是我的解决方案，它执行set_difference两次，一次是计算我们需要的额外插槽的数量，另一次是进行实际复制。

注意：这意味着我们将对源进行两次迭代。

#include <algorithm>
#include <boost/function_output_iterator.hpp>

// for the test
#include <vector>
#include <iostream>


struct output_counter
{
   output_counter(size_t & r) : result(r) {}
   template <class T> void operator()(const T & x) const { ++result; }
private:
   size_t & result;
};


// Target is assumed to work the same as a vector
// Both target and source must be sorted
template <class Target, class It>
void inplace_union( Target & target, It src_begin, It src_end )
{
   const size_t mid = target.size(); // Store the end of first sorted range

   // first, count how many items we will copy
   size_t extra = 0;
   std::set_difference( 
         src_begin, src_end,
         target.begin(), target.end(),
         boost::make_function_output_iterator(output_counter(extra)));

   if (extra > 0) // don't waste time if nothing to do
   {
      // reserve the exact memory we will require
      target.reserve( target.size() + extra );

      // Copy the items from the source that are missing in the destination
      std::set_difference( 
            src_begin, src_end,
            target.begin(), target.end(),
            std::back_inserter(target) );

      // Then perform the in place merge on the two sub-sorted ranges.
      std::inplace_merge( target.begin(), target.begin() + mid, target.end() );
   }
}



int main()
{
   std::vector<int> a(3), b(3);
   a[0] = 1;
   a[1] = 3;
   a[2] = 5;

   b[0] = 4;
   b[1] = 5;
   b[2] = 6;

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

   for (size_t i = 0; i != a.size(); ++i)
      std::cout << a[i] << ", ";
   std::cout << std::endl;

   return 0;
}

使用 boost headers 编译，结果是：

$ ./test 
1, 3, 4, 5, 6,
于 2012-05-02T02:26:05.957 回答