合并具有交替模式的两个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

这太专业了，直接被<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); } 
}; 

我觉得有点过分。

Answer 2

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

如他所示，这不是算法的问题，而是迭代的问题。然而他的解决方案并不完全符合该法案，因为测试迭代的end非常困难：它在准备容器和创建迭代器时需要非常小心以避免未定义的行为。

我认为使用与iterators：views非常相似的概念可以更好地表达问题。

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

关于意见的美丽的事情是，你可以经常组成它们。

例如，一个很简单的观点：

/// 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通常会容纳无限数量的序列。