时间戳

首页 > 解决方案 > C++ STL 交错两个范围

c++ - C++ STL 交错两个范围

问题描述

我做了一些事情来实现两个范围的交错。这是问题所在。

假设我有两个范围[a1, b1), call R1和[a2, b2) call R2. 现在，假设他们的std::distance结果是相同的，比如说n。我想写一个算法

std::interleave(a1, b1, a2, b2, bool swap)

这将以一种方式重新排列元素，即 R2 的一个元素将跟随 R1 的一个元素，通过所有2n元素。根据 的值swap，它也应该重新排序，因为 R1 的一个元素后跟 R2 的一个元素。

我使用一个额外的存储空间和两个 for 循环来做到这一点。这个解决方案很简单。如果我尝试更长的时间，我也可能会想出一个就地解决方案。但我想要的是，我想通过从 STL 组装算法来实现这个目标。如何使用 STL 解决这个问题？如果解决方案是就地的，那就更好了，但我也愿意使用额外的存储，只要我们使用来自 STL 的算法。

编辑：不应更改给定范围内元素的排列。换句话说，这实际上应该类似于stable_interleave. 这就是为什么我无法想出使用std::merge.

应用：其中一种应用是将视频和图像格式从平面转换为非平面或半平面。

标签： c++stl

解决方案

我的使用方法std::merge可能会失败。我没有足够的创造力来理解为什么有人会这样写merge，但它违反了下面评论中指出的比较要求，所以有人可以。

无论如何，merge这是一个矫枉过正的解决方案。隐藏额外工作的代码行更少，因为merge' 的预期用途是用于比我们在这里做的更复杂的工作。

例子：

#include <iostream>
#include <iterator>
#include <algorithm>
#include <vector>
#include <list>
#include <deque>

template<typename IN1,
         typename IN2,
         typename OUT>
inline OUT interleave(IN1 it1,
                      IN1 end1,
                      IN2 it2,
                      IN2 end2,
                      OUT out)
{
    // interleave until at least one container is done
    while (it1 != end1 && it2 != end2) 
    {
        // insert from container 1
        *out = *it1;
        out++;
        it1++;
        // insert from container 2
        *out = *it2;
        out++;
        it2++;
    }
    if (it1 != end1) // check and finish container 1
    {
        return std::copy (it1, end1, out);
    }
    else if (it2 != end2)// check and finish container 2
    {
        return std::copy (it2, end2, out);
    }
    return out; // both done
}

int main()
{
    // fill the containers  with numbers
    std::vector<int> in1 = {1,3,5,7,9};
    std::list<int> in2 = {8,6,4,2};

    // construct output container of sufficient size.
    // Could also use empty container and *_inserter
    std::deque<int> out(in1.size() + in2.size());

    // Container-agnostic. reads from vector and list and stores in deque
    interleave(in1.begin(), in1.end(),
               in2.begin(), in2.end(),
               out.begin());
    for (int val: out)
    {
        std::cout << val << ' ';
    }
}

注意：与其使用交换输入顺序的选项来实现并让所有用户interleave为此付费，调用者应该以相反的输入参数顺序调用。

推荐阅读