代码之家 › 专栏 › 技术社区 › Sam Harwell

转换多个迭代器元素

iterator stl algorithm c++

Sam Harwell · 技术社区 · 16 年前

假设我有一个输入迭代器。我想要从它派生一个新的输入迭代器,其中每个元素都是原始输入的多个连续元素的组合,其模式如下。游程长度在输入序列中编码。

输入: { 1 1 2 3 4 4 6 7 8 9 ... }

输出: { (1) (3+4) (6+7+8+9) ... }

我在想这样的函数可以处理单个元素并增加input begin迭代器(通过引用传递)。在我的评论中有几个问题,另外我想知道是否有一个好的方法来处理整个元素流。

编辑: 我知道在呼叫 std::advance 在哪里 tmp 迭代器递增为 end 编辑2: 现在应该修好了吗?

template<class TInputIterator, class TOutputIterator>
void process_single(TInputIterator& begin, TInputIterator end, TOutputIterator destination)
{
    std::iterator_traits<TInputIterator>::value_type run_length = *begin;
    ++begin;

    // is there a better way to specify run_length elements to accumulate() without having to call advance() here?
    TInputIterator tmp(begin);
    std::advance(tmp, run_length);
    // Edited: this condition should work for the different kinds of iterators?
    if ((end < tmp) || (std::distance(begin, tmp) != run_length))
        throw std::range_error("The input sequence had too few elements.");

    // std::plus is the default accumulate function
    *destination = std::accumulate(begin, tmp, 0/*, std::plus<TInputIterator::value_type>()*/);

    // should I use std::swap(begin, tmp) here instead?
    begin = tmp;
}

编辑3:

template<class TInputIterator, class TOutputIterator>
TInputIterator process_single(TInputIterator begin, TInputIterator end, TOutputIterator destination)
{
    typedef std::iterator_traits<TInputIterator>::value_type value_type;

    value_type run_length = *begin;
    ++begin;

    value_type sum = 0;
    while (run_length > 0 && begin != end)
    {
        sum += *begin;
        ++begin;
        --run_length;
    }

    if (run_length)
    {
        throw std::range_error("The input sequence had too few elements.");
    }

    *destination = sum;

    return begin;
}

template<class TInputIterator, class TOutputIterator>
void process(TInputIterator begin, TInputIterator end, TOutputIterator destination)
{
    while (begin != end)
    {
        begin = process_single(begin, end, destination);
    }
}

2 回复 | 直到 16 年前

UncleBens 16 年前

我会手动编写这个算法。

输入迭代器

其次,错误检查关闭。如果我没弄错的话 end < tmp 表示调用了某些未定义的行为。假设容器是一个std::list。如果你成功地超过列表.结束()? 但我认为即使使用向量或数组,它也是未定义的(MSVC++可能会在您之前启动迭代器调试)。

所以,为了解码整个序列,我会做如下的事情:

#include <iostream>
#include <algorithm>
#include <vector>
#include <stdexcept>
#include <iterator>

template <class InputIterator, class OutputIterator>
void decode(InputIterator start, InputIterator end, OutputIterator output)
{
    typedef typename std::iterator_traits<InputIterator>::value_type value_type;
    while (start != end)
    {
        value_type count = *start;
        ++start;
        value_type result = value_type();
        for (value_type i = value_type(); i != count; ++i, ++start) {
            if (start == end) {
                throw std::range_error("The input sequence had too few elements.");
            }
            result += *start;
        }
        *output = result;
        ++output;
    }
}

int main()
{
    try {
        std::vector<int> v;
        decode(std::istream_iterator<int>(std::cin), std::istream_iterator<int>(), std::back_inserter(v));
        std::copy(v.begin(), v.end(), std::ostream_iterator<int>(std::cout, " "));
    }
    catch (const std::exception& e) {
        std::cout << e.what() << '\n';
    }
}

Billy ONeal IS4 16 年前

// is there a better way to specify run_length elements to accumulate() without having to call advance() here?

// Edited: this condition should work for the different kinds of iterators?
if ((end < tmp) || (std::distance(begin, tmp) != run_length))
    throw std::range_error("The input sequence had too few elements.");

这里的问题是<运算符,它只适用于randomAccessIterator。为什么不只是:

if (std::distance(tmp, end) < run_length)

// should I use std::swap(begin, tmp) here instead?
begin = tmp;

不。

EDIT: I'm aware there's a bug in the call to std::advance where the tmp iterator is incremented to be exactly end, which would be valid for this code. Let's focus on the rest of my questions and I'll fix that.

递增到结尾是STL算法的标准行为。

void process_single(TInputIterator& begin, TInputIterator end, TOutputIterator destination)

STL迭代器通常不是传递byref的好类型。调用方经常希望在调用函数后保留它们。例如,传递byRef会导致无法编译:

std::vector<something> t;
std::vector<something> t2;
process_single(t.begin(), t.end(), std::back_inserter(t2))

(许多编译器会接受它,但它不是标准的)

更好的方法是传递迭代器byval,然后返回结束算法的新位置,以便与STL的其余部分更加一致。例如,请参见std::find()。

希望有帮助。。。。