用交替模式合并两个STL向量

Question

我有两个STL向量A和B，需要将它们合并成第三个向量。合并后的元素应该按照一定的顺序排列，输出向量中每n个元素应该是来自向量B的。我的当前代码大致如下：

std::vector<int> a(10, 4);
std::vector<int> b(10, 8);
std::vector<int> c;
static const std::size_t STEP(3);

std::vector<int>::const_iterator bIt = b.begin();
for(std::vector<int>::const_iterator aIt = a.begin();
    aIt != a.end(); ++aIt)
{
    c.push_back(*aIt);
    if((c.size() + 1) % STEP == 0)
    {
        c.push_back(*bIt);
        ++bIt; //assume b is large enough
    }
}

现在向量c的样子是: 4 4 8 4 4 8 ...

这个方法可以正常运行，但我想知道是否有更加优雅的解决方案。有没有办法使用STL算法代替我手写循环呢？

- Mel

---

C语言的结束怎么处理？你想让它是4 4 8 .... 8 8 8 8 还是像你的例子一样只需要停止合并a.end()？ - dyp

那么，如果任一输入向量的元素不足会发生什么？ - AnT stands with Russia

STL已经有了一个惯例 - 当任一输入序列元素不足时，std::transform会做什么？ - MSalters

我已经合并了您的账户，现在您可以完全控制这个问题。然而，您的“回答”已被删除，因为它是针对多人的，无法正确转换。 - Tim Post

Answer 1

这个问题太专业化，无法直接由 <algorithm> 来处理。避免循环将需要一个自定义的迭代器。

template< typename I1, typename I2 >
struct interleave_iterator
    : std::iterator< forward_iterator_tag, typename I1::value_type > {
    using typename I1::value_type;

    I1 i1;
    I2 i2;
    size_t cnt, stride;

    interleave_iterator( I1 in1, I2 in2, size_t in_stride=0, size_t in_off=0 )
        : i1( in1 ), i2( in2 ), cnt( in_off ), stride( in_stride ) {}

    value_type &operator*() const { return cnt? * i1 : * i2; }
    interleave_iterator &operator++() {
        if ( ++ cnt == stride ) {
            cnt = 0;
            ++ i2;
        } else ++ i1;
        return *this;
    }
    value_type *operator->() const
        { return cnt? i1.operator->() : i2.operator->(); }

    interleave_iterator &operator++(int)
        { interleave_iterator r = *this; ++ *this; return r; }

    friend bool operator==
        ( interleave_iterator const &lhs, interleave_iterator const &rhs )
        { return lhs.i1 == rhs.i1 && lhs.i2 == rhs.i2; }
    friend bool operator!=
        ( interleave_iterator const &lhs, interleave_iterator const &rhs )
        { return ! ( lhs == rhs ); }
};

我觉得有点过度了。

- Potatoswatter

---

我认为你应该重新考虑++运算符。当步长！= 1，并且a和b的大小相等时，它会导致异常。这是期望的行为吗？ - dyp

@DyP：最终你会在一个序列中用尽空间。这个类不进行边界检查。我认为这完全是不切实际的。 - Potatoswatter

Answer 2

我必须承认，我相当喜欢Potatoswatter的解决方案... 相当。

正如他所展示的那样，这不是算法问题，而是迭代问题。然而，他的解决方案并不完全符合要求，因为测试迭代的end非常困难：需要在容器的准备和迭代器的创建上格外谨慎，以避免未定义行为。

我认为可以使用一个与迭代器非常相似的概念来更好地表达这个问题：视图。

视图是一个适配器接口，用于一个或多个容器。它本身实际上并不包含任何东西（这是重要的部分）。但它确实暴露了类似于容器的接口，以便您可以使用通常的习惯用语编码。

关于视图的美好之处在于，你经常可以将它们组合起来。

例如，一个非常简单的视图：

/// Only allow to see a range of the container:
/// std::vector<int> v(40, 3); // { 3, 3, 3, ... }
/// auto rv = make_range_view(v, 4, 5);
/// rv exposes the elements in the range [4,9)
/// in debug mode, asserts that the range is sufficiently large
template <typename Container>
class range_view
{
};

针对您的问题，您最好创建一个interleave_view:

/// Allow to interleave elements of 2 containers each at its own pace
/// std::vector<int> v(40, 3);
/// std::set<int> s = /**/;
/// 
/// auto iv = make_interleave_view(v, 3, s, 1);
/// Takes 3 elements from v, then 1 from s, then 3 from v, etc...
template <typename C1, typename C2>
class interleave_view
{
};

在这里，结束迭代器的问题得到了缓解，因为我们知道两个容器，因此我们能够自己创建迭代器，确保传递正确的参数。

当然，如果容器没有提供有效的“size”成员（list没有，它是O(n)），可能会变得有点繁琐。

然而，一般原则是视图给你更多的控制（并允许更多的检查），并且更安全使用，因为你可以精确地控制迭代器的创建。

请注意，在C++0x中，interleave_view通常会容纳无限数量的序列。

- Matthieu M.

---

适配器的问题在于你必须定义自己的接口，或者尝试满足容器的要求。我本质上编写了一个OutputIterator并将其称为ForwardIterator——序列结尾的概念被简单地留空，因为OP没有要求它。然而，这可以通过一个特殊的make_end_interleaved_iterator工厂、一个bool is_end成员和一个智能的operator==来解决，该运算符在is_end == true时检查LHS和RHS的i1和i2之间的集合交集。 - Potatoswatter

更新答案以支持范围结束的不同语义：必须同时达到两个基础范围的结尾。因此，用户必须正确掌握比例，但至少有可能实现。 - Potatoswatter

@Potatoswatter：我同意，在所有可能的“视图”中，像filter、transform等那些倾向于具有增量的视图与skip和zip这样的“异常”视图相比，对于确定序列的结束，它们提供了一些挑战。 - Matthieu M.

@Potatoswatter：接口不太让我担心，因为它非常简洁。视图不允许修改底层容器的结构，因此其接口被减少了。empty、size、begin、end、rbegin、rend、operator[]、at，大概就这些了（必要时带有const重载）。 - Matthieu M.

啊，现在我明白了。那太好了。 - Potatoswatter