使用交替模式合并两个 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算法代替我手写的循环？

Answer 1

我必须承认我非常喜欢 Potatoswatter 解决方案......非常喜欢。

正如他所证明的，这不是算法的问题，而是迭代的问题。然而，他的解决方案不太符合要求，因为测试迭代的结束非常困难：在准备容器和创建迭代器时需要非常小心，以避免未定义的行为。

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

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

视图的美妙之处在于您可以经常组合它们。

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

/// 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
{
};

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

当然，如果容器不提供有效的“大小”成员（list 不提供，它的时间复杂度为 O(n)），它可能会变得更加乏味。

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

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

Answer 2

这太专业了，无法直接由 涵盖。避免循环将需要自定义迭代器。

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 ); }
};

我觉得有点过分了。